通过删除边（不超过 edges/2）将图转换为二分图 - 算法？
Graph to bipartite graph by removing edges (not more than edges/2) - algorithm?
假设我们得到了一个图，您可以删除边（不超过（原始图的边）/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}
应该如何解决这个问题？有什么算法可以做到这一点吗？任何形式的解释将不胜感激。
任意选择一个节点作为集合A的第一个成员。如果有任何节点链接到它，选择一个作为集合B的第一个成员。如果没有，选择任何其他节点作为集合B的第一个成员.
现在你有两组节点，A 和 B。重复选择一个不在任何一组中的节点。计算将该节点链接到 A 和 B 中节点的边数。如果有更多边将其链接到集合 A，则删除将其链接到集合 B 中节点的边并将其放入集合 B。否则删除将其链接到的边集合 A 中的节点并将其放入集合 A。请注意，您删除的边不超过链接到该节点的一半。
假设我们得到了一个图，您可以删除边（不超过（原始图的边）/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}
应该如何解决这个问题？有什么算法可以做到这一点吗？任何形式的解释将不胜感激。
任意选择一个节点作为集合A的第一个成员。如果有任何节点链接到它，选择一个作为集合B的第一个成员。如果没有，选择任何其他节点作为集合B的第一个成员.
现在你有两组节点，A 和 B。重复选择一个不在任何一组中的节点。计算将该节点链接到 A 和 B 中节点的边数。如果有更多边将其链接到集合 A，则删除将其链接到集合 B 中节点的边并将其放入集合 B。否则删除将其链接到的边集合 A 中的节点并将其放入集合 A。请注意，您删除的边不超过链接到该节点的一半。