Может кто-нибудь направить меня на сайт, где даны пошаговые инструкции о том, как применить метод форд-фулкерсон на графике, чтобы найти максимальный поток.
Заранее большое спасибо.
Насколько я знаю ( ссылка ), Википедия ( ссылка ) и первый альтернативный хит Google ( Ссылка ).
Алгоритм маркировки Форда-Фулкерсона (Инициализация) Пусть x - начальный возможный поток (например, x (e) = 0 для всех e в E). (Увеличение потока) Еслив остаточной сети нет пути увеличения от s до t, затем остановите.Настоящий х - это максимальный поток.Если есть путь увеличения потока p, замените поток x на 2. x (e) = x (e) + delta, если e - прямая дуга на p. x (e) = x (e) -дельта, если e - обратная дуга на p.где дельта - это минимальное значение остаточной емкости на р.Повторите этот шаг. Пример исходного кода: Java
Пример исходного кода: Java
также интересна теорема о минимальном разрезе. Максимальный объем потока, проходящего от источника к раковине, равен минимальному срезу кромок и их расходу. я просто завалил этот вопрос в школе: (
http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm