§2.5. Потоки в сетях

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

Сеть – это ориентированный связный граф, рёбра которого помечены положительными действительными числами (для ребра идущего из вершины в вершину В графе должны быть выделены вершины (источник) и (сток).

В сети допускаются кратные рёбра, но не допускаются петли. Вершины сети часто называют узлами.

Поток в сети – это функция определённая для каждого ребра и удовлетворяющая условиям:

(а) для любого ребра

(б) существует число такое, что

Число называется величиной потока Иногда пишут вместо чтобы подчеркнуть зависимость от Величина потока выражает количество субстанции (воды, или количества электричества, или автомашин), “перетекающих” из в за определённый промежуток времени.

Поток называется максимальным, если его величина максимальна.

Основная задача теории потоков в сетях состоит в нахождении максимального потока. Мы покажем, что максимальный поток всегда существует, и приведём алгоритм его нахождения.

Теорема. В любой сети существует максимальный поток.

Доказательство. Пусть все рёбра сети. Положим Если поток, то полагаем Тогда поток можно отождествить с точкой п-мерного пространства Конечно, не всякая точка из определяет поток. Должно быть выполнено условие (а): т.е. (точка лежит в параллелепипеде ).

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

Введём ещё несколько обозначений. Пусть множество всех узлов сети. Для двух подмножеств положим Очевидно, при и аналогичное равенство имеет место для функции Введём ещё одно понятие.

Разрез – это разбиение множества всех узлов сети на два непересекающихся подмножества и причём а Число называется пропускной способностью разреза

Пример. В сети, изображённой на рисунке 2.72, на каждом ребре написаны числа (пропускная способность этого ребра и поток через него). В этом примере величина потока Этот поток не максимальный, так как можно, например, вдоль пути увеличить поток через рёбра на 1, условия (а) и (б) будут выполняться, но уже с Рассмотрим разрез где Его пропускная способность равна Мы имеем:

Оказывается, такое неравенство выполняется во всякой сети для любого потока и любого разреза.

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

Доказательство. Пусть поток и разрез. Пусть множество всех узлов сети. По определению потока имеем: при и Складывая выражения для и учитывая, что получим: Отсюда следует, что

,

так как Лемма доказана.

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

Алгоритм построения максимального потока в сети.

1-й шаг. Полагаем для каждого ребра данной сети

2-й шаг. Будем просматривать узлы сети и расставлять на них пометки вида или по следующему принципу. Источнику присваиваем метку Если вершина уже помечена, а вершина ещё нет, то мы помечаем вершину в следующих случаях:

если есть ребро из в и

если есть ребро из в и

В случае вершина получает метку где в случае метку где

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

(1) вершина оказалась помеченной;

(2) вершина не помечена, но больше никакие вершины пометить невозможно.

Покажем, что в случае (1) величину потока можно увеличить, а в случае (2) построенный поток является максимальным. Действительно, пусть имеет место случай (1). Тогда в процессе расстановки меток можно будет “добраться” из в Следовательно, существует путь состоящий из помеченных вершин. Будем считать, что вершины этого пути взяты в “хронологическом” порядке (т.е. в порядке, в котором расставлялись метки). Некоторые из стрелок прямые, а некоторые обратные (см. рис 2.74).

Метки для прямых и обратных стрелок выглядят так, как показано на рис. 2.75.

Из принципа расстановки меток видно, что

3-й шаг. Увеличим величину потока на число прибавив к потоку для прямых рёбер и отняв от для обратных рёбер (см. рис. 2.76).

Условия (а) и (б) при этом не нарушатся, и мы получим поток величины После этого стираем все метки и начинаем расстановку меток заново, т.е. возвращаемся к шагу 2.

Пусть теперь имеет место случай (2), т.е. в процессе расстановки меток “добраться” до вершины невозможно. Докажем, что в этом случае алгоритм можно считать завершённым, так как построенный поток уже максимальный. Обозначим через множество всех помеченных вершин, а непомеченных. Очевидно, разрез. Покажем, что для стрелок из в имеет место равенство а для стрелок из в равенство

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

Так как величина потока равна пропускной способности разреза, то поток максимальный.

Проверим теперь эффективность этого алгоритма, т.е. тот факт, что, применяя его, за конечное число итераций будет построен максимальный поток. Проверку осуществим для случая, когда все пропускные способности являются рациональными числами. Это ограничение не носит принципиального характера, так как действительное число можно приблизить с любой степенью точности рациональным числом, а при реализации на компьютере действия и так проводятся лишь с рациональными числами. Заметим, что наш алгоритм монотонный в том смысле, что величина потока в ходе алгоритма постоянно увеличивается. Так как числа рациональны, то можно их привести к общему знаменателю, а затем умножить на знаменатель; 7таким образом, можно считать, что все целые числа. В ходе работы алгоритма числа будут также получаться целыми, а значит, и числа целые. Монотонность алгоритма означает, что ( величина потока на i-й итерации алгоритма). Очевидно, последовательность ограниченная. Так как члены последовательности – целые числа, то величина достигнет своего наибольшего значения, а значит, алгоритм будет завершён.

Из алгоритма нахождения максимального потока и леммы следует основная теорема о потоках в сетях:

Теорема Форда – Фалкерсона. Для всякой сети существуют поток и разрез такие, что величина потока равна пропускной способности разреза: В этом случае поток максимальный.