自 2010 年 · 每月支持超过 200 万次工具运行
自 2010 年
添加到 Chrome

我的工具箱

自动模式

还没有收藏的工具。

升级为高级版
相关工具
图着色计算器邻接矩阵计算器最小生成树计算器迪杰斯特拉最短路径计算器72规则计算器
主页 > 数学 > 进阶数学计算
 

图度数序列验证器

使用 Havel-Hakimi 算法确定给定的数字序列是否可以形成一个简单的无向图。具有动画分步可视化、邻接矩阵和样本图渲染功能。

免费使用无需注册2026年2月更新
图度数序列验证器立即免费试用 ▼

尝试以下示例：

简单图 三角形 混合度数 3-正则图 非可图化 10 个顶点
ℹ 提示： 输入由逗号或空格分隔的非负整数。每个数字代表图中一个顶点的度数。序列不需要预先排序。

Embed 图度数序列验证器 Widget

图度数序列验证器

欢迎使用图度数序列验证器，这是一个功能强大的工具，它使用 Havel-Hakimi 算法来确定给定的非负整数序列是否可以构成一个简单的无向图。本工具提供算法的分步动画演示、有效序列的交互式图形渲染以及完整的邻接矩阵，是图论和离散数学领域的学生、教育工作者和研究人员的理想选择。

什么是度数序列？

在图论中，度数序列是图中各个顶点度数的单调非递增序列。顶点的度数是与之相连的边的数量。例如，在一个三角形（3 个顶点，3 条边）中，每个顶点的度数均为 2，因此其度数序列为 (2, 2, 2)。

如果至少存在一个简单图（无自环，无重边）的顶点度数与该序列匹配，则该度数序列被称为可图化的 (graphical)。并非所有的非负整数序列都是可图化的 —— 例如，(3, 1, 1) 就不是可图化的，因为其中一个顶点需要 3 条连接，但总共只有另外 2 个顶点存在。

Havel-Hakimi 算法

Havel-Hakimi 算法（以 Václav Havel 和 Samuel Louis Hakimi 命名）是一种递归算法，用于确定给定的有限非负整数序列是否是可图化的。它是离散数学中最优雅的算法之一。

算法步骤

function HavelHakimi(sequence):
  while 序列不为空:
    按非递增顺序排序序列
    移除前导零
    if 序列为空: return 可图化
    d ← 第一个元素 // 最大度数
    移除第一个元素
    if d > 剩余元素数量: return 非可图化
    从接下来的 d 个元素中各减去 1
    if 任何元素变为负数: return 非可图化
  return 可图化

Havel-Hakimi 定理

Havel-Hakimi 定理

对于 \( n \geq 1 \)，非递增非负整数序列 \( d_1 \geq d_2 \geq \cdots \geq d_n \) 是可图化的当且仅当序列

$$d_2 - 1,\; d_3 - 1,\; \ldots,\; d_{d_1+1} - 1,\; d_{d_1+2},\; \ldots,\; d_n$$

是可图化的。

握手定理 (Handshaking Lemma)

任何度数序列的一个基本前提是握手定理：

握手定理
$$\sum_{i=1}^{n} d_i = 2|E|$$

所有顶点度数的总和等于边数的两倍。

这直接意味着度数序列的总和必须是偶数。如果总和为奇数，该序列绝对不可能是可图化的 —— 不存在对应的图实现。

Erdos-Gallai 定理

可图化序列的另一种特征描述由 Erdős–Gallai 定理给出：

Erdős–Gallai 定理

非递增序列 \( d_1 \geq d_2 \geq \cdots \geq d_n \) 是可图化的，当且仅当其总和为偶数，且对于每个 \( k = 1, 2, \ldots, n \)：

$$\sum_{i=1}^{k} d_i \leq k(k-1) + \sum_{i=k+1}^{n} \min(d_i, k)$$

虽然 Erdős–Gallai 定理给出了闭式特征描述，但在实践中，Havel-Hakimi 算法因其简单性以及能够构造性地构建图形而更受青睐。

