图论：练习题及分步解答

1顶点、边和度

图由顶点（点）和边（连接两个顶点的线）组成。简单图中没有环，也没有重边。

顶点的度是与它相连的边的条数。每条边有两个端点，所以它使每个端点的度加 1。由此得到握手引理：

两个推论：度数之和总是偶数，奇度顶点的个数也是偶数。

• 完全图 K_n 把每一对顶点都连起来：有 n(n − 1)/2 条边。
• 完全二部图 K_m,n 把一侧的每个顶点与另一侧的每个顶点相连：有 m·n 条边。
• n 个顶点的 k-正则图有 n·k/2 条边。

邻接矩阵在 i 与 j 相连时，在 (i, j) 处为 1。无向图的邻接矩阵是对称的，行和就是度数，而 Mᴸ 的 (i, j) 元素给出从 i 到 j 的长度为 L 的途径条数。

2欧拉与哈密顿

欧拉回路恰好经过每条边一次并回到起点。欧拉通路恰好经过每条边一次，但可以在别处结束。对于连通图：

• 所有度数都是偶数：存在欧拉回路；
• 恰有两个奇度顶点：存在欧拉通路，从一个奇度顶点到另一个奇度顶点；
• 奇度顶点多于两个：两者都不存在。

哈密顿回路恰好经过每个顶点一次。对它没有简单的度数判别法。K_n 中有 (n − 1)!/2 条不同的哈密顿回路：固定起点，把其余 n − 1 个顶点排序，再因两个方向而除以 2。

3树

树是不含圈的连通图。n 个顶点的树恰有 n − 1 条边。添加任何一条边都会产生圈；去掉任何一条边都会使它不连通。

n 个顶点、c 棵树组成的森林有 n − c 条边。有 m 条边的连通图在去掉 m − n + 1 条边后保留一棵生成树。

握手引理可用来数叶子：Σ deg = 2(n − 1)。简便的写法是 L = 2 + Σ (d − 2)，对度数 d ≥ 3 的顶点求和。有两个度为 3 的顶点、其余全为叶子的树有 2 + 1 + 1 = 4 片叶子。

4迪杰斯特拉算法与最小生成树

迪杰斯特拉算法在权重非负的图中求从起点出发的最短距离。

1. 令起点的距离为 0，其他每个顶点的距离为 ∞。
2. 确定距离最小的未确定顶点；它的距离现在是最终值。
3. 对每个邻点 v，更新 d(v) = min(d(v), d(u) + w(u, v))。
4. 重复上述过程，直到目标顶点被确定。

最小生成树以最小的总权重连接所有顶点。克鲁斯卡尔算法把边按权重从轻到重排序，每条边除非会形成圈都取下。普里姆算法从一个起点出发扩展一棵树，每次加入离开这棵树的最轻的边。两者都在取够 n − 1 条边后停止。

5常见错误

• 忘记把度数之和除以 2 来得到边数。
• 没有检查图是否连通就判断是否有欧拉回路。
• 在迪杰斯特拉算法中，顶点的暂定距离还不是最小时就把它确定下来。
• 不检查圈就取最轻的 n − 1 条边。
• 把 K_n 的哈密顿回路数算成 n!，而不是 (n − 1)!/2。

6考试题是什么样的

• 简单：度与边。你要使用握手引理，数出 K_n、K_m,n、正则图和树的边数，读懂邻接矩阵，或点选具有给定度数的顶点。
• 中等：欧拉通路与树。你要判断一个图是否有欧拉回路或通路，数出树的叶子数，数出为得到生成树需要去掉的边数，或数出 K_n 中的哈密顿回路数。
• 困难：最短路径与生成树。你要运行迪杰斯特拉算法，找出某一轮中被确定的顶点，求最小生成树的权重，点选克鲁斯卡尔或普里姆算法下一步加入的边，或用邻接矩阵数途径条数。