如何去除边缘以生成图形二部分？

我有可能（或可能不）包括一组边缘，使其二分的曲线图。我怎么能发现这样的一套存在？如何去除边缘以生成图形二部分？

将移除所有边缘BFS遍历有助于在一个特定的水平？

2014-01-06 user3080029

由于任何二分图也2-着色的，你可以使用检查这一特性的任何算法。你可以例如使用基于回溯的算法来处理BFS。一般来说它可能看起来像这样：

假设如果图是二分的顶点可分为组A和B选择一个源顶点，颜色红它（A组）。然后将所有相邻顶点着色为蓝色（B组），然后这些邻居的邻居变成红色。如果在着色过程中你会发现有颜色作为当前顶点不是2-着色的，因此不双边同一个邻居。这可能不包括所有细节，但你应该明白。

来源

2014-01-06 15:10:35 Draugr

图为不偶最初。我需要看到，如果我可以删除一些边缘，使其成为双方 – user3080029

哦，对不起，现在我得到你的问题，这对我来说不是最初的帖子。您不必计算这一点，保罗·埃尔德什表明，随e边缘的任何图形总是包含至少E/2边的二分子。我不记得它在哪里发布，但你应该很容易地在互联网上找到它。另外，如果我记得正确的话，图形的任何切割都是双向的，所以如果你想实际找到一个图形，你可能只需要一个获得最大切割的算法。 – Draugr

如何去除边缘以生成图形二部分？

回答

相关问题