图论进阶

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^{\prime }=G-e$ 连通，$n^{\prime }=n$，$m^{\prime }=m-1$，$f^{\prime }=f-1$。由归纳假设 $n-(m-1)+(f-1)=2$，即 $n-m+f=2$

1.3 推论

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

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

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

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

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

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

1.4 Kuratowski 定理

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

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

1.5 对偶图

平面图 $G$ 的对偶图 $G^{\ast }$：

• $G$ 的每个面对应 $G^{\ast }$ 的一个顶点
• $G$ 的每条边对应 $G^{\ast }$ 的一条边（连接相邻面对应的顶点）

2. 图的着色

2.1 顶点着色

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

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

2.2 色数的界

上界：

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

下界：

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

2.3 特殊图的色数

2.4 四色定理

定理：任何平面图的色数不超过4，即 $\chi (G)\le 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$ 是最大匹配 $⟺$ 不存在关于 $M$ 的增广路径。

3.4 匈牙利算法

求二部图最大匹配：

1. 初始匹配为空
2. 对每个未匹配顶点，寻找增广路径
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}}^{+}$ 满足：

1. 容量约束：$0\le f(e)\le c(e)$
2. 流量守恒：${\sum }_{e\in {\delta }^{+}(v)}f(e)={\sum }_{e\in {\delta }^{-}(v)}f(e)$（$v\ne 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=\varnothing$。

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

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

4.3 Ford-Fulkerson 算法

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

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

Edmonds-Karp 算法：用 BFS 找最短增广路径，时间复杂度 $O(V{E}^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)$

6. 拓扑排序

6.1 适用条件

有向无环图（DAG）。

6.2 定义

拓扑排序是将 DAG 的顶点排成线性序列，使得对每条有向边 $(u,v)$，$u$ 在序列中位于 $v$ 之前。

6.3 算法

Kahn 算法：

1. 计算所有顶点的入度
2. 将入度为0的顶点入队
3. 出队一个顶点，将其所有后继的入度减1
4. 若后继入度变为0，入队
5. 重复直到队列为空

时间复杂度：$O(V+E)$

DFS 方法：按完成时间的逆序排列。

例：课程先修关系可用 DAG 表示，拓扑排序给出一种合法的选课顺序。

7. 关键路径

7.1 AOE 网

AOE 网（Activity On Edge）：用边表示活动，顶点表示事件。

• 源点：入度为0的顶点（工程开始）
• 汇点：出度为0的顶点（工程结束）

7.2 关键路径

最早发生时间：$ve(v_j)=\max \{ve(v_i)+w(v_i,v_j)\}$

最迟发生时间：$vl(v_j)=\min \{vl(v_k)-w(v_j,v_k)\}$

关键活动：$e(i)=l(i)$ 的活动（最早开始时间 = 最迟开始时间）

关键路径：由关键活动组成的路径，决定了工程的最短完成时间。