Заметим, во-первых, что это задача линейного программирования, так что ее можно
решать симплекс-методом. Более того, теорема о максимальном потоке и
минимальном
разрезе - в точности теорема двойственности для задачи линейного
программирования.
Hо для этой конкретной задачи есть более просто описываемый алгоритм - алгоритм
Форда-Фалкерсона (в сущности, это и есть симплекс-метод, примененный в
конкретной ситуации).
Алгоритм, грубо говоря, жадный. Hайдем сначала хоть
какой-то поток ненулевого веса (нужно найти путь из истока в сток, желательно,
с
максимальным весом (чтобы алгоритм быстрее работал); можно для этого применить
соответствующим образом модифицированный алгоритм Дейкстры).
После этого на кажом шаге алгоритма смотрим, можем ли мы модифицировать наш
поток так, чтобы его вес стал больше. Если так модифицировать нельзя, то мы
нашли максимальный поток.
Модификация заключается в следующем. Попытаемся "прибавить" к нашему потоку
новый. Для этого рассмотим новый граф с теми же вершинами, но новыми
пропускными
способностями ребер: если пропускная способность ребра от вершины A к вершине B
равна c, а в нашем потоке по этому ребру пущено x, то в новом графе есть ребро
от A к B с пропускной способностью c-x и ребро от B к A с пропускной
способностью x (грубо говоря, мы можем увеличить поток по этому ребру максимум
на c-x или уменьшить максимум на x).
После этого в новом графе ищем
какой-нибудь
поток из истока в сток ненулевого веса (снова можно применить что-нибудь вроде
Дейкстры). Если такого нет - ура, тот поток, который у нас был - максимальный.
Если есть - складываем эти два потока, получаем новый, с большим весом.
Повторяем процесс.
К сожалению, этот алгоритм (как и симплекс-метод) не гарантирует, что время
работы полиномиально (если нет ограничений на пропускные способности). В
_подавляющем_ _большинстве_ случаев это так, но можно придумать "плохие"
примеры, для которых время работы будет экспоненциальным (но в практических
задачах они вряд ли встретятся).
Если известно, что пропускные способности ребер - "небольшие" целые числа, то
алгоритм действительно работает за O(N3).
|
