图论

参考资料

• 图论 - 维基百科
• 七桥问题 - 维基百科
• 图论 - OI Wiki
• 欧拉公式 - 维基百科

引入

图（Graph）是描述「对象之间联系」的数学结构。社交网络（人与好友）、路网（路口与道路）、电路、程序的函数调用、任务依赖——凡是「一堆东西加上它们之间的连接」，都是图。

图论的奠基性问题是欧拉解决的 柯尼斯堡七桥问题（1736）：能否一次走遍七座桥且每座只走一次？欧拉把陆地抽象成点、桥抽象成边，发现答案只取决于「奇数度的点有几个」，从此开创了图论。这正是图论的思维方式——把具体问题抽掉无关细节，只留下点和边的连接结构。

基本概念

定义

图 $G=(V,E)$ 由 顶点集（Vertex Set）$V$ 和 边集（Edge Set）$E$ 组成。$|V|$ 称图的 阶。

• 无向图：边是无序对 $\set{u,v}$，连接没有方向。
• 有向图：边是有序对 $(u,v)$，从 $u$ 指向 $v$。
• 多重图：允许 平行边（两点间多条边）和 自环（连到自己的边）。
• 简单图：既无平行边也无自环——最常打交道的图。
• 加权图：每条边带一个权值（距离、费用、容量等）。

度数

无向图里，顶点 $v$ 的 度（Degree）$d(v)$ 是与它关联的边数，自环算 $2$（两端都连到 $v$）。

有向图区分 入度 $d^-(v)$（指进来的边数）与 出度 $d^+(v)$（指出去的边数），$d(v)=d^-(v)+d^+(v)$。

度为 $0$ 的顶点叫 孤立点，度为 $1$ 的叫 悬挂点。

握手定理

每条边恰好贡献 $2$ 个「度」（两个端点各 $1$），于是：

$$\sum_{v\in V}d(v)=2|E|$$

这就是 握手定理（Handshaking Lemma）——名字来自「一群人握手，所有人握手次数之和必为偶数（每次握手算两人各一次）」。

推论：奇度顶点的个数必为偶数。 因为总度数是偶数，偶度顶点贡献偶数，剩下奇度顶点的度数之和也得是偶数，那它们只能有偶数个。

有向图对应版本：$\sum d^+(v)=\sum d^-(v)=|E|$。

例：度数之和必为偶数，可用来快速否定。问「能否有一个 $5$ 个顶点、各点度数为 $3,3,3,3,3$ 的简单图」？度数和 $=15$ 为奇数，违反握手定理，不存在。

度序列与可图化

给定一列非负整数，能否画出一个简单图恰好以它为各顶点的度？这叫 可图化（graphical）判定，Havel–Hakimi 定理 给出递归办法：把序列降序排，取出最大度 $d$，从其后 $d$ 个数各减 $1$，再降序、重复；若中途出现负数则不可图化，若最终全为 $0$ 则可图化。

例：判断 $(3,3,2,2,2)$ 可否图化。降序已就绪，取出首项 $3$，把其后 $3$ 个数各减 $1$：

$$(3,3,2,2,2)\ \to\ (\underline{3-1},2-1,2-1,\;2)=(2,1,1,2)\ \xrightarrow{\text{降序}}\ (2,2,1,1)$$

再取出首项 $2$，后 $2$ 个减 $1$：$(2,2,1,1)\to(\underline{2-1},1-1,\;1)=(1,0,1)\xrightarrow{\text{降序}}(1,1,0)$。再取出首项 $1$，后 $1$ 个减 $1$：$(1,1,0)\to(\underline{1-1},\;0)=(0,0)$，全零，故 可图化。直觉上每步都是「让度最大的点先连出去」，逐步消化掉它的需求。

子图与补图

• 子图（Subgraph）：$V'\subseteq V$，$E'\subseteq E$，且 $E'$ 的端点都在 $V'$ 里。
• 生成子图：保留全部顶点（$V'=V$），只删边。
• 导出子图：选定 $V'$ 后，把 $V'$ 内部的边 全部 保留。
• 补图 $\overline{G}$：顶点相同，原来有边的现在没边、原来没边的现在补边。简单图 $G$ 与 $\overline{G}$ 的边集恰好拼成完全图。

