如何去除邊緣以生成圖形二部分？

我有可能（或可能不）包括一組邊緣，使其二分的曲線圖。我怎麼能發現這樣的一套存在？如何去除邊緣以生成圖形二部分？

將移除所有邊緣BFS遍歷有助於在一個特定的水平？

2014-01-06 user3080029

由於任何二分圖也2-着色的，你可以使用檢查這一特性的任何算法。你可以例如使用基於回溯的算法來處理BFS。一般來說它可能看起來像這樣：

假設如果圖是二分的頂點可分爲組A和B選擇一個源頂點，顏色紅它（A組）。然後將所有相鄰頂點着色爲藍色（B組），然後這些鄰居的鄰居變成紅色。如果在着色過程中你會發現有顏色作爲當前頂點不是2-着色的，因此不雙邊同一個鄰居。這可能不包括所有細節，但你應該明白。

來源

2014-01-06 15:10:35 Draugr

圖爲不偶最初。我需要看到，如果我可以刪除一些邊緣，使其成爲雙方 – user3080029

哦，對不起，現在我得到你的問題，這對我來說不是最初的帖子。您不必計算這一點，保羅·埃爾德什表明，隨e邊緣的任何圖形總是包含至少E/2邊的二分子。我不記得它在哪裏發佈，但你應該很容易地在互聯網上找到它。另外，如果我記得正確的話，圖形的任何切割都是雙向的，所以如果你想實際找到一個圖形，你可能只需要一個獲得最大切割的算法。 – Draugr

如何去除邊緣以生成圖形二部分？

回答

相關問題