6.1.1 图的定义与基本术语

教材导航 · 第6章

原书定位

印刷页P198起,对应PDF第210页。下文为目视整理的知识提要;完整内容见原书对照。

图 G=(V,E)G=(V,E) 的顶点集非空,边集可以为空。有向边是有序对,无向边是无序对;简单图无自环、无重边。

概念关键性质
无向图的度$\sum d(v)=2
有向图的度$\sum d^+(v)=\sum d^-(v)=
路径长度无权时为边数;带权时可讨论边权和
简单路径、简单回路顶点不重复;回路允许首尾相同
连通分量无向图的极大连通子图
强连通分量有向图中任意两点互相可达的极大子图
生成树含全部顶点的极小连通子图,n−1n-1 条边
生成森林各连通分量的生成树集合,n−cn-c 条边

子图的边端点必须都在子图顶点集中。极大连通强调不能再扩张,极小连通强调删边就不连通。

简单无向图最多 n(n−1)/2n(n-1)/2 条边,有向图最多 n(n−1)n(n-1) 条弧。连通无向图至少 n−1n-1 条边,但边数达到 n−1n-1 并不能保证连通;对于 n≥2n\ge2,边数大于 (n−1)(n−2)/2(n-1)(n-2)/2 才能仅由边数保证连通。强连通有向图在 n>1n>1 时至少 nn 条弧。

有向树还应要求从唯一入度为 0 的根可达所有顶点;仅有一个顶点入度为 0、其余入度为 1,仍可能在另一分量形成有向环。

有向图、无向图与有向完全图

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

连通分量

连通分量,原书P200。

强连通分量与生成树

强连通分量与生成树,原书P201。

对应练习

6.1 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P198,PDF第210页

原书对照,原书P199,PDF第211页

原书对照,原书P200,PDF第212页

原书对照,原书P201,PDF第213页