特殊图

名称	记号	描述	边数
完全图	$K_n$	$n$ 顶点两两相连	$\dbinom{n}{2}$
完全二部图	$K_{m,n}$	两部分 $m,n$ 顶点，跨部分两两相连	$mn$
圈	$C_n$	$n$ 顶点环状相连	$n$
路径	$P_n$	$n$ 顶点链状相连	$n-1$
轮图	$W_n$	圈 $C_n$ 加一个连所有顶点的中心	$2n$

二部图

二部图（Bipartite Graph）的顶点能分成两组 $X,Y$，使得 每条边都跨组、组内无边——像「学生」与「课程」之间的选课关系。

判定有个漂亮的结论：一个图是二部图 $\iff$ 它不含奇圈。直觉是，二部图沿边走会在两组间「左右横跳」，要回到起点必须走偶数步。这也对应着「图的 $2$-着色」。

路径与连通

概念

• 通路（walk）：顶点和边交替的序列，顶点、边都可重复。
• 迹（trail）：边不重复的通路。
• 路径（path）：顶点不重复（从而边也不重复）。
• 回路 / 圈（cycle）：起点终点相同的路径。

简单说，限制越来越严：通路 → 不重边的迹 → 不重点的路径。

连通性

无向图中，任意两顶点之间都存在通路，则为 连通图；否则图分裂成若干 连通分量（Connected Component）——每个分量是一块极大的连通部分。

有向图的连通分两个层次：

• 强连通：任意两顶点 互相可达（$u$ 能到 $v$，$v$ 也能到 $u$）。
• 弱连通：把方向擦掉、当成无向图后连通。

强连通比弱连通严格。一张图也可以划分成若干 强连通分量，这在编译器、依赖分析里是核心工具。

图的矩阵表示

把图交给计算机，靠的就是矩阵——抽象的「连接」变成可计算的数。

邻接矩阵

$A=(a_{ij})$，$a_{ij}$ 是顶点 $v_i,v_j$ 之间的边数（简单图里就是 $0/1$）。

• 无向图的 $A$ 对称；有向图未必。
• 关键性质：$A^k$ 的 $(i,j)$ 项 $=$ 从 $v_i$ 到 $v_j$ 长度恰为 $k$ 的通路数。

最后一条很有用：邻接矩阵的幂能数路径，可达性、计数问题都能转化成矩阵运算。

例：取路径图 $1-2-3$（边 $\set{1,2},\set{2,3}$），求从 $1$ 到 $3$ 长度恰为 $2$ 的通路数。邻接矩阵

$$A=\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix},\qquad A^2=\begin{pmatrix}1&0&1\\0&2&0\\1&0&1\end{pmatrix}$$

$(A^2)_{13}=1$，确有一条 $1\to2\to3$；而 $(A^2)_{22}=2$ 表示从 $2$ 出发走两步回到 $2$ 有两条（$2\to1\to2$ 和 $2\to3\to2$）。继续算 $A^3$，$(A^3)_{13}=0$，说明 $1,3$ 之间没有长度 $3$ 的通路（奇偶性使然，二部图里同侧两点只有偶长通路）。

关联矩阵

$M=(m_{ij})$，顶点 $v_i$ 与边 $e_j$ 关联时 $m_{ij}=1$。无向图每条边连两个端点，所以 每列恰有两个 $1$（列和为 $2$）——这其实就是握手定理的矩阵版。

最短路

加权图上常问：从 $u$ 到 $v$ 边权之和最小的路径是多少？这就是 最短路（Shortest Path）问题，是导航、路由的核心。

• 边权非负时，Dijkstra 算法 从起点出发，每次「贪心」地确定当前最近的未定点。
• 允许负权时用 Bellman–Ford；求所有点对之间最短路则用 Floyd–Warshall（思想和上一章关系传递闭包的 Warshall 完全一致：让每个点轮流当中转站，看绕过它能否更近）。

Dijkstra 逐步算例

