顶点的度与握手引理

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. 顶点的度

顶点的度是与它相接的边的条数。在简单图中，它就等于该顶点的邻居个数。它是图中最局部的数：只看这一个顶点、不看其他任何东西就能读出它。然而，相当多的全局结构仅由度就决定了，这正是本文要讨论的内容。

记号很简短。 deg(v) 表示顶点 v的度， δ(G) 是最小度（取遍所有顶点）， Δ(G) 是最大度。度为 0 的顶点称为孤立顶点，度为 1 的顶点称为叶子或悬挂顶点，而每个顶点的度都等于同一个数 r 的图称为 r 正则图。基本术语（包括为什么一个自环会让度加 2）在顶点与边指南中有介绍；本文以此为起点，探讨度能告诉我们什么。

一个小小的友谊网络贯穿全文。八个人 A 到 H，十二对朋友关系：

E = {AB, AC, AD, BC, BD, CD, AE, DE, AF, EF, FG, AH}       12 条边

度：   A 6   B 3   C 3   D 4   E 3   F 3   G 1   H 1
δ = 1（G 和 H）      Δ = 6（A）      平均度 = 24 / 8 = 3

2. 握手引理

把示例中的度加起来得到 24，恰好是 12 条边的两倍。这并不是这个图的巧合。

握手引理。在任何图中，所有顶点的度之和等于边数的两倍： ∑ deg(v) = 2m。

证明是一个双重计数。考虑所有的（顶点，位于该顶点的边端点）对。按顶点计数，得到的是度之和。按边计数，每条边贡献 2，因为每条边恰好有两个端点，自环也不例外，它的两个端点落在同一个顶点上。两种计数描述的是同一组有序对，所以结果相等。这一观察可以追溯到 Euler 1736 年关于 Königsberg 七桥问题的论文，在那里它是用桥和陆地区域的语言表述的；“握手引理”这个名字则是现代的，来自这样一个画面：在一场聚会上，每次握手都要用到两只手。

这个引理最有用的推论是显而易见的。所有度之和是偶数，所以奇数度必须成对出现：

每个图中奇数度顶点的个数都是偶数。

在示例中，奇数度顶点是 B、 C、 E、 F、 G 和 H：共六个，是偶数，正如引理所保证的。

3. 从存储的图中计算度

读取一个度的代价取决于图的存储方式，这种权衡在图的表示一文中有介绍。使用邻接表时，顶点 v 的度就是其列表的长度，如果存储了长度，就能在 O(1) 时间内得到。使用邻接矩阵时，它是第 v行之和，需要 O(n)时间。如果只有一个边列表，你就必须扫描全部 m 条边，所以通常的做法是一次遍历算出所有的度并保存结果。下面的程序正是这样做的，它还检验了握手引理，并算出了第 9 节所依据的两个平均值。

from collections import Counter

edges = ['AB', 'AC', 'AD', 'BC', 'BD', 'CD', 'AE', 'DE', 'AF', 'EF', 'FG', 'AH']
adj = {v: set() for v in 'ABCDEFGH'}
for u, v in edges:
    adj[u].add(v)
    adj[v].add(u)

deg = {v: len(adj[v]) for v in adj}
print(deg)
# {'A': 6, 'B': 3, 'C': 3, 'D': 4, 'E': 3, 'F': 3, 'G': 1, 'H': 1}

print(sum(deg.values()), 2 * len(edges))     # 握手引理
# 24 24
print(sorted(v for v in deg if deg[v] % 2))   # 它们的个数总是偶数
# ['B', 'C', 'E', 'F', 'G', 'H']

# 友谊悖论：平均度与朋友的平均度对比。
mean_degree = sum(deg.values()) / len(deg)
mean_friend = sum(deg[v] ** 2 for v in deg) / sum(deg.values())
print(mean_degree, mean_friend)
# 3.0 3.75

# 有多少人的朋友数少于其朋友们的平均朋友数？
fewer = [v for v in adj if deg[v] < sum(deg[w] for w in adj[v]) / deg[v]]
print(sorted(fewer))
# ['B', 'C', 'E', 'F', 'G', 'H']
print(Counter(deg.values()).most_common(1))  # 总有某个度会重复
# [(3, 4)]

输出中有两行现在就值得注意。握手检验打印出 24 24。最后一行报告度 3 出现了四次。总有某个度会重复，原因在第 4 节中解释。

4. 握手引理立刻解决的谜题

