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