我想找到最大的二分匹配，所以我将使用 Flow Ford Fulkerson 算法，如此处所述。
但是当我实现这个函数时，我只得到了最大流量的值，但我感兴趣的是流量本身，这样我才能找到匹配的。
有谁能够帮我？
我maxFlowFordFulkerson在R中使用了这个函数。
问问题
171 次
1 回答
0
仅使用您找到的函数的输出是无法做到这一点的。除了最大流量的值之外，它还提供了一个最小切割，它提供了一些额外的信息，但仍然不是你想要的。
使用您参考的页面中的示例（为了便于参考，在下面转载）：
> 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 匹配。
于 2019-10-08T08:56:28.360 回答