例：顶点 $\set{1,2,3,4}$，有向边权 $1\to2:1$、$1\to3:4$、$2\to3:2$、$2\to4:7$、$3\to4:3$，从 $1$ 出发求单源最短路。维护距离表 $d$，每轮取未定点中 $d$ 最小者「定下来」并松弛它的出边：

轮次	定点	$d_1$	$d_2$	$d_3$	$d_4$
初始	—	$0$	$\infty$	$\infty$	$\infty$
1	$1$	$0$	$1$	$4$	$\infty$
2	$2$	$0$	$1$	$3$	$8$
3	$3$	$0$	$1$	$3$	$6$
4	$4$	$0$	$1$	$3$	$6$

第 $2$ 轮定下 $2$ 后，经 $2\to3$ 把 $d_3$ 从 $4$ 松弛到 $1+2=3$；第 $3$ 轮定下 $3$，经 $3\to4$ 把 $d_4$ 松弛到 $3+3=6$（优于经 $2$ 的 $1+7=8$）。最终 $1\to4$ 最短路为 $1\to2\to3\to4$，长 $6$。贪心成立的前提是 边权非负：一旦某点被定下，没有更短的路能再绕回来。

Floyd 逐步算例

例：同一张图用 Floyd 求全源最短路。初始矩阵 $D^{(0)}$ 填入直接边权（无边记 $\infty$，对角线 $0$），然后让 $k=1,2,3,4$ 依次当中转：

$$D^{(0)}=\begin{pmatrix}0&1&4&\infty\\\infty&0&2&7\\\infty&\infty&0&3\\\infty&\infty&\infty&0\end{pmatrix}$$

$k=2$ 时检查「经过 $2$ 是否更近」：$D_{13}\leftarrow\min(4,\,D_{12}+D_{23})=\min(4,1+2)=3$，$D_{14}\leftarrow\min(\infty,1+7)=8$。$k=3$ 时：$D_{14}\leftarrow\min(8,\,D_{13}+D_{34})=\min(8,3+3)=6$，$D_{24}\leftarrow\min(7,2+3)=5$。最终

$$D^{(4)}=\begin{pmatrix}0&1&3&6\\\infty&0&2&5\\\infty&\infty&0&3\\\infty&\infty&\infty&0\end{pmatrix}$$

与 Dijkstra 的 $1\to4=6$ 吻合。三重循环 $k,i,j$ 的写法和 Warshall 求传递闭包一模一样，只是把「$\lor$」换成了「取 $\min$」、把「$\land$」换成了「相加」。

树

树（Tree）$=$ 连通且无圈 的无向图。它是最简洁的连通结构——刚好连通，多一条边就出圈、少一条边就断开。文件系统、表达式解析、组织架构都是树。

等价定义

设 $|V|=n$，下列条件相互等价（满足其一即为树）：

1. $T$ 连通且无圈。
2. $T$ 连通且 $|E|=n-1$。
3. $T$ 无圈且 $|E|=n-1$。
4. $T$ 中任意两顶点有且仅有 一条路径 相连。
5. $T$ 连通，但删去任一条边后不再连通（边都是「桥」）。
6. $T$ 无圈，但添加任一条边后恰好形成 一个圈。

把这些连起来理解：$n$ 个点的树恰好 $n-1$ 条边，是「用最少的边连通所有点」的方案，少一条就断、多一条就成圈。度为 $1$ 的顶点称 叶子。

生成树

连通图 $G$ 的 生成树（Spanning Tree）是它的生成子图且为树——保留所有顶点、抽掉一些边直到「刚好无圈连通」。任何连通图都有生成树。

加权图上找边权之和最小的生成树，就是 最小生成树（Minimum Spanning Tree，MST），对应「用最少成本把所有点连起来」（修路、铺网）。两个经典贪心算法：

• Kruskal：把边按权 从小到大 排序，依次尝试加入，不形成圈就保留（用并查集判圈）。
• Prim：从一个顶点出发，每次加入连接「树内与树外」的 最小边，逐步长大。

两者都基于同一条「切割性质」：横跨任一割的最小边一定属于某棵 MST。

