我有一个二分图G我想找到一个快速算法（渐近地）来找到将G的所有顶点分配到两个集合X和Y中的方法，这样由集合X和Y形成的完整的二部图具有尽可能多的边。
稍长的解释：G是二部的，由一组连接的组件组成（显然，每个组件都是二部的）我们想决定每个组件在X和Y中的位置（因为缺少更好的词）在确定所有位置之后，我们完成了二分图（即，我们将X的每个顶点连接到Y的每个顶点）。然后我们计算出总共有多少个边（包括原始边），我们想要最大化这个数。简单的数学计算表明，边的数量将|X|*|Y|。
我对解决方案的思考过程：
随着组件数量的增加，G的选择数量呈指数增长。但是，如果我们将G的连接组件的数目等于G中的节点数目，则解是简单的-拆分，以便X和Y中的节点数目相等（或在G中的节点数目为奇数的情况下几乎相等）。这使我想概括地说，这个问题与试图最小化X和Y的基数差（可以像this SO question中那样解决）是同一回事然而，我一直未能证明这一点。
最佳答案
让我们把问题分解。
图实际上是一组连接的组件，每个组件都是连接的
组件是(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|，它会在减少的的范围内，并且以相同的数量出现。此函数具有单个最大值：f(x) = xk - x^2
f'(x) = k - 2x = 0 ---> x = k/2
也就是说，我们应该分配节点，使
|Y|和X的基数（大小）尽可能彼此最接近（并使用所有顶点）。这可以减少到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，v，i中的哪一个包含在哪一个集合中，并确保大小差异保持最小。