图论第十、十一章精讲

课件① 第 7–28 页

这部分是动机，考试一般不考细节，记住下面三件事就够了。

1. 哥尼斯堡七桥问题（1736，欧拉）：能否每座桥恰好走一次再回到家？把 4 块陆地当点、7 座桥当边，问题变成"图里有没有一条经过每条边恰好一次的回路"（欧拉回路）。结论：连通无向图有欧拉回路 ⇔ 每个点的度都是偶数。七桥图 4 个点的度是 5、3、3、3，全是奇数，所以走不成。这样判断只需看一遍所有点，复杂度 O(|V|)；枚举 7 座桥的顺序要 7! = 5040 种。
2. 哈密顿图问题：是否存在经过每个顶点恰好一次的回路？看起来只是把"边"换成"点"，难度却天差地别：它是 NP 完全问题，目前没有已知的多项式算法。20 个点暴力枚举要 20! ≈ 2.4×10¹⁸ 种排列。
3. 复杂度分级：多项式 O(n^a) ≪ 指数 O(2ⁿ) ≪ 阶乘 O(n!)。后面讲"同构"时还会用到这个视角：判断同构如果去试所有点的对应方式，就是 O(n!)。

课件里 Google 图计算（Pregel）、图神经网络、知识图谱那几页，是在说明图模型的应用面，属于拓展阅读。

课件① 第 29–53 页

无序偶与有序偶

一切从"两个点怎么配成一对"开始：

• 无序偶 (x, y)：不分先后，(a, b) = (b, a)。用来表示无向边。
• 有序偶 ⟨x, y⟩：分先后，⟨a, b⟩ ≠ ⟨b, a⟩。用来表示有向边（从 x 指向 y）。

注意 G = ⟨V, E⟩ 这个尖括号是"图这个整体是一个有序对（先写点集再写边集）"，跟边是不是有向无关。

必须分清的几个术语

三种"挨着"的关系：邻接、关联、相邻

图里只有两种东西（点和边），两两配对就有三种关系，课件用同一个竖线符号 | 表示：

对照这张图：v₁|v₂（有边 a），v₃|v₃（自环 c 让 v₃ 和自己邻接）；v₂|f（v₂ 是 f 的端点）；a|g（a、g 共用 v₁），d|h（共用 v₄）。

度：一个点"挂着"几条边

上图里：d(v₁)=2，d(v₂)=4，d(v₄)=3，d(v₅)=2，而 d(v₃)=5：边 g、b、d 各贡献 1，自环 c 贡献 2。

握手定理

一句话证明：每条边有 2 个端头，每个端头给某个点的度贡献 1。所有点的度之和就是在数端头总数，也就是 2m。名字的由来：一群人握手，每次握手两个人各记一次，所有人记的次数加起来必然是握手次数的两倍。

课件的归纳证明（对边数 m 归纳）：m=1 时成立。假设 m=k 时成立，再加一条边 e，度数和增加 2，不管 e 是连接两个旧点、引入一个新点还是引入两个新点（课件分了 n′=n, n+1, n+2 三种情况），都有 2k + 2 = 2(k+1)。

课件① 第 54–73 页

课件第 54 页给的双射：u₁→v₁，u₂→v₄，u₄→v₂，u₃→v₃。逐条验证 G 的 4 条边：

两边都是 4 条边，G 的边全部映到了 H 的边，H 也没有多出来的边，所以"⇔"两个方向都满足，G ≅ H。把 H 的 v₃、v₄ 左右交换一下重画，它就是正方形。

有向图的同构（课件第 62 页）同理，只是还要保持方向：⟨u,v⟩∈E ⇔ ⟨f(u),f(v)⟩∈E′。

怎么判断同构：必要条件只能用来"否定"

直接按定义找双射，最坏要试 n! 种对应，太慢。课件说，目前没有"简单而充分"的判定条件，但有一组必要条件。同构的两张图必须满足：

1. 点数相同；
2. 边数相同；
3. 度数序列相同（度数相同的点个数相同）。而且同构映射一定把 k 度点映到 k 度点。

还可以继续加：两个 3 度点相邻吗？有没有三角形？有几个连通块？这些"图的不变量"在同构下都不会变。

同胚与同态（了解）

同胚（定义 10.2.11）：如果 G′ 是在 G 的边上"插入若干新点"（把一条边 (u,v) 换成一条路 u–w₀–…–v）得到的，就称 G′ 是 G 的同胚图。插入的点度都是 2，图的"形状骨架"没变。这个概念后面判断平面图时会用到。

同态（扩展）：比同构宽松，只要求有函数 f : V→V′ 把边映成边，不要求一一对应，允许多个点合并成一个。课件例子里 x₃、x₄ 都映到 y₃。

Weisfeiler–Lehman 算法：给点"上色"来比较

课件介绍了一个实用的同构检验思路。不去试所有对应方式，而是反复给点重新上色：

1. 开始时所有点同一种颜色。
2. 每一轮，每个点看"自己的颜色 + 所有邻居颜色组成的多重集"，相同的组合给同一个新颜色。第一轮之后颜色其实就等于度数。
3. 每轮比较两张图各颜色的点数。只要某一轮对不上，一定不同构；颜色不再细分且两边一直一样，就判"可能同构"。

它的弱点正好是课件说的正则图：每个点度数相同，邻居颜色也相同，颜色永远不会分开。下面可以亲手试：

补充：图同构问题目前既不知道是否属于 P，也不知道是否 NP 完全。Babai 在 2015 年给出了拟多项式时间 2^{(log n)k} 的算法。而"子图同构"（判断 G 里是否含有一个和 H 同构的子图）已被证明是 NP 完全的。

课件① 第 75–109 页

这些图之所以"特殊"，是因为它们的边有清楚的规律，点数、边数、度数都能直接写出公式。学的时候把三个量对上就行：几个点、几条边、每个点几度，边数都可以用握手定理（度数和 ÷ 2）验算。

平凡图与完全图

每个点和其他 n−1 个点相连，所以 K_n 是 (n−1) 次正则图，边数 n(n−1)/2（握手：n·(n−1) = 2m）。这也是 n 阶简单图边数的上限。课件第 99–101 页的计时表说明：K_n 的边数随 n 平方增长，n = 5000 时已有约 1250 万条边。

圈图与轮图

C_n：n 点、n 边，2 次正则。W_n（课件记法，共 n 个点）：圈上 n−1 条边 + 辐条 n−1 条，共 2(n−1) 条边；圈上的点度为 3，中心点度为 n−1。

二部图（偶图）与完全二部图

K_m,n：m+n 个点，mn 条边；左边每点度 n，右边每点度 m（验算：mn + nm = 2mn）。

n 立方体图 Q_n

每个串有 n 位，翻转任意一位都得到一个邻居，所以 Q_n 是 n 次正则图，边数 n·2ⁿ/2 = n·2ⁿ⁻¹（Q₃：12 条）。它还是二部图：按"1 的个数是奇数还是偶数"分两组，翻一位一定改变奇偶性。

0-1 序列图 S_n（De Bruijn 图）

r 次正则图与彼德森图

已经见过的：K_n 是 (n−1) 正则，C_n 是 2 正则，Q_n 是 n 正则，K_n,n 是 n 正则。彼德森图是 10 个点、15 条边的 3 次正则图（外五边形 + 内五角星 + 5 条连线），是图论里最常用的反例。