Kruskal 逐步算例

例：顶点 $\set{1,2,3,4}$，无向带权边 $\set{1,2}:1$、$\set{2,3}:2$、$\set{1,3}:3$、$\set{3,4}:4$、$\set{1,4}:5$，求最小生成树。按权从小到大依次考虑，用并查集判圈：

边	权	是否成圈	决定
$\set{1,2}$	$1$	否	加入
$\set{2,3}$	$2$	否	加入
$\set{1,3}$	$3$	是（$1,2,3$ 已连通）	跳过
$\set{3,4}$	$4$	否	加入
$\set{1,4}$	$5$	—（已 $3$ 条边）	停止

$4$ 个顶点选满 $n-1=3$ 条边即停。MST 为 $\set{\set{1,2},\set{2,3},\set{3,4}}$，总权 $1+2+4=7$。

Prim 逐步算例

例：同一张图，从顶点 $1$ 出发用 Prim。每轮在「树内连树外」的边里挑最小的：

轮次	树内顶点	候选最小边	加入边（权）
1	$\set 1$	$\set{1,2}:1$	$\set{1,2}$（$1$）
2	$\set{1,2}$	$\set{2,3}:2$	$\set{2,3}$（$2$）
3	$\set{1,2,3}$	$\set{3,4}:4$	$\set{3,4}$（$4$）

同样得总权 $7$ 的树。两个算法路径不同——Kruskal 全局排边、Prim 从一点长大——但因切割性质，结果权值必然相同。

欧拉图与哈密顿图

概念	定义	存在条件
欧拉通路	经过 每条边恰一次 的通路	连通图恰有 $0$ 或 $2$ 个奇度顶点
欧拉回路	经过 每条边恰一次 的回路	连通图所有顶点度均为 偶数
哈密顿通路	经过 每个顶点恰一次 的通路	NP-完全问题，无简单充要条件
哈密顿回路	经过 每个顶点恰一次 的回路	同上

欧拉条件的直觉：每次「路过」一个顶点都要「进一条边、出一条边」，成对消耗，所以中间顶点的度必须是偶数；起点和终点若不同，则它俩可以是奇度。柯尼斯堡七桥的四块陆地全是奇度（共 $4$ 个奇度点 $>2$），所以一笔走完不可能——这就是欧拉的答案。

提示

欧拉看边、哈密顿看点——一字之差，难度天壤。

判断欧拉图只需数一数奇度顶点，是 多项式时间 能解的；而判断哈密顿图属于 NP-完全，一般图上 没有已知的高效算法。直觉上「遍历每条边」有局部的度数约束可循，「遍历每个点」却是全局的、牵一发动全身。

判欧拉算例

例：七桥问题。四块陆地的度数（按桥数）为 $5,3,3,3$，奇度点有 $4$ 个，既超过 $2$，故 既无欧拉回路也无欧拉通路——一笔走遍七桥不可能。

例：完全图 $K_5$ 每个顶点度为 $4$，全是偶数且连通，故 有欧拉回路。而 $K_4$ 每点度为 $3$，奇度点有 $4$ 个，无欧拉通路。一般地，$K_n$ 有欧拉回路 $\iff n$ 为奇数（此时每点度 $n-1$ 为偶）。

判哈密顿算例

例：圈 $C_5$（$5$ 个顶点的环）显然有哈密顿回路——它本身就是。但用 Dirac 定理验证却「测不出来」：每点度为 $2<5/2$，不满足充分条件。这印证了 Dirac/Ore 是 充分非必要——条件不满足，不代表没有哈密顿回路，得另行判断。

例：含 悬挂点（度为 $1$）的连通图一定 没有哈密顿回路，因为回路要求每点恰好进出各一次、度至少为 $2$。这是排除哈密顿回路最快的一招。

哈密顿图的充分条件

虽无充要条件，但有好用的 充分条件。设简单图 $G$ 有 $n\ge 3$ 个顶点：

