图论：连接世界的数学语言

图论是研究图的数学分支，图由顶点（节点）和连接它们的边（连线）组成。这门学科起源于1736年欧拉解决柯尼斯堡七桥问题，如今已成为计算机科学、网络分析、生物信息学等领域的核心工具。

一、图的基本概念

1.1 图的定义与类型

定义：一个图 $G=(V,E)$ 由：

• 顶点集 $V$（非空有限集）
• 边集 $E$（$V$ 中元素的无序对或多重集）

基本类型：

1. 无向图：边没有方向，$(u,v)$ 和 $(v,u)$ 表示同一条边
2. 有向图：边有方向，$(u,v)$ 表示从 $u$ 到 $v$ 的弧
3. 简单图：无自环（顶点到自身的边）且无平行边
4. 多重图：允许平行边
5. 加权图：边带有权重（距离、成本等）

1.2 基本术语

度数：

• 无向图：顶点 $v$ 的度数 $deg(v)$ 是与 $v$ 关联的边数
• 有向图：出度 $de{g}^{+}(v)$（从 $v$ 出发的边数），入度 $de{g}^{-}(v)$（进入 $v$ 的边数）

握手定理（图论第一定理）：
对任意无向图 $G=(V,E)$，
$$\sum _{v\in V}deg(v)=2|E|$$
证明：每条边贡献2度（两个端点各1度）。

推论：任何图中奇度顶点的个数为偶数。

路径与回路：

• 路径：顶点序列 $v_0,v_1,\dots ,v_k$，其中 $(v_{i-1},v_i)\in E$
• 简单路径：顶点不重复（边自然也不重复）
• 回路：起点=终点的路径
• 简单回路：起点外顶点不重复的回路

连通性：

• 连通图：任意两顶点间存在路径
• 连通分量：极大连通子图
• 强连通（有向图）：任意两顶点双向可达

---

二、图的表示与基本算法

2.1 图的表示方法

1. 邻接矩阵：$n\times n$ 矩阵 $A$，$A_{ij}=1$ 如果 $(v_i,v_j)\in E$（有权图则为权重）

   • 空间：$O(n^2)$
   • 查边：$O(1)$
   • 适合稠密图

2. 邻接表：每个顶点维护一个邻居列表

   • 空间：$O(n+m)$
   • 查边：$O(deg(v))$
   • 适合稀疏图

3. 关联矩阵：$n\times m$ 矩阵，$B_{ve}=1$ 如果边 $e$ 关联顶点 $v$

   • 主要用于理论分析

2.2 图的遍历

深度优先搜索（DFS）

DFS(v):
    标记 v 为已访问
    for 每个邻居 u of v:
        if u 未访问:
            DFS(u)

性质：

• 时间复杂度：邻接表 $O(n+m)$，邻接矩阵 $O(n^2)$
• 形成DFS树/森林
• 可检测回路、求连通分量

广度优先搜索（BFS）

BFS(s):
    队列 Q ← {s}
    标记 s 为已访问
    while Q 非空:
        v ← Q.dequeue()
        for 每个邻居 u of v:
            if u 未访问:
                标记 u 为已访问
                Q.enqueue(u)

性质：

• 时间复杂度和DFS相同
• 求无权图最短路径
• 按层次遍历

---

三、树与生成树

3.1 树的基本性质

定义：树是连通无环图。

等价定义（对 $n$ 个顶点的图）：

1. 连通且 $m=n-1$
2. 无环且 $m=n-1$
3. 任意两顶点间有唯一路径
4. 连通但删除任意边后不连通
5. 无环但添加任意边后产生环

证明思路（归纳法）：
基础：$n=1$，$m=0$，成立
归纳：对 $n>1$ 的树，必有一度顶点（叶子），删除它得 $n-1$ 顶点的树，由归纳假设有 $n-2$ 条边，故原树有 $(n-2)+1=n-1$ 条边。

3.2 生成树

定义：图 $G$ 的生成树是包含 $G$ 所有顶点的树（$G$ 的子图）。

存在性：$G$ 有生成树 ⇔ $G$ 连通

最小生成树（MST）问题

给定连通加权无向图，找权重和最小的生成树。

Kruskal算法（贪心，按边权重排序）：

Kruskal(G):
    将边按权重升序排序
    T ← ∅
    for 每条边 e (按序):
        if T ∪ {e} 无环:
            T ← T ∪ {e}
        if |T| = n-1: break

使用并查集高效检测环，时间复杂度 $O(m\log m)$

Prim算法（贪心，从顶点扩张）：

Prim(G, s):
    T ← {s}
    while |T| < n:
        选连接 T 与 V\T 的最小权重边 e
        T ← T ∪ {e 的另一个端点}

