Метод расстановки пометок нахождения максимального потока

Лабораторные работы № 6,7

Оптимизация на сетях

Цель работы:ознакомление с методами оптимизации на сетях

Краткие теоретические сведения

Задача о максимальном потоке. Алгоритм Форда-Фалкерсона

Краткие теоретические сведения

Орграф G=(V, E) называется взвешенным, если каждой его дуге приписано число , называемое весом дуги.

Сетью называется конечный связный взвешенный орграф G=(V, E) без петель, в котором выделены две вершины:

1) вершина , не имеющая входящих дуг и называемая источником или началом сети;

2) вершина , не имеющая выходящих дуг и называемая стоком или концом сети, здесь n − число вершин графа G.

Каждой дуге орграфа поставлено в соответствие некоторое неотрицательное число , называемое пропускной способностью дуги (вес дуги). В дальнейшем предполагается, что − целые числа.

Потоком по сети G=(V, E) из источника s в сток t называется неотрицательная функция f = , определенная на дугах сети и такая, что выполняется:

1) для любой дуги ;

2) =

Числа называются дуговыми потоками,а число r − величиной потока.

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

Задача о максимальном потоке состоит в нахождении такого потока f = , при котором величина потока r максимальна.

Введем вспомогательные понятия. Пусть , а . Разрезом сети называется множество дуг таких, что или . Разрез называется разделяющим источник от стока, если .

Пропускной способностью или величиной разреза называется величина .

Дуга называется насыщеннойпотоком f, если

Теорема Форда-Фалкерсона.

В любой сети величина максимального потока равна пропускной способности минимального разреза.

Из этой теоремы следует, что решив задачу о максимальном потоке мы одновременно решим и задачу о минимальном разрезе.

Метод расстановки пометок нахождения максимального потока

Алгоритм начинает работать с произвольного потока. В качестве начального потока можно взять, очевидно, нулевой поток, который будет последовательно увеличиваться до тех пор, пока это возможно. Алгоритм заключается в систематическом поиске путей, по которым можно увеличить поток. После того, как такой путь найден, увеличивают поток по сети.

Решать задачу будем методом расстановки пометок, используя две операции:

− расстановки пометок;

− изменения потока.

В процессе работы каждая вершина графа может находиться в одном из трех состояний:

1) не помечена;

2) помечена, но не просмотрена;

3) помечена и просмотрена.

В процессе работы алгоритма каждая вершина данной сети получает метку. Метка произвольной вершины j имеет вид: или , где , а – натуральное число или бесконечность. Первая часть метки указывает на то, что можно увелить поток по дуге на величину в случае «+», и уменьшить поток по дуге − в случае «-». Помеченная вершина считается просмотренной, если все смежные с ней вершины обработаны, т.е. сделана попытка их пометить.

Алгоритм Форда-Фалкерсона

Подготовительный этап.

Выбираем произвольный поток. В качестве начального потока можно взять нулевой поток: для любой дуги .

Помечаем источник s: (эта метка означает, что мы пытаемся пропустить через сеть бесконечный по величине поток). Теперь источник помечен, но не просмотрен. Остальные вершины не помечены.

Этап расстановки пометок.

Выбираем произвольную помеченную и непросмотренную вершину i (например, вершину, имеющую минимальный номер) и пытаемся пометить все смежные с ней непомеченные вершины j:

все те вершины j, для которых , получают метку , где ; такие узлы j теперь помечены и непросмотрены;

все те вершины j, для которых , получают метку , где ; такие узлы j теперь помечены и непросмотрены.

После этой процедуры вершина i считается помеченной и просмотренной и больше не рассматривается на этом шаге даже в случае, если не все смежные с ней вершины удалось пометить.

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

Если максимальный поток найден, то все вершины, которые удалось пометить на этом этапе и вершина s образуют множество X и определяют минимальный разрез . величины . Отметим, что все дуги разреза такие,что , являются насыщенными, а по остальным дугам разреза «течет» нулевой поток.

Этап изменения потока.

Используя первую часть метки вершины, определяем путь, по которому мы пришли из вершины s в вершину t. Выделение этого пути начинаем с вершины t: если вершина t имеет метку , то вершина t помечена из вершины i и т.д. В результате мы получаем последовательность смежных вершин: . По всем дугам этого пути , начальная вершина которых имеет пометку «+», увеличиваем поток на величину , а по всем остальным дугам этого пути , начальная вершина их имеет пометку «-», уменьшаем поток на эту же величину «направление» дуги на этом пути совпадает с направлением пути. В результате − поток по сети увеличится на величину .

После изменения потока все метки вершин, кроме метки вершины s , удаляются и возвращаемся на этап расстановки пометок.

Конец работы алгоритма.