Невозможно сделать это, используя только вывод найденной функции. Помимо значения максимального потока, он также обеспечивает минимальное сокращение, которое предоставляет некоторую дополнительную информацию, но все же не то, что вы ищете.
Используя пример со страницы, на которую вы ссылаетесь (воспроизведено ниже дляпростота использования):
> 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, ничему, 7, 9, 10 и 12 соответственно.