圖著色計算機

圖著色計算機

圖著色計算機可為任何無向圖計算著色數 χ(G) 和有效的頂點著色。以邊列表或鄰接列表形式輸入圖形，該工具將返回所需的最少顏色數量（確保任何兩個相鄰頂點都不共享同一種顏色），並提供互動式 SVG 視覺化、動畫 DSATUR 軌跡以及每個頂點顏色分配的詳細說明。

什麼是圖著色？

圖形 G = (V, E) 的適當頂點著色是為每個頂點分配一種顏色，使得每條邊的端點顏色都不同。著色數（記作 χ(G)）是使此類著色存在所需的最少顏色數量。計算 χ(G) 在一般情況下是 NP-hard 問題，但該問題具有優美的數學理論和許多實際應用：考試排程、無線電頻率分配、編譯器中的暫存器分配，以及著名的平面地圖四色定理。

主要定理和界限

• 平凡界限： 對於任何圖形，1 ≤ χ(G) ≤ |V|。
• 團下界： χ(G) ≥ ω(G)，其中 ω(G) 是最大團的大小。
• 二分圖特徵： 當且僅當 G 沒有奇環時，χ(G) ≤ 2（König 定理）。
• Brooks 定理： χ(G) ≤ Δ(G)，除非 G 是完全圖或奇環，在這種情況下 χ(G) = Δ(G) + 1。這裡 Δ(G) 是最大度數。
• 四色定理： 每個平面圖都是 4-可著色的。
• 貪婪上界： 任何貪婪算法最多使用 Δ(G) + 1 種顏色。

此計算機使用的算法

DSATUR (飽和度算法)

由 Daniel Brélaz 於 1979 年提出，DSATUR 是圖著色最強大的實用啟發式算法之一。它反覆選擇鄰居已使用最多不同顏色（即其飽和度）的未著色頂點，通過頂點度數打破平局，並為其分配鄰居未使用的小序號顏色。DSATUR 在二分圖和許多結構化圖族上被證明是最佳的，並且可以在幾毫秒內為具有數百個頂點的圖形產生高質量的著色。

Welsh-Powell

Welsh-Powell 算法將頂點按度數降序排序，然後進行貪婪著色。它的運行時間為 O(|V|²)，並保證最多使用 Δ(G) + 1 種顏色。它非常快速，通常是一個很好的初步近似值，儘管在具有多變局部結構的圖形中可能會被 DSATUR 超越。

貪婪 (輸入順序)

最簡單的算法：按輸入順序遍歷頂點，並為每個頂點分配已著色鄰居未使用的小序號顏色。輸出結果對輸入順序很敏感，但隨機排序可以提供一個基準，以便您與更智能的啟發式算法進行比較。

精確回溯

對於小規模圖形（最多約 18 個頂點），計算機可以通過嘗試 k = 2, 3, 4, ... 並嘗試使用深度優先回溯進行 k-著色來找到真實的著色數。搜索按度數降序排列頂點，並在無顏色可用時進行剪枝。當精確算法成功時，結果會標記為「精確」。

輸入格式

邊列表

將每條邊寫成由連字符、空格或箭頭分隔的兩個頂點標籤。使用逗號或換行符分隔邊。頂點標籤可以是字母、數字或下劃線。範例：

鄰接列表

寫出每個頂點、一個冒號以及其鄰居的逗號分隔列表。範例：

自環會被拒絕，因為一個頂點的顏色不能與其自身不同。重複的邊會被自動去重，圖形被視為無向圖。

如何使用此計算機

1. 選擇格式： 使用單選按鈕在邊列表和鄰接列表之間切換。
2. 輸入圖形： 貼上您的數據或點擊其中一個快速範例（三角形、完全圖 K₅、Petersen 樣式輪圖、二分圖 K₃,₃、考試排程）。
3. 選擇算法： 保留「自動」以使用最佳預設值，或強制選擇 Welsh-Powell、貪婪、DSATUR 或精確回溯。
4. 點擊「開始著色」： 著色數、逐色列表、帶有可拖動節點的互動式 SVG 以及動畫逐步軌跡將顯示在下方。
5. 探索： 按下「播放」觀看算法逐步為頂點著色，拖動節點重新排列佈局，並使用「退後」/「下一步」手動查看軌跡。

圖著色的實際應用

考試排程

將每門考試設為一個頂點，並在至少共用一名學生的考試之間連邊。使用 k 種顏色的適當著色可提供具有 k 個時間段的排程，從而確保沒有學生發生衝突。著色數即為所需的最少時間段數量。

無線電頻率分配

處於彼此干擾範圍內的發射器必須在不同的頻率上進行廣播。干擾圖的著色數即為所需的最少頻率數量。

暫存器分配

在編譯器中，變數的存活範圍是頂點；兩個存活範圍在時間上重疊意味著它們之間存在一條邊。k-著色可將變數分配給 k 個 CPU 暫存器而不會發生碰撞。

地圖著色

共享邊界的國家必須分配不同的顏色。四色定理（Appel-Haken, 1976）證明了對於任何平面地圖，四種顏色始終足夠。

數獨和約束拼圖

完成的數獨是 81 個單元格作為頂點的圖形的 9-著色，其邊連接同一行、同一列或 3×3 方格中的單元格。圖著色是許多約束滿足拼圖的數學核心。

有趣的特殊情況

