2

我有这样的问题：

我们得到一个二分图。例如

A1 B1
A2 B2
A3 B3
A4

这是邻接表表示（假设图是双向的）

B1 -> A2, A3
B2 -> A2, A3, A4
B3 -> A1

最终结果应该是左侧 (As) 中的所有节点恰好有 1 个传入边，同时 - 我们需要最小化需要从单个 Bs 节点出来的最大边数。在这种情况下，答案将是：

B3 can connect to A1
B2 can connect to A2, A4
B1 can connect to A3

所以这里需要从单个 Bs 节点出来的最大边数是 2。我们不能覆盖所有 As，同时有一个 B 节点没有 2 个边从它出来覆盖 As。

另一个例子：

A1 B1
A2 B2
A3 B3
A4 B4

B1 -> A1, A2, A3
B2 -> A1, A2, A3, A4
B3 -> A1, A2, A3
B4 -> A1, A2, A3

在这种情况下，答案将是：

B1 can connect to A1
B2 can connect to A4
B3 can connect to A3
B2 can connect to A2

这样，我们将只覆盖所有 A 一次，同时我们最小化了需要从单个 B 中取出的最大边数。所以这里需要从单个 Bs 节点出来的最大边数是 1。

另一个例子：

A1 B1
A2 B2
A3 B3
A4
A5
A6

B1 -> A6
B2 -> A1, A2, A3, A4, A5
B3 ->

在这种情况下，答案将是 5，即需要从单个 B 中取出的最大边数是 5。不能少于这个数。

我已经实现了基本的福特富尔克森算法，我知道这也是网络流，但不知道如何与之相关。

如果有人可以对图表提供一些提示，那就太好了。

谢谢

4

2 回答 2

3

找到一个最佳解决方案 - 所有 B 最多有一个出边（如果存在的话）很简单：

  • 向图中添加源和汇。源对于 B 的列表中的所有顶点将具有容量为 1 的出边。
  • 所有(B,A)边的容量都为 1。
  • 所有 A 将有一个外边，其容量为 1 到水槽。
  • 现在，运行流算法将产生 A 中的最大顶点数，每个 B 只有一条出边可以覆盖这些顶点（最优解，如果存在）

编辑：

现在，基于上述想法，并且由于您试图最小化从单个 B 到 A 的最大边数（而不是它们的总数，正如我之前认为的那样），最佳解决方案很简单：

while there is no coverage:
   set capacity(source,b_k) = increase_size() (for each b_k in B)
   run max flow algorithm on the graph suggested above
return last flow found

复杂性是O(E*V*#iterations)（在这个问题f <= V中，如果福特-富尔克森是复杂性O(EV)），#iterations可以在您寻求的最小最大数中线性完成，或者使用指数增加，然后在范围上进行二进制搜索（如 Evkeny Kluev 所建议的），在这个号码的日志中。
由于E=O(V)在二部图中，我们得到总数O(V^2*log(V))

于 2012-10-02T09:31:57.413 回答
2

将所有 A 连接到一个具有容量 1 边的公共汇节点。将所有 B 连接到一个具有可变容量边的公共源节点C。

在这个图中找到最大的网络流量，C当不是每个 A 都被覆盖时增加，否则减少它。这意味着找到C使用二进制搜索的最佳值。

于 2012-10-02T09:39:41.147 回答