图的度序列与图实现问题 度序列是指图中每个顶点的度按非递增顺序排列成的序列。例如，图 \( G \) 的顶点度为 \( (3,2,2,1) \)，则其度序列为 \( (3,2,2,1) \)。度序列是图的基本不变量，但并非每个非负整数序列都能对应一个简单图（无重边无自环）。 1. 度序列的可图化判定（Graphic Sequence） 一个非负整数序列 \( (d_ 1, d_ 2, \ldots, d_ n) \)（满足 \( d_ 1 \geq d_ 2 \geq \ldots \geq d_ n \)）称为 可图化的 ，如果存在一个简单图以其为度序列。判定定理如下： Erdős–Gallai 定理 序列 \( (d_ 1, \ldots, d_ n) \) 是可图化的当且仅当： 度之和 \( \sum_ {i=1}^n d_ i \) 为偶数（握手引理）； 对任意 \( k \)（\( 1 \leq k \leq n \)），满足 \[ \sum_ {i=1}^k d_ i \leq k(k-1) + \sum_ {i=k+1}^n \min(d_ i, k). \] 该条件保证了前 \( k \) 个顶点之间的边数不超过可能的最大边数（前 \( k \) 点内部完全图有 \( k(k-1) \) 条边，与其余点最多连 \( k \) 条边）。 Havel–Hakimi 算法 更实用的判定方法： 将序列降序排列； 设首项为 \( d_ 1 \)，将后续 \( d_ 1 \) 项各减 1（表示顶点 1 与这些顶点连边）； 移除首项，重新降序排列剩余序列； 重复直到所有项为 0（可图化）或出现负数（不可图化）。 2. 度序列的唯一实现问题 同一个度序列可能对应多个不同构的图。例如，度序列 \( (2,2,2,2) \) 可对应 4 边形或两个不连通的 2 边形。但某些度序列具有 唯一实现 （up to isomorphism），如 \( (2,1,1) \) 只能对应一条 3 个顶点的路径。 关键性质 ： 若度序列满足 Erdős–Gallai 定理的边界条件（如某不等式取等），可能限制图的构造； 树图的度序列必然满足 \( \sum d_ i = 2(n-1) \) 且所有 \( d_ i \geq 1 \)，但实现可能不唯一。 3. 度序列的极值问题 给定度序列，可研究其对应图的最大/最小边数、直径、连通性等。例如： 最大边数 ：度序列固定时，边数固定（由握手引理决定）； 最小直径 ：如何构造图使直径最小？这类问题涉及“度序列可行性”的扩展。 4. 有向图度序列 对有向图，度序列分为 出度序列 和 入度序列 。判定定理为 Gale–Ryser 定理 （对二分度序列）或 Fulkerson–Chen–Anstee 定理 （有向图版本），要求出度序列与入度序列和相等，且满足类似 Erdos–Gallai 的不等式组。 5. 概率与随机度序列 在随机图模型中（如配置模型），给定度序列可生成随机图，用于研究典型性质（如连通性、圈存在性）。此时度序列的分布（如幂律分布）会影响图的宏观特征。 6. 应用 网络分析 ：社交网络中度序列反映节点影响力分布； 化学图论 ：分子结构的度序列与稳定性相关； 算法设计 ：生成特定度序列的图用于测试算法性能。 通过度序列，我们可在不已知图结构时推断其部分性质，这是图重构与网络推断的重要工具。