使用优先队列，时间复杂度 $O(m\log n)$

正确性证明（切割性质）：
对图的任意切割（划分顶点为两个集合），最小横跨边一定在某个MST中。
反证：若某MST不含最小横跨边 $e$，添加 $e$ 会产生环，环中必有另一横跨边 $f$（权重≥$e$），用 $e$ 替换 $f$ 得权重更小的生成树，矛盾。

---

四、最短路径问题

4.1 单源最短路径（SSSP）

Dijkstra算法（非负权重）

Dijkstra(G, s):
    dist[s] ← 0, 其他 dist[v] ← ∞
    Q ← 所有顶点（按dist）
    while Q 非空:
        u ← Q中dist最小的顶点
        Q.remove(u)
        for 每个邻居 v of u:
            alt ← dist[u] + w(u,v)
            if alt < dist[v]:
                dist[v] ← alt
                prev[v] ← u
                Q.decrease_key(v, alt)

时间复杂度：

• 数组：$O(n^2)$
• 二叉堆：$O((n+m)\log n)$
• 斐波那契堆：$O(m+n\log n)$

正确性证明（归纳法）：
归纳假设：每次从Q取出的顶点 $u$，其dist值已是最短距离。
基础：$u=s$，dist=0正确
归纳：设下个取出的是 $u$，假设存在更短路径 $s\to \cdots \to x\to y\to u$，其中 $x$ 在已处理集，$y$ 在Q中。
由三角不等式和贪心选择矛盾。

Bellman-Ford算法（允许负权重，检测负环）

Bellman-Ford(G, s):
    dist[s] ← 0, 其他 dist[v] ← ∞
    for i = 1 to n-1:
        for 每条边 (u,v):
            if dist[u] + w(u,v) < dist[v]:
                dist[v] ← dist[u] + w(u,v)
                prev[v] ← u
    # 检测负环
    for 每条边 (u,v):
        if dist[u] + w(u,v) < dist[v]:
            存在负环

时间复杂度：$O(nm)$
原理：松弛操作进行 $n-1$ 轮（最长无环路径最多 $n-1$ 条边）

4.2 所有顶点对最短路径

Floyd-Warshall算法（动态规划）

定义 $d_{ij}^{(k)}$ = $i$ 到 $j$ 只经过 { 1 , … , k } \{1,\ldots,k\} {1,…,k} 的最短路径长度
递推：$d_{ij}^{(k)}=\min (d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)})$

Floyd-Warshall(G):
    初始化 d[i][j] = w(i,j) 或 ∞
    for k = 1 to n:
        for i = 1 to n:
            for j = 1 to n:
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

时间复杂度：$O(n^3)$
空间优化：可原地更新
应用：求传递闭包、检测负环（对角线出现负值）

---

五、匹配与网络流

5.1 二分图匹配

二分图：顶点可划分为 $X,Y$，所有边连接 $X$ 和 $Y$ 中的顶点。

匹配：边集 $M\subseteq E$，其中任意两边不共享顶点。

• 最大匹配：含边数最多的匹配
• 完美匹配：覆盖所有顶点的匹配（$|M|=n/2$）

增广路径定理（Berge定理）

$M$ 是最大匹配 ⇔ 不存在 $M$-增广路径

证明思路：

• ⇒：若存在增广路径，可翻转匹配/非匹配边，得到更大匹配
• ⇐：若 $M$ 不是最大，设 $M^{\prime }$ 是最大匹配，考虑对称差 $M\oplus M^{\prime }$，由度数和连通性分析必存在增广路径

匈牙利算法（求二分图最大匹配）

Hungarian(G):
    M ← ∅
    while 存在增广路径:
        找增广路径 P
        M ← M ⊕ P
    return M

时间复杂度：$O(nm)$
应用：任务分配、婚姻问题

Hall婚姻定理

二分图 $G=(X\cup Y,E)$ 有匹配覆盖 $X$ ⇔ 对任意 $S\subseteq X$，$|N(S)|\ge |S|$
其中 $N(S)$ 是 $S$ 的邻居集。

证明：

• 必要性：若匹配覆盖 $X$，$S$ 中顶点匹配不同的 $Y$ 中顶点
• 充分性：对 $|X|$ 归纳，分 $N(S)=|S|$ 和 $N(S)>|S|$ 两种情况处理

5.2 网络流

最大流问题

给定有向图 $G=(V,E)$，源点 $s$，汇点 $t$，边容量 $c(u,v)$，求从 $s$ 到 $t$ 的最大流量。

流函数 $f:V\times V\to R$ 满足：

