Ford-Fulkerson 最大流量逐步计算？

Question

我目前正在研究基于 R 文档中这段代码的 Ford-Fulkerson 算法：

nodes <- 1:6
arcs <- matrix(c(1,2,1, 1,3,7, 2,3,1, 2,4,3, 2,5,2, 3,5,4, 4,5,1, 4,6,6,
                5,6,2), byrow = TRUE, ncol = 3)
# Maximum flow with Ford-Fulkerson algorithm
maxFlowFordFulkerson(nodes, arcs, source.node = 2, sink.node = 6)

& 得到以下结果：

$`s.cut`
[1] 2 3 1 5

$t.cut
[1] 4 6

$max.flow
[1] 6

结果中表示该网络的最大流量为6

但是，我一直在尝试手工计算最大流量，但无论如何，我得到的最大流量只有5。

这是我能够根据代码示例绘制的可能图：

& 我能够获得的一些可能的流程：

2 --> 4 --> 5 --> 6....................[Capacity: 1]

2 --> 5 --> 4 --> 6(backflow)...[Capacity: 1]

2 --> 5 --> 6............................[Capacity: 1]

2 --> 4 --> 6............................[Capacity: 2]

[Total capacity: 5]

或

2 --> 3 --> 5 --> 6....................[Capacity: 1]

2 --> 4 --> 5 --> 6....................[Capacity: 1]

2 --> 5 --> 4 --> 6 (backflow)...[Capacity: 1]

2 --> 4 --> 6.............................[Capacity: 2]

[Total capacity: 5]

我是不是误解了这个过程？有谁能一步步写出最大流量为6的路径吗？

Answer 1

我认为你的是正确的（最大流量应该是5）。也许你可以尝试 igraph 进行交叉检查，例如

df <- as.data.frame(`colnames<-`(arcs,c("from","to","capacity")))
g <- graph_from_data_frame(df)
res <- max_flow(g,2,6)

这给出了

> res
$value
[1] 5

$flow
[1] 0 0 0 3 2 0 0 3 2

$cut
[1] 4 9

$partition1
+ 4/6 vertices, named, from bfc5f42:
[1] 1 2 3 5

$partition2
+ 2/6 vertices, named, from bfc5f42:
[1] 4 6

$stats
$stats$nopush
[1] 4

$stats$norelabel
[1] 3

$stats$nogap
[1] 2

$stats$nogapnodes
[1] 2

$stats$nobfs
[1] 1

Answer 2

无向网络最大流量为6.($t.cut [1] 4 6)

有向网络最大流量为5。（瓶颈在节点5）

命令： maxFlowFordFulkerson（节点，弧，1，source.node = 2，sink.node = 6）

Ford-Fulkerson 最大流量逐步计算？

Ford-Fulkerson maximum flow step-by-step calculation?

r

algorithm

max-flow

ford-fulkerson