课件① 第 111–134 页

六个定义，全部都是在 V_s、E_s 上加不同的条件。先看总表，再逐个看。

隐含要求：G_s 自己也得是个图，所以 E_s 里每条边的端点都要在 V_s 中。不能删掉一个点却留下连着它的边。

课件① 第 136–151 页，课件② 第 1–14 页

把图写成矩阵有两个好处：计算机能存，也能用矩阵运算回答图的问题（两点之间有几条长度为 k 的通路？谁能到达谁？最短距离是多少？）。这一节的主线是：邻接矩阵 A → A^k → 可达矩阵 R → 距离矩阵 D。

先说存储：为什么需要稀疏格式

邻接矩阵是 n×n 的。100 万个点就是 10¹² 个元素，每个按 int64 占 8 字节，约 8×10¹² 字节 ≈ 7.28 TB。可真实网络很稀疏，绝大多数元素是 0，所以只存非零元素。课件第 142–144 页用下面这个矩阵演示了三种格式：

课件把 CSR 的行指针也叫 row_index，容易和 COO 的 row 混淆，看长度区分：指针数组长度是"行数+1"。课件第 144 页手写的 CSC 中 value 和 row 两行与 COO 相同，没有按列重排；按列重排后应是上表的结果，可以自己逐列读一遍验证。图的"邻接表"（课件第 141 页的数组 + 链表）本质上和 CSR 是一回事。

关联矩阵：点 × 边

读法：每一列恰有两个 1（一条边两个端点）；每一行的和是这个点的度。所有元素之和 = 2m，这就是握手定理的矩阵版。

读法：每列恰好一个 1、一个 −1，列和为 0；某一行中 1 的个数是出度，−1 的个数是入度。例如 d 行：1 出现 3 次（e4、e5、e6 从 d 出发），−1 出现 1 次（e3 指向 d）。

邻接矩阵：点 × 点

从邻接矩阵能直接读出什么（课件② 第 6–7 页）

1. 无向图的 A 是对称矩阵；有向图一般不对称。
2. 没有平行边 ⇔ 元素只有 0 和 1；有自环 ⇔ 对角线有非 0 元素；简单图 ⇔ 只有 0、1 且对角线全 0；零图（没有边）⇔ A 是零矩阵。
3. 无向图：d(v_i) = 2a_ii + ∑_j≠i a_ij（自环算两次）。简单图就是"第 i 行之和"。
4. 有向图：第 i 行之和 = 出度，第 i 列之和 = 入度。
5. 图有 k 个连通分支 ⇔ 适当重排点的顺序后，A 变成分块对角矩阵，每块是一个分支自己的邻接矩阵。

核心：A^k 在数通路

为什么？看 k = 2：

乘积 a_it·a_tj 等于 1 恰好当 i→t 和 t→j 两条边都存在，也就是"走两步、中间经过 t"。对所有中间点 t 求和，就是长度 2 的通路总数。同理 A^k = A^k−1·A：先用 k−1 步到某个 t，再走一步到 j，归纳即得。

例：路 a – b – c。

(A²)_bb = 2：b→a→b 和 b→c→b。(A²)_ac = 1：a→b→c。(A²)_ab = 0：a 到 b 没法恰好走 2 步。简单无向图里 (A²)_ii = d(v_i)，因为每个邻居都提供一条"去了就回"的长度 2 通路。

可达矩阵

逐项理解：

• A^k 的 (i,j) 非 0 ⇔ 存在长度恰好为 k 的通路。把 k = 0, 1, …, n−1 加起来，非 0 就说明"存在某个长度的通路"，即可达。
• 为什么有 I：I = A⁰，代表走 0 步，规定每个点可达自己（课件② 第 12 页 R(v₁) 里包含 v₁ 自己）。
• 为什么只加到 n−1：10.6 节的定理 10.6.1 会证明，如果 u 能到 v，一定有一条长度 ≤ n−1 的通路（不重复经过点的通路最多 n 个点、n−1 条边）。更长的项不会带来新的"可达"信息。

距离矩阵

二部图与邻接矩阵（课件② 第 8–9 页）

(⇒) G 是二部图，点分成 V₁、V₂，每条边跨两边。从点 i 出发，每走一步就换一边。若 i ∈ V₁，走奇数步后一定在 V₂，不可能回到 i；i ∈ V₂ 同理。所以 k 为奇数时从 i 回到 i 的长度 k 通路条数为 0，即 A^k[i,i] = 0。

(⇐) 假设所有奇数 k 都有 A^k[i,i] = 0，即没有奇数长的闭通路。先看一个连通分支，任取其中一点 v，令

• V_o：从 v 出发能用奇数步到达的点
• V_e：能用偶数步到达的点

1. 两者不相交：若某点 u 既能奇数步到、又能偶数步到，把"v 奇数步到 u"和"u 偶数步返回 v"（无向图可以原路倒着走）接起来，就是一条从 v 回到 v 的奇数长闭通路，矛盾。
2. 两者覆盖整个分支：分支连通，每个点都能从 v 到达，步数不是奇就是偶。
3. 每条边跨两边：若边 (x,y) 两端都在 V_e，则到 x 偶数步、再走一步到 y 就是奇数步，y 同时属于 V_o，与 1 矛盾。两端都在 V_o 同理。

每个分支都这样分好，再合并，就得到整张图的二分，所以 G 是二部图。∎

实际判断时只需检查 k = 1, 3, 5, … 到 n 为止：如果有奇数长的闭通路，就一定有长度 ≤ n 的奇数圈。实验室里的"二部图"判断就是这样算的，可以选 C₆ 和 C₅ 对比。

课件② 第 16–38 页

通路、简单通路、基本通路

说人话：沿着边一步一步走出来的点序列就是通路，点和边都允许重复。

关系：基本通路一定是简单通路（点不重复，边自然不重复：边重复意味着它的端点也重复）。反过来不对。

回路

无向图的连通

直觉：桥是"唯一的通道"。一条边在某个回路上，删掉它还能绕回路另一侧走，就不是桥。所以一条边是桥 ⇔ 它不在任何回路上。

有向图的三种连通

强连通 ⇒ 单向连通 ⇒ 弱连通，反方向都不成立（上面后两个图就是反例）。判断时从强往弱试：先看能不能两两互达，再看任意两点是不是至少一个方向能到，最后忽略方向看连不连通。在矩阵实验室里勾选"有向图"，判断栏会给出这个结论。

两个定理：用"一条通路"刻画连通性

容易的方向（⇐）：有完备通路 w₁ ⇒ w₂ ⇒ ⋯ ⇒ w_t，所有点都在上面。任取两点 u、v，它们在通路上一前一后，前面的沿着通路就能走到后面的，所以至少一个方向可达，G 单向连通。完备回路的情况更强：沿回路绕一圈，谁都能到谁，所以强连通。

强连通 ⇒ 完备回路：把点排成 v₁, v₂, …, v_n，强连通保证每段 v_i ⇒ v_i+1 和最后 v_n ⇒ v₁ 都有通路，首尾接起来就是一条经过所有点的回路。

单向连通 ⇒ 完备通路（难点）：这里不能随便排顺序，因为 v_i 不一定能到 v_i+1。课件第 30–38 页用的是对点数归纳 + 插入的思路：

