圖著色計算機

尋找任何無向圖的色數和有效的頂點著色方案。輸入邊列表或鄰接列表，即可獲取最小顏色數、顏色分配、動畫化的 DSATUR 分步解法以及互動式 SVG 圖表可視化。

圖著色計算機

⚡ 嘗試範例：

4-環 C₄ 三角形 K₃ 完全圖 K₅ 五邊形 C₅ 輪圖 W₆ 二分圖 K₃,₃ 鄰接範例考試排程

輸入格式

⬌ 邊列表

⧇ 鄰接列表

圖形數據

邊格式：A-B 或 A B，以逗號或換行符分隔。最多 60 個頂點和 600 條邊。

鄰接格式：A: B, C, D — 每行一個頂點，後跟其鄰居。

算法

自動模式為小規模圖形選擇精確回溯，為較大規模圖形選擇 DSATUR。

Embed 圖著色計算機 Widget

圖著色計算機

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

什麼是圖著色？

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

著色數定義

χ(G) = min { k : G 允許一個適當的 k-著色 }

主要定理和界限

平凡界限： 對於任何圖形，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-著色來找到真實的著色數。搜索按度數降序排列頂點，並在無顏色可用時進行剪枝。當精確算法成功時，結果會標記為「精確」。

輸入格式

邊列表

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

A-B, B-C, C-D, D-A
A-C

鄰接列表

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

A: B, C, D
B: A, D
C: A
D: A, B

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

如何使用此計算機

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

圖著色的實際應用

考試排程

將每門考試設為一個頂點，並在至少共用一名學生的考試之間連邊。使用 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，因為回溯會變得太慢。對於實際用途，這涵蓋了大多數課堂範例、考試排程問題以及中小型應用。

延伸閱讀

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

"圖著色計算機" 於 https://MiniWebtool.com/zh-tw/圖著色計算機/，來自 MiniWebtool，https://MiniWebtool.com/

由 miniwebtool 團隊提供。更新日期：2026年4月20日

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

其他相關工具:

圖著色計算機

圖著色計算機

什麼是圖著色？

主要定理和界限

此計算機使用的算法

DSATUR (飽和度算法)

Welsh-Powell

貪婪 (輸入順序)

精確回溯

輸入格式

邊列表

鄰接列表

如何使用此計算機

圖著色的實際應用

考試排程

無線電頻率分配

暫存器分配

地圖著色

數獨和約束拼圖

有趣的特殊情況

常見問題

什麼是圖形的著色數？

此計算機使用什麼算法？

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

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

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

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

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

延伸閱讀

其他相關工具:

進階數學計算:

常用工具: