Research Space for Linear Algebra & Discrete Mathematics
在p6-108頁有定義甚麼是n-著色, 在任兩相鄰點不著同色的情況下, 可以不超過 n 個顏色對每個點來著色, 這就是 n-colorable 的定義因為定理告訴我們 planar graph 一定是 4-colorable, 而你畫得這個圖因為是平面圖, 所以會是 4-colorable, 驗證一下: 假設對這個圖上的那個degree為 4 的點著 0 號顏色, 然後因為其餘的4個點彼此皆不相鄰, 因此可以對它們皆著以 1 號顏色, 那這就是一個正當的著色方法, 所以這個圖事實上也是 2-colorable
啊... 對耶...我一直想成下面4個點因為都相鄰所以要畫不同顏色...謝謝~
張貼留言
在書上對於四色問題的定義是---任意平面圖皆為4著色，看了不是很懂...
2 則留言:
在p6-108頁有定義甚麼是n-著色, 在任兩相鄰點不著同色的情況下, 可以不超過 n 個顏色對每個點來著色, 這就是 n-colorable 的定義
因為定理告訴我們 planar graph 一定是 4-colorable, 而你畫得這個圖因為是平面圖, 所以會是 4-colorable, 驗證一下: 假設對這個圖上的那個degree為 4 的點著 0 號顏色, 然後因為其餘的4個點彼此皆不相鄰, 因此可以對它們皆著以 1 號顏色, 那這就是一個正當的著色方法, 所以這個圖事實上也是 2-colorable
啊... 對耶...
我一直想成下面4個點因為都相鄰所以要畫不同顏色...
謝謝~
張貼留言