1. 假设除 v 以外的点已经串成一条通路 v₁ ⇒ v₂ ⇒ ⋯ ⇒ v_n。
2. 把 v 插进去。单向连通保证 v 和每个 v_i 之间至少一个方向可达。
   • 若 v ⇒ v₁：把 v 放最前面。
   • 若 v_n ⇒ v：把 v 放最后面。
   • 否则 v₁ ⇒ v 且 v ⇒ v_n。从左往右找第一个满足 v ⇒ v_i 的位置 i（i ≥ 2），那么 v_i−1 ⇒ v，于是 ⋯ ⇒ v_i−1 ⇒ v ⇒ v_i ⇒ ⋯，v 插进了中间。

课件的图就是在演示这个"找插入位置"的过程（红色箭头表示 v 和各点的可达方向）。课件第 37–38 页还处理了一个细节：去掉 v 之后，剩下的图可能不再单向连通（原来的通路可能要经过 v），所以要先把剩下的点分成几段通路，再逐段扩充。

课件③ 第 41–67 页

这一部分在上一节"连通"的基础上继续往下走，回答四个问题：一张不连通的图能拆成几块（分支）；什么样的图本身就是一个圈（回路、半回路、有向回路）；怎么判断图里有没有圈（W-过程、非循环图）；边要多到什么程度图才一定连通（连通的充分条件）。

竞赛图与勒代定理

名字来自循环赛：每两个选手恰好比一场，u → v 表示 u 赢了 v。把 K_n 的每条边任意定一个方向，得到的就是竞赛图。

课件第 43 页的定义只写了"或者"，没有写"恰好一个"。通常的定义要求两点之间只有一个方向（一场比赛只有一个胜者），下面的证明也用到了这一点。

它和上一节定理 10.6.3 的关系：竞赛图里任意两点之间都有一条边，当然单向连通，所以由定理 10.6.3 它有完备通路；勒代定理更进一步，说这条通路可以做到每个点只经过一次。

证明（对点数归纳，就是"插队"）：1 个点时显然成立。假设前 k 个点已经排成一条有向通路 v₁ → v₂ → ⋯ → v_k，现在加入新点 v，要把它插进队伍里：

1. 如果 v → v₁：把 v 排在最前面，变成 v → v₁ → ⋯ → v_k。
2. 否则一定是 v₁ → v（竞赛图里两点之间恰好一条边）。此时如果 v_k → v，把 v 排在最后面。
3. 剩下的情况是 v₁ → v 而 v → v_k。从左往右找第一个满足 v → v_i 的位置 i（因为 v → v_k，一定找得到，而且 i ≥ 2）。i 是第一个，所以 v 没有指向 v_i−1，只能是 v_i−1 → v。于是 ⋯ → v_i−1 → v → v_i → ⋯，v 插在了中间。

每次插入后仍是一条经过所有已加入点、每点一次的有向通路，归纳完成。∎

部分概念关系图（课件第 41 页）

这张表是这一节的"地图"，后面每个概念都能在里面找到位置。每一行的"⟺"表示：图具有左边的连通性，当且仅当它恰好有一个对应的分支。

极大子图与分支

道理很直接：G 本身连通时，G 就是一个连通子图，而且不能再扩大，所以它就是唯一的分支。

有向图的三种分支（课件第 47–48 页）

用上一节距离矩阵那张有向图来看：

弱分支只有 1 个，就是整张图（忽略方向后连通）。

• 为什么 {v1,v2,v3} 是强分支：沿着 v1→v2→v3→v1 绕圈，三点两两互达。加入 v4 就不行了，v4 回不到 v3。
• 为什么 {v1,…,v5} 是单向分支：任意两点至少一个方向能到（比如 v1⇒v5，v2⇒v4）。加入 v6 就不行：v6 只能到 v5，v6 和 v1 互相都到不了。
• 为什么 {v5,v6} 也是单向分支：v6⇒v5，而且它已经不能扩大：再加入任何一个点 x ∈ {v1,…,v4}，x 和 v6 互相都到不了。

回路、半回路、有向回路（作为"图"）

为什么"连通"不能省：两个分开的三角形也是 2 度正则图，但它是两个圈，不是一个回路。为什么有向回路要求"弱连通"：两个分开的有向三角形每点出入度都是 1，同样要排除。有向回路一定是半回路，反之不然。

条件 (ii) 说的是：从 v 出发能"一笔画"地把所有点、所有边各走一遍回到 v。

充分性（(i)(ii) ⇒ G 是回路）：

1. 由 (ii)，所有点都在一条闭合走法上，任意两点都能沿着它互相到达，G 连通。
2. 回路每经过一个点，就"进来一条边、出去一条边"，所以每个点的度至少是 2。
3. 如果某个点的度大于 2，那么 2|E| = ∑d(v) > 2|V|，与 (i) 的 |V| = |E| 矛盾。所以每点度恰好为 2，G 是连通 2 度正则图，即回路。

必要性（G 是回路 ⇒ (i)(ii)）：

1. (i)：每点度为 2，由握手定理 2|E| = ∑d(v) = 2|V|，所以 |E| = |V|。
2. (ii)：从 v 出发沿一条边走。到达一个新点时，它有 2 条边，进来用掉一条，还剩一条可以出去，所以不会卡住。也不会第二次走到 v 以外的某个旧点（那需要它有第 3 条边）。点数有限，最终一定回到 v。这样走出的闭合路径上的点和边构成一个连通的 2 度正则子图，它不和其他点相连，而 G 连通，所以它就是 G 的全部。

有向回路的版本相同，把"度为 2"换成"出度、入度都是 1"。课件第 56 页用的是对阶数归纳：在 n+1 阶有向回路里删掉 v，把它前后两点 v_n、v₁ 直接连上，得到 n 阶有向回路（可能出现重边），由归纳假设拿到通路后再把 v 插回去。

有回路与非循环图

直觉：在 G′ 里每个点都有路可走（都能出去），从任何点出发一直走，永远不会卡住；但点只有有限个，迟早会走到走过的点，这就绕成了一个圈。

证明（入度版，课件写法）：取 G′ 中最长的基本通路 v₀ → v₁ → ⋯ → v_n。v₀ 的入度大于 0，所以有边 e = ⟨v, v₀⟩。如果 v 不在这条通路上，把 v 接在最前面就得到更长的基本通路，与"最长"矛盾。所以 v 就是通路上的某个 v_i，于是 v₀ → ⋯ → v_i → v₀ 是一条有向回路。∎

反过来读（逆否命题）：没有有向回路的有向图，它的每个子图里都至少有一个出度为 0 的点（也至少有一个入度为 0 的点）。W-过程就是靠这一点工作的。

W-过程：判断有向图是否有有向回路

为什么删 v 不影响答案：有向回路上每个点出度、入度都至少为 1。v 的出度或入度为 0，它不可能在任何有向回路上，删掉它不会破坏任何回路，也不会凭空造出回路。

为什么无回路时一定能删到只剩 1 个点：由上面定理的逆否命题，没有有向回路的图里总有出度为 0 的点，所以每一步都有点可删；删完后的子图仍然没有有向回路，可以继续。反过来，如果中途卡住（剩下的每个点出度、入度都大于 0），由定理，图里一定有有向回路。

