графы, поиск максимального потока и минимального разреза

[broccoli]

задачу необходимо решить с помощью метода Форда-Фалкерсона.
граф выглядит следующим образом:


не имею понятия, как это сделать. методичка и всемогущий гугл, увы, меня не спасли. уповаю на вашу помощь, подсказки, любые мысли по этому поводу.

[Nemiroff]

Вики с легкостью выдает формальное и неформально описания алгоритма. А вообще алгоритм Форда-Фалкерсона интуитивно прост: мы ищем какой-нибудь путь, пускаем максимальный поток, модифицируем граф и повторяем, пока у нас получается.
А в вашем случае, вообще по всем ребрам можно пустить максимальный поток, это без всякого алгоритма заметно.

[broccoli]

Вики выдаёт, но мы с ней, видимо, на разных языках говорим :)
максимальный поток - поток равный пропускной способности, так?
я поняла этот алгоритм до места "модифицируем граф" - как? допустим, я пустила по моему графу максимальные потоки (по всем рёбрам, да?), и что дальше? как модифицировать?

[Nemiroff]

Ну смотрите, вы ищете любой путь из истока в сток. Пускаете по нему максимально возможный поток. Уменьшаете пропускную способность всех ребер из этого пути на значение потока (если по ребру путь прямой). Повторяете процедуру.