简单图

简单图：边无方向、无自环、两点间至多一条边。握手引理（12.2.1）：所有顶点度数之和 = 边数的两倍——每次握手都贡献两只手。

它有个炸裂的应用。芝加哥大学、ABC News、美国卫生统计中心都调查过"美国人平均有过多少异性伴侣"，结论一致：男性比女性多 74%、233% 不等。原书用一行图论把这堆调查全部判死：把人当顶点、伴侣关系当边，男性度数和 = 女性度数和 = 边数，于是

两边平均度之比完全由人口性别比决定（美国 |F|/|M| ≈ 1.035，男性平均只可能多 3.5%）——与谁的"花心程度"毫无关系。亲手连边验证：

明星图全家福：完全图 Kₙ（两两有边，n(n−1)/2 条边）、空图、线图 Lₙ、圈图 Cₙ。同构（isomorphism，Definition 12.4.1）则是"换个标签还是同一张图"的严格说法——一个保持边的双射 f：⟨u—v⟩ ∈ E(G) ⟺ ⟨f(u)—f(v)⟩ ∈ E(H)。同构保持度数、连通性、圈长等一切图性质；反过来，找到一个被保持的性质（比如度序列）不成立就证明了两图不同构。顺带：判断两图是否同构至今没有已知的多项式算法——这个"难"还支撑着一类加密协议。

"每个男生都能配到一个他喜欢的女生，且不撞车"——这就是二部图匹配问题。Hall 定理（12.5.2）给出充要条件：每个男生子集喜欢的女生集合，至少与子集本身一样大（Matching Condition；违反者叫 bottleneck）。加强版：degree-constrained（左度 ≥ 右度）的二部图必有匹配覆盖左侧；正则二部图必有完美匹配（定理 12.5.8）。快判三题：

12.5.2把 15 个男生子集全部过一遍堂

原书 Figure 12.9 的"谁喜欢谁"图：Chuck、Tom、Michael、John 四位男生，Alice、Martha、Sara、Jane、Mergatroid 五位女生。Hall 条件要求"每个男生子集"都够大——4 个男生共 15 个非空子集，一个都不能是 bottleneck（|S| > |N(S)|）。这张图恰好是 degree-constrained 的（每人至少喜欢 2 位、每位至多被 2 人喜欢），定理 12.5.6 预告了结局。亲手扫一遍：

边也可以表示冲突：顶点是考试，边=有学生同时选两门 ⇒ 不能同时考。给顶点涂色使相邻不同色，最少颜色数就是色数 χ(G)。原书五门课的调度图（6.041, 6.042, 6.003, 6.170, 6.002）恰需 3 色——其中有个三角形卡死了 2 色的可能。来，亲自排考：

简单图里的 walk/path/cycle 与有向图版本几乎一样，只是箭头换成无向边、长度 2 的来回不算圈（Definition 12.7.1）。圈是子图（12.7.2）：没有起点、没有方向，bcdehb 和 dehbc 是同一个圈。连通性（12.8）：任意两点间有 path 则图连通；极大连通块叫连通分量。定理 12.8.3 的三等价：有奇圈 ⟺ 非 2-着色 ⟺ 有奇长闭合 walk。边还能论"结实程度"：割边（cut edge）= 拔掉就断的边，引理 12.8.6 一句话——割边 ⟺ 不在任何圈上；Kₙ 是 (n−1)-连通的，每个圈都 2-连通。

12.9 登场的树（连通无圈图）是计算机科学里最重要的图：定理 12.9.3 列了六条等价性质——连通子图仍是树、任意两点 path 唯一、加边生圈、每边都是割边、≥2 顶点必有 ≥2 叶、n 顶点恰 n−1 条边。每个连通图都含生成树（Theorem 12.9.6）；给边加上权重、想要总权最小的生成树（MST），Prim/Kruskal 的贪心就够（引理 12.9.11"最小灰边"）。原书 Figure 12.20(b) 那张加权图的最小生成树重 17——贪心拿到了。

两道原书 Practice Problem 做成解题器。

八题，覆盖 12.1–12.9。