網絡圖中節點的雙染色

Question

我正在尋找一種很好的算法來在給定的網絡圖上執行2染色（即，在兩種顏色之一中繪製網絡中的每個節點，使得沒有直接的節點對由邊緣連接具有相同的顏色）。如果發生衝突，該算法應該從網絡中刪除節點，但要儘量減少被刪除的節點的數量。有誰知道這樣的算法是否可用（在Python或R中的實現將是一個很大的獎勵）。

謝謝！

Answer 1

在每次迭代中在活動顏色之間交替的任何節點處啓動BFS。顏色節點尚未訪問。對每個連接的組件重複。

如果您到達已訪問的節點u，並且顏色顯示爲當前未激活的顏色，則該圖不是可着色的。

無法有效實施最佳節點刪除。考慮一個帶有至少3個輻條的輪子作爲子圖。一個集線器節點連接到偶數長度> = 4的週期的每個節點。要允許2種着色的最小節點數量爲1，並且實現此目的的解決方案只有1個：移除集線器。

所以車輪檢測是優化稀疏化的先決條件。

然而，this paper證明車輪檢測是np完整的。