將圖轉換爲二分圖

我正在閱讀BFS算法的應用。我讀的一個應用程序是檢查天氣給出的圖是否是二分圖。現在我想知道，是否有任何算法將圖轉換爲二分集/圖。將圖轉換爲二分圖

例如，我們有給一組邊的作爲

E = {（4,1），（1,2），（2,3），（7,2），（1， 5），（8,4），（5,8），（8,9）}

並設置頂點

的

V = {1,2,3,4,5， 6,7,8}

我們必須創建二分集/圖。

預期輸出爲： -

S1 = {1，4,8，1,7，3}
S2 = {2,5，6，9}

2013-08-29 YS.

您沒有提供衡量指標來評估轉化與另一個轉化相比的效果。你可以「刪除」儘可能多的邊緣嗎？否則，將兩個頂點分成兩個隨機的子總是一個有效的輸出。 – Save

你期望它爲非二分圖做什麼，例如E = {（1,2），（2,3），（3,1）}？你沒有解釋這一點，而你（或某人）已經低估了這兩種試圖在這種情況下做出明智之舉的解決方案，所以-1。 –

的一般BFS算法檢查一個圖是否爲二部分：

如果，在任何時候，你要標記爲S2已經被標記爲S1，反之亦然頂點，圖不是二分。相反，如果你最終得到一個空隊列，你就完成了，並且你有了你的分區。

編輯

如果你想知道什麼，取而代之的，是如何構建從一般一個二分圖，你應該先添加一個指標來比較兩個不同的解決方案：否則，刪除所有邊並將頂點隨機分配到兩組，將始終從任何給定的一個生成（平凡）二部圖。

2013-08-29 08:12:56 Save

你所回答的只是檢查圖形是否爲二分圖。如果你需要將圖轉換爲二部圖 – yasen

@yasen對不起，我誤解了你的問題。如果您正在尋找一種方法來消除某些邊緣以創建二部圖，則應該提供一種方法來針對另一種方法評分解決方案。閱讀關於您的問題的評論以獲取更多詳情。 – Save

不，我指出，在原始問題中，用戶需要一種算法將圖轉換爲二部圖。你所回答的只是檢查圖形是否是雙方的方法。如果你需要將圖轉換爲二部圖，你應該簡單地刪除連接頂點的所有邊，無論它是s1還是s2。 – yasen

邊緣二分法問題，即刪除邊的最小數目以形成圖二部分，是NP-hard。 Here是關於如何儘可能高效地解決問題的幻燈片。

2013-08-29 12:56:11 adrianN

回答