1. 容量限制：$0\le f(u,v)\le c(u,v)$
2. 流量守恒：${\sum }_{v}f(u,v)={\sum }_{v}f(v,u)$（$u\ne s,t$）

剩余网络 $G_f$：边 $(u,v)$ 容量为 $c(u,v)-f(u,v)$，添加反向边 $(v,u)$ 容量为 $f(u,v)$

Ford-Fulkerson方法

Ford-Fulkerson(G, s, t):
    f ← 零流
    while G_f 中存在 s-t 路径:
        找增广路径 P
        augment ← P上最小剩余容量
        沿P推送augment单位流量
    return f

Edmonds-Karp算法（BFS找最短增广路）

时间复杂度：$O(n{m}^2)$
实际更快：$O(nm)$ 次增广，每轮BFS $O(m)$

最大流最小割定理

最大流值 = 最小割容量

证明：

1. 任何流 ≤ 任何割容量（显然）
2. 当FF算法终止时，剩余网络无s-t路径
   设 $S$ = $s$ 在 $G_f$ 中可达的顶点集
   则 $(S,V\backslash S)$ 是割，且割边流量=容量，反向边流量=0
   故当前流值 = 割容量，达到最大

应用：二分图最大匹配可转化为最大流（添加源汇，容量设为1）

---

六、图的着色

6.1 顶点着色

正常着色：相邻顶点颜色不同
色数 $\chi (G)$：最小所需颜色数

性质：

• $\chi (G)\ge \omega (G)$（团数）
• $\chi (G)\le \Delta (G)+1$（最大度+1）
• 对任意图，$\chi (G)\le \Delta (G)$（Brooks定理，除完全图和奇环）

五色定理（Heawood，1890）

任何平面图可用5种颜色着色。

证明思路（归纳法）：

1. 平面图有顶点 $v$，$deg(v)\le 5$（欧拉公式推论）
2. 删除 $v$，5-着色剩余图（归纳假设）
3. 若邻居用了≤4色，$v$ 用第5色
4. 若5个邻居用5色，找颜色交替路径调整

四色定理（Appel & Haken，1976）

任何平面图可用4种颜色着色。

证明概要（计算机辅助）：

1. 寻找不可避免集：任何平面图必含某构型（约1500种）
2. 证明可约性：这些构型可缩小而不增加色数
3. 用计算机检查所有情况

6.2 边着色

正常边着色：相邻边颜色不同
边色数 ${\chi }^{\prime }(G)$：最小所需颜色数

Vizing定理：
对简单图，$\Delta (G)\le {\chi }^{\prime }(G)\le \Delta (G)+1$

二分图的König定理：
对二分图，${\chi }^{\prime }(G)=\Delta (G)$

应用：课程安排、任务调度

---

七、平面图

7.1 平面图基本定理

定义：可在平面上绘制且边仅在顶点相交的图。

欧拉公式（连通平面图）：
$$n-m+f=2$$
其中 $f$ 是面数（包括外无限面）。

证明（归纳法）：
基础：树，$m=n-1$，$f=1$，满足
归纳：添加边将面一分为二，$m+1$，$f+1$，$n-m+f$ 不变

推论：

1. $m\le 3n-6$（$n\ge 3$，简单无环图）
2. $m\le 2n-4$（无三角形，$n\ge 3$）
3. 存在顶点 $v$，$deg(v)\le 5$

7.2 Kuratowski定理

定理：图是非平面图 ⇔ 它包含 $K_5$ 或 $K_{3,3}$ 的细分。

细分：在边上添加顶点。

应用：判定平面性的理论基础（实际用线性时间算法如PQ树）

---

八、特殊图类与算法

8.1 欧拉图与哈密顿图

欧拉图（一笔画问题）

欧拉回路：经过每条边恰好一次的回路
欧拉路径：经过每条边恰好一次的路径

欧拉定理（无向图）：

• 连通图有欧拉回路 ⇔ 所有顶点度数为偶数
• 连通图有欧拉路径 ⇔ 恰有0或2个奇度顶点

证明思路：

• 必要性：进入次数=离开次数
• 充分性：归纳法，拼接回路

Fleury算法（避免桥）和Hierholzer算法（$O(m)$）

哈密顿图

哈密顿回路：经过每个顶点恰好一次的回路
哈密顿路径：经过每个顶点恰好一次的路径

判定是NP完全问题，但有一些充分条件：

• Dirac定理：$n\ge 3$，$\delta (G)\ge n/2$ ⇒ 有哈密顿回路
• Ore定理：任意不相邻顶点 $u,v$，$deg(u)+deg(v)\ge n$ ⇒ 有哈密顿回路

8.2 有向无环图（DAG）

