图论进阶

9 minAdvanced2026/6/14

平面图与Euler公式、图的着色、匹配与覆盖、网络流、最短路径算法、最小生成树、拓扑排序。

1. 平面图与 Euler 公式

1.1 平面图

平面图：可以在平面上画出且边不相交的图。

面：平面图将平面划分的区域。

外部面（无限面）：无界的区域
内部面：有界的区域

1.2 Euler 公式

设连通平面图 $G$ 有 $n$ 个顶点、 $m$ 条边、 $f$ 个面，则

$n - m + f = 2$

证明（对边数归纳）：

$m = 0$ ： $n = 1$ ， $f = 1$ ， $1 - 0 + 1 = 2$

设 $m < k$ 时成立。 $m = k$ 时：

若 $G$ 无圈（树）： $m = n-1$ ， $f = 1$ ， $n-(n-1)+1 = 2$

若 $G$ 有圈：删除圈上一边 $e$ ， $G' = G - e$ 连通， $n' = n$ ， $m' = m-1$ ， $f' = f-1$ 。由归纳假设 $n - (m-1) + (f-1) = 2$ ，即 $n - m + f = 2$

1.3 推论

推论1：简单连通平面图（ $n \geq 3$ ）满足 $m \leq 3n - 6$ 。

每个面至少由3条边围成， $2m \geq 3f$ ， $f \leq \frac{2m}{3}$ 。代入 Euler 公式： $n - m + \frac{2m}{3} \geq 2$ ， $m \leq 3n - 6$ 。

推论2： $K_5$ 不是平面图。

$K_5$ ： $n = 5$ ， $m = 10$ ， $3n - 6 = 9 < 10$ ，矛盾。

推论3： $K_{3,3}$ 不是平面图。

$K_{3,3}$ 无三角形，每个面至少4条边， $2m \geq 4f$ ， $f \leq m/2$ 。 $n - m + m/2 \geq 2$ ， $m \leq 2n - 4 = 8 < 9$ ，矛盾。

1.4 Kuratowski 定理

定理：图 $G$ 是平面图 $\iff$ $G$ 不含与 $K_5$ 或 $K_{3,3}$ 同胚的子图。

同胚：两个图通过在边上插入或删除2度顶点后同构。

1.5 对偶图

平面图 $G$ 的对偶图 $G^*$ ：

$G$ 的每个面对应 $G^*$ 的一个顶点
$G$ 的每条边对应 $G^*$ 的一条边（连接相邻面对应的顶点）

2. 图的着色

2.1 顶点着色

正常着色：相邻顶点颜色不同。

色数 $\chi(G)$ ：正常着色所需的最少颜色数。

2.2 色数的界

上界：

$\chi(G) \leq \Delta(G) + 1$ （ $\Delta$ 为最大度）
Brooks 定理：若 $G$ 不是完全图也不是奇圈，则 $\chi(G) \leq \Delta(G)$

下界：

$\chi(G) \geq \omega(G)$ （ $\omega$ 为最大团的大小）

2.3 特殊图的色数

图	色数
二部图	2
偶圈 $C_{2k}$	2
奇圈 $C_{2k+1}$	3
$K_n$	$n$
树	2（非平凡）

2.4 四色定理

定理：任何平面图的色数不超过4，即 $\chi(G) \leq 4$ （ $G$ 为平面图）。

2.5 色多项式

$P(G, k)$ ：用 $k$ 种颜色正常着色的方案数。

性质：

$P(K_n, k) = k(k-1)(k-2)\cdots(k-n+1)$
$P(T, k) = k(k-1)^{n-1}$ （ $T$ 为 $n$ 阶树）
缩减公式： $P(G, k) = P(G-e, k) - P(G \cdot e, k)$

其中 $G \cdot e$ 为收缩边 $e$ 后的图。

3. 匹配与覆盖

3.1 基本概念

匹配 $M$ ：边集，其中任意两条边不共享端点
最大匹配：边数最多的匹配
完美匹配：覆盖所有顶点的匹配
顶点覆盖 $C$ ：顶点集，每条边至少有一个端点在 $C$ 中
独立集 $I$ ：顶点集，其中任意两个顶点不相邻

3.2 König 定理

在二部图中，最大匹配的边数 = 最小顶点覆盖的顶点数。

3.3 增广路径

增广路径：交替使用匹配边和非匹配边，且两端都是未匹配顶点的路径。

Berge 定理：匹配 $M$ 是最大匹配 $\iff$ 不存在关于 $M$ 的增广路径。

3.4 匈牙利算法

求二部图最大匹配：

初始匹配为空
对每个未匹配顶点，寻找增广路径
若找到，翻转路径上的匹配/非匹配边
重复直到无增广路径

4. 网络流

4.1 流网络

流网络 $N = (G, s, t, c)$ ：

$G = (V, E)$ 为有向图
$s$ 为源点， $t$ 为汇点
$c: E \to \mathbb{R}^+$ 为容量函数

流 $f: E \to \mathbb{R}^+$ 满足：

容量约束： $0 \leq f(e) \leq c(e)$
流量守恒： $\sum_{e \in \delta^+(v)} f(e) = \sum_{e \in \delta^-(v)} f(e)$ （ $v \neq s, t$ ）

流的值： $|f| = \sum_{e \in \delta^+(s)} f(e) - \sum_{e \in \delta^-(s)} f(e)$

4.2 最大流最小割定理

割 $(S, T)$ ： $s \in S$ ， $t \in T$ ， $S \cup T = V$ ， $S \cap T = \emptyset$ 。

割的容量： $c(S, T) = \sum_{u \in S, v \in T} c(u,v)$

定理：最大流的值 = 最小割的容量。

4.3 Ford-Fulkerson 算法

初始流为0
在残量网络中找 $s$ 到 $t$ 的增广路径
沿增广路径增加流量
重复直到无增广路径

残量网络： $c_f(u,v) = c(u,v) - f(u,v) + f(v,u)$

Edmonds-Karp 算法：用 BFS 找最短增广路径，时间复杂度 $O(VE^2)$ 。

5. 最短路径算法

5.1 Dijkstra 算法

求单源最短路径（非负权图）。

dist[s] = 0, dist[v] = ∞ (v ≠ s)
S = ∅
while S ≠ V:
    u = V\S 中 dist 最小的顶点
    S = S ∪ {u}
    for each (u, v) ∈ E:
        dist[v] = min(dist[v], dist[u] + w(u,v))

时间复杂度： $O(V^2)$ 或 $O((V+E)\log V)$ （优先队列）

5.2 Bellman-Ford 算法

允许负权边，可检测负圈。

dist[s] = 0, dist[v] = ∞ (v ≠ s)
for i = 1 to |V| - 1:
    for each (u, v) ∈ E:
        dist[v] = min(dist[v], dist[u] + w(u,v))
// 检测负圈
for each (u, v) ∈ E:
    if dist[v] > dist[u] + w(u,v):
        存在负圈

时间复杂度： $O(VE)$

5.3 Floyd-Warshall 算法

求所有顶点对之间的最短路径。

d[i][j] = w(i,j) if (i,j) ∈ E, else ∞
for k = 1 to |V|:
    for i = 1 to |V|:
        for j = 1 to |V|:
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

时间复杂度： $O(V^3)$