这就是数据结构课里的"拓扑排序"：按删除顺序倒过来排，就得到一个使所有边都从前指向后的顶点顺序。课件说课程选修系统检测先修课是否循环依赖、编译器检测递归调用，用的都是这个方法。

判断一个图是否是非循环图（课件第 61 页）

这里的度对有向图按基础图算（入度加出度）。理由和有向版本一样：在每个点度都 ≥ 2 的子图里，走到一个点总能从另一条边离开，走不到头，迟早绕成圈；反过来，一个圈本身就是每点度为 2 的子图。

判定算法：令 G₀ = G。只要 G_i 里有度 ≤ 1 的结点 v_i，就令 G_i+1 = G_i − {v_i}。得到序列 G₀, G₁, …, G_m（m ≤ n−1）。如果 G_m 是平凡图，G 是非循环图；否则（卡住了）不是。直观上就是不断"剪掉叶子"。

课件第 61 页的图 (a) 就是 W-过程那张图，它标注"不是非循环图"：忽略方向后 v1、v2、v5 构成三角形，这是一个半回路。在上面实验里切到"看作无向图"，一个点都删不掉。

连通的充分条件（课件第 62–63 页）

(1) 的证明：任取两个结点 u、v，证明它们之间有路。

• 如果 u、v 相邻，已经连通。
• 如果不相邻：简单图中，u 的邻居和 v 的邻居都只能在其余 n−2 个点里（不能是自己，也不能是对方）。可是 d(u) + d(v) ≥ n−1 > n−2，两个邻居集合的大小加起来超过了 n−2 个"位置"，由抽屉原理它们必有公共元素 w。于是 u–w–v 是一条路。

所以任意两点都连通（而且距离不超过 2）。

(2) 的证明：对任意 u、v，d(u) + d(v) ≥ (n−1)/2 + (n−1)/2 = n−1，由 (1) 得 G 连通。

分支数与边数的关系（课件第 64–67 页）

先猜边数最多的情形：k 个分支，要让边尽量多，就把点尽量"堆"到一个分支里，并且让它是完全图。也就是 k−1 个孤立点 + 一个 K_n−k+1，边数恰好是 (n−k+1)(n−k)/2。课件第 64 页的图是 n=7、k=4：K₄ 加 3 个孤立点，6 条边，(7−4)(7−4+1)/2 = 6。

证明：

1. 先让每个分支变成完全图。在一个分支内部加边不会把两个分支连起来，分支数 k 不变，边数只增不减。所以只需证明"每个分支都是完全图"时结论成立。
2. 设各分支点数为 n₁, …, n_k，n₁ + ⋯ + n_k = n，每个 n_i ≥ 1。边数
   M = [n₁(n₁−1) + ⋯ + n_k(n_k−1)] / 2
3. 令 T = max n_i。其余 k−1 个分支每个至少 1 个点，所以 T ≤ n − (k−1) = n−k+1。
4. 每一项 n_i(n_i−1) ≤ T(n_i−1)，所以
   M ≤ T[(n₁−1) + ⋯ + (n_k−1)] / 2 = T(n−k) / 2 ≤ (n−k+1)(n−k) / 2

∎ 课件第 65–66 页还给了另一种思路：比较两个各有 n₁, n₂ ≥ 2 个点的完全图分支（边数 B）和"一个 K_n1+n2−1 加一个孤立点"（边数 A），算出 A − B = (n₁−1)(n₂−1) > 0。意思是：把一个分支的点挪到另一个分支里，只留一个孤立点，边数会变多。反复这样做，最后就得到"k−1 个孤立点 + 一个大完全图"。

k = 1 时公式给出 n(n−1)/2，正是 K_n 的边数。反过来用：n 阶简单图如果边数 > (n−1)(n−2)/2（k=2 时的上界），它一定连通。

课件③ 第 69–86 页

上一节问"图连不连通"，这一节问"图连得牢不牢"：最少拿掉哪些点或边，图就断开了？这些关键的点和边就是网络里的薄弱环节。

引例：嗅探器（ZJOI 2004）

红军要在蓝军网络的某台中间服务器上装一个嗅探器，截获两个信息中心之间的所有数据包。数据包可以走不同的路。问：装在哪台服务器上，才能保证所有数据包都经过它？

换成图论的说法：找一个点 v（不是 2 也不是 4），使得从 2 到 4 的每条路都经过 v。上图中 4 只连着 1，任何到达 4 的路都必须先经过 1，所以答案是 1 号服务器。下面的割点定理会告诉我们，这样的 v 正是"割点"的另一种刻画。

课件第 71 页的图里还画了一条 3–4 的连线。如果真有这条边，2 到 4 就有 2–1–4 和 2–3–4 两条不共用中间点的路，装在哪台中间服务器上都截不全。原题样例的边表里没有 3–4，答案是 1。

点割集与割点

边割集与割边（桥）

为什么：设 T 是所有一端在 V₁、另一端在 V₂ 的边。

• 删掉 T：V₁ 和 V₂ 之间没有边了，图断开（够用）。
• 少删 T 中任意一条边 e：e 把 V₁ 和 V₂ 接上，而 V₁、V₂ 内部各自连通，所以整个图又连通了（不多余）。

"每个子集的导出子图连通"这个条件不能少。如果 V₁ 自己内部就是断开的两块，跨边集合里可能有多余的边：只删其中一部分图就已经断了。

圈与距离

无向图的距离满足四条性质：不连通时 d(u,v) = ∞；d(u,u) = 0；d(u,v) = d(v,u)（对称）；d(u,w) ≤ d(u,v) + d(v,w)（三角不等式：先到 v 再到 w 也是一条从 u 到 w 的链，最短链不会比它长）。

课件这里用"链"指无向图中的通路，"路"一般指不重复点的链。

割点、割边的等价刻画

⇐：u 到 w 的每条路都经过 v，那么在 G − {v} 中 u 和 w 之间一条路都没有，G − {v} 不连通，v 是割点。

⇒：v 是割点，G − {v} 至少有两个分支 G₁、G₂。取 u ∈ G₁、w ∈ G₂。G 连通，所以 G 中有 u 到 w 的路。对其中任意一条路 Γ：如果 Γ 不经过 v，它就完整地留在 G − {v} 里，u、w 就在同一个分支中，矛盾。所以 Γ 必经过 v。∎

回到嗅探器：要找的就是这样一个 v，只不过 u、w 已经指定为两个信息中心。

证明和割点完全一样，把"删点 v"换成"删边 e"。

证明：设 e = (x,y)。下面四句话一个推一个，每一步都是"当且仅当"：

1. e 是割边
2. ⇔ 删掉 e 后，x 和 y 落在 G − {e} 的不同分支中（删掉 e 只可能把 e 的两端拆开，别的点之间原来怎么连还怎么连）
3. ⇔ 在 G − {e} 中不存在 x 到 y 的路
4. ⇔ e 不在任何基本回路中。因为：如果 e 在某个基本回路上，回路去掉 e 剩下的部分就是一条 x 到 y、不用 e 的路；反过来，如果有一条不用 e 的 x–y 基本路，把 e 接上就是一个包含 e 的基本回路。

∎ 一句话：桥就是不在任何圈上的边。在圈上的边删了可以绕道，桥删了没有路可绕。

Tarjan 算法：一次 DFS 找出所有割边

