1

我有一个关于设计算法以使二分图无环的问题。我希望有人可以在这里帮助我。问题陈述描述如下:

考虑一个无向二分图 G = (U,V,E),其中 U = {u_1, u_2, ...u_M} 是一组 M 个节点,V = {v_1, v_2, ..., v_N} 是一个N 个节点的集合,E 是将 U 中的节点连接到 V 中的节点的边的集合。为简单起见,假设图是连通的和循环的,即具有循环。

目的是设计一种消除循环并将图简化为树或森林的算法,如下所示。算法循环进行。一轮被描述为选择 U 中的每个节点 u_i, i = 1, 2, ..., M, 并移除与其连接的边。如果节点 u_i 是孤立的(即,它没有连接到它的边),我们将忽略它并继续。这样每轮最多删除 M 条边。当图形在某一轮结束时减少为一棵树或森林时,该算法停止。

我想知道是否有可能有一个多项式时间算法(以 M,N 为单位)来设计轮次,以使轮数最小化(用于将图形减少为树/森林)。

4

1 回答 1

0

请参阅Wikipedia上的 Cycle 文章。

要检测任何无向图中的循环,请执行 DFS,维护访问节点列表。如果检测到后边缘,则它是循环的一部分,您可以从图中删除该边缘。没有后边缘的 DFS 没有循环。复杂度为 O(M+N)。

于 2013-02-05T21:49:44.403 回答