第 6 章 · 图论基础

图论起源于 1736 年欧拉解决「柯尼斯堡七桥问题」:能否每座桥恰走一次走遍全城?欧拉的答案(不能,因为奇度点超过 2 个)开创了两个传统:把问题抽象成图,以及用不变量(奇点数)给出不可能性证明。图是计算机科学的第一结构(数据结构课第 6 章讲过实现与算法,本章补数学理论):社交网络、路由、依赖图、状态机,全是图。

6.1 图的基本词汇

图 G = (V, E),V 顶点集、E 边集。分类:无向/有向(边有无方向)、带权/无权、简单图(无自环无重边)。基本词汇一览:

度 deg(v):顶点关联的边数(有向图分入度/出度);
子图、生成子图:保留部分顶点/边;
路径与通路:顶点序列,路径(v0…vk)边不重,通路不重顶;
连通:任意两点间有路径(有向图分强连通/弱连通);
回路/环:起点终点的闭合路径。

握手定理:所有顶点度数之和 = 2|E|(每条边贡献两个端点)。推论:度数和必为偶数;奇度点的个数必为偶数。这条「小定理」是图论证明的第一工具(欧拉七桥的答案就靠它)。

6.2 欧拉与哈密顿:两种「走遍」

欧拉回路:每条边恰走一次回到起点。欧拉定理:连通图有欧拉回路 ⟺ 所有顶点度数为偶;有欧拉通路(不必回起点)⟺ 恰有 2 个奇度点。直观:每次「进入并离开」消耗两个度,偶度才能处处自洽。一笔画问题的全部秘密,一张图上数奇点即可判定。

哈密顿回路:每个顶点恰经过一次。注意反差:欧拉回路有 O(E) 的完美判定定理,哈密顿回路的判定是 NP 完全的(没有已知的多项式算法,计算复杂度的分水岭,离散数学最著名的「一字之差、天壤之别」)。旅行商问题(TSP)就是哈密顿回路的加权版,运筹学与近似算法的主战场。

哈密顿的充分条件(不是充要):Dirac 定理,每个顶点度数 ≥ n/2(n ≥ 3)则必有哈密顿回路。考试爱考「用 Dirac 验证某图」。

6.3 图的同构:什么时候两张图是同一张

同构 = 顶点重命名后完全一致(存在双射 f,边集经 f 映射后完全相同)。判定不变量(同构必相同,可用来快速排除):顶点数、边数、度序列(排序后的度数列表)、回路长度集合。

度序列相同不能保证同构:C₆(六环)与「两个三角形」度序列都是全 2 但不同构(连通性不同)。图同构的复杂度地位微妙:既无已知多项式算法,又不 believed NP 完全(介于 P 与 NP 完全之间的著名难民)。实际意义:化学分子式检索、芯片比对,都是同构判定的应用。

6.4 特殊图与建模实战

几类高频建模图:

二分图:顶点分两组,边只在组间。判定:无奇圈(奇数长度的环)。应用:任务分配(员工-任务匹配,匈牙利算法)、推荐系统(用户-物品)。König 定理:最大匹配 = 最小点覆盖(对偶之美);
平面图:能画在平面上边不交叉。欧拉公式:V − E + F = 2(含外部面,多面体的欧拉公式同源);推论:简单平面图 E ≤ 3V − 6。四色定理(平面图四色可染,1976 年计算机辅助证明,第一个著名机器证明);
正则图、完全图 Kₙ、完全二分图 K_{m,n}:计数练习的标准道具(Kₙ 的边数 C(n,2),握手定理的练手场)。

6.5 建模三步法:把现实问题变成图

图论应用的通用流程:

定义顶点:什么是一个「实体」?(路口、人、网页、任务、状态)
定义边:什么算「有关系」?(道路、好友、超链接、依赖、转移)
选择问题:要什么?(最短路 = 导航,最大匹配 = 分配,环检测 = 死锁,拓扑排序 = 依赖顺序)

数据结构课第 6 章的算法(Dijkstra、MST、拓扑排序)都是这三步之后的第二步工具。举一个跨课的完整建模:操作系统死锁检测(操作系统课第 5 章):顶点 = 进程与资源,「资源→进程」边 = 分配,「进程→资源」边 = 请求;有环即死锁嫌疑(单实例资源时充要)。图的抽象在这里直接变成内核算法。

常见错误

握手定理的推论记反。「度数和为偶」对任何图成立,但「每个顶点度数是偶」只对欧拉图;别把两者混同。
奇点数判欧拉,忘了连通前提。不连通的图哪怕全偶度也没有欧拉回路;两个条件缺一不可。
哈密顿与欧拉条件乱套。一个管「边不重」(欧拉,度数判定),一个管「点不重」(哈密顿,NP 完全,无简单判定);名字对上对象。
建模时顶点粒度选错。「城市之间最短路」把每个路口当顶点 vs 把城市当顶点,图的规模和算法选择完全不同;先想清「边权代表什么」。

练习

手算:画 Petersen 图(教材经典),数它的 V、E,验证握手定理;判断它是否二分图(找奇圈)。
手算:6 人的派对,若每人恰认识 3 人,这张「认识图」存在吗?(度序列 2+2+2+2+2+2 = 12 = 2E 合法;再具体构造或证明多种情况。)
动手:用你熟悉的语言实现「欧拉回路判定」(连通 + 全偶度)并找一条欧拉回路(Hierholzer 算法,数据结构课第 6 章 DFS 的变体),拿七桥图验证「无解」。
思考:四色定理的证明依赖计算机穷举 1936 种构型,引发「机器证明算证明吗」的百年争论。结合第 4 章(证明 = 推理序列)和本章,写一段你的立场:可验证性与可理解性,哪个是证明的本质?