跳转到内容
← 返回概念
离散数学约 18 分钟阅读

图论

Graph Theory

关键人物

eulererdosdijkstraramsey
离散数学图论网络组合优化算法

一个直觉：从"七座桥能不能一次走遍"说起

十八世纪的柯尼斯堡城里有一条河、两座小岛和七座桥，市民们闲来争论一个问题：能不能从家出发，每座桥不重不漏地恰好走一遍，最后回到原地？无数人试着画路线，没人成功，但也没人能说清为什么不行。1736 年，欧拉指出：这道题里，岛有多大、桥有多长、城市什么形状，统统无关紧要——真正决定答案的，只是"哪块陆地和哪块陆地之间有桥相连"。

于是他把每块陆地缩成一个点，把每座桥画成一条连接两点的线，整座城市瞬间塌缩成一张极简的网。想一笔不重复地走完再回到起点，每个点连出的线数（它的"度"）都必须是偶数：每次进来一条、出去一条才配得平。柯尼斯堡的四块陆地度数全是奇数——一块连着五座桥，另外三块各连三座——所以这样的回路根本不存在。

同年他把论证写成《与位置几何有关的一个问题的解》（Solutio problematis ad geometriam situs pertinentis），这篇论文 1741 年才印在圣彼得堡科学院院刊上，习惯上仍以 1736 年为纪年。欧拉当时把它归入莱布尼茨所说的"位置几何"，并没有宣布一门新学科在一个下午诞生；图论这个名字、顶点与边的整套语言，是十九世纪以后才慢慢长成的。

这就是图论的灵魂：剥掉一切无关的细节，只留下"谁和谁有关系"这件事。一旦把对象画成点、把关系画成边，社交网络、互联网、分子结构、交通路网、任务依赖……这些天差地别的东西，就都成了同一种数学对象。图论研究的，正是这种最朴素也最普适的结构里，藏着哪些深刻的规律。

定义

图论（Graph Theory）研究图的结构与性质。所谓图，就是把对象写成顶点、把关系写成边的离散结构 $G = (V, E)$：顶点集 $V$ 装的是"谁"，边集 $E$ 装的是"谁和谁有关系"。它不关心对象在空间里的位置或形状，只关心连接本身——这也是七桥问题能从一张城市地图塌缩成四个点的原因。

边可以没有方向，也可以有方向。无向图里 $(u,v)$ 与 $(v,u)$ 是同一条边，适合友谊、化学键、双向道路；有向图（Digraph）里箭头有意义，适合网页链接、食物网、任务依赖。还可以给每条边贴一个数值，得到加权图，用来写距离、容量或代价。若既无自环也无重边，就叫简单图；柯尼斯堡那张图有重边，已经不是简单图，但下面的握手定理对它照样成立。

顶点 $v$ 的度 deg⁡(v)\deg(v) 是与它关联的边数。路径是一串顶点 v0,v1,…,vkv_0, v_1, \ldots, v_k，相邻两点都有边相连；任意两点之间都有路径的图叫连通图。树是无圈的连通图：要维持连通又不许出现圈，$n$ 个顶点的树恰好有 $n-1$ 条边——少一条就断开，多一条就冒出圈。

核心内容

图的基本性质

握手定理（也称握手引理）说：任意有限无向图里，所有顶点的度数加起来恰好等于边数的两倍，∑v∈Vdeg⁡(v)=2∣E∣\sum_{v \in V} \deg(v) = 2|E|。理由几乎是同义反复：每条边有两个端点，在度数求和时被数了两次。聚会上每握一次手，两个人的"握手次数"各加一，全场次数之和因此必是偶数。这条求和不需要图连通，也不需要图简单，自环和重边同样适用。

由此立刻得到一条用得上的推论：度数为奇数的顶点必有偶数个——奇数个奇数加起来是奇数，对不上左边的 $2|E|$。柯尼斯堡恰好有四个奇度顶点，不是零个，也不是两个。零个奇度顶点才可能有欧拉回路（从哪出发都能走完再回来）；恰好两个时只可能有欧拉路径（必须从其中一个奇度点出发、在另一个结束）。四个奇度点把两条路都堵死了。

