目录
1. 三种定义，两项放宽
无序对的集合无法表达两件事：连接顶点与自身的边，以及连接同一对顶点的两条不同的边。是否允许它们，会得到三种不同的对象，而名称值得弄准确，因为定理都是针对特定对象陈述的。
所谓简单图，是大多数文献中的默认设定，其定义与顶点与边指南中的相同：
G = (V, E) 其中 E ⊆ [V]² 每条边都是 V 的二元子集由于 E 是二元子集构成的集合， {v, v} 是不合法的（它只有一个元素），同一对顶点也不能出现两次（集合中每个元素只出现一次）。这两条限制都是记号带来的结果，而不是某人做出的决定。
要解除它们，就需要另一种形式化。Bondy 和 Murty 的 Graph Theory 给每条边赋予自身的身份，并增加一个函数，说明每条边连接的是哪一对顶点：
G = (V, E, ψ) 其中 ψ: E → （不必互异的）顶点无序对现在， e1 和 e2 可以是 E 中的不同元素，且满足 ψ(e1) = ψ(e2) = {u, v}，这就构成一对平行边；而 ψ(e) = {v, v} 则是一个自环。Diestel 用两个把每条边映到其端点的映射达到同样的效果，West 则用一种把每条边与其端点关联起来的关系。形式化不同，内容相同。
| 对象 | 自环 | 平行边 | 需要 |
|---|---|---|---|
| 简单图 | 否 | 否 | E ⊆ [V]² |
| 多重图 | 通常否 | 是 | 关联函数 |
| 伪图 | 是 | 是 | 关联函数 |
关于术语本身有两点提醒，因为它们在阅读论文时确实会造成混乱：
- “多重图”的用法并不统一。有些作者允许多重图含有自环，有些则把这种情况留给“伪图”，还有少数人把任何图都叫作“多重图”。在引用某个来源的定理之前，先核对它自己的定义。
- “图”通常指“简单图”。大多数教材只在第一章说明一次，此后再不重复。一个针对“图”陈述的结果往往隐含着简单性假设，而第 5 节展示了其中一些结果在没有这个假设时会失败得多么彻底。
2. 图论奠基于一个多重图
这不是事后附加上去的边缘情况。开创这门学科的问题本身就是一个多重图，简化之后它就不再是同一个问题。
欧拉 1736 年关于柯尼斯堡七桥的论文，对由七座桥连接的四块陆地进行建模。两座桥连接北岸与岛，另外两座连接南岸与岛。这些都是平行边，没有任何简单图能容纳它们。
欧拉的判据关乎度的奇偶性，而正是平行的桥决定了度的取值：
柯尼斯堡多重图 7 条边 度 3, 5, 3, 3 四个奇数 → 不存在欧拉迹
基础简单图 5 条边 度 2, 3, 2, 3 两个奇数 → 欧拉迹存在删掉重复边，答案就反转了。多重性不是模型上的装饰，它就是模型本身，而图论的历史中的历史细节与形式化密不可分。谁要是把七座桥载入一个会悄悄去重的数据结构，就会得出欧拉错了的结论。
3. 自环对度的影响
度统计的是与顶点相接的边端数，而不是边数。自环有两个端点，而且都落在同一个顶点上，因此：
顶点v上的自环贡献 2 到deg(v)中。每条平行边各贡献 1，与独立的边完全一样。
这一约定是被迫的，而非选择。握手引理用两种方式统计（顶点，该顶点处的边端）这样的对，而每条边（包括自环）都恰有两个端点，所以 ∑ deg(v) = 2m 对伪图依然成立。若把自环的度记为 1，这门学科中最古老的定理会立刻失效。
值得记住的几个推论：
- 只有一个自环、没有其他边的顶点度为 2，而不是 0，它也不是孤立顶点。
- 奇数度顶点的个数仍然是偶数，因为证明只用到了
∑ deg(v) = 2m。 - 在简单图中，
deg(v) = |N(v)|，即邻域的大小。在多重图中这个等式不成立：连向同一个邻居的三条平行边给出度 3，却只有一个邻居。把度算成去重后邻居集合大小的代码，算出的是错误的数。
4. 多重性会改变什么，又不能改变什么
有用的问题不是“我的图是简单图吗”，而是“我要计算的性质是否依赖于多重性”。答案泾渭分明，但分界并不显而易见。
| 性质 | 平行边 | 自环 | 原因 |
|---|---|---|---|
| 连通性、连通分量 | 无影响 | 无影响 | 可达性只需要一对顶点之间有一条边 |
| 平面性 | 无影响 | 无影响 | 多重图是平面图，当且仅当其基础简单图是平面图 |
| 二部性 | 无影响 | 破坏二部性 | 自环是长度为 1 的奇闭途径 |
| 正常顶点着色 | 无影响 | 使其不可能 | 平行边把同一约束施加两次；自环要求顶点与自身颜色不同 |
| 度、握手引理 | 各计 1 | 计为 2 | 统计边端，而非边 |
| 围长（最短环） | 降为 2 | 降为 1 | 两条平行边构成长度为 2 的环 |
| 边连通度、最小割 | 改变 | 无影响 | 每条平行副本也必须被割断 |
| 生成树数 | 改变 | 无影响 | 每条平行副本都给出一棵不同的树 |
| 最大流 | 改变 | 无影响 | 平行边的容量相加 |
| 欧拉迹或欧拉回路 | 改变 | 使度增加 2 | 度的奇偶性就是全部判据 |
其中三行值得详细说明理由。
着色忽略平行边，却无法容忍自环。正常着色要求每条边的两个端点颜色不同。再加一条 {u, v} ，只是重复了已有的约束，所以正常着色的集合，进而色数和色多项式，都与基础简单图完全相同。自环要求 c(v) ≠ c(v)，这是任何着色都无法满足的，因此带自环的伪图根本没有正常着色，其色多项式恒为零。这就是为什么图着色几乎总是针对无自环的图来陈述。
生成树数确实依赖于多重性。由一条边相连的两个顶点有一棵生成树；由两条平行边相连时则有两棵，因为选择不同的边就得到不同的树。Kirchhoff 1847 年的矩阵树定理由拉普拉斯矩阵计数生成树，它之所以针对多重图陈述，正是因为多重性以非对角元计数的形式进入矩阵。在 Kirchhoff 遇到这个问题的电路网络中，并联元件十分常见。
割和流依赖于多重性。使 u 与 v 分离所需删除的最少边数，在一条边相连时为 1，两条边相连时为 2。由于最大流等于最小割，流也是如此： k 条单位容量的平行边可以运送 k 个单位。这正是带单位容量的多重图成为流网络自然的无权模型的原因。
5. 简单图的界全部失效
相当多的标准结果都隐含着简单性假设，而离开这个假设，它们不是逐渐变差，而是彻底失效。
| 标准结果 | 简单图 | 多重图 |
|---|---|---|
| 最大边数 | m ≤ n(n-1)/2 | 无上界：平行副本可以任意重复 |
| 稀疏或稠密的划分 | m = O(n) 对比 Θ(n²) | 没有多重性上界时毫无意义 |
| 邻接矩阵为 0/1 | 是 | 否：元素是计数 |
| 度等于邻域大小 | deg(v) = |N(v)| | 失效；度可以超过邻居数 |
| 平面图的欧拉公式 | n - m + f = 2 | 依然成立，因为它统计的是面，与简单性无关 |
| 平面图的边数界 | m ≤ 3n - 6 对 n ≥ 3 | 失效：平行边会围出长度为 2 的面 |
| 握手引理 | ∑ deg(v) = 2m | 依然成立，自环计两次 |
幸存下来的两行与失效的几行同样值得注意。握手引理和欧拉多面体公式都是通过计数关联关系证明的，而计数论证并不在乎两条边是否恰好连接同一对顶点。失效的界则是通过选取不同的顶点对来证明的，而这正是多重图使之失效的那一步。
本节的实用版本是：查阅一个界时，看看它的证明是在计数关联关系还是在计数顶点对。前一类可以推广到多重图，后一类不行。
6. 存储：邻接矩阵力不从心之处
三种标准表示的退化方式大不相同，而这些差异决定了你该用哪一种。
邻接矩阵不再是 0/1 矩阵。自然的扩展是存储连接每对顶点的边数，于是元素 (u, v) 变成计数；按照惯例，自环在对角线上记 2，使行和仍然等于度。这样可行，但对真实数据有一个致命限制：计数无法携带逐边的信息。如果你的三班平行航班各有不同的价格，计数矩阵根本没地方存放它们。
简单图 A[u][v] ∈ {0, 1}
多重图 A[u][v] = 连接 u 和 v 的边数
伪图 A[v][v] = 2 × (v 上的自环数) 使行和等于度邻接表保留重复项。在 u 的表中， v 出现的次数就等于连接它们的边数。遍历代码无需改动，BFS 或 DFS 会多次看到同一个邻居，只要访问标记是针对顶点的，这就没有害处。
边列表成为自然的格式。这才是真正契合数学的表示：每条边都是一条有自身身份的记录，所以平行边就是不同的记录，逐边属性也有了存放之处。这就是第 1 节中关联函数定义的数据结构形式。
由此得出一条设计原则，也是本节最值得带走的一点：
在多重图中，边需要身份。一对端点不再能确定一条边，所以任何指代边的东西，无论是匹配、生成树、流还是删除操作，都必须引用边 ID，而不是 (u, v)。
几乎每个多重图 bug 都能追溯到这一句话。把生成树存成顶点对的集合，或者用 (u, v)作为已访问边集合的键，都会悄悄混淆平行边，得出任何类型检查器都发现不了的错误答案。
7. 哪些算法会受影响
大多数遍历类算法对多重性毫不在意，因为它们标记的是顶点。那些标记或选择边的算法才需要留意。
| 算法 | 在多重图上 | 注意事项 |
|---|---|---|
| BFS 与 DFS | 无需改动即可工作 | 重复的邻居会被看到两次并被跳过；访问集合针对的是顶点 |
| Dijkstra | 无需改动即可工作 | 松弛操作会自然保留多条平行边中最便宜的一条 |
| Kruskal、Prim | 无需改动即可工作 | 环检测会自动拒绝多余的副本 |
| 欧拉迹或欧拉回路 | 需要多重图 | 每条边都必须经过一次，所以平行边是各自独立的任务；标记边 ID，而不是顶点对 |
| 中国邮递员问题 | 需要多重图 | 该算法的整个方法就是复制边，有意制造平行副本 |
| 最大流 | 可行，且多重性很重要 | 平行边的容量相加；要么分开保存，要么显式求和 |
| Karger 最小割 | 会产生多重图 | 收缩一条边会合并顶点并产生平行边；去重会破坏正确性 |
| 匹配 | 需谨慎 | 平行边为同一对顶点提供了不同的选择；自环永远不会出现在匹配中 |
| 顶点着色 | 忽略平行边 | 先简化；有自环就意味着不存在着色 |
Karger 这一行最出人意料，值得完整说明，因为它颠覆了通常的直觉。Karger 的随机最小割算法反复地均匀随机选取一条边并收缩，把它的两个端点合并成一个顶点。收缩会把原先分别指向两个被合并顶点的两条边，变成指向新顶点的两条平行边，而算法的概率分析依赖于保留每一个副本，因为收缩某条边的概率与它的副本数成正比。简化中间图，算法就不再正确。Borůvka 生成树算法中的收缩步骤也是如此。
8. 何时必须使用多重图
多重图不是需要规范化掉的奇特现象。只要两个实体之间可以存在不止一次关系，而且每一次关系本身都很重要，多重图就是如实的模型：
- 交通网络。两座城市由三班不同的航班相连，或者同一对城市之间既有公路也有铁路。每条连接都有自己的时长、价格和容量。
- 电路。同一对节点之间的并联元件，这正是 Kirchhoff 在 1847 年提出矩阵树定理时所处的背景。
- 交易与支付图。两个账户之间可能发生多次交易；把它们合并成一条边会丢失金额、时间戳以及次数本身，而次数往往正是要寻找的信号。
- 化学反应图与分子图。在分子的经典图模型中，双键和三键就是平行边。
- 知识图谱与 RDF。两个实体之间由多个不同的谓词相关联。这就是这类数据通常以三元组存储的原因，也就是每条边带一个标签的边列表。
- 一切通过收缩构造的东西。 Karger 算法、Borůvka 算法以及许多近似算法中的凝聚步骤，无论输入是什么，都会在运行过程中产生平行边。
- 欧拉路线问题。街道清扫和邮递路线需要走遍每一条实际的街道，同一对路口之间的两条街道就是两项任务。
9. 简化及其代价
把多重图转换为简单图往往是正确的做法，但只有当你清楚自己将要改变第 4 节中的哪些性质时，这样做才安全。标准做法有三种，它们回答的是不同的问题：
| 方法 | 保留 | 丢失 | 适用于 |
|---|---|---|---|
| 合并平行边为一条，删除自环 | 连通性、平面性和色数，但要注意，删除自环会把不可着色的图变成可着色的图 | 割、流、生成树数、欧拉结构 | 结构性问题 |
| 合并并对权重求和 | 总容量，因此最大流和最小割得以保留 | 各条边的属性 | 流与割问题 |
| 合并并取最小权重 | 最短路径距离 | 备选路线，因此割和流会失效 | 路由 |
注意，第二条和第三条规则互不相容：求和对容量正确、对距离错误，取最小值对距离正确、对容量错误。该用哪一条，取决于权重沿路径如何组合，这正是配套指南带权图与无权图的主题。选错合并方式，就会悄悄回答另一个问题，而事后看起来图还完全合理。
第四种选择往往比以上都好：保留多重图，让算法去处理它。 BFS、DFS、Dijkstra、Kruskal 和 Prim 都能直接在多重图上正确运行，因此简化往往毫无收益，还会丢失信息。
10. 有向多重图
以上内容都可以推广到有向图，但有一个额外的区别值得点明。在有向图中，弧 (u, v) 和 (v, u) 本来就是不同的对象，这不是多重性，而是方向：这样一对弧是双向弧对，普通的有向图无需扩展定义就可以包含它。许多有向图根本不含这种弧对，DAG 就从来不含。有向情形下的多重性，是指两条或更多条具有相同弧尾和相同弧头的弧，这同样需要关联函数式的定义，正如 Bang-Jensen 和 Gutin 的 Digraphs中所用的那样。
实际后果可以直接推广：入度和出度统计的是弧，而不是不同的邻居；有向自环使两者各增加 1；有向多重图上的欧拉条件仍然是在每个顶点比较入度与出度。
11. 常见错误
- 把多重图载入会去重的结构。由顶点对组成的
Set、布尔邻接矩阵，或者数据库中针对(u, v)的唯一约束，都会悄悄丢弃平行边。图看起来没问题，所有计数却都是错的。 - 用端点来标识边。在多重图中，
(u, v)指的是一组边，而不是一条边。匹配、生成树、流和已访问边集合都必须以边 ID 为键。 - 把度算成邻居数。在简单图中正确，一旦出现重复边或自环就错了。
- 把自环的度记为 1。它贡献 2，握手引理依赖于此。
- 套用
m ≤ n(n-1)/2。这个界以及由它推出的一切，包括稀疏与稠密的判断，都需要简单性。 - 在欧拉、割或流计算之前进行简化。这三者都依赖于多重性，正如柯尼斯堡在这门学科的奠基例子上所展示的那样。
- 在收缩算法内部去重。 Karger 和 Borůvka 的算法有意产生平行边，并且需要保留它们。
- 以为图库会按你的预期行事。不同的图库在添加已存在的边时行为不同：可能创建重复边、忽略或者报错。在测试中检查一次。
12. 术语表
| 术语 | 含义 |
|---|---|
| 简单图 | 无自环、无平行边； E ⊆ [V]² |
| 多重图 | 允许平行边；是否允许自环取决于作者 |
| 伪图 | 自环和平行边都允许 |
| 平行边 | 端点对相同的两条或更多条不同的边；也称重边 |
| 多重性 | 连接给定顶点对的边数 |
| 自环 | 两个端点是同一个顶点的边；为该顶点的度贡献 2 |
关联函数 ψ | 把每条边映射到它所连接的顶点对，从而赋予边自身的身份 |
| 基础简单图 | 合并平行边、删除自环之后剩下的图 |
| 无自环图 | 允许平行边，不允许自环 |
| 围长 | 最短环的长度；有平行边时为 2，有自环时为 1 |
13. 常见问题
简单图和多重图有什么区别？
简单图中任意两个顶点之间至多有一条边，也没有从顶点连到自身的边，因为它的边集是顶点集的二元子集构成的集合。多重图允许多条不同的边连接同一对顶点，这需要另一种定义：边拥有自身的身份，并由关联函数说明每条边连接哪一对顶点。伪图还进一步允许自环。
柯尼斯堡七桥问题是多重图吗？
是的，而且必然如此。两座桥连接北岸与岛，另外两座连接南岸与岛，因此模型含有平行边，不可能是简单图。这一点很重要：七桥多重图的度为 3、5、3、3，四个全是奇数，所以不存在欧拉迹，这正是欧拉在 1736 年给出的答案。把平行的桥合并后，度变为 2、3、2、3，只有两个是奇数，于是欧拉迹就会存在。简化改变了答案。
自环在度中算一次还是两次？
两次。度统计的是与顶点相接的边端，而自环有两个端点，都连在同一个顶点上。这一约定是被迫的，而非选择：握手引理说度之和等于边数的两倍，其证明统计的是每条边的两个端点，所以把自环的度记为 1 会破坏它。只带一个自环的顶点度为 2，不是孤立顶点。
平行边会改变色数吗？
不会。正常着色要求每条边的两个端点颜色不同，而重复的边只是重复了已有的约束，所以多重图的正常着色与其基础简单图完全相同，色数和色多项式都不变。自环则不同：它要求一个顶点的颜色与自身不同，因此带自环的图根本不存在正常着色。
运行算法之前可以直接把多重图简化吗？
只适用于不依赖多重性的性质。连通性、平面性和着色在简化后保持不变。最小割、最大流、生成树数、围长和欧拉迹则不然。如果必须合并带权的平行边，容量要把权重相加，距离要取最小值，并且要注意这两条规则互不相容。通常更好的做法是根本不简化，因为 BFS、DFS、Dijkstra、Kruskal 和 Prim 都能不加修改地在多重图上正确运行。
在代码中如何存储多重图？
给每条边一个身份。由记录组成的边列表，每条记录有自己的 ID、端点和属性，是关联函数定义的直接表达，也是能够承载逐边数据的格式。邻接表同样可行，每条平行边对应存一次邻居。邻接矩阵只能存计数，因此无法携带逐边属性，而布尔矩阵会悄悄抹掉多重性。无论选择哪种方式，都不要用端点对作为已访问或已选边集合的键。
14. 参考文献
以上定义、定理和归属均出自以下文献，按时间顺序排列。
- Euler, L. (1736). "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Petropolitanae 8（1741 年出版），128 至 140 页。柯尼斯堡七桥，以多重图建模。
- Kirchhoff, G. (1847). "Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird." Annalen der Physik 148(12)，497 至 508 页。矩阵树定理，基于含并联元件的电路网络提出。
- Harary, F. (1969). Graph Theory. 马萨诸塞州雷丁：Addison-Wesley。区分了图、多重图和伪图。
- Karger, D. R. (1993). "Global Min-cuts in RNC, and Other Ramifications of a Simple Min-cut Algorithm." Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms，21 至 30 页。在运行中产生平行边的收缩算法。
- Karger, D. R. and Stein, C. (1996). "A New Approach to the Minimum Cut Problem." Journal of the ACM 43(4)，601 至 640 页。
- Bollobás, B. (1998). Modern Graph Theory. Graduate Texts in Mathematics 184。纽约：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。第 1 节中关联函数定义的出处。
- 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。
- Wilson, R. J. (2010). Introduction to Graph Theory，第 5 版。Harlow：Prentice Hall。从第一章起就把多重图与简单图并列讲解。
- Chartrand, G., Lesniak, L. and Zhang, P. (2015). Graphs & Digraphs，第 6 版。Boca Raton：CRC Press。
- Diestel, R. (2017). Graph Theory，第 5 版。Graduate Texts in Mathematics 173。柏林：Springer。简单图定义及用两个端点映射表述多重图的出处。