最直接的办法是逐条边删掉、做一次连通性检查：一共 |E| 条边，每次检查 O(|V|+|E|)，总共 O(|E|(|V|+|E|))（课件写的是 O(|V|(|V|+|E|))，那是逐个点判断割点的代价）。1986 年图灵奖得主 Robert Tarjan 给出的算法只需要做一次深度优先搜索（DFS），复杂度 O(|V|+|E|)。

第一步：做一次 DFS，分出两种边

从任一点出发做 DFS。沿着它"第一次走到新点"所用的边（树枝边）构成一棵 DFS 树，其余的边叫返祖边（回边）。

理由：假设 DFS 正在处理 u，u 有一个邻居 w 还没被访问，DFS 一定会在离开 u 之前访问 w，所以 w 会成为 u 的后代。也就是说，相邻的两个点之间一定是祖先—后代关系。

这立刻告诉我们：返祖边一定不是桥（它和树上的那段路构成一个圈），只有树枝边才可能是桥。

第二步：给每个点记两个数

• dfs[u]：u 被访问的次序（时间戳），第几个被访问就是几。
• low[u]：从 u 的子树里的任意点出发，最多走一条返祖边，能到达的点的时间戳的最小值。直观地说，就是"u 这一支最高能爬回到哪"。

计算方法：先令 low[u] = dfs[u]；遇到返祖边 (u, w) 时 low[u] = min(low[u], dfs[w])；子结点 v 处理完返回时 low[u] = min(low[u], low[v])。

第三步：判定

为什么：low[v] > dfs[u] 意思是 v 的整棵子树，靠返祖边最高也只能爬到 v 自己这一层，碰不到 u 或 u 上面的点。那么子树和外界唯一的联系就是树枝边 (u, v)，删掉它子树就掉下来了，所以是桥。反之，如果 low[v] ≤ dfs[u]，子树里有一条返祖边能绕到 u 或更高的地方，(u, v) 删了也能绕过去，就不是桥。

最后的结果与课件第 86 页的表一致：dfs = (1,2,3,4,5,6,7,9,8)，low = (1,1,1,1,2,6,7,1,1)（按结点 1~9 排列）。检查每条树枝边：

• (5, 6)：dfs[5] = 5 < low[6] = 6，是桥。
• (6, 7)：dfs[6] = 6 < low[7] = 7，是桥。
• (4, 5)：low[5] = 2（5 有返祖边连到 2），dfs[4] = 4 ≮ 2，不是桥。
• (4, 9)：low[9] = 1（经 8 的返祖边到 1），不是桥。其余同理。

同样的 dfs/low 也能找割点：非根结点 u 是割点 ⇔ 它有某个子结点 v 满足 dfs[u] ≤ low[v]（注意是 ≤）；根结点是割点 ⇔ 它在 DFS 树上有至少两个子结点。这张图里割点是 5 和 6。

课件③ 第 88–100 页

这一节的概念都是同一个模式：从图里选一些点或边，要求它们满足某种"照顾到"或"互不冲突"的条件，然后问最少（或最多）要选几个。下面先给全景，再逐个讲。

下面所有例子都用课件里这张 8 个点、11 条边的图（v7、v8 分别在两条对角线的中间）：

支配集

引例（选址问题，课件第 93 页）：要在 n 个地点中选若干处设应急中心，使每个地点要么本身是应急中心，要么和至少一个应急中心直接相邻。为了省钱，中心要尽量少。应设几个？设在哪？

对照课件的图：

• {v2, v3, v4, v6} 是支配集（课件第 95 页）：v1 被 v2 支配，v5 被 v4 或 v6 支配，v7 被 v2 支配，v8 被 v3 支配。但它不是极小的：去掉 v4，v4 自己被 v3 支配，其余点照旧被支配，剩下的 {v2, v3, v6} 仍是支配集。
• {v2, v5} 是最小支配集（课件第 96 页右图）：v2 支配 v1、v3、v7，v5 支配 v4、v6、v8。
• 为什么不可能只用 1 个点：度最大的点 v2、v5 度都是 4，一个点最多照顾到自己和 4 个邻居共 5 个点，不够 8 个。所以最小支配集大小是 2。程序枚举可知只有 {v2, v5} 和 {v3, v6} 两个。
• {v1, v2, v3} 是极小支配集但不是最小的：去掉 v1，v6 就没人支配；去掉 v2，v7 没人支配；去掉 v3，v4 没人支配。它不能再减，可是比 {v2, v5} 多一个点。

所以选址问题的答案是：至少设 2 个应急中心，可以设在 v2、v5，或 v3、v6。

课件只给了结论。证明分两步，核心是证明"剩下的点 V − V₁* 本身也是支配集"。记 D = V₁*。

1. D 中每个点 v 都有邻居在 D 外面。 D 是极小的，去掉 v 后 D − {v} 不再是支配集，所以有某个点 w 没被 D − {v} 支配。分两种情况：
   • w 就是 v 自己：说明 v 在 D 里没有邻居。可是 G 没有孤立点，v 总有邻居，那这个邻居只能在 D 外面。
   • w 是 D 外面的点：w 原来被 D 支配，去掉 v 后就不被支配了，说明 w 唯一的 D 中邻居是 v。于是 w 就是 v 在 D 外面的邻居。
2. 所以 V − D 是支配集：不在 V − D 中的点就是 D 中的点，由第 1 步它们都和 V − D 中的某点相邻。
3. V − D 是支配集，但不一定极小。从中不断去掉多余的点，直到不能再去，得到一个极小支配集 V₂* ⊆ V − D，它和 D 不相交。∎

例：{v2, v5} 是极小支配集，V − {v2,v5} = {v1,v3,v4,v6,v7,v8} 是支配集，从中可以减出 {v3, v6}。"无孤立点"不能去掉：孤立点必须属于每一个支配集（没人能支配它），两个支配集就不可能不相交。

覆盖集（课件定义：边覆盖点）

说人话：挑一些边，让每个点都至少被一条挑中的边碰到。显然有孤立点的图不存在覆盖集。

左图为什么是极小的：每条边都"独占"某个点，例如 (v1,v2) 是唯一碰到 v1 的边，(v2,v3) 是唯一碰到 v3 的边，去掉任何一条都有点没被覆盖。右图为什么是最小：一条边最多覆盖 2 个点，8 个点至少要 4 条边，右图正好 4 条，而且这 4 条边两两不共用端点。

独立集（课件定义：两两不相邻的边，即匹配）

两条边"相邻"就是共用一个端点（10.2 节的定义）。所以独立集就是一组互不共用端点的边，在别的教材和算法课里叫匹配（matching）：可以想成给点两两配对，每个点最多配一次。

课件第 103 页把左图放在"极大独立集"的定义旁边，但它只有 (v1,v2)、(v4,v5) 两条边，还可以再加入 (v6,v7) 和 (v3,v8) 而不冲突，所以严格按定义它不是极大的。加满之后就是右图。

最小点覆盖问题

这里选的是点，要求每条边都被碰到，和上面的"覆盖集"方向正好相反。应用：软件测试里，"点覆盖"指测试用例要经过程序控制流图的所有结点，"边覆盖"指要经过所有边（课件第 99 页）。这个问题是 NP 难的，没有已知的多项式时间精确算法。

2-近似算法

