6.1.1 图的定义与基本术语
原书定位
印刷页P198起,对应PDF第210页。下文为目视整理的知识提要;完整内容见原书对照。
图 的顶点集非空,边集可以为空。有向边是有序对,无向边是无序对;简单图无自环、无重边。
| 概念 | 关键性质 |
|---|---|
| 无向图的度 | $\sum d(v)=2 |
| 有向图的度 | $\sum d^+(v)=\sum d^-(v)= |
| 路径长度 | 无权时为边数;带权时可讨论边权和 |
| 简单路径、简单回路 | 顶点不重复;回路允许首尾相同 |
| 连通分量 | 无向图的极大连通子图 |
| 强连通分量 | 有向图中任意两点互相可达的极大子图 |
| 生成树 | 含全部顶点的极小连通子图, 条边 |
| 生成森林 | 各连通分量的生成树集合, 条边 |
子图的边端点必须都在子图顶点集中。极大连通强调不能再扩张,极小连通强调删边就不连通。
简单无向图最多 条边,有向图最多 条弧。连通无向图至少 条边,但边数达到 并不能保证连通;对于 ,边数大于 才能仅由边数保证连通。强连通有向图在 时至少 条弧。
有向树还应要求从唯一入度为 0 的根可达所有顶点;仅有一个顶点入度为 0、其余入度为 1,仍可能在另一分量形成有向环。

有向图、无向图与有向完全图,原书P199。

连通分量,原书P200。

强连通分量与生成树,原书P201。
对应练习
关联知识
原书对照
展开原书对照截图



