图度序列与可实现性

形式陈述 ​

非负整数序列 $(d_1,\dots ,d_n)$ 称为可图化，若存在顶点标号为 $1,\dots ,n$ 的有限简单无向图，使各顶点度数按某一顺序恰为这些数。以下总把序列重排为

$$d_1\ge d_2\ge \cdots \ge d_n\ge 0.$$

Havel–Hakimi 定理给出递归判据：若 $d_1\ge n$，序列不可图化；否则删除 $d_1$，把随后 $d_1$ 项各减 $1$，并重新按非增次序排列。原序列可图化，当且仅当约化后的序列非负且可图化。证明使用二边交换：若最高度顶点 $v$ 邻接 $y$ 却不邻接度数不小于 $y$ 的 $x$，可找到 $x$ 的某个邻点 $z\notin \{v,y\}$ 不与 $y$ 邻接，把边 $vy,xz$ 换成 $vx,yz$。所有顶点度数保持不变；反复交换后，$v$ 连接余下最高的 $d_1$ 个需求，删去 $v$ 便得到约化序列。逆向则给约化图补回一个连接这些顶点的新顶点。

Erdős–Gallai 定理给出闭式刻画：非增非负整数序列可图化，当且仅当

$$\sum _{i=1}^n{d}_i\equiv 0(\mathrm{mod}2)$$

且对每个 $k=1,\dots ,n$ 都有

$$\sum _{i=1}^k{d}_i\le k(k-1)+\sum _{i=k+1}^{n}min(d_i,k).$$

必要性来自统计前 $k$ 个顶点的关联边：它们内部最多贡献 $k(k-1)$ 个度，余下每个顶点向该集合最多贡献 $min(d_i,k)$。充分性可由 Havel–Hakimi 约化归纳证明，并验证不等式在每次约化后保持。

直觉 ​

度数是每个顶点尚需连接多少条边的“需求”。Havel–Hakimi 每次先满足最大需求，并把它接到当前需求最大的顶点；交换论证保证这种规范化不会错过一个本来存在的实现。它既是判定过程，也是构造过程。

Erdős–Gallai 不等式则检查任何最高需求的前缀是否向图索取了过多边。左边是前 $k$ 个顶点的总需求，右边是内部边和外部顶点最多能够提供的容量。所有前缀都不过载，再加总度数为偶数，恰好足以保证实现存在。

例子与边界 ​

序列 $(3,3,2,2,2)$ 的 Havel–Hakimi 约化为

$$(3,3,2,2,2)\to (2,2,1,1)\to (1,1,0)\to (0,0),$$

所以它可图化。一个具体实现的边集是

$$\{ab,ac,ad,bc,be,de\},$$

其中 $a,b$ 的度为 $3$，$c,d,e$ 的度为 $2$。

序列 $(3,3,3,1)$ 的度数和为 $10$，满足握手引理公理库握手引理Handshaking lemma有限无向图中所有顶点度数之和等于边数的两倍。给出的偶数必要条件，却不可图化。取 $k=2$，Erdős–Gallai 不等式要求

$$3+3\le 2+min(3,2)+min(1,2)=5,$$

但左边为 $6$，所以失败。这说明偶数度数和远非充分条件。

本页只处理简单无向图。允许重边、自环、有向边或指定二分图两侧度数后，约束与判据都会改变；例如重边可让两个顶点反复满足彼此需求，简单图中的 $d_i\le n-1$ 就不再是同一边界。Havel–Hakimi 每一步还必须重新排序，不能机械地总减原序列的固定位置。

推论与应用 ​

Havel–Hakimi 在每步同时记录新增边，因而能在判定成功时构造一个实现；若出现负数或首项超过剩余长度，则给出失败证书。Erdős–Gallai 提供不依赖具体构造的数值证书，并可借助前缀和高效检查全部不等式。

度序列可实现性是从局部统计恢复全局图公理库有限简单无向图Graph · Finite simple undirected graph · 图用有限顶点集合和无序二元边集合表示的简单无向图。结构的最基本问题。它用于生成满足指定度分布的网络、检验数据中的度数报告，并为随机图的配置模型提供输入边界；但同一可图序列通常有许多非同构实现，度序列本身不能恢复连通性、圈或其他全局结构。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017, section on degree sequences.
• Douglas B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001, Chapter 1.