欧拉 1736 年的论文里已经用到了这条度数求和：他证明了"能一笔画"的必要条件。充分性——奇度点为 0 或 2 时一定走得出来——他只是断言，完整构造直到 1873 年才由希尔霍尔策（Carl Hierholzer）发表。所以七桥问题给出的是判据，不是一门学科的全部定理清单。

平面图另有一条欧拉公式 $V - E + F = 2$，说的是连通平面图的顶点数减边数加面数恒等于二。它来自欧拉后来对多面体的计数，和七桥问题里的欧拉回路不是同一件事。把图画歪、拉长都不会改变这个数字，因为它是拓扑不变量，不是几何度量。

欧拉路径经过每条边恰好一次；哈密顿圈经过每个顶点恰好一次。前者有上面那条干净的度数判据，后者的存在性判定却是 NP 完全问题——边和点只差了一个字，计算难度可以差出一个复杂度类。最短路、最大流也属于"边"这一侧的好说话问题；旅行商则站在"点"这一侧，规模一大就只能退而求近似。

树与生成树

树可以用几条彼此等价的话来刻画。对 $n$ 个顶点的图来说，下面四条说的是同一件事：连通且无圈；连通且恰有 $n-1$ 条边；无圈且恰有 $n-1$ 条边；任意两点之间有唯一路径。少一条边会断开，多一条边会冒出圈，所以 $n-1$ 不是记口诀，而是连通性与无圈性卡死的那个整数。

给 $n$ 个顶点标上号，不同的树有多少棵？Cayley 公式说答案是 nn−2n^{n-2}。凯莱 1857 年先研究了树这种"无圈的连接"，这条计数公式要到后来才以他的名字流传；加权图上要找总重量最小的生成树，则有 Kruskal 算法和 Prim 算法，都能在多项式时间内做完。

图的着色

顶点着色要求相邻顶点着不同颜色，色数 χ(G)\chi(G) 是最少需要的颜色数。平面图的色数不超过 4，这就是四色定理——证明本身、计算机辅助枚举与"算出来的证明还算不算证明"，都写在那一篇里，这里不展开。边着色则要求相邻边不同色；Vizing 定理说，简单图的边色数只可能是最大度 Δ\Delta 或 Δ+1\Delta + 1，没有第三种可能。

网络流

最大流最小割定理说：从源到汇的最大流量，等于把网络"切断"所需的最小容量。写成式子，就是同一件事的正反两面。

max⁡flow=min⁡cut\max \text{flow} = \min \text{cut}

Ford–Fulkerson 算法靠反复寻找增广路径来逼近最大流；容量为整数时它保证停得下来。网络流理论在运输、匹配和调度里反复出现，因为它把"能过多少"和"最窄的瓶颈在哪"写成了同一个数。

匹配与覆盖

匹配是边的集合，其中任意两条边不共享顶点；能盖住全部顶点的匹配叫完美匹配。Hall 定理给了二部图一个干净的判据：左侧每个子集 $S$ 的邻居都至少有 $|S|$ 个，当且仅当存在完美匹配。它把"每个人都能找到舞伴"翻译成一条可检查的计数条件，而不是一句愿望。Hall 1935 年的原文写的是集合族的相异代表系，二部图匹配是它最常用的翻译。

历史演变

图论的习惯纪年，落在欧拉 1736 年对柯尼斯堡七桥问题的分析。他证明了一次走遍七座桥是不可能的，并把问题抽象成点和线；这篇论文本身讨论的是位置几何，后来的人把它读成图论的起点，而不是一张在一个下午写完的学科出生证明。

凯莱（Arthur Cayley）1857 年研究了树的计数，哈密顿（William Rowan Hamilton）1859 年提出了经过每个顶点恰好一次的回路问题。到 1936 年，柯尼希（Dénes König）写出第一本图论专著，这门学问才有了独立的教科书形态。顶点、边、度、路径这些今天的课堂语言，是这条长线上陆续沉淀下来的，并不是 1736 年一次齐备。

二十世纪图论长成一个庞大的学科。Ramsey 在 1930 年证明了 Ramsey 定理；Erdős 和 Rényi 1959 年开创了随机图理论；Dijkstra 同年给出最短路径算法。随机图让"典型的图长什么样"第一次有了概率语言，最短路算法则把图论送进了每一台计算机。四色定理的计算机辅助证明（Appel 与 Haken，1976）把"什么叫证明"这个问题重新推到台前，细节见四色定理本文。

关键人物

欧拉（Leonhard Euler，1707—1783）在 1736 年解决了柯尼斯堡七桥问题：四块陆地全是奇度，故无欧拉回路。他把具体的桥梁问题抽象为连接结构，并在同一篇论文里用到了度数求和这条后来被称为握手定理的观察。严格地说，他给出的是必要性判据；充分性要等到希尔霍尔策 1873 年的构造。图论并不是他一天下午发明出来的，但他把"只问连接、不问形状"这件事第一次写成了可检验的数学。

埃尔德什（Paul Erdős，1913—1996）在图论中贡献了极值图论、随机图理论和 Ramsey 理论。他与 Rényi 共同开创的随机图理论，后来成了网络科学的数学底座：边按概率出现时，连通性会在某个密度阈值上突然涌现。他提出的问题和悬赏往往比单篇证明传播得更广，Erdős 数至今仍是数学圈的学术趣谈。

迪杰斯特拉（Edsger Dijkstra，1930—2002）在 1959 年给出了最短路径的贪心算法。Dijkstra 算法至今仍是导航系统和网络路由的基础，前提是边权非负；有负权时要换 Bellman–Ford 一类允许松弛的方法。

数学意义

图论把"关系"变成可以计数、可以判定、可以优化的对象。握手定理 ∑deg⁡(v)=2∣E∣\sum \deg(v) = 2|E| 保证奇度点成双出现；平面图的欧拉公式 $V - E + F = 2$ 把顶、边、面锁在同一个整数上。

最大流等于最小割，是对偶性最干净的一条样本。Ramsey 定理 $R(3,3) = 6$ 则说完全无序不可能——六个人里必有三人两两相识或两两不相识。Tutte 定理把完美匹配写成对每个子集 $S$，$G-S$ 的奇分支数不超过 $|S|$，是 Hall 定理在一般图上的升级。

核心概念辨析

图、树、森林差在圈与连通。树是无圈连通图，森林是无圈图，也就是若干棵树的不交并；加上那条 $n$ 个顶点 $n-1$ 条边的计数，三者不会混。欧拉路径走边、哈密顿圈走点：前者有度数判据，后者没有多项式时间的充要条件。

顶点着色给点涂色使相邻不同色，边着色给边涂色使相邻边不同色，色数与边色数是两套量。最大流和最小割是同一问题的对偶形式，算出一个就等于算出了另一个。把其中任何一对画等号，课堂习题里最常见的错就出现了。

当代应用

图论是网络时代的数学语言。社交网络里，人是点、关系是边，社区发现和影响力传播都基于图算法；计算机网络里，OSPF、BGP 一类路由协议走的是最短路径和网络流。把网页写成有向图之后，PageRank 不过是在图上求特征向量，排序问题就变成了线性代数。具体算法与建模选择，见图论应用。

生物信息学把蛋白质相互作用和基因调控写成图；交通规划用最短路径和流量优化安排路网。推荐系统依赖二部图上的匹配，编译器用控制流图做可达性与寄存器分配，化学用分子图表述原子之间的化学键。同一套点与边，在不同学科里只是换了标签。

核心公式汇编

概念公式
握手定理$\sum\deg(v) = 2E$
Euler 公式$V - E + F = 2$（平面图）
Cayley 公式$n$ 个标号顶点的树有 nn−2n^{n-2} 棵
色多项式$P(G,k)$：用 $k$ 种颜色着色的方式数
最大流最小割max⁡flow=min⁡cut\max\text{flow} = \min\text{cut}
邻接矩阵特征值λ1≥λ2≥⋯\lambda_1 \geq \lambda_2 \geq \cdots，λ1\lambda_1 反映"中心性"
图的连通度κ(G)≤λ(G)≤δ(G)\kappa(G) \leq \lambda(G) \leq \delta(G)（Whitney 不等式）