握手引理把好几个听起来需要搜索的问题变成了一行算术。

• 七个人能否每人恰好与另外三个人握手？不能。那样的话度之和为 7 × 3 = 21，这是奇数，而任何度之和都是握手次数（一个整数）的两倍。
• 9 个顶点上存在 3 正则图吗？不存在，理由相同。一个 r 正则图若有 n 个顶点，就有 nr / 2 条边，所以当 r 为奇数时， n 必须是偶数。
• 一个有 10 个顶点、平均度为 3 的图有多少条边？恰好 15 条，因为平均度等于 2m / n。
• 一条通路能否恰好经过每条边一次、起点和终点不同，而图中只有一个奇数度顶点？这个问题根本不会出现：一个图不可能恰好有一个奇数度顶点。Euler 的判据要求奇数度顶点为零个或两个，正如欧拉路径指南所解释的，而握手引理排除了所有奇数个的情形。

另一个经典结论用的则是鸽巢原理：

在任何至少有两个顶点的简单图中，总有两个顶点的度相同。

若图有 n 个顶点，可能的度为 0, 1, …, n − 1，共 n 个值，对应 n 个顶点，所以要让所有度都不同，就必须每个值恰好用一次。但 0 和 n − 1 不能同时出现：度为 n − 1 的顶点与所有其他顶点相邻，因此没有顶点的度为 0。于是最多只剩 n − 1 个可用的值分给 n 个顶点，必有两个顶点共用一个值。用日常的话说：在任何聚会上，总有两个人在场的朋友数相同。这个命题要求图是简单图；有平行边时它不成立。这一结论已在顶点数不超过七的所有简单图上用穷举法验证过。

5. 度序列：哪些数列能构成图？

把度从大到小排列，就得到度序列， (6, 4, 3, 3, 3, 3, 1, 1) 就是示例的结果。一个序列如果是某个简单图实际具有的度序列，就称为可图的。由握手引理，和为偶数是必要条件，但远不充分： (4, 4, 4, 1, 1) 的和为偶数，却不对应任何图。五个顶点中若有三个度为 4，它们每个都要与其余所有顶点相邻，这会使最后两个顶点的度都至少为 3。

有两个经典判定方法可以精确地回答这个问题。在顶点与边指南中，两者都有手工演算；这里给出它们的代码。 Havel–Hakimi 方法源于 Havel（1955）和 Hakimi（1962），它反复地把剩余度最大的顶点与排在其后的若干顶点相连，最终要么构造出一个图，要么卡住。 Erdős–Gallai 定理（1960）是一个封闭形式的判定：一个和为偶数的非增序列是可图的，当且仅当对每个 k，最大的 k 个度之和至多为 k(k − 1) 加上其余各项的 min(di, k) 之和。

import heapq

def havel_hakimi(seq):
    """返回具有这些度的一个简单图的边；如果不存在，返回 None。"""
    if sum(seq) % 2:
        return None                           # 总和为奇数违反握手引理
    heap = [(-d, i) for i, d in enumerate(seq) if d > 0]
    heapq.heapify(heap)
    edges = []
    while heap:
        d, v = heapq.heappop(heap)
        d = -d
        if d > len(heap):
            return None                       # 剩下可连接的其他顶点不够
        taken = [heapq.heappop(heap) for _ in range(d)]
        for dw, w in taken:                   # 把 v 与度最大的 d 个顶点相连
            edges.append((v, w))
            if dw + 1 < 0:
                heapq.heappush(heap, (dw + 1, w))
    return edges

def erdos_gallai(seq):
    """当且仅当序列可图时返回 True（Erdős 和 Gallai，1960）。"""
    d = sorted(seq, reverse=True)
    if sum(d) % 2:
        return False
    for k in range(1, len(d) + 1):
        if sum(d[:k]) > k * (k - 1) + sum(min(x, k) for x in d[k:]):
            return False
    return True

print(len(havel_hakimi([6, 4, 3, 3, 3, 3, 1, 1])))
# 12
print(havel_hakimi([4, 4, 4, 1, 1]), erdos_gallai([4, 4, 4, 1, 1]))
# None False
print(havel_hakimi([3, 3, 3, 3, 3]), erdos_gallai([3, 3, 3, 3, 3]))
# None False

