圖度數序列驗證器
使用 Havel-Hakimi 演算法判斷給定的數字序列是否可以構成一個簡單無向圖。具備動畫逐步視覺化、鄰接矩陣和範例圖形渲染功能。
偵測到廣告封鎖，導致我們無法顯示廣告
MiniWebtool 依靠廣告收入免費提供服務。如果這個工具幫到你，歡迎升級 Premium（無廣告 + 更快），或將 MiniWebtool.com 加入允許清單後重新整理頁面。
- 或升級 Premium（無廣告）
- 允許 MiniWebtool.com 顯示廣告，然後重新載入
圖度數序列驗證器
歡迎使用 圖度數序列驗證器，這是一款功能強大的計算機，使用 Havel-Hakimi 演算法 來確定給定的非負整數序列是否可以形成一個簡單的無向圖。該工具提供演算法的動畫逐步視覺化、有效序列的互動式圖形渲染以及完整的鄰接矩陣，是圖論和離散數學學生、教育工作者和研究人員的理想選擇。
什麼是度數序列？
在圖論中，度數序列 是圖的頂點度數的單調非遞增序列。頂點的度數是與之關聯的邊數。例如，在三角形（3 個頂點，3 條邊）中，每個頂點的度數均為 2，因此度數序列為 (2, 2, 2)。
如果存在至少一個簡單圖（無自環、無多重邊）其頂點度數與該序列匹配，則稱該度數序列為 可圖化的。並非所有的非負整數序列都是可圖化的 —— 例如，(3, 1, 1) 不是可圖化的，因為一個頂點需要 3 個連接，但只存在另外 2 個頂點。
Havel-Hakimi 演算法
Havel-Hakimi 演算法（以 Václav Havel 和 Samuel Louis Hakimi 命名）是一種遞迴演算法，用於確定給定的有限非負整數序列是否是可圖化的。它是離散數學中最優雅的演算法之一。
演算法步驟
while 序列不為空:
按非遞增順序排序序列
移除前導零
if 序列為空: return 可圖化
d ← 第一個元素 // 最大度數
移除第一個元素
if d > 剩餘數量: return 非可圖化
從接下來的 d 個元素中各減去 1
if 任何元素變為負數: return 非可圖化
return 可圖化
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)
任何度數序列的基本前提是 握手定理：
所有頂點度數的總和等於邊數的兩倍。
這直接意味著度數序列的總和必須是 偶數。如果總和是奇數，該序列就不可能是可圖化的 —— 不存在對應的圖實現。
Erdos-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 演算法因其簡單性以及能夠構造性地構建圖而在實踐中更受青睞。
如何使用此工具
- 輸入度數序列： 輸入以逗號或空格分隔的非負整數列表。可以使用快速示例開始。
- 點擊驗證： 計算機將檢查奇偶條件並運行 Havel-Hakimi 演算法。
- 查看動畫： 使用步驟控制按鈕（播放、下一步、顯示全部、重置）來視覺化演算法的每次迭代。
- 探索結果： 對於可圖化的序列，可以查看示例圖形渲染和鄰接矩陣。
理解結果
- 判定結果： 序列是否是可圖化的（能否形成簡單圖）。
- 奇偶校驗： 度數總和是否為偶數（必要條件）。
- 演算法步驟： 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日
您還可以嘗試我們的 AI數學解題器 GPT，通過自然語言問答解決您的數學問題。