• 完全圖 K_n： χ(K_n) = n。每對頂點都相鄰，因此所有顏色必須不同。
• 環圖 C_n： 如果 n 為偶數，χ(C_n) = 2；如果 n 為奇數，χ(C_n) = 3。
• 樹： 任何具有 ≥ 2 個頂點的樹都有 χ = 2（樹是二分圖）。
• 二分圖： 如果圖形至少有一條邊，則 χ = 2。
• Petersen 圖： 一個著名的 3-正則圖，其 χ = 3。
• 輪圖 W_n： 一個中心頂點連接到一個 n-環。如果 n 為偶數，χ = 3；如果 n 為奇數，χ = 4。

常見問題

什麼是圖形的著色數？

著色數 χ(G) 是為圖形頂點著色所需的最少顏色數量，使得任何兩個相鄰頂點都不共享同一種顏色。二分圖的著色數最多為 2；任何包含三角形的圖形著色數至少為 3；根據 Brooks 定理，除了完全圖和奇環外，著色數絕不超過最大度數。

此計算機使用什麼算法？

對於小規模圖形，計算機會執行精確回溯搜索以找到真實的著色數。對於較大的圖形，它使用 DSATUR 啟發式算法，該算法會反覆為未著色且已著色鄰居最多的頂點著色。您也可以從算法下拉選單中強制選擇 Welsh-Powell 或單純的貪婪算法。

我應該如何輸入我的圖形？

使用邊列表模式每行輸入一條邊，例如 A-B，或使用逗號分隔，如 A-B, B-C, C-A。使用鄰接列表模式寫出每個頂點，後跟冒號及其鄰居，例如 A: B, C。自環會被拒絕，因為一個頂點的顏色不能與其自身不同。

為什麼 DSATUR 並非總能找到真實的著色數？

圖著色是 NP-hard 問題，因此目前尚無已知的快速算法能始終找到最少顏色數量。DSATUR 是一種極佳的實用啟發式算法，通常能匹配真實著色數，但在對抗性圖形中它可能會使用比必要更多的顏色。計算機同時報告使用的顏色和從發現的最大團中獲得的下界，因此您可以判斷答案的緊湊程度。

圖著色在現實世界中有哪些用途？

圖著色模型可用於考試排程（每個考試是一個頂點，衝突是邊，顏色是時間段）、無線電頻率分配（頂點是發射器，邊是干擾）、編譯器中的暫存器分配、地圖著色、數獨求解以及衝突約束下的作業分配。

著色數是否總等於最大團？

不。團數 ω(G) 始終是著色數 χ(G) 的下界，它們在完美圖（如二分圖、樹、區間圖和弦圖）中相等。對於一般圖形，χ(G) 可以嚴格大於 ω(G)；典型的例子是 Mycielski 圖，它們不含三角形但需要任意多的顏色。

此計算機可以處理的最大圖形是多少？

該計算機支援最多 60 個頂點和 600 條邊。對於精確算法，頂點超過約 18 個的圖形可能會回退到 DSATUR，因為回溯會變得太慢。對於實際用途，這涵蓋了大多數課堂範例、考試排程問題以及中小型應用。

延伸閱讀

• 圖著色 — 維基百科
• DSATUR 算法 — 維基百科
• 著色多項式 — 維基百科
• 四色定理 — 維基百科
• Brooks 定理 — 維基百科

其他相關工具:

進階數學計算:

• antilog計算機
• Beta函數計算機
• 二項式係數計算機
• 二項概率分布計算機
• 按位計算機
• 中央極限定理計算機
• 組合計算機 精選
• 互補誤差函數計算機
• 複數計算機
• 熵計算機
• 誤差函數計算機
• 指數衰減計算機-高精度
• 指數增長計算機 高精度
• 指數積分計算機
• 指數計算機-高精度
• 階乘計算機 精選
• 伽瑪功能計算機
• 黃金比例計算機
• 半衰期計算機
• 百分比增長率計算機 精選
• 排列計算機
• 泊松分佈計算機
• 多項式根計算機與詳細步驟
• 機率計算機
• 概率分布計算機
• 比例計算機 精選
• 二次公式計算機 精選
• 科學計算機 精選
• 科學記數法計算機
• 有效數字計算機 新
• 立方和計算機
• 連續數之和計算機
• 平方和計算機
• 真值表產生器 新
• 集合論計算機 新
• 韋恩圖產生器3集合 新
• 中國剩餘定理計算機 新
• 歐拉函數計算機 新
• 擴展歐幾里得演算法計算機 新
• 模乘逆元計算機 新
• 連分數計算機 新
• 戴克斯特拉最短路徑計算機 新
• 最小生成樹計算機 新
• 圖度數序列驗證器 新
• 錯排 子階乘計算機 新
• 斯特林數計算機 新
• 鴿巢原理計算機 新
• 馬可夫鏈穩態分布計算機 新
• 四捨五入計算機 新
• 負二項分布計算機 新
• 重複排列計算機 新
• 模冪運算計算機 新
• 原根計算機 新
• 布林代數化簡器 新
• 卡諾圖 (K-Map) 求解器 新
• 圖著色計算機 新
• 拓撲排序計算機 新
• 鄰接矩陣計算機 新
• 容斥原理計算機 新
• 線性規劃求解器 新
• 旅行推銷員問題求解器 (TSP) 新
• 漢密爾頓路徑檢查器 新