对于 (4, 4, 4, 1, 1)，Erdős–Gallai 不等式在 k = 3处不成立：最大的三个度之和为 12，但上界是 3 × 2 + 1 + 1 = 8。两个函数都与穷举法做了对照，覆盖了全部 2,353 个长度为 n ≤ 7、各项至多为 n − 1的非增序列；我们还检验了 Havel–Hakimi 函数返回的确实是一个度恰好符合要求的简单图。一个可图序列通常有许多不同的实现，所以一个度序列描述的是一族图，而不是一个图。

6. 较大的最小度能保证什么

强迫每个顶点都有很多邻居，就会强迫出结构。下面前三个事实的论证都是同一个想法的变体：尽可能走远，然后看最后一个顶点的邻居都在哪里。

• δ ≥ 2 迫使图中存在环。取一条最长路径。它的最后一个顶点至少有两个邻居，而且这些邻居全都在这条路径上，否则路径还可以延长。其中至少有一个不是它的前驱，那条边就闭合成一个环。
• δ ≥ k 迫使图中存在一条至少有 k 条边的路径。同一条最长路径必须包含其最后一个顶点的全部 δ 个邻居，所以它至少有 δ + 1 个顶点。
• δ ≥ (n − 1) / 2 迫使图连通。位于不同连通分量中的两个顶点，各自都需要在自己的分量内至少有 (n − 1) / 2 个邻居，这样两个分量合起来将包含超过 n 个顶点。

这类结果中最著名的是关于哈密顿回路的，即恰好经过每个顶点一次的回路。一般情况下，判定哈密顿回路是否存在是 NP 完全问题，但较大的最小度就能解决这个问题。

Dirac 定理（1952）。每个有 n ≥ 3 个顶点、最小度至少为 n / 2 的简单图都有哈密顿回路。

Ore 在 1960 年加强了这一结论：只需每两个不相邻顶点的度之和至少为 n即可。阈值 n / 2 不能再降低。完全二分图 K2,3 有五个顶点，最小度为 2，略低于 5 / 2，而它没有哈密顿回路，因为经过全部五个顶点的回路必须在两侧之间交替，而两侧的大小不同。

示例网络的 δ = 1，远低于 8 / 2，而且它没有哈密顿回路：回路永远无法经过像 G这样只有一条边的叶子。Dirac 条件是充分的而非必要的，所以不满足它本身并不能证明什么；这里真正的原因是叶子。

7. 最大度给出的上界

最大度控制着着色。按任意顺序逐个给顶点着色，每次都给它分配其已着色邻居没有用过的最小颜色。一个顶点至多有 Δ 个邻居，所以至多有 Δ 种颜色被占用，前 Δ + 1 种颜色中总有一种可用。

每个图都能用至多 Δ + 1 种颜色正常着色，而且贪心算法按任何顶点顺序都能做到。

Brooks 在 1941 年证明，除了恰好两类例外，少用一种颜色就够了：一个连通图需要 Δ + 1 种颜色，仅当它是完全图或奇环。奇环的 Δ = 2，需要 3 种颜色；而 Kn 的 Δ = n − 1，需要 n种颜色。对于边着色，界甚至更紧：Vizing 在 1964 年证明，每个简单图的边都可以用 Δ 或 Δ + 1 种颜色着色。

在示例中， Δ = 6，所以贪心着色保证至多使用 7 种颜色，而 Brooks 定理把上界降到 6。真实答案是 4，因为示例包含由 A、 B、 C 和 D构成的完全图，它需要 4 种颜色，而 4 种也就够了。当某个顶点远比其他顶点繁忙时，最大度只是一个粗糙的上界。Welsh 和 Powell 1967 年的启发式方法按度递减的顺序给顶点着色，是一种应对办法；下一节给出一个更精确的办法。

8. 退化度与 k 核

枢纽顶点 A 抬高了 Δ，却没有让图变得难以着色。更好的度量看的是图在各处有多稀疏，而不是它那个最繁忙的顶点。反复删除当前剩余度最小的顶点。删除时遇到过的最大度就是图的退化度。等价地说， k 核是使每个顶点在其中都至少有 k 个邻居的最大子图，这一概念由 Seidman 于 1983 年提出；而退化度就是使 k 核非空的最大 k 值。

如果按当前的度把顶点放进桶里，剥离过程可以在线性时间内完成。Matula 和 Beck 在 1983 年给出了这样一种线性时间的“最小者最后”（smallest-last）排序，而 Batagelj 和 Zaveršnik 的桶算法能在 O(m)时间内算出每个顶点的核数：