如何使用此工具

  1. 输入度数序列： 输入由逗号或空格分隔的非负整数列表。可以使用快速示例开始。
  2. 点击验证： 工具将检查奇偶性条件并运行 Havel-Hakimi 算法。
  3. 观看动画： 使用步骤控制按钮（播放、下一步、显示全部、重置）来可视化算法的每次迭代。
  4. 查看结果： 对于可图化序列，可以查看示例图形渲染和邻接矩阵。

理解结果

  • 结论： 序列是否是可图化的（是否能构成简单图）。
  • 奇偶性检查： 度数之和是否为偶数（必要条件）。
  • 算法步骤： 带有颜色标记元素追踪的 Havel-Hakimi 每次迭代过程。
  • 图形可视化： 实现该度数序列的一个简单图示例（如果是可图化的）。
  • 邻接矩阵： 示例图的 0/1 矩阵表示。

度数序列的应用

网络设计

在设计通信或运输网络时，工程师需要知道预期的连接模式是否可以实现。度数序列验证可确保规划的网络拓扑在投入资源之前是可实现的。

社会网络分析

在社会科学中，研究人员将社交网络建模为图。度数序列描述了连接的分布情况。验证观察到的度分布是否能形成简单网络有助于建模和模拟研究。

生物信息学

蛋白质相互作用网络和基因调节网络被建模为图。度数序列分析帮助研究人员了解网络属性，并生成具有相同度分布的随机图以进行零模型测试。

算法设计教育

Havel-Hakimi 算法是离散数学课程的基石。它展示了核心概念：贪心算法、数学归纳法和图的实现。此工具帮助学生直观地理解算法的每一步。

常见问题解答

什么是图论中的度数序列？

度数序列是一个非负整数列表，表示图中连接到每个顶点的边数。例如，序列 (3, 2, 2, 1) 表示一个顶点有 3 条边，两个顶点各有 2 条边，一个顶点有 1 条边。有效的（可图化的）度数序列必须具有偶数和，因为每条边对总度数的贡献为 2。

什么是 Havel-Hakimi 算法？

Havel-Hakimi 算法是一种递归方法，用于确定有限非负整数序列是否可以作为简单图的度数序列。它的工作原理是反复按降序排列序列，移除最大的元素 d，并从接下来的 d 个元素中各减去 1。如果过程减少到全零，则序列是可图化的；如果出现负数或 d 超过剩余数量，则不是。

序列“可图化”是什么意思？

如果存在一个简单无向图（无自环，无重边），其顶点度数恰好匹配该序列，则称该非负整数序列为可图化的。例如，(2, 2, 2) 是可图化的，因为它可以形成一个三角形，而 (3, 1, 1) 则不是，因为当只有 2 个其他顶点时，单个顶点无法连接到 3 个顶点。

为什么度数序列的和必须是偶数？

这是握手定理的结果，该定理指出图中所有顶点的度数之和等于边数的两倍。由于任何整数的两倍都是偶数，因此度数序列之和必须为偶数。这是序列可图化的必要（但非充分）条件。

什么是 Erdos-Gallai 定理？

Erdos-Gallai 定理提供了一组非递增非负整数序列必须满足的不等式，才能成为可图化的。序列 d1 >= d2 >= ... >= dn 是可图化的，当且仅当其总和为偶数，且对于从 1 到 n 的每个 k，前 k 项之和至多等于 k(k-1) 加上剩余项中 min(dk, k) 的总和。在实践中通常首选 Havel-Hakimi 算法，因为它更容易实现。

额外资源

引用此内容、页面或工具为：

"图度数序列验证器" 于 https://MiniWebtool.com/zh-cn/图度数序列验证器/，来自 MiniWebtool，https://MiniWebtool.com/

由 miniwebtool 团队提供。更新日期：2026年2月19日

开发者 API 可用: 用一次 JSON HTTP 请求，把这个工具接入你的应用、自动化流程或智能体。 查看 API 文档

您还可以尝试我们的 AI数学解题器 GPT，通过自然语言问答解决您的数学问题。

进阶数学计算:

热门与最新工具:

平面图检查器度到弧度转换器几何序列计算器查看全部 →
主页 > 数学 > 进阶数学计算 > 图度数序列验证器