算法 - 平衡断开连接的二分图

Question

我有一个二分图 G。我想找到一种快速算法（渐近地）来找到将 G 的所有顶点分配到两个集合 X 和 Y 中的完整二分图，使得集合 X 和 Y 有尽可能多的边。

稍微长一点的解释:

G 是二分的，由一组连接的组件组成（显然，每个组件都是二分的）。我们想确定每个组件在 X 和 Y 中的定位（因为缺少更好的词）。在决定了所有的定位之后，我们完成了二分图（即我们将 X 的每个顶点连接到 Y 的每个顶点）。然后我们计算出总共有多少条边（包括原始边），我们想要最大化这个计数。简单的数学表明边数为 |X|*|Y|.

我对解决方案的思考过程：

随着组件数量的增加，G的选择数量呈指数增长。但是，如果我们将 G 的连通分量数等于 G 中的节点数，那么解决方案很简单 - 拆分使得 X 和 [= 中的节点数13=] 相等（或在 G 中节点数为奇数的情况下几乎相等）。这让我想总结一下，这个问题与试图最小化 X 和 Y 的基数差异（可以像 this SO question 中那样解决）是一回事。然而，我一直未能证明这一点。

Answer 1

让我们分解问题。

你的图实际上是一组连接的组件，每个连接组件是 (U_i,V_i,E_i).
要最大化边数，需要最大化 |X|*|Y|
为了得到|X|*|Y|的最大值，你显然需要使用所有顶点（否则，通过添加另一个顶点，您将获得更大的值）。
你的选择自由实际上是为每个组件选择i - 如果你应该将U_i添加到X，并将V_i添加到Y - 反之亦然。

那么，您实际要做的是：

maximize:
sum { x_i * |V_i| : for each component i} * sum { y_i * |U_i| : for each component i}
subject to constraints:
x_i, y_i in {0,1} for all i
x_i + y_i = 1     for all i

我们想要最大化的值与函数 f(x) = x(k-x) 的行为类似，因为如果我们增加 |X|，它会在减少 |Y| 的范围内出现，并且数量相同.此函数有一个最大值：

f(x) = xk - x^2
f'(x) = k - 2x = 0  ---> x = k/2

意思是，我们应该分配节点，使 X 和 Y 的基数（大小）尽可能彼此接近（并使用所有顶点）。

这可以简化为 Partition Problem:

Given U_1,V_1,U_2,V_2,...,U_k,V_k
Create an instance of partition problem:
abs(|U_1| - |V_1|), abs(|U_2| - |V_2|), ... , abs(|U_k| - |V_k|)

现在，找到的分区问题的最优解可以直接转化为U_i、V_i中的哪个包含在哪个集合中，并确保大小差异保持最小.

算法 - 平衡断开连接的二分图

Algorithm - Balancing a disconnected bipartite graph

algorithm

graph-theory

bipartite