1. 令 E′ = ∅，A = ∅。
2. 只要还有边没处理：任取一条边 (u, v)，放进 E′，把 u 和 v 都加入 A，然后删掉所有和 u 或 v 相邻的边（它们已经被覆盖了）。
3. 没边了就停止，输出 A。

A 是点覆盖：每条边要么被选进了 E′（两端都在 A 中），要么是因为和某条选中的边相邻而被删掉（共用的那个端点在 A 中）。

近似比 ≤ 2（为什么最多只比最优多一倍）：

• E′ 中的边两两不相邻（选一条就删掉它所有相邻边），也就是说 E′ 是一个独立集（匹配）。
• 设 OPT 是最优解。OPT 要覆盖 E′ 的每条边，每条边至少要用一个端点。E′ 的边互不共用端点，所以 OPT 至少要用 |E′| 个不同的点：|E′| ≤ |OPT|。
• A 恰好由 E′ 的端点组成：|A| = 2|E′| ≤ 2|OPT|，即 |A| / |OPT| ≤ 2。

在下面实验的"点覆盖"模式里可以运行这个算法，看看它在课件这张图上给出几个点。

POJ 3041 Asteroids：二部图上的点覆盖

题目：N×N 网格里有 K 颗小行星，第 i 颗在 (R_i, C_i)。一发光束能清除一整行或一整列。最少几发？课件的例子：小行星在 (1,1)、(1,3)、(2,2)、(3,2)。

建模：上面一排点代表"行"，下面一排点代表"列"，每颗小行星 (r, c) 连一条边 r–c。打一发行光束 = 选中一个行点，它清除这一行所有小行星 = 覆盖这个点关联的所有边。所以"清除所有小行星的最少发数" = 这个二部图的最小点覆盖。

一般图的点覆盖是 NP 难的，但二部图有 König 定理：最小点覆盖的点数 = 最大匹配的边数，而最大匹配可以用匈牙利算法在多项式时间内求出。这里最大匹配是 {行1–列1, 行2–列2}，2 条，所以答案是 2。下界的理由和近似算法一样：匹配中的边互不共用端点，每条都需要一个不同的点去覆盖。

课件④ 第 1–32 页

第十一章叫"图的基本问题"，本章内容分三块：穿程问题（欧拉图、哈密顿图、骑士周游）、通路问题（最短通路、关键通路）、匹配问题（二分图）。这份课件讲的是前两个：欧拉图和哈密顿图。

哥尼斯堡七桥问题与一笔画

普雷格尔河把城市分成 4 块陆地：两岸 C、D 和两个岛 A、B，之间有 7 座桥。问：能否从某块陆地出发，每座桥恰好走一次，最后回到出发点？

课件第 7 页把边写成三元组 (A, C, 1), (A, C, 2)，第三个分量是给两座平行的桥编号，这样它们就是两条不同的边。

欧拉在 1736 年证明了这是不可能的，而且不能走成"不回到起点"的版本（课件第 8 页："既无欧拉回路，又无欧拉路径"）。理由在下面的定理里：4 个点的度都是奇数。

"交点处的线条数"就是这个点的度。所以一笔画问题完全由度数的奇偶决定，下面是严格的定义和定理。

定义

课件里那两行逻辑式正好对应"恰好一次"的两半：第一行说每条边都出现（至少一次），第二行说出现的边互不相同（至多一次）。

例：判断四个图（课件第 11–14 页）

观察出的规律：有欧拉圈的图所有结点度数都是偶数；只有欧拉链的图恰有两个奇点，欧拉链就从一个奇点走到另一个；奇点有 4 个的 G₄ 两样都没有。下面把这个规律证明出来。

欧拉图的判定定理

证明分三步：先证 1 ⇒ 2（定理 11.2.2，必要性），再证 2 ⇒ 1（定理 11.2.1，充分性），最后 2 ⇔ 3 在证明 2 ⇒ 1 的过程中顺带得到。

必要性：欧拉图 ⇒ 连通且每点度为偶数（定理 11.2.2）

连通：欧拉圈经过所有边，任意两个有边的点都在这条回路上，沿回路就能互相到达。（定义里本来就要求了 G 连通。）

度为偶数：沿欧拉圈走一圈。每次"路过"一个点，都是从一条边进来、从另一条边出去，给这个点的度贡献 2。起点也一样：出发时用掉一条边，最后回来时又用掉一条，合起来也是 2。每条边恰好被走一次，所以每个点的度 = 2 × 它被路过的次数，是偶数。

充分性：连通且每点度为偶数 ⇒ 欧拉图（定理 11.2.1）

证明要用到一个辅助事实：每点度数都是偶数（且有边）的图里一定有圈。理由就是 10.6 节非循环图那条定理：所有点度 ≥ 2 的图不是非循环图。直观地说：从任一点出发沿没走过的边走，每进入一个点，因为度是偶数，进来用掉一条边后还剩奇数条，至少有一条可以出去，所以不会被卡住，点数有限，最后一定走回走过的点，形成一个圈。课件定义 11.2.3 的"极大路径"（不能再延长的路径）就是用来严格写这个论证的：极大路径的端点的所有邻居都在路径上，而它度 ≥ 2，所以它还连着路径上另一个点，这就构成圈。

证明（对边数 m 归纳，课件第 16–18 页）：

1. 起步：G 是平凡图（没有边）时结论成立。m = 1 时，连通且度为偶数，唯一的边只能是一个自环，自环本身就是欧拉圈。
2. 归纳假设：设边数 ≤ k 时结论都成立，看 m = k+1。
3. 取一个圈 C：由上面的辅助事实，G 中有圈 C。把 C 上所有的边删掉，得到生成子图 G′。
4. G′ 的每个分支都满足归纳假设：C 经过每个点时用掉这个点的 2 条边（或 0 条），所以删掉 C 后每个点的度仍是偶数。G′ 可能不连通，设它有若干个分支 G′₁, …, G′_n，每个分支连通、度数全偶、边数 ≤ k，由归纳假设，每个 G′_i 都是欧拉图，有自己的欧拉回路。
5. 每个分支都和 C 有公共结点：G 是连通的，G′_i 原来和外面相连只能靠 C 的边，所以 G′_i 一定碰到 C，设公共结点为 v_ij。
6. 拼接：沿着 C 走，每走到一个 v_ij，就先把 G′_i 的欧拉回路从 v_ij 出发走一遍再回到 v_ij，然后继续沿 C 往前走。走回起点时，C 的边和所有 G′_i 的边都恰好走了一次，这就是 G 的欧拉回路。∎

从这个证明还能看出：不断"拿出一个圈"，最后边全部拿完，所以欧拉图是若干个边不相交的圈的并（命题 3）。反过来，若干个边不重的圈并起来，每个圈给经过的点贡献 2 度，所以每点度为偶数，连通时就是欧拉图。

例：把证明过程走一遍（课件第 19 页）

拼接：沿 C 从 u₄ 出发。在 u₄ 先插入分支 1 的回路 u₄u₇u₅u₆u₄，然后沿 C 走到 u₃，在 u₃ 插入分支 2 的回路 u₃u₁u₂u₃，再沿 C 经 u₅ 回到 u₄：

10 条边全部恰好走一次。注意 u₄、u₅、u₃ 都经过了两次，这在欧拉回路里是允许的。

欧拉链的判定（定理 11.2.4）

