自 2010 年 · 每月支援超過 200 萬次工具執行
自 2010 年
加到 Chrome

我的工具箱

自動模式

尚未收藏任何工具。

升級為高級版
相關工具
圖著色計算機鄰接矩陣計算機最小生成樹計算機戴克斯特拉最短路徑計算機72規則計算機
主頁 > 數學 > 進階數學計算
 

圖度數序列驗證器

用 Havel–Hakimi 演算法判斷度數列能否構成簡單無向圖。附逐步動畫、鄰接矩陣與範例圖。

免費使用無需註冊2026年2月更新
圖度數序列驗證器立即免費試用 ▼

試試這些示例：

簡單圖 三角形 混合度數 3-正則圖 非可圖化 10 個頂點
ℹ 提示： 輸入以逗號或空格分隔的非負整數。每個數字代表圖中一個頂點的度數。序列不需要預先排序。

Embed 圖度數序列驗證器 Widget

圖度數序列驗證器

歡迎使用 圖度數序列驗證器，這是一款功能強大的計算機，使用 Havel-Hakimi 演算法 來確定給定的非負整數序列是否可以形成一個簡單的無向圖。該工具提供演算法的動畫逐步視覺化、有效序列的互動式圖形渲染以及完整的鄰接矩陣，是圖論和離散數學學生、教育工作者和研究人員的理想選擇。

什麼是度數序列？

在圖論中，度數序列 是圖的頂點度數的單調非遞增序列。頂點的度數是與之關聯的邊數。例如，在三角形（3 個頂點，3 條邊）中，每個頂點的度數均為 2，因此度數序列為 (2, 2, 2)。

如果存在至少一個簡單圖（無自環、無多重邊）其頂點度數與該序列匹配，則稱該度數序列為 可圖化的。並非所有的非負整數序列都是可圖化的 —— 例如，(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 個頂點各與另外 2 個連接），而 (3, 1, 1) 不是可圖化的，因為當只有 2 個其他頂點存在時，單個頂點無法連接到 3 個其他頂點。

為什麼度數序列的總和必須是偶數？

這是握手定理的結果，該定理指出任何圖中所有頂點度數的總和等於邊數的兩倍。由於任何整數的兩倍都是偶數，因此度數序列的總和必須為偶數。這是序列可圖化的必要（但非充分）條件。

什麼是 Erdos-Gallai 定理？

Erdős-Gallai 定理提供了一組非遞增非負整數序列必須滿足的等式，才能成為可圖化的。一個序列 d1 >= d2 >= ... >= dn 是可圖化的，若且唯若其總和為偶數，且對於從 1 到 n 的每個 k，前 k 個項的總和不超過 k(k-1) 加上剩餘項中 min(dk, k) 的總和。Havel-Hakimi 演算法在實踐中通常更受青睞，因為它更容易實現。

其他資源

引用此內容、頁面或工具為：

"圖度數序列驗證器" 於 https://MiniWebtool.com/zh-tw/圖度數序列驗證器/，來自 MiniWebtool，https://MiniWebtool.com/

由 miniwebtool 團隊開發。更新日期：2026年2月19日

開發者 API 可用: 用一次 JSON HTTP 請求，把這個工具接入你的應用程式、自動化流程或代理。 查看 API 文件

您還可以嘗試我們的 AI數學解題器 GPT，通過自然語言問答解決您的數學問題。

進階數學計算:

熱門與最新工具:

平面圖檢查器度到弧度轉換器幾何序列計算機查看全部 →
主頁 > 數學 > 進階數學計算 > 圖度數序列驗證器