algorithm - 通过删除边(不超过边/2)将图转换为二分图 - 算法？

Question

假设我们有一个图，您可以删除边(不超过(原始图的边)/2)直到它成为二分图。

假设我们得到:

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}

应该如何解决这个问题？有什么算法可以做到这一点吗？任何形式的解释将不胜感激。

Answer 1

选择一个任意节点作为集合 A 的第一个成员。如果有任何节点链接到它，选择一个作为集合 B 的第一个成员。如果没有，选择任何其他节点作为集合 B 的第一个成员。

现在你有两组节点，A 和 B。重复选择一个不在任何一组中的节点。计算将该节点链接到 A 和 B 中节点的边数。如果有更多边将其链接到集合 A，则删除将其链接到集合 B 中节点的边并将其放入集合 B。否则删除将其链接到的边集合 A 中的节点并将其放入集合 A。请注意，您删除的边不超过连接到该节点的一半。