证明思路：加一条边，把欧拉链变成欧拉回路（课件第 23–26 页）。令 e 是一条连接 v₁、v₂ 的新边（如果 G 里已经有边 (v₁,v₂)，就加一条与它平行的新边），G′ = G + {e}。下面每一步都是"当且仅当"：

1. G 有一条从 v₁ 到 v₂ 的欧拉链
2. ⇔ G′ 有一条欧拉回路（欧拉链走到 v₂ 后再沿 e 回到 v₁，就是 G′ 的欧拉回路；反过来，G′ 的欧拉回路去掉 e 就是 G 中 v₁ 到 v₂ 的欧拉链）
3. ⇔ G′ 是欧拉图
4. ⇔ G′ 中每个结点都是偶结点（上面的判定定理）
5. ⇔ G 中恰有两个奇结点 v₁ 和 v₂（加边 e 只让 v₁、v₂ 的度各加 1，别的点不变）。∎

课件第 25–26 页讨论了 e ∈ E 的情形（v₁、v₂ 本来就相邻），把 G − {e} 拆成两个圈来处理。用"加一条平行边"的写法可以把两种情形统一起来，因为欧拉图的判定定理对有平行边的图同样成立（七桥图本身就有平行边）。

序列图是欧拉图（课件第 21 页）

10.3 节的 0-1 序列图 S_m（m = 3 时 8 个点）每个点入度 2、出度 2，课件的 degreeset 函数算出度数全是 4，所以按无向图看它是欧拉图（自环 (0,0)、(7,7) 算 2 度）。对有向图也有同样的定理：弱连通有向图有有向欧拉回路 ⇔ 每个点入度 = 出度（课件第 21 页那两个公式就是入度、出度的定义）。

拓展：S_m 的有向欧拉回路有一个漂亮的用途。每条边对应一个 m+1 位 0-1 串，沿欧拉回路依次写下每条边的最后一位，就得到一个长 2^m+1 的环形 0-1 序列，每个 m+1 位串恰好在其中出现一次（De Bruijn 序列）。这正是"序列图"这个名字的来源。

Fleury 算法：实际把欧拉回路找出来

判定定理只告诉我们"有没有"，Fleury 算法告诉我们"怎么走"。

"桥"是相对于剩下还没走的边而言的：把已经走过的边擦掉，在剩下的图里，如果某条边一删掉就会把图分成两块，它就是桥。

为什么不能随便走桥：桥是两块之间唯一的通道。如果另一侧还有没走的边，过了桥就回不来，留在这一侧的边就再也走不到了。所以只有在"别无选择"时才过桥，这时过桥后另一侧就是剩下的全部。

课件第 28 页的动画演示的就是在下面这张图上用 Fleury 算法从左上角出发走一圈。在下面的实验里可以一步步看到每一步为什么这样选，也可以自己点边走，故意走桥看看会怎么卡住。

中国邮递员问题

1962 年，中国数学家管梅谷提出并解决了这个问题，所以国际上叫它 Chinese Postman Problem。

和欧拉问题的区别：欧拉要求每条边恰好一次，这里允许重复，只求总长最短。

• 街道图本身是欧拉图：直接用 Fleury 算法走一条欧拉回路，每条街恰好一次，这显然最短。
• 不是欧拉图：必须重复走一些街道。重复走一条边，相当于在图里给它再添一条平行边。目标变成：添一些边，使所有点的度都变成偶数（图变成欧拉图），并且添的边总权值最小。

两个条件为什么合理：

• (1) 如果某条边重复了 2 次以上（一共走了 3 次或更多），去掉其中两次，每个端点的度都减 2，奇偶不变，仍然能走成回路，路程却更短。所以最优解里每条边最多多走一次。
• (2) 在某个圈上，如果重复边的总长超过了圈长的一半，就把这个圈上"重复"和"不重复"对调：原来重复的改成不重复，原来不重复的改成重复。圈上每个点的度变化 0 或 ±2，奇偶不变，仍可走成回路，而重复的总长变成了原来不重复的那部分，更短。所以最优解一定满足 (2)。

课件最后提到 Edmonds–Johnson 算法可以在 O(n³) 时间内求出最优解。它的核心是：把所有奇点两两配对，每一对之间沿最短路添一遍重复边，选总长最小的配对方式。

课件④ 第 33–60 页

哈密顿问题是爱尔兰数学家哈密顿在 1857 年发明的智力题（"周游世界"游戏）：正十二面体的 20 个顶点代表 20 个城市，从一个城市出发，每个城市恰好经过一次，最后回到出发城市。也就是判断图中是否存在一条遍历所有结点的简单回路。

为什么难（课件第 35–36 页）：通常没有简单的判断方法。最直接的做法是把 20 个城市排成一个顺序，检查相邻两个是否有边。排列一共 20! = 2432902008176640000 种，即使每秒验证 10000 种，也要约 771 万年，复杂度 O(n!)。哈密顿圈问题是 NP 完全问题，至今没有已知的多项式时间算法。

回溯搜索：课件的周游算法

比起盲目枚举所有排列，更聪明的做法是沿着边一步步延长路径，走不下去就退回一步换个方向（回溯）。走不通的分支会被提前剪掉，不用把整个排列写完再检查。

第一步：建邻接表（课件第 39–40 页）

对每个结点 u，列出和它相邻的所有结点，记为 [u, [v | (u,v) ∈ E]]。课件的 adjacentlist(V,E) 对每个点 w 扫一遍边集，把另一端加进列表并排序。例如十二面体图中：

['a', ['b', 'n', 't']]   ['b', ['a', 'c', 'l']]   ['c', ['b', 'd', 's']]   ...

有了邻接表，"从 w 能走到哪些点"就能直接查到，不用每次扫全部边。

第二步：三个函数（课件第 41–46 页）

"从 v 之后继续找"是关键：回溯回到 u 时，排在 v 前面的邻居已经试过了，不用再试，这保证了不重复、不遗漏。

运行结果（课件第 47–51 页）

• 十二面体图从 a 出发，共找到 162 条哈密顿通路。其中终点是 a 的邻居（b、n、t）的，再加一条边就能回到 a，构成哈密顿圈。课件第 47 页的代码 if path[-1] in ['b','n','t'] 就是在筛选这些，我用程序验证共有 60 条。所以十二面体图是哈密顿图，"周游世界"有解。
• 彼德森图从每个结点出发都有 24 条哈密顿通路，10 个点共 240 条，但没有一条能闭合：彼德森图没有哈密顿圈，不是哈密顿图。它每点度都是 3，也不是欧拉图。

哈密顿图的充分条件

既然没有简单的充要条件，就退而求其次：给出"只要满足就一定是哈密顿图"的条件。共同的直觉是：边越多、每个点的度越大，越容易找到哈密顿圈。

证明（反证法 + "极大"反例）：

1. 构造一个"极大"的反例。假设定理不成立，有满足条件的非哈密顿图。往里面不断加边，只要加完仍不是哈密顿图就继续加。加边不会让度变小，条件 δ ≥ n/2 一直满足；而 K_n（n ≥ 3）是哈密顿图，所以加边过程一定在某处停下。停下时得到的 G 满足：G 不是哈密顿图，但再加任何一条边都会变成哈密顿图。这就是课件说的"极大非哈密顿简单图"。显然 G 不是完全图。
2. 得到一条哈密顿路。取两个不相邻的顶点 u、v。由极大性，G + uv 是哈密顿图，而且它的每个哈密顿圈都必须用到新边 uv（否则这个圈在 G 里就存在了）。把这个圈里的 uv 去掉，得到 G 中一条从 u 到 v 的哈密顿路：
   P = v₁v₂ ⋯ v_n，　v₁ = u，v_n = v
