主題
Search

最小頂點著色

VertexColoring

一個 頂點著色 是將標籤或顏色分配給圖的每個頂點，使得沒有邊連線兩個顏色相同的頂點。最小化給定圖 G 所需顏色數量的頂點著色被稱為 G 的最小頂點著色。顏色的最小數量本身被稱為 色數，記為 chi(G)，色數為 chi(G)=k 的圖被稱為 k-色圖。

Brelaz 的啟發式演算法可以用來找到一個好的，但不一定是最小的頂點著色。找到最小著色可以使用暴力搜尋（Christofides 1971; Wilf 1984; Skiena 1990, p. 214），儘管更復雜的方法可以顯著更快。

使用啟發式方法計算圖的最小頂點著色在 Wolfram 語言 中實現為FindVertexColoring[g].

Mehrotra 和 Trick (1996) 設計了一種列生成演算法，用於計算色數和頂點著色，該演算法可以快速解決大多數中小型圖。

另請參閱

Brelaz 的啟發式演算法, Brooks 定理, 色數, 色多項式, 著色, 邊色數, 邊著色, 四色定理, 圖著色, k-色圖, k-可著色圖, 標記圖, 最小邊著色, 頂點著色

使用 探索

參考文獻

Christofides, N. “圖的色數演算法。” Computer J. 14, 38-39, 1971.Gould, R. (Ed.). 圖論。 Menlo Park, CA: Benjamin-Cummings, 1988.Manvel, B. “極其貪婪的著色演算法。” 在 圖與應用 (Ed. F. Harary 和 J. Maybee). New York: Wiley, pp. 257-270, 1985.Matula D. W.; Marble, G.; and Isaacson, J. D. “圖著色演算法。” 在 圖論與計算 (Ed. R. Read). New York: Academic Press, pp. 109-122, 1972.Mehrotra, A. 和 Trick, M. A. “圖著色的列生成方法。” INFORMS J. on Computing 8, 344-354, 1996.Pemmaraju, S. 和 Skiena, S. 計算離散數學：Mathematica 中的組合數學和圖論。 Cambridge, England: Cambridge University Press, 2003.Skiena, S. “尋找頂點著色。” §5.5.3 in 實現離散數學：Mathematica 中的組合數學和圖論。 Reading, MA: Addison-Wesley, pp. 214-215, 1990.Soifer, A. 新數學著色書：著色數學及其創造者的多彩生活。 New York: Springer, 2024.Thomassen, C. “固定表面上圖的 k-著色的數量。” Disc. Math. 306, 3145-3153, 2006.Wilf, H. “回溯：圖著色問題的 O(1) 預期時間演算法。” Info. Proc. Let. 18, 119-121, 1984.

請引用為

Weisstein, Eric W. “最小頂點著色。” 來自 —— 資源。 https://mathworld.tw/MinimumVertexColoring.html

學科分類