目录
1. 图的形式化定义
几乎所有入门介绍都说图就是“用线连起来的点”。这个画面很有用，也正是许多人后来卡住的原因：点和线并不是那个数学对象。这个对象是一对集合。
Diestel 的 Graph Theory是研究生阶段的标准参考书，开篇就以最简洁的形式给出了定义：
图是一对集合 G = (V, E) ，满足 E ⊆ [V]2，其中 [V]2 表示 V 的所有二元子集构成的集合。
把它展开，本文其余的一切都由此而来：
- V 是一组对象，称为顶点。对它们不做任何假设。它们可以是城市、人、网页、化学原子或整数。这套理论从不查看它们的内部，只关心哪些是可以彼此区分的。
- E 是 V 的二元子集构成的集合。一条边字面上就是集合
{u, v}，既不是箭头也不是曲线。除了它连接的是哪一对顶点之外，它不记录任何信息。 - 由于 E 是一个集合，一条边要么存在，要么不存在，不能出现两次。
- 由于 E 的每个元素都恰好有两个互不相同的成员，一条边不可能把一个顶点连到它自己。
最后这两条推论并不是后来有人加上的限制，而是直接从集合论中推出的，满足它们的图称为简单图。允许重复边或自环意味着修改定义本身，这正是第 4 节的内容。
还有两个随处可见的标准记号。当涉及多个图时，写作 V(G) 和 E(G) ，以指明你说的是哪个图。两个衡量大小的量也各有名称：顶点的个数是图的阶，边的条数是它的规模。大多数算法教材把它们简写为 n = |V| 和 m = |E|，本站全文采用这一约定。
本文余下部分都以这个图为贯穿示例。它的顶点集是 V = {A, B, C, D, E, F}，因此阶为 n = 6，它的边集是
E = { {A,B}, {A,C}, {B,C}, {B,D}, {C,D}, {D,E}, {E,F} } 因此 m = 72. 顶点：它是什么，不是什么
顶点本身不携带任何结构。在形式化对象中，它只是集合中的一个匿名元素，关于它所能说的一切都来自与它相连的边。这一点值得强调，因为正是它让图论具有可迁移性：一个关于顶点的定理，同时也是关于机场、晶体管、蛋白质和 Git 提交的定理。
在实践中，有三条推论常让人绊倒：
- 顶点彼此可区分，但除此之外可以互换。两个只是顶点名称不同的图是同构的，图论把它们视为同一个图。当你在代码里给顶点贴标签时，你添加的是记录信息，而不是数学。
- 孤立顶点仍然是顶点。一个完全没有边的顶点完全合法，称为孤立顶点。初学者常常从边列表构建图，于是悄无声息地丢掉所有孤立顶点，这会改变图的阶，并让任何以
n为除数的计算悄悄出错。 - 空图是存在的，无限图同样存在。定义中没有任何地方禁止
V = ∅，也没有任何地方禁止V是无限的，后者正是有限图与无限图这篇指南的主题。大多数教材允许它，少数则直接排除；重要的是在你相信某个边界情形之前，先弄清你的资料采用哪种约定。
这段历史注记值得写一行，因为在一个多世纪的文献中，术语并不稳定。Harary 1969 年的经典教材称它们为点和线。物理学家和许多应用领域的论文说节点和连接。化学家沿用 Sylvester 1878 年发表在 Nature 上的那则短文，正是它最早赋予这门学科“图”这个词，他们说的是原子和化学键。这四套术语描述的是同一对集合。
3. 边、相邻与关联
一条边恰好连接两个顶点，这两个顶点就是它的端点或两端。初学者最常混淆的两个词，正是从这一条关系中获得各自的精确含义：
- 相邻是两个顶点之间的关系。顶点
u和v相邻，记作u ~ v，当且仅当{u, v} ∈ E。相邻的顶点也称为邻居，而v的所有邻居构成的集合是它的邻域，记作N(v)。 - 关联是一个顶点与一条边之间的关系。边
{u, v}与u关联，也与v关联，而不与任何其他顶点关联。
这个区分听起来像是咬文嚼字，直到你遇到“两条相邻的边”这样的说法。它是正确的，指的是共享一个端点的两条边。顶点通过边而相邻，边通过顶点而相邻。把这两种关系分清楚，才能毫无歧义地读懂诸如正常着色（“相邻顶点着不同的颜色”）这样的定义。
在贯穿示例中， N(B) = {A, C, D}，因此 B 有三个邻居。边 {B, D} 与 B 和 D 关联。边 {B, D} 和 {C, D} 彼此相邻，因为它们都与 D 关联。
4. 自环与平行边：定义不得不改变的地方
真实系统会产生两样集合定义无法表达的东西。一条从环岛出发又回到环岛的道路，是一条从某个顶点到它自身的边。同一对机场之间的两个不同航班，是连接同一对顶点的两条不同的边。在 E ⊆ [V]2 之下，两者都不存在： {A, A} 是一个只有一个元素的集合，而集合不能两次包含同一个元素。
解决办法不是一个脚注，而是另一个定义。Bondy 和 Murty 的 Graph Theory 在两个集合之外，明确引入了一个关联函数：
G = (V, E, ψ) 其中 ψ: E → 顶点的无序对（两者不必不同）现在，一条边本身就是一个有身份的独立对象，而 ψ 指明它连接的是哪一对顶点。两条不同的边可以映射到同一对顶点，这就得到平行边，也叫多重边。一条边也可以映射到两个元素相同的一对顶点，这就得到一个自环。West 的 Introduction to Graph Theory 走的是同一条路，把图定义为一个顶点集、一个边集，以及把每条边与其端点关联起来的一种关系。
由此得到的术语体系：
| 术语 | 允许自环？ | 允许平行边？ | 所需的定义 |
|---|---|---|---|
| 简单图 | 否 | 否 | G = (V, E)，其中 E ⊆ [V]2 |
| 多重图 | 通常否 | 是 | 关联函数 ψ |
| 伪图 | 是 | 是 | 关联函数 ψ |
两点实用的提醒。第一，“多重图”的用法并不统一：有些作者允许其中包含自环，有些不允许，因此在引用定理之前先核对来源。第二，一个自环给它所在顶点的度贡献的是 2 而不是 1，因为它的两端都连在那里。这个约定并非随意规定，下一节会解释为什么必须如此。
除非教材另有说明，“图”就是指“简单图”。本文余下部分的每一个结论都以此为前提，而配套指南简单图与多重图则详细说明了这两项放宽究竟改变了什么，以及哪些标准上界在没有它们时不再成立。
5. 度与图论中的第一个定理
一个顶点的度，例如顶点 v，记作 deg(v) 或 d(v)，是与它关联的边的条数。等价地，也更有用地说，它是边端点的个数，这些端点交汇于 v。在简单图中，它等于邻域的大小， deg(v) = |N(v)|。
还有两个相关的量在各种上界和证明中不断出现：最小度 δ(G) 和最大度 Δ(G)。如果一个图中每个顶点的度都相同，都等于 k ，就称它是 k-正则的。
下面是这门学科中最古老的定理，它来自欧拉 1736 年关于柯尼斯堡七桥的论文，也正是这篇论文开创了图论：
握手引理。对任何有限图，所有顶点的度之和等于边数的两倍： ∑v∈V deg(v) = 2m。
证明只需一行双重计数。数出所有这样的组合：（顶点，交汇于它的边端点）。按顶点求和得到 ∑ deg(v)。按边求和得到 2m，因为每条边恰好有两个端点。两者数的是同一个有限集合，所以相等。请注意，正是这个论证使得自环必须计两次：自环同样有两个端点，只不过两端都落在同一个顶点上。
在贯穿示例上验证一下：各顶点的度是 2、3、3、3、2、1，相加为 14，而该图有 7 条边。这个引理有一个直接且非常有用的推论。
推论。在任何图中，奇数度顶点的个数都是偶数。
把求和拆成奇数度顶点和偶数度顶点两部分。总和是偶数，偶数度那部分也是偶数，所以奇数度那部分也必须是偶数，这就迫使奇数项的个数为偶数。正因如此，一场聚会上永远不可能恰好有三个人各自与奇数个人握过手；决定是否存在欧拉路径的，也是同一个奇偶性论证。
6. 度序列：哪些数字列表是图
把各顶点的度按不增的顺序写下来，就得到度序列。对贯穿示例来说，它是 (3, 3, 3, 2, 2, 1)。自然的问题是反过来问的：给定一列数字，是否存在一个图，其各顶点的度恰好是这些数？存在这样一个图的数列称为可图的。
握手引理已经排除了一半的候选：任何和为奇数的数列都不是可图的。但这个判据远远不够。考虑 (3, 3, 1, 1)。它的和是 8，是偶数，而且没有哪个顶点要求超过可用的 3 个邻居。然而没有任何简单图能实现它：两个度为 3 的顶点必须各自与其余三个顶点相连，这就迫使两个度为 1 的顶点的度变成 2。
两个经典结论彻底解决了这个问题：
- Erdős–Gallai 定理（1960）给出了精确判据：一个和为偶数的不增数列是可图的，当且仅当对每个
k，前k项之和至多等于k(k-1)加上其余各项的min(di, k)之和。这是一个闭式判据，排序之后可在线性时间内检验。 - Havel–Hakimi 算法出自 Havel（1955）以及独立完成的 Hakimi（1962），它是构造性的版本：去掉最大的度
d，把随后的d个元素各减 1，重新排序，然后重复。原数列可图，当且仅当这一化简最终得到全零，而这些步骤同时也是构造一个实现该数列的图的方法。
在失败的例子上运行 Havel–Hakimi，看看它如何工作：
(3, 3, 1, 1) 去掉 3，把随后三个元素各减 1
(2, 0, 0) 重新排序
去掉 2，把随后两个元素各减 1
(-1, -1) 出现负数，因此该数列不是可图的再看贯穿示例，它是成功的：
(3, 3, 3, 2, 2, 1) → (2, 2, 1, 2, 1) → 排序后 (2, 2, 2, 1, 1)
(2, 2, 2, 1, 1) → (1, 1, 1, 1) → 排序后 (1, 1, 1, 1)
(1, 1, 1, 1) → (0, 1, 1) → 排序后 (1, 1, 0)
(1, 1, 0) → (0, 0) → 全为零，因此该数列是可图的有一点常常出人意料：一个可图的数列可以由多个互不同构的图来实现。知道了所有的度，并不能确定这个图。
7. 有向边：弧、入度与出度
把无序对换成有序对，你就得到一个有向图，也叫 digraph：
D = (V, A) 其中 A ⊆ V × V集合 (u, v) 中的一个元素 A 是一条弧，也叫有向边，它从尾端 u 指向头端 v。由于这个对是有序的， (u, v) 和 (v, u) 是不同的弧，而且两者可以同时存在。Bang-Jensen 和 Gutin 的 Digraphs 是这套术语的标准参考书，它把“弧”专门留给有向对象，正是为了避免把两者都叫作边所带来的歧义。
度也一分为二：
- 出度
d+(v)，即以v为尾端的弧的条数。 - 入度
d-(v)，即以v为头端的弧的条数。
握手引理也随之一分为二。每条弧恰好有一个尾端和一个头端，因此分别统计弧的尾端和头端可得
∑v∈V d+(v) = ∑v∈V d-(v) = |A|注意这里少了因子 2：在无向情形中，每条边给同一个和贡献两个端点；而在这里，每条弧给两个和各贡献一个端点。完整的比较，包括定向、三种连通性以及哪些算法仍然适用，见有向图与无向图。入度为 0 的顶点是源点，出度为 0 的顶点是汇点，而拓扑排序和网络流正是建立在这套术语之上的。
8. 带权边，以及为什么权重位于图之外
最短路径问题需要距离，流问题需要容量，调度问题需要工期。这些都不在 G = (V, E)之中，而且本来也不该在其中。带权图就是一个图加上一个函数：
w: E → ℝ 为每条边指定一个实数把权重放在一个单独的函数里，而不是放进边里面，正是这一点让同一个图可以同时承载多个代价模型。同一个道路网络就是一个图配三个权重函数：公里数、分钟数和油耗。配套指南带权图与无权图沿着这个思路讨论算法选择、负权和顶点强度。换掉这个函数，所有最短路径都会改变，而不必改动任何一个顶点或一条边。
这也解释了为什么算法附带的条件是关于 w 的，而不是关于图的。 Dijkstra 算法要求每条边都满足 w(e) ≥ 0 ； Bellman-Ford 能容忍负权，但不能容忍负环。这些都是对函数的约束，而底层的那对集合对此毫不在意。
9. 一个图最多能有多少条边？
在一个有 n 个顶点的简单图中，一条边就是从 n个顶点中选出 2 个互不相同的顶点，因此最大值就是二项式系数
mmax = C(n, 2) = n(n - 1) / 2达到这个上限的图，也就是任意两个顶点都相邻的图，称为完全图 Kn。对贯穿示例而言， n = 6 给出的上限是 15 条边，而该图用了其中 7 条。比值 2m / (n(n-1)) 就是密度，这里是 0.47。
正是这一个上界，让两个说法主导了算法文献：
- 一个稠密图的
m接近它的最大值，即m = Θ(n2)。 - 一个稀疏图的
m远低于这个上限，通常是m = O(n)或O(n log n)。几乎所有大型真实网络都是稀疏的：道路地图、社交图和网页图的平均度都只有个位数或两位数，无论它们包含多少顶点。
稀疏性不是细节。它决定了该用哪种数据结构，也就是下一节的内容；它也是为什么在真实输入上 O(m log n) 会胜过 O(n2) ，尽管两者在最坏情况下完全相同。
10. 在代码中存储顶点和边
在内存中保存 V 和 E 有三种标准方式，它们之间的取舍由 Cormen、Leiserson、Rivest 和 Stein 在 Introduction to Algorithms中给出。完整的比较，包括压缩稀疏行格式以及矩阵反而更省空间的密度阈值，见图的表示。
| 表示方式 | 空间 | u 与 v 相邻吗？ | 访问 v 的所有邻居 | 最适合 |
|---|---|---|---|---|
| 邻接矩阵 | Θ(n2) | O(1) | Θ(n) | 稠密图，常数时间的边查询 |
| 邻接表 | Θ(n + m) | O(deg(u)) | Θ(deg(v)) | 稀疏图，遍历 |
| 边列表 | Θ(m) | O(m) | O(m) | 需要对边排序的算法，例如 Kruskal |
实用的经验法则来自第 9 节。像 BFS 和 DFS 这样的遍历，全部运行时间都花在走访邻居集合上，因此在稀疏图上邻接表给出 O(n + m) ，而矩阵则会强制要求 O(n2) ，仅仅是为了扫描一行行的零。在稠密图上，矩阵在空间和简洁性上都更有优势。边列表看起来很原始，直到你遇见 Kruskal 算法，它按权重对所有边排序，完全不需要查找邻居。
11. 决定顶点应该是什么
应用图论时最难的部分不是任何定理，而是选择顶点是什么，因为这个选择决定了后面的一切，而且往往不唯一。
以道路网络为例。显而易见的模型把路口作为顶点，把路段作为边，这正是路径规划引擎想要的：图中的一条路径就是地面上的一条路线。但转向限制和转向代价存在于路口，而不在道路上，这个模型没有地方安放它们。标准的解决办法把选择反过来：让每一个路段成为一个顶点，当可以合法地从其中一段驶入另一段时，就把这两个顶点连起来。这样一来，一次转向就是一条边，可以带上代价。
这种反转是一种形式化构造，不是权宜之计。线图 L(G) 为 G的每条边设一个顶点，当 G 中对应的两条边共享一个端点时，这两个顶点相邻。它可以追溯到 Whitney 1932 年关于同余图的论文，也正因如此，关于边的问题常常可以交给一个只认识顶点的算法去解决。例如，匹配问题在线图上就变成了独立集问题。
一份简短的检查清单，可以避免大多数建模错误：
- 你的两个顶点之间可能被连接不止一次吗？如果是，你需要多重图，或者需要把这些平行边聚合成一个权重。
- 这个关系是对称的吗？ “是……的朋友”通常是对称的，“关注”和“依赖于”则不是。弄错这一点，你就会在有向问题上使用无向算法。
- 这个关系是否一次涉及两个以上的对象？一条边恰好连接两个顶点。一个由五人组成的委员会，或者一个有三种反应物的化学反应，是一条超图的边，把它硬塞进普通的边里会丢失信息。
- 结构会随时间变化吗？标准的图是一张快照。时序图或动态图是另外的模型，有各自的研究文献。
12. 不同教科书之间的术语陷阱
图论同时在多个领域中成长，因此同一个对象有好几个名字，而且有些名字在不同作者笔下含义不同。下面这些是真正会引发错误的：
| 你可能读到 | 它通常指 | 注意 |
|---|---|---|
| 节点、点、站点 | 顶点 | 含义没有区别；“节点”在计算领域占主导，“点”则见于 Harary 较早的教材 |
| 连接、线、弧、键 | 边 | 在多数现代教材中，“弧”特指有向边 |
| 价 | 度 | 常见于化学和英式教材 |
| 图 | 简单图 | 少数应用论文允许“图”包含自环和平行边 |
| 多重图 | 允许平行边 | 有些作者在这里也允许自环，另一些则把那种情形留给“伪图” |
| 阶与规模 | 分别是 |V| 和 |E| | 容易弄反；“规模”指的是边数，不是顶点数 |
| 路径 | 没有重复顶点的途径 | 有些教材允许重复，并用“简单路径”表示受限的那种 |
| 环 | 一条闭路径 | 在有向的语境中，仅仅一对 u 到 v 和 v 到 u 的弧就已经构成一个 |
稳妥的习惯正是每篇论文都遵循的那一条：在开头一次性说明你的约定，然后始终如一。引用定理时，也要引用它被证明时所依据的定义。
13. 符号表
本站以及下列参考文献中使用的记号。
| 符号 | 读作 | 含义 |
|---|---|---|
G = (V, E) | 图 G | 一个顶点集连同一个边集 |
V(G), E(G) | G 的顶点集、边集 | 在涉及多个图时使用 |
n, |V|, |G| | G 的阶 | 顶点的个数 |
m, |E| | G 的规模 | 边的条数 |
{u, v} | 边 u v | 一条无向边，常简写为 uv |
(u, v) | 从 u 到 v 的弧 | 一条有向边，尾端为 u，头端为 v |
u ~ v | u 与 v 相邻 | 存在一条连接它们的边 |
N(v) | v 的邻域 | 与 v 相邻的顶点构成的集合 |
deg(v), d(v) | v 的度 | 交汇于 v 的边端点的个数 |
d+(v), d-(v) | 出度、入度 | 按尾端和按头端统计的弧数 |
δ(G), Δ(G) | 小 delta、大 delta | G 中的最小度和最大度 |
Kn | n 个顶点的完全图 | 任意两个顶点都相邻，共有 n(n-1)/2 条边 |
L(G) | G 的线图 | G 的每条边对应一个顶点，当两条边共享一个端点时对应顶点相邻 |
w: E → ℝ | 权重函数 | 为每条边指定一个数 |
14. 常见问题
顶点和节点有什么区别？
没有区别。它们是同一事物的两个名字，你遇到哪一个取决于领域。数学教材说顶点（vertex），计算机科学和网络科学通常说节点（node），Harary 1969 年的经典著作说点（point），化学则说原子。选定一个词，并在同一份文档中始终如一地使用它。
边和弧有什么区别？
在多数现代教材中，边是无向的，写成无序对 {u, v}；而弧是有向的，写成有序对 (u, v)，有尾端和头端。由于这个对是有序的，弧 (u, v) 和 (v, u) 是不同的对象，一个有向图可以同时包含两者。有些作者用“有向边”代替“弧”，意思完全相同。
一条边可以把一个顶点连到它自己吗？
在简单图中不可以。按照标准定义，边是顶点集的二元子集，而 {v, v} 只有一个元素，因此不是合法的边。把一个顶点连到它自己的边称为自环，要允许自环，就必须改用带显式关联函数的定义，多重图和伪图正是这样做的。在这样的图中，一个自环会给它所在顶点的度加 2，因为它的两端都连在那里。
什么是顶点的度，什么是握手引理？
顶点的度是交汇于它的边端点的个数，记作 deg(v)。握手引理可追溯到欧拉 1736 年关于柯尼斯堡七桥的论文，它指出所有顶点的度之和恰好等于边数的两倍，因为每条边在它的两个端点处各贡献一个端点。它最著名的推论是：奇数度顶点的个数总是偶数。
一个有 n 个顶点的图最多能有多少条边？
一个有 n 个顶点的简单无向图最多有 n(n-1)/2 条边，因为一条边就是从 n 个顶点中选出 2 个互不相同的顶点。达到这一上限的图是完全图 K_n。一个简单有向图最多可以有 n(n-1) 条弧，因为每个有序对都单独计数。多重图则完全没有上限，因为平行边可以任意重复。
任何一列数字都是合法的度序列吗？
不是。能被某个简单图实现的数列称为可图的。握手引理给出一个快速的必要条件，即总和必须是偶数，但这并不充分：(3, 3, 1, 1) 的和是偶数，却没有任何简单图具有这些度。1960 年的 Erdős–Gallai 定理给出了精确判据，而出自 Havel（1955）和 Hakimi（1962）的 Havel–Hakimi 算法既能判定这个问题，又能在存在实现时构造出一个实现。
15. 参考文献
上文的定义、定理和归属均出自以下文献，按时间顺序排列。
- Euler, L. (1736). "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Petropolitanae 8（1741 年出版），128 至 140 页。关于柯尼斯堡七桥的论文，也是度数论证的起源。
- Sylvester, J. J. (1878). "Chemistry and Algebra." Nature 17，284 页。正是这则短文引入了现代意义上的“graph”一词。
- Whitney, H. (1932). "Congruent Graphs and the Connectivity of Graphs." American Journal of Mathematics 54(1)，150 至 168 页。线图构造的出处。
- König, D. (1936). Theorie der endlichen und unendlichen Graphen. 莱比锡：Akademische Verlagsgesellschaft。第一本完全献给图论的著作。
- Havel, V. (1955). "A remark on the existence of finite graphs"（捷克语）。 Časopis pro pěstování matematiky 80，477 至 480 页。
- Erdős, P. 与 Gallai, T. (1960). "Graphs with prescribed degrees of vertices"（匈牙利语）。 Matematikai Lapok 11，264 至 274 页。可图数列的精确判据。
- Hakimi, S. L. (1962). "On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I." Journal of the Society for Industrial and Applied Mathematics 10(3)，496 至 506 页。
- Harary, F. (1969). Graph Theory. 马萨诸塞州雷丁：Addison-Wesley。这本经典把顶点称为“点”，把边称为“线”。
- Bollobás, B. (1998). Modern Graph Theory. Graduate Texts in Mathematics 184. New York: Springer.
- West, D. B. (2001). Introduction to Graph Theory，第 2 版。Upper Saddle River：Prentice Hall。用一个顶点集、一个边集和一个端点关系来定义图。
- Bondy, J. A. and Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244。伦敦：Springer。第 4 节所用关联函数表述的出处。
- Bang-Jensen, J. and Gutin, G. (2009). Digraphs: Theory, Algorithms and Applications，第 2 版。伦敦：Springer。弧与有向度的标准参考书。
- Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2009). Introduction to Algorithms，第 3 版。马萨诸塞州剑桥：MIT Press。第 10 节中各表示方式开销的出处。
- Diestel, R. (2017). Graph Theory，第 5 版。Graduate Texts in Mathematics 173。柏林：Springer。第 1 节所引定义的出处。