6.1.1 图的基本概念

图 G=(V,E) 由顶点集和边集组成。有向边写作 <u,v>，无向边写作 {u,v}。无向图度数和等于 2|E|；有向图入度和、出度和都等于 |E|。路径长度按边数或权值和计算，简单路径不重复顶点。连通分量针对无向图，强连通分量要求有向图中任意两点互相可达。

手工状态

无向边 AB、AC、BC、CD：各点度为 2、2、3、1，度数和 8=2×4。图连通，删 CD 后 D 成孤立点，分量变为两个。

结构与代码

稠密图接近顶点平方条边，稀疏图边数远小于顶点平方。简单无向图最多 n(n-1)/2 条边，简单有向图最多 n(n-1) 条弧，不含自环和重边。

正确性依据

握手定理来自每条无向边贡献两个端点计数；有向边恰给一个出度和一个入度。非连通无向图的生成森林若有 c 个分量，共有 n-c 条树边。

错解反馈

把“可达”当作必须直接相邻；有向弱连通当强连通；路径与简单路径混用；度数和只等于边数。

迁移训练

5 个顶点的简单无向图最多多少边？答案10。若连通，最少边4；写出两种能取等号的图。