def core_numbers(adj):
    """每个顶点的核数：反复剥离剩余度最小的顶点。"""
    deg = {v: len(adj[v]) for v in adj}
    buckets = [set() for _ in range(max(deg.values(), default=0) + 1)]
    for v, d in deg.items():
        buckets[d].add(v)
    core, k = {}, 0
    for _ in range(len(adj)):
        d = next(i for i, b in enumerate(buckets) if b)   # 最小的非空桶
        k = max(k, d)                         # 核数永远不会回落
        v = buckets[d].pop()
        core[v] = k
        for w in adj[v]:
            if w not in core:                 # w 失去一个邻居：把它下移一个桶
                buckets[deg[w]].remove(w)
                deg[w] -= 1
                buckets[deg[w]].add(w)
    return core

edges = ['AB', 'AC', 'AD', 'BC', 'BD', 'CD', 'AE', 'DE', 'AF', 'EF', 'FG', 'AH']
adj = {v: set() for v in 'ABCDEFGH'}
for u, v in edges:
    adj[u].add(v)
    adj[v].add(u)

core = core_numbers(adj)
print(dict(sorted(core.items())))
# {'A': 3, 'B': 3, 'C': 3, 'D': 3, 'E': 2, 'F': 2, 'G': 1, 'H': 1}
print(max(core.values()))                     # 图的退化度
# 3

示例的退化度为 3，远低于它的 Δ 值 6。这对着色很重要，因为按剥离顺序的逆序进行贪心着色时，每个顶点至多有 退化度 个已着色的邻居，所以至多使用 退化度 + 1 种颜色：这里是 4 种，恰好是最优的。退化度还限定了团枚举的工作量，按退化度顺序处理顶点是那里的标准加速手段；k 核也是观察大型网络时常用的第一步：内层的核是紧密相连的中心，外层的壳则是外围。

9. 友谊悖论

1991 年，社会学家 Scott Feld 指出了一件听起来像是冒犯的事：平均而言，你的朋友比你拥有更多的朋友。这不是关于人的事实，而是关于度的事实，第 3 节的程序已经为示例算出了它。平均度是 3，而朋友的平均度是 3.75。

原因在于抽样偏差。对人取平均时，每个人只计一次。对朋友取平均时，你要遍历每一段朋友关系，看看另一端的那个人，于是一个有 d 个朋友的人会被计入 d 次。受欢迎的人在别人的朋友列表中占比过高，恰恰是因为他们受欢迎。用公式表示，平均度是 ∑ d / n，而朋友的平均度是 ∑ d² / ∑ d，Cauchy–Schwarz 不等式表明后者永远不小于前者，且仅当每个顶点的度都相同时才取等号。

图中展示的是一个相关的、逐人比较的版本：八个人中有六个人的朋友数少于自己朋友们的平均朋友数，只有 A 和 D 领先。极端情形是星形图：在有九片叶子的星形图中，平均度为 1.8，而朋友的平均度为 5，每片叶子的朋友数都少于它唯一那个朋友的朋友数。不过，使用逐人比较的版本时要小心。上面的不等式说的是平均值，并不保证有多少个体会低于平均。尽管如此，在真实网络中这个效应依然很强：在 Ugander 等人 2011 年对 Facebook 图的研究中，92.7% 的用户的朋友数少于其朋友们的平均朋友数。

这个悖论有实际用途。随机选一个人，再取他的一个朋友，是比随机抽样更好的找到高连接度者的方法；正因如此，有人提出通过抽样随机人群的朋友来尽早发现流行病，给熟人接种疫苗也能比随机接种保护更多的人。

10. 真实网络中的度分布

对于大型网络，度的列表太长而无法逐一阅读，因此用度分布来概括：对每个 k，度为 k的顶点所占的比例。它的形状很能说明网络是如何形成的。

• 随机图在 Erdős–Rényi 模型中（每对顶点独立地相连），其度紧密地集中在平均值附近，几乎没有顶点远离平均值。
• 许多真实网络则截然不同：大多数顶点的度很小，少数枢纽的度却极大。Barabási 和 Albert 在 1999 年提出，优先连接（新顶点倾向于连接已经受欢迎的顶点）会产生幂律分布，“无标度网络”这个术语由此流传开来。
• 真正的幂律有多普遍，至今存在争议。 Broido 和 Clauset 在 2019 年检验了 927 个网络数据集，发现只有其中一小部分有很强的无标度结构证据。重尾的度分布很常见；干净的幂律却不常见。