拓扑排序：将顶点线性排列，使所有边从前指向后。

算法（Kahn算法）：

TopologicalSort(G):
    L ← 空列表
    S ← 所有入度为0的顶点
    while S 非空:
        v ← S.pop()
        L.append(v)
        for 每个邻居 u of v:
            删除边 (v,u)
            if u入度变为0:
                S.push(u)
    if 还有边剩下: 有环
    return L

时间复杂度：$O(n+m)$

应用：任务调度、依赖解析

---

九、图的连通性

9.1 顶点连通度

点割集：删除后使图不连通的顶点集
连通度 $\kappa (G)$：最小点割集大小（完全图 $\kappa (K_n)=n-1$）

Menger定理（点形式）：
$\kappa (G)\ge k$ ⇔ 任意两顶点间有 $k$ 条内部不相交的路径

9.2 边连通度

边割集：删除后使图不连通的边集
边连通度 $\lambda (G)$：最小边割集大小

Menger定理（边形式）：
$\lambda (G)\ge k$ ⇔ 任意两顶点间有 $k$ 条边不相交的路径

不等式：$\kappa (G)\le \lambda (G)\le \delta (G)$

9.3 强连通分量（有向图）

Kosaraju算法：

1. DFS遍历，记录完成时间
2. 反转所有边
3. 按完成时间降序DFS

Tarjan算法（单次DFS，$O(n+m)$）：

Tarjan(v):
    index[v] = low[v] = ++time
    stack.push(v)
    onStack[v] = true
    
    for 每个邻居 u of v:
        if index[u] 未定义:
            Tarjan(u)
            low[v] = min(low[v], low[u])
        else if onStack[u]:
            low[v] = min(low[v], index[u])
    
    if low[v] == index[v]:
        创建新SCC
        repeat:
            u = stack.pop()
            onStack[u] = false
            将u加入当前SCC
        until u == v

---

十、现代应用与前沿

10.1 社交网络分析

• 中心性度量：

  • 度中心性：$C_D(v)=deg(v)/(n-1)$
  • 接近中心性：$C_C(v)=(n-1)/{\sum }_{u}d(u,v)$
  • 介数中心性：$C_B(v)={\sum }_{s\ne v\ne t}{\sigma }_{st}(v)/{\sigma }_{st}$
    ${\sigma }_{st}$：$s$ 到 $t$ 的最短路径数
    ${\sigma }_{st}(v)$：经过 $v$ 的最短路径数

• 社区检测：模块度最大化、谱聚类

• 小世界现象：六度分隔、高聚类系数、短平均路径

10.2 网络科学

• 无标度网络（幂律度分布）：BA模型（优先连接）
• 随机图：Erdős–Rényi 模型 $G(n,p)$
  • 阈值现象：$p=\ln n/n$ 时从几乎不连通到几乎连通
• 渗流理论：边的随机删除对连通性的影响

10.3 算法设计与复杂性

P与NP问题：

• 哈密顿回路、旅行商问题（TSP）、图着色是NP完全问题
• 最大匹配、最大流、最短路径是P问题

近似算法：

• 顶点覆盖：2-近似（取最大匹配的端点）
• TSP：Christofides算法（1.5-近似，若满足三角不等式）

参数复杂性：固定参数可解（FPT）问题，如顶点覆盖参数化为解大小

10.4 图神经网络（GNN）

基本思想：将深度学习扩展到图结构数据

• 消息传递：顶点聚合邻居信息
• 图卷积网络（GCN）：谱域方法
• 应用：分子性质预测、推荐系统、知识图谱

---

结语：图论的统一视角

图论提供了一种统一的语言来描述离散结构中的关系。从欧拉的七桥问题到现代的万维网分析，图论始终在连接着数学的各个分支和现实世界的复杂系统。

图论的独特魅力在于：

1. 直观与抽象的平衡：图形表示直观易懂，但背后是严谨的数学理论
2. 理论与应用的紧密联系：最纯粹的数学问题（如四色定理）催生了实际的算法和技术
3. 跨学科的影响力：从物理学（Ising模型）到社会学（社交网络），从计算机科学（算法设计）到生物学（蛋白质相互作用网络）

“图论的美在于它能够用简单的点和线，捕捉到世界复杂关系的本质。” —— Paul Erdős

随着大数据和复杂网络时代的到来，图论的重要性只增不减。它不仅帮助我们理解现有的网络结构，更为我们设计更高效、更鲁棒的未来系统提供了数学基础。从社交媒体的朋友推荐到物流网络的路径优化，从大脑神经元的连接到全球互联网的拓扑，图论都在默默地描绘着连接世界的数学蓝图。