什麼是圖着色需要？

Question

圖着色的實際應用是什麼？換句話說，爲什麼我們需要使用這種算法來優化顏色的數量（問題的一些重要特徵）。

Answer 1

看起來你對graph coloring有些誤解，可能還有什麼是graph。
實際顏色與此沒有任何關係，圖着色用於解決您在資源有限或其他限制條件下出現的問題。顏色只是您試圖優化的任何資源的抽象，圖形是您問題的抽象。

Web上有大量關於圖論的資源，簡而言之 - 圖是一組元素（稱爲頂點）的抽象表示，其中一些共享連接（稱爲邊）。這當然是最基本的概念，除此之外還可以添加許多其他屬性，例如有向邊，權重等等，但現在這個概念應該足夠了。

圖形經常被用來模擬各種現實世界的問題（有時候還會造成問題，因爲數學家和計算機科學家仍然需要不斷髮表論文），現在我們有很多算法可以有效地處理它們（就複雜性而言），尋找各種可能有趣的歸因方法來解決上述問題。另外，我們有時可以證明一個問題不能用任何有效的算法來解決。圖表着色是其中的一種（或者更確切地說，問題：can a graph be colored in up to k colors，或者問題what is the minimal number of colors needed to color the graph），除非我們正在處理某些圖形的子類型，例如平面圖形（鄰居國家的地圖就是一個很好的例子，因爲它是用於一些有趣的圖形着色證明）。此處的着色意味着在每個頂點附加一個「顏色」或數字，使得沒有連接邊的兩個頂點具有保存值。

其中圖着色可被應用於一個現實生活問題的一個例子：你設計一個編譯器，在給定的程序，你觀察N個變量，並希望，因爲其中許多分配到寄存器儘可能（其餘將不得不泄漏到記憶中，這是較慢和最好的避免）。但是，您的CPU總共只有16個邏輯寄存器。然而，光明的一面 - 你知道哪些變量在相同的上下文和時間中使用，哪些不是。顯然，那些不在一起的人可以使用相同的寄存器。那麼，你可以將所有變量分配到現有的寄存器組中嗎？

要解決這個問題，可以使用變量作爲頂點，以及邊在相同時間範圍內連接每個兩個變量的位置來構建一個圖。用最少數量的「顏色」對圖進行着色會告訴你總共需要多少個寄存器，因爲每種顏色都可以分配給一個寄存器，並且由於着色前提 - 同時存在的2個變量不能同時使用相同的「顏色「（註冊），因爲它們將通過邊緣連接並且不能以相同的方式着色。

Answer 2

A Sudoku solver是圖着色派上用場的典型例子。

請注意，這裏的顏色數量受遊戲規則的限制。圖表着色算法中的「顏色」通常是比喻性的而不是文字。數獨比數字1-9更經常地使用顏色，但是這不會停止圖形着色的相關性。

Answer 3

有很多實用的應用程序依賴於圖着色。例如，頻率分配到蜂窩天線是一個着名的問題。在這個問題中，只能使用少量的頻率（顏色），並將它們分配給天線，以便客戶端始終連接到其中一個天線。當幾個天線的覆蓋區域重疊時會出現問題，在這種情況下，我們希望至少有一個具有獨特頻率（顏色）的天線。在此問題中，不能使用簡單的正確（非單調）着色。

在上面的情況下，我們處理超圖的着色。我們根據着色問題定義超圖。並有顏色的不同變種，如無衝突着色,獨特 - 最大着色。許多研究已經在靜態情況下進行，超圖不隨時間變化。並且在在線設置的情況下有許多有趣的研究正在進行，其中超邊可能隨時間改變（例如，某些天線停止工作，或者新天線固定在某個位置）。

你也可以參考1調查文件閱讀更多關於有趣的着色問題及其應用。