algorithm - 将图转换为二分图

Question

我正在阅读 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}

Answer 1

检查图是否为二分图的通用 BFS 算法是：

1. 从顶点 v_0 开始，并将其标记为 s1。
2. 将所有 v_0 的邻居标记为 s2，并将它们排队。
3. 将所有邻居的邻居标记为s1，并排队

如果在任何时候，您将已标记为 s1 的顶点标记为 s2，反之亦然，则该图不是二分图。相反，如果你最终得到一个空队列，你就完成了，你有了你的分区。

编辑

相反，如果您想知道如何从一般的二分图构建二分图，则应首先添加一个度量来比较两种不同的解决方案：否则，删除所有边并将顶点随机分配给两组，将总是从任何给定的图中生成一个（平凡的）二部图。

Answer 2

边二分问题，即删除最小数量的边以使图二分，是 NP-hard。以下是关于如何尽可能有效地解决它的讨论幻灯片。