• Ore 定理：若对任意 不相邻 顶点 $u,v$ 都有 $d(u)+d(v)\ge n$，则 $G$ 是哈密顿图。
• Dirac 定理（Ore 的推论）：若每个顶点 $d(v)\ge n/2$，则 $G$ 是哈密顿图。

直觉是「边足够多、足够稠密」就一定能串起一条遍历所有点的回路。注意这是充分非必要——圈 $C_n$ 是哈密顿图却不满足条件。

平面图与欧拉公式

平面图（Planar Graph）是能画在平面上、边互不交叉 的图。电路板布线、地图绘制都关心平面性。

平面图把平面分成若干 面（Face，含无界的外部面）。欧拉公式：连通平面图满足

$$V-E+F=2$$

其中 $V,E,F$ 分别是顶点数、边数、面数。这是一条极强的约束，由它能推出简单连通平面图（$V\ge 3$）必有 $E\le 3V-6$。据此可证 $K_5$（完全图）和 $K_{3,3}$（三对三完全二部图）都不是 平面图——它们边太多塞不下。

库拉托夫斯基定理 进一步给出充要刻画：一个图是平面图当且仅当它不含 $K_5$ 或 $K_{3,3}$ 的「细分」。

例：用欧拉公式求面数。一个连通平面图有 $V=6$ 个顶点、$E=9$ 条边，问它把平面分成几个面？由 $V-E+F=2$ 得 $F=2-V+E=2-6+9=5$（含外部面）。

例：用 $E\le 3V-6$ 证 $K_5$ 非平面。$K_5$ 有 $V=5$、$E=\binom{5}{2}=10$，而 $3V-6=9<10$，边数超标，故 不可能画成平面图。对 $K_{3,3}$ 则要用更强的 $E\le 2V-4$（二部图无三元环，每个面至少 $4$ 条边界）：$V=6,E=9$，$2V-4=8<9$，同样非平面。这两条不等式都是欧拉公式的直接推论。

对偶图

给定平面图，把 每个面 变成一个顶点，相邻的面之间 连一条边（对应它们共享的原边），得到 对偶图（Dual Graph）。对偶把「面」和「点」的角色互换，在地图着色、电路分析里很有用。

图的着色

顶点着色

用 $k$ 种颜色给顶点染色，要求 相邻顶点颜色不同。所需的 最少 颜色数称 色数（Chromatic Number）$\chi(G)$。

着色抽象的是「冲突分组」——把互相冲突的东西分到不同组里，最少分几组。考试排考场（同一学生的科目不能撞）、寄存器分配（同时活跃的变量不能共用寄存器）都是着色。

• 二部图：$\chi=2$（充要：无奇圈）。
• 完全图 $K_n$：$\chi=n$（人人相邻，只能各染一色）。
• 圈 $C_n$：偶圈 $\chi=2$，奇圈 $\chi=3$。

例：求 $C_5$（五元奇圈）的色数。先证 $\chi\ge3$：若只用两色，沿环交替染 $1,2,1,2,\dots$，绕一圈回到起点时第 $5$ 个顶点是 $1$，却与起点（也是 $1$）相邻，冲突，故 $2$ 色不够。再给出一种 $3$ 色方案 $1,2,1,2,3$ 确实合法，所以 $\chi(C_5)=3$。

例：求轮图 $W_5$（$C_5$ 外加一个连所有顶点的中心）的色数。外圈是奇圈需 $3$ 色，中心与外圈每点都相邻、不能用外圈用过的任何色，得再加 $1$ 色，故 $\chi(W_5)=4$。一般地，$W_n$ 当外圈为奇圈时 $\chi=4$、偶圈时 $\chi=3$。求色数的通法是「下界靠找团 / 奇圈，上界靠给出构造」，两边夹出确切值。

四色定理

四色定理（Four Color Theorem）：任何 平面图 的色数 $\le 4$，即任何地图用四种颜色就能让相邻区域不同色。它于 $1976$ 年首次借助计算机穷举验证完成，是历史上第一个主要依赖计算机的著名证明，至今没有纯手工的简短证明。

边也可着色：边着色 要求共端点的边不同色，最少颜色数称 边色数，对应任务调度里「同一时刻同一资源不能两用」的约束。