r - 从 R 中的 maxFlowFordFulkerson 恢复最大二分匹配

Question

我想找到最大的二分匹配，所以我将使用 Flow Ford Fulkerson 算法，如此处所述。

但是当我实现这个函数时，我只得到了最大流量的值，但我感兴趣的是流量本身，这样我才能找到匹配的。

有谁能够帮我？

我maxFlowFordFulkerson在R中使用了这个函数。

标签： rgraph-theorymathematical-optimizationbipartiteford-fulkerson

Answer 1

仅使用您找到的函数的输出是无法做到这一点的。除了最大流量的值之外，它还提供了一个最小切割，它提供了一些额外的信息，但仍然不是你想要的。

使用您参考的页面中的示例（为了便于参考，在下面转载）：

> library("optrees")
> vertices <- 1:14
> edges <- matrix(c(1,2,1, 1,3,1, 1,4,1, 1,5,1, 1,6,1, 1,7,1, 2,9,1, 2,10,1, 4,8,1, 4,11,1, 5,10,1, 6,11,1, 7,13,1, 8,14,1, 9,14,1, 10,14,1, 11,14,1, 12,14,1, 13,14,1), byrow = TRUE, ncol = 3)
> maxFlowFordFulkerson(vertices, edges, source.node = 1, sink.node = 14)
$s.cut
[1] 1 3

$t.cut
 [1]  2  4  5  6  7  8  9 10 11 12 13 14

$max.flow
[1] 5

在这里，两个分区中的顶点分别是 2:7 和 8:13，所以这告诉我们顶点 3，即左分区顶部的第二个顶点，仍然不匹配，但除此之外，它没有告诉你任何关于匹配。

如果你想坚持igraph，你可以用maximum.bipartite.matching得到你想要的。由于这个直接在二分图上操作，我们根本不必弄乱辅助源/汇顶点。使用上面的示例：

> library("igraph")
> A <- matrix(c(0,1,1,0,0,0, 0,0,0,0,0,0, 1,0,0,1,0,0, 0,0,1,0,0,0, 0,0,1,1,0,0, 0,0,0,0,0,1), byrow = T, ncol = 6)
> g <- graph.incidence(A)
> maximum.bipartite.matching(g)
$matching_size
[1] 5

$matching_weight
[1] 5

$matching
 [1]  8 NA  7  9 10 12  3  1  4  5 NA  6

这里，左分区用 1:6 表示，右分区用 7:12 表示。从$matching中，我们读到左分区中的 6 个顶点分别与 8、nothing、7、9、10 和 12 匹配。