3. 定义两个下标集合。
   S = { v_i | uv_i+1 ∈ E(G) }，　T = { v_i | v_iv ∈ E(G) }
   S 是"u 的每个邻居在路上的前一个点"组成的集合，T 是 v 的邻居集合。u 的每个邻居 v_i+1 对应 S 中唯一的 v_i，所以 |S| = d(u)；|T| = d(v)。
4. |S ∪ T| < n。S 中的点下标 i ≤ n−1（因为 v_i+1 要存在），所以 v_n ∉ S；v 不和自己相邻，所以 v_n ∉ T。S ∪ T 最多包含 v₁, …, v_n−1，|S ∪ T| ≤ n−1 < n。
5. S ∩ T = ∅。否则设 v_i ∈ S ∩ T，即 uv_i+1 ∈ E 且 v_iv_n ∈ E。那么
   v₁ → v_i+1 → v_i+2 → ⋯ → v_n → v_i → v_i−1 → ⋯ → v₁
   是 G 中经过所有点的圈（下图），G 是哈密顿图，与假设矛盾。（课件第 55 页写成 "|S ∩ T| = ∅"，应为 S ∩ T = ∅，即 |S ∩ T| = 0。）
6. 导出矛盾。
   d(u) + d(v) = |S| + |T| = |S ∪ T| + |S ∩ T| < n + 0 = n
   但 δ(G) ≥ n/2 意味着 d(u) + d(v) ≥ n/2 + n/2 = n，矛盾！∎

定理 11.2.5：哈密顿链的充分条件

条件比 Dirac 弱了 1（n−1 而不是 n），结论也弱一些：只保证哈密顿链，不保证闭合成圈。证明分三步。

1. G 是连通的（反证法）。若不连通，至少有两个分支 G₁、G₂，各取一点 u ∈ G₁、v ∈ G₂。u 的邻居只能在 G₁ 里，d(u) ≤ |G₁| − 1，同理 d(v) ≤ |G₂| − 1。于是 d(u) + d(v) ≤ |G₁| + |G₂| − 2 ≤ n − 2，与条件矛盾。（这和 10.6 节"连通的充分条件"是同一个结论。）

2. 取最长的基本路径，证明它能闭合成圈。设 Γ = v₁v₂ ⋯ v_l 是 G 中最长的基本路径（点不重复）。如果 l = n，它就是哈密顿链，证毕。下面设 l < n，证明存在一个经过 v₁, …, v_l 全部 l 个点的圈。

• (i) v₁ 与 v_l 相邻：Γ 加上边 (v₁, v_l) 就是这样的圈。
• (ii) v₁ 与 v_l 不相邻：
  • Γ 是最长的，所以 v₁、v_l 只能和 Γ 上的点相邻（如果 v₁ 有一个 Γ 外的邻居 w，把 w 接在前面就得到更长的基本路径）。
  • 设 v₁ 与 v_i1, v_i2, …, v_ik 相邻，共 k = d(v₁) 个点。
  • v_l 不能和任何 v_ij−1 相邻，否则下面就是经过 Γ 全部点的圈（和上面 Dirac 证明里的交叉弧完全一样），已经找到了：
    v₁ → v_ij → ⋯ → v_l → v_ij−1 → ⋯ → v₁
  • 所以如果圈不存在，v_l 的邻居只能在 v₁, …, v_l−1（l − 1 个点）中，并且要去掉这 k 个"禁区"点，最多 l − 1 − k 个。
  • 于是 d(v₁) + d(v_l) ≤ k + (l − 1 − k) = l − 1 < n − 1，与条件矛盾。所以圈一定存在。

3. 扩展路径，导出矛盾。现在有一个经过 Γ 上全部 l 个点的圈 C，而 l < n，所以 Γ 外还有点。G 连通，所以一定有 Γ 外的点 v 与 C 上某点 v_j 相邻（一个圈 + 一个点）。从 v 出发走到 v_j，再沿 C 绕一圈（不闭合），得到一条有 l + 1 个点的基本路径，比 Γ 还长，与"Γ 最长"矛盾。所以 l = n，Γ = v₁v₂ ⋯ v_n 是哈密顿链。∎

课件第 57 页还列了两条相关结论：每一对结点度数之和 ≥ n 时存在哈密顿圈（上面的 Ore 定理）；有向完全图（竞赛图）中必存在哈密顿通路（勒代定理，见 10.6 节）。课件特别强调：这些定理都是充分条件。

点选项即判对错并显示解析。每题只能选一次，刷新页面可重来。

公式

易错点

1. 自环对度数贡献 2；邻接矩阵对角线记 1 个自环，算度时要乘 2。
2. 有向简单图允许 ⟨u,v⟩ 与 ⟨v,u⟩ 同时存在，它们不是平行边。
3. 同构的必要条件（点数、边数、度数序列）只能用来否定同构。要肯定同构必须给出双射并验证。
4. W_n 的下标在不同教材里指"总点数"或"圈上点数"，先确认定义。
5. 生成子图看"点全不全"，导出子图看"选中点之间的边全不全"。
6. 补图只对简单图定义，参照物是同阶的 K_n。
7. 可达矩阵别忘了加 I，也别忘了最后布尔化；课件 Python 输出的大数是 (I+A)ⁿ⁻¹ 原值。
8. 有向图的距离不对称，可达也不对称。
9. "简单"管边不重复，"基本"管点不重复；基本 ⇒ 简单。
10. 完备通路/回路允许点重复，它和"每个点恰好一次"的哈密顿通路/回路不是一回事。
11. "G 有一条回路"指走法，"G 是回路"指图本身是一个圈（连通 2 度正则）。
12. 有向图"没有有向回路"不等于"非循环图"，后者要求连半回路都没有。
13. "极小 / 极大"是不能再减 / 不能再加，"最小 / 最大"是个数最少 / 最多，前者不一定是后者。
14. 点割集和边割集都要求"极小"：删掉能断开，但少删任何一个都断不开。
15. 有割点不一定有割边（领结图）。
16. 本课件的覆盖集、独立集是边集；"最小点覆盖"是点集。看清选的是点还是边。
17. Tarjan 判桥用 dfs[u] < low[v]，判割点用 dfs[u] ≤ low[v]（根结点另判）。
18. 欧拉看边（每条边恰好一次，点可重复），哈密顿看点（每点恰好一次，边不必走完）。两者互不蕴含。
19. "欧拉圈"允许点重复，不是 10.7 节"点不重复"的圈。
20. 判断欧拉图前先确认连通；奇点个数一定是偶数，不会出现 1 个或 3 个。
21. Fleury 里的"桥"是指剩余图（擦掉已走过的边）中的桥，不是原图中的桥。
22. Dirac、Ore、定理 11.2.5 都是充分条件，不满足不代表不是哈密顿图（例如 C_n）。
23. 度数和 ≥ n−1 只保证哈密顿链，≥ n 才保证哈密顿圈。