图度序列与可实现性

形式陈述

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

d_1\ge d_2\ge\cdots\ge d_n\ge0.

空序列由空图实现，作为递归基例；全零序列也可直接由相应数量的孤立点实现。对非空序列，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\equiv0\pmod2

且对每个 $k=1,\ldots,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$ ，满足握手引理给出的偶数必要条件，却不可图化。取 $k=2$ ，Erdős–Gallai 不等式要求

3+3\le2+\min(3,2)+\min(1,2)=5,

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

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

推论与应用

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

度序列可实现性是从局部统计恢复全局图结构的最基本问题。它用于生成满足指定度分布的网络、检验数据中的度数报告，并为随机图的配置模型提供输入边界；但同一可图序列通常有许多非同构实现，度序列本身不能恢复连通性、圈或其他全局结构。

参考资料

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.

形式陈述 ​

反向链接

形式陈述