6顏色圖頂點着色算法

我想在C++中製作一個算法，它將使用至多6種顏色的平面圖的頂點着色。我只是在尋找一些僞碼來幫助我開始。任何幫助表示讚賞。謝謝。6顏色圖頂點着色算法

2012-01-26 OhioState22

@EdHeal我以爲我們停止標記作業？當然聽起來像這樣。 –

是的。我知道使用一個雙向鏈表，我認爲我應該指定最小j的非空實j度列表的第一個頂點作爲頂點ui。從j度列表中刪除ui。對於在G中與ui相鄰並且保留在某種程度上的每個頂點U'，比如j'，從j'度列表中刪除-u'，並將u'插入到j'-1度列表中。有一個for循環來爲每個頂點分配最小的顏色值（1-6之間），而不是在已經着色的與vi相鄰的頂點上出現。聽上去怎麼樣？ – OhioState22

聽起來像你已經看到了我在下面鏈接的同一篇論文的摘錄。算法很好......那麼問題是什麼？（我最近用Java編寫了這個算法，所以如果你更具體的話可以給出指針）。 –

參見：

兩個線性時間算法五，着色一個平面圖形大衛Matula，貝納Shiloach，羅伯特·塔揚

（只是谷歌這一點，你會發現一個PDF該論文）。

因此，這是一篇關於在O（n）時間內對一個平面圖進行着色的5篇論文，但是它首先對6着色算法進行了簡單的描述。這裏是重要的摘錄（道歉的格式，這只是一個PDF刮）：

算法6顏色。給定鄰接表形式的n個頂點平面圖G，該算法確定G的6-染色。步驟1. [建立度列表。]對於其中0-j-n-1的每個j形成雙倍的< <鏈接度數爲j的所有頂點的列表。 - 步驟2. [標籤頂點最小度數最後。]對於i = n，n - 1，n * - 1 ,. 。。，1指定非空值j的第一個頂點的最小j作爲頂點t/i。從j度列表中刪除vi。對於在G中與tli相鄰的每個頂點U'並且保留在某個度列表中，比如說f，從jr度列表中刪除u'，並在j9-1度列表中插入u'到中。第3步。[顏色頂點]對於i = 1,2 ,. 。。， n，指定頂點t）i是在與相鄰的頂點上未發生的最小顏色值（其必須是一個和六個之間的一些整數）。

來源

2012-01-26 16:43:27

6顏色圖頂點着色算法

回答

相關問題