经典问题

四色问题问的是任何平面地图是否只需四种颜色，1976 年给出计算机辅助证明；命题、争议与后续形式化见四色定理，此处不重复展开。Hamilton 问题问图中是否存在 Hamilton 圈，它是 NP 完全问题，与欧拉回路的多项式判据正好对照。

图同构问两个图是否只是顶点标签不同。它既没有被证明属于 P，也没有被证明是 NP 完全；Babai 2015 年给出了拟多项式时间算法，复杂度类上的归属仍未盖棺。Ramsey 数 $R(5,5)$ 的精确值至今未知，目前最好的夹逼是 43≤R(5,5)≤4643 \leq R(5,5) \leq 46（下界 Exoo 1989，上界 Angeltveit 与 McKay 2024）。Hadwiger 猜想说色数 χ(G)≥t\chi(G) \geq t 蕴含 $G$ 包含 KtK_t 的缩约，仍是图论最深的开放问题之一。

与其他概念的关系

图论是离散数学的核心，几乎每个相邻分支都从点与边里拿走一截。组合计数、谱、拓扑、优化、随机图和算法，走的都是同一张网。

  • → 组合数学：图的计数、着色、匹配都是组合问题
  • → 线性代数：图的邻接矩阵和拉普拉斯矩阵——谱图论用特征值研究图的性质
  • → 拓扑学：图是 1 维 CW 复形——图的拓扑性质（如连通性）有组合刻画
  • → 优化：最短路径、最大流、最小生成树——图上的优化问题
  • → 概率论：随机图理论——Erdős–Rényi 模型研究图的涌现性质
  • → 计算机科学：数据结构（树、堆、图）、算法（搜索、排序、最短路径）

跨域连接

  • 拓扑学：七桥问题的答案与桥多长、岛多大无关，只取决于连接方式——这正是拓扑学的思路：只保留连续形变下不变的东西。平面图的顶点数减边数加面数恒等于二，是一条拓扑不变量而非几何度量。推论是把图画歪、拉长都不会改变任何结论。
  • 化学键：分子被写成原子为点、共价键为边的图，于是同分异构现象有了精确说法——化学式相同而图不同构。这直接推出分子式无法唯一确定物质，必须补上连接方式；手性还要再补三维嵌入信息，因为图同构分不出互为镜像的两个分子。
  • 句法：依存分析把句子画成以谓语为根的树，每个词恰有一个支配者。"投射性"这条约束翻成图的语言就是弧不交叉，而真实语言中的长距离依存恰恰会破坏它。因此非投射结构所占的比例可以拿来量化不同语言的语序自由度。
  • 食物网：物种为点、捕食关系为有向边之后，"移除谁会引发连锁灭绝"变成一个连通性问题：删掉某点后有多少点失去全部入边。推论是关键种未必是数量最多的种，而是位于入度分布上游的少数节点。
  • 编译器：程序被编译成控制流图，基本块是点、跳转是边，循环识别与死代码删除都成了可达性与支配关系问题。寄存器分配更直接：把同时活跃的变量连边，分配寄存器就是给这张图着色，可用颜色数就是硬件寄存器数。

参考文献

  1. Leonhard Euler, "Solutio problematis ad geometriam situs pertinentis" (1736; Commentarii academiae scientiarum Petropolitanae, 1741).
  2. Carl Hierholzer, "Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren", Mathematische Annalen 6 (1873).
  3. Reinhard Diestel, Graph Theory (5th ed., 2017).
  4. Béla Bollobás, Modern Graph Theory (1998).
  5. 田丰, 马仲蕃, 《图与网络流理论》, 科学出版社, 2005.
  6. Fan Chung, Spectral Graph Theory (1997).
  7. Vigleik Angeltveit and Brendan D. McKay, "R(5,5)≤46R(5,5)\le 46", Journal of Graph Theory (2026).

图论用顶点与边为关系建模，把现实问题转化为可算的结构问题。最短路（Dijkstra）支撑导航，最大流刻画网络容量，PageRank 用图的特征向量给网页排序，社交网络与分子结构也都借图论分析。