圖度數序列驗證器

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

什麼是度數序列？

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

如果存在至少一個簡單圖（無自環、無多重邊）其頂點度數與該序列匹配，則稱該度數序列為 可圖化的。並非所有的非負整數序列都是可圖化的 —— 例如，(3, 1, 1) 不是可圖化的，因為一個頂點需要 3 個連接，但只存在另外 2 個頂點。

Havel-Hakimi 演算法

Havel-Hakimi 演算法（以 Václav Havel 和 Samuel Louis Hakimi 命名）是一種遞迴演算法，用於確定給定的有限非負整數序列是否是可圖化的。它是離散數學中最優雅的演算法之一。

演算法步驟

Havel-Hakimi 定理

握手定理 (Handshaking Lemma)

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

這直接意味著度數序列的總和必須是 偶數。如果總和是奇數，該序列就不可能是可圖化的 —— 不存在對應的圖實現。

Erdos-Gallai 定理

可圖化序列的另一種特徵描述由 Erdős–Gallai 定理 給出：

雖然 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 演算法在實踐中通常更受青睞，因為它更容易實現。

其他資源

• Erdős–Gallai 定理 - 維基百科
• Havel-Hakimi 演算法 - 維基百科