минимальная вырезать/максимальный поток в ориентированном графе

Question

У меня Ориентированный граф

Во-первых, я использовал алгоритм Форда-Фалкерсона, чтобы увеличить поток сети. Когда я отметил вершины, я увидел, что поток на пути: s->a->b->d->t может быть увеличен на один так график изменен на:

Я знаю, что при поиске максимального потока, необходимо сложить все capacaties ребер, соединяющих минимальный разрез и внешнюю часть графика. Мой минимальный разрез содержит вершины: s, a, c, поэтому когда я добавил все границы, которые я получил c(G, !G) = 3 + 2 +2 + 1, однако, это намного больше, чем течь t которая 5.

Что я делаю неправильно, я испортил с FF или минимальным разрезом?

Answer 1

You минимальный разрез нет s, a, c, но s, a, b, c. Его емкость составляет 5, что является максимальным потоком, который вы рассчитали.

Вы можете найти минимальный разрез, используя определение остаточной сети . Напомним, что Ford-Fulkerson завершает работу, когда в остаточной сети нет путей между s и t.

Минимальное сократить (S,T) определяется как

S = { v | there exists a path from s to v in the residual network } 

В вы график, узел b достижима из c в остаточной сети, из-за потока b->c с весом 3.