有两个基于度的度量在网络分析中经常出现。度中心性就是简单地按度给顶点排名，是对“谁重要”这个问题最廉价的回答。而同配性（由 Newman 于 2002 年提出）衡量度大的顶点是否倾向于与其他度大的顶点相连。Newman 发现社交网络是同配的，而许多技术网络和生物网络是异配的，其中的枢纽主要与度小的顶点相连。示例网络也是异配的：它的枢纽 A 是两片叶子唯一的朋友。

11. 有向图：入度与出度

在有向图中，每条弧都有一个尾和一个头，所以一个顶点有入度（到达它的弧数）和出度（离开它的弧数）。握手引理相应地一分为二：每条弧给某个出度贡献 1，也给某个入度贡献 1，所以

∑ in-deg(v)  =  ∑ out-deg(v)  =  m          弧的条数

注意这里少了因子 2，这是从无向图转到有向图时常见的失误。有向图中的度有其特有的含义。入度为 0 的顶点称为源点，出度为 0 的顶点称为汇点；拓扑排序的 Kahn 算法正是从源点出发，靠不断降低入度来推进。一个连通的有向图存在恰好经过每条弧一次的回路，当且仅当每个顶点的入度都等于出度。在网页图中，入度是衡量受欢迎程度的第一个指标，PageRank 则按来源的重要性给每个入链加权，从而细化了这个量。

12. 常见错误

13. 术语表

15. 参考文献

以上定义、定理和归属均出自以下文献，按时间顺序排列。

1. Euler, L. (1736). "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Petropolitanae 8（1741 年出版），128 至 140 页。握手引理背后的观察，以桥和陆地区域的形式表述。
2. Brooks, R. L. (1941). "On Colouring the Nodes of a Network." Proceedings of the Cambridge Philosophical Society 37(2)，194 至 197 页。
3. Dirac, G. A. (1952). "Some Theorems on Abstract Graphs." Proceedings of the London Mathematical Society s3-2(1)，69 至 81 页。
4. Havel, V. (1955). "Poznámka o existenci konečných grafů." Časopis pro pěstování matematiky 80(4)，477 至 480 页。关于有限图存在性的一个注记。
5. Erdős, P. and Gallai, T. (1960). "Gráfok előírt fokszámú pontokkal." Matematikai Lapok 11，264 至 274 页。具有给定顶点度数的图。
6. Ore, O. (1960). "Note on Hamilton Circuits." American Mathematical Monthly 67(1)，55 页。
7. Hakimi, S. L. (1962). "On the 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 页。
8. Vizing, V. G. (1964). "On an Estimate of the Chromatic Class of a p-Graph." Diskretnyi Analiz 3，25 至 30 页。
9. Welsh, D. J. A. and Powell, M. B. (1967). "An Upper Bound for the Chromatic Number of a Graph and Its Application to Timetabling Problems." The Computer Journal 10(1)，85 至 86 页。
10. Matula, D. W. and Beck, L. L. (1983). "Smallest-Last Ordering and Clustering and Graph Coloring Algorithms." Journal of the ACM 30(3)，417 至 427 页。
11. Seidman, S. B. (1983). "Network Structure and Minimum Degree." Social Networks 5(3)，269 至 287 页。k 核。
12. Feld, S. L. (1991). "Why Your Friends Have More Friends Than You Do." American Journal of Sociology 96(6)，1464 至 1477 页。
13. Barabási, A.-L. and Albert, R. (1999). "Emergence of Scaling in Random Networks." Science 286(5439)，509 至 512 页。
14. Newman, M. E. J. (2002). "Assortative Mixing in Networks." Physical Review Letters 89(20)，208701。
15. Ugander, J., Karrer, B., Backstrom, L. and Marlow, C. (2011). "The Anatomy of the Facebook Social Graph." arXiv:1111.4503.
16. Batagelj, V. and Zaveršnik, M. (2011). "Fast Algorithms for Determining (Generalized) Core Groups in Social Networks." Advances in Data Analysis and Classification 5(2)，129 至 145 页。2003 年首次以“An O(m) Algorithm for Cores Decomposition of Networks”为题流传。
17. Broido, A. D. and Clauset, A. (2019). "Scale-Free Networks Are Rare." Nature Communications 10，1017。
18. Diestel, R. (2017). Graph Theory，第 5 版。Graduate Texts in Mathematics 173。柏林：Springer。