Теорема Форда-Фалкерсона: В транспортной сети величина максимального потока равна пропускной способности минимального разреза.
Алгоритм Форда-Фалкерсона предназначен для определения максимального потока в транспортной сети:
1.Перенумеровать все вершины сети произвольным образом, кроме истока и стока.
2.Задать некоторый начальный поток в сети (например, нулевой).
3.Вершинам сети присвоить целочисленные метки, а дугам — знаки “+” и “-” по следующим правилам:
а) вершине-истоку присвоить метку 0;
б) находим непомеченную вершину , смежную помеченной вершине . Если поток по соединяющей вершины дуге меньше пропускной способности этой дуги, то происходит помечивание, иначе переходим к рассмотрению следующей вершины. Если вершина является образом помеченной вершины , то происходит прямое помечивание: вершина получает метку, равную номеру вершины , соединяющая вершины дуга получает метку “ + ” и мы переходим к рассмотрению следующей вершины. Если вершина не имеет ни одного помеченного прообраза, то происходит обратное помечивание: вершина получает метку, равную номеру вершины (являющейся в данном случае её образом ), соединяющая вершины дуга получает метку “ — ” и мы переходим к рассмотрению следующей вершины. Процесс помечивания продолжается до тех пор , пока все удовлетворяющие этим условиям вершины не получат метку.
4. Если в результате процедуры помечивания вершина-сток метки не получила, то текущий поток — максимальный, задача решена. В противном случае, перейти к пункту 5.
5.Рассмотреть последовательность вершин = ( , ... , ), метка каждой из которых равна номеру следующей за ней вершины, и множество дуг , соединяющих соседние вершины из .
Построить новый поток по схеме:
Если дуга принадлежит множеству и имеет знак “ + ”, то новый поток по этой дуге = старый поток по этой дуге +
Если дуга принадлежит множеству и имеет знак “ — ”, то новый поток по этой дуге = старый поток по этой дуге —
Если дуга не принадлежит множеству ,то новый поток по дуге = старый поток по этой дуге.
Схема нахождения К:
= min{ ; }, где
Для нахождения рассматриваются все дуги , принадлежащие множеству и имеющие знак “+” и для каждой такой дуги вычисляется разность между пропускной способностью дуги и потоком по этой дуге. Затем из этих значений разностей выбирается минимальное значение и присваивается .
Для нахождения рассматриваются все дуги , принадлежащие множеству и имеющие знак “—” .Затем из этих дуг выбирается дуга с минимальным потоком и значение потока по этой дуге присваивается .
Перейти к п.3.
Список литературы
1. Электронный учебник по решению задач на графах — Татарский институт содействия бизнесу, http://www.tisbi.ru/resource/lib/graph/cont.htm