5. Задача о максимальном потоке

    Транспортная сеть

Определение:

Сеть (англ. flow network)   представляет собой ориентированный граф, в котором каждое ребро   имеет неотрицательную пропускную способность(англ. capacity)  . Если  , предполагается что  .

В транспортной сети выделяются две вершины: исток   и сток  .

[Править]Определение потока

Определение:

Потоком (англ. flow)   в   является действительная функция  , удоволетворяющая условиям: 1)   (антисимметричность); 2)   (ограничение пропускной способности), если ребра нет, то  ; 3)   для всех вершин  , кроме   и   (закон сохранения потока). Величина потока   определяется как  .

Также существует альтернативное определение (по Асанову), не вводящее антисимметричность (зачастую, из-за этого с ним труднее работать):

Определение:

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

Число   можно интерпретировать, например, как количество жидкости, поступающей из   в   по дуге  . С этой точки зрения значение   может быть интерпретировано как поток, втекающий в вершину  , а   — вытекающий из  . Условие 1) называется условием ограничения по пропускной способности, а условие 2) — условием сохранения потока в вершинах; иными словами, поток, втекающий в вершину  , отличную от   или  , равен вытекающему из неё потоку.

[Править]Пример

Пример сети с источником   и стоком  .

Первое число означает величину потока, второе — пропускную способность ребра. Отрицательные величины потока не указаны (так как они мгновенно получаются из антисимметричности:  ). Сумма входящих ребер везде (кроме источника и стока) равна сумме исходящих и на то, что в общем  . Кроме того, величина потока на ребре никогда не превышает пропускную способность этого ребра.

Величина потока в этом примере равна   (считаем от вершины  ).

Поток через любой разрез равен сумме потоков из источника. Доказательство: пускай есть разрез (A,B). Рассмотрим сумму всех потоков из всех вершин, принадлежащих А. Она равна

В первой из сумм для любой пары вершин (u, v) есть два слагаемых f(u, v) и f(v, u), равных по модулю и противоположных по знаку. Следовательно, эта сумма равна нулю. Вторая сумма есть поток через разрез (A,B). Следовательно, сумма всех потоков из всех вершин, принадлежащих А, равна потоку через разрез. С другой стороны, сумма потоков из любой вершины, кроме s и t, равна нулю, а  . Следовательно, сумма всех потоков из всех вершин, принадлежащих А, равна сумме потоков из s. Следовательно, поток через разрез (A,B) равен сумме потоков из s, что и требовалось доказать.

Сумма потоков из источника равна сумме потоков в сток. Доказательство: рассмотрим разрез  . Поток через этот разрез равен сумме потоков в сток. С другой стороны, по только что доказанному, поток через этот (как и любой другой) разрез равен сумме потоков из источника. Теорема доказана.

Максимальный поток положителен тогда и только тогда, когда существует путь из источника в сток, проходящий по рёбрам с положительной пропускной способностью. Доказательство: Пускай такой путь P существует. Пусть c — минимальная из пропускных способностей рёбер, принадлежащих P. Пускай поток равен c на всех рёбрах из P, и нулю на всех остальных рёбрах. Тогда суммарный поток из источника равен c, то есть положителен. Теперь допустим, что такого пути нет, то есть t недостижимо из s по рёбрам с положительной пропускной способностью. Пусть A — множество вершин, достижимых из s по таким рёбрам, B — недостижимых. Тогда, поскольку  ,  , то (A,B) является разрезом. Кроме того, не существует ребра (a, b) с положительной пропускной способностью, такого что  ,  , иначе b было бы достижимо из s. Следовательно, пропускная способность разреза (A,B) равна нулю, а значит и поток через него всегда равен нулю. Следовательно, сумма потоков из источника всегда равна нулю.

Поток максимален тогда и только тогда, когда нет увеличивающего пути в остаточной сети. Доказательство: пускай такой путь P есть. Пусть c — минимальная из остаточных пропускных способностей рёбер, принадлежащих P, в остаточной сети. Для всех пар   увеличим f(u, v) на c и уменьшим f(v, u) на c. Мы увеличили суммарный поток из источника на c, следовательно, он был не максимален. Теперь, наоборот, допустим, что такого пути нет. Докажем от противного, что поток f в исходной сети обеспечивает максимальный суммарный поток из s. Пусть это не так, тогда есть поток f', обеспечивающий больший суммарный поток из s. Легко убедиться, что f'-f — поток в остаточной сети, обеспечивающий в ней положительный суммарный поток из s. Следовательно, в остаточной сети есть путь из источника в сток, то есть увеличивающий путь. Мы получили противоречие.

Теорема Форда-Фалкерсона. Величина максимального потока равна пропускной способности минимального разреза. Доказательство: сумма потоков из s равна потоку через любой разрез, в том числе минимальный, следовательно, не превышает пропускной способности минимального разреза. Следовательно, максимальный поток не больше пропускной способности минимального разреза. Осталось доказать, что он и не меньше её. Пускай поток максимален. Тогда в остаточной сети сток не достижим из источника. Пусть A — множество вершин, достижимых из источника в остаточной сети, B — недостижимых. Тогда, поскольку  ,  , то (A,B) является разрезом. Кроме того, в остаточной сети не существует ребра (a, b) с положительной пропускной способностью, такого что  ,  , иначе бы b было достижимо из s. Следовательно, в исходной сети поток по любому такому ребру равен его пропускной способности, и, значит, поток через разрез (A,B) равен его пропускной способности. Но поток через любой разрез равен суммарному потоку из источника, который в данном случае равен максимальному потоку. Значит, максимальный поток равен пропускной способности разреза (A,B), которая не меньше пропускной способности минимального разреза. Теорема доказана.

    Формальное определение потока

Определение:

Потоком (англ. flow)   в   является действительная функция  , удоволетворяющая условиям: 1)   (антисимметричность); 2)   (ограничение пропускной способности), если ребра нет, то  ; 3)   для всех вершин  , кроме   и   (закон сохранения потока). Величина потока   определяется как  .

    Сеть с несколькими источниками и стоками (сведение к сети с одним источником и одним стоком)

Пусть в сети в общем случае имеется несколько истоков и стоков. Стоки и истоки занимают в сети крайние положения. Все остальные вершины могут быть дальше или ближе к ним. Расположение вершины в сети определяется ее уровнем. Определим это понятие. Вершины уровня 0 — это истоки; они образуют множество N₀. Если N_i — множество вершин уровня i 6 k, то N_k+1 — множество вершин уровня k +1 состоящее из тех и только тех вершин, предшественники которых принадлежат любому из множеств N₀,...,N_k, причем среди этих множеств нет пустых [3].

Порядковой функцией сети называют отображение, сопоставляющее каждой вершине сети ее уровень.

Задача. Найти порядковую функцию сети (рис. 4.8).

Ответы

№	Порядковая функция
а	4, 3, 7, 9, 6, 5, 1, 8, 2
б	8, 7, 5, 4, 6, 9, 2, 1, 3
в	(2, 6), 3, 5, 7, 8, 4, 9, 1
г	(4, 8), 2, 6, 1, 7, 5, 3, 9
д	9, 3, (1, 7, 4, 5), 6, 8, 2
е	1, 2, (7, 3, 4, 5), 6, 8, 9
ж	(5, 6, 2, 9), (4, 7, 8), 3, 1
з	(2, 5, 4), (8, 6, 7, 9), (3, 1)
и	(4, 8), (5, 9), (6, 2), (1, 3), 7

Пример. Отсортировать топологически сеть на рис. 4.9.

Решение. Находим вершины (4 и 9), полустепень захода которых равна 0. Удаляем эти вершины и дуги, выходящие из них [3]. Удаленные вершины образуют первый уровень упорядоченной сети. Получаем новую сеть (рис. 4.10). В новой сети в вершины 1, 5 и 8 не входят дуги. Удаляем эти вершины (они образуют второй уровень) и получаем сеть, изображенную на рис. 4.11. Очевидно, третий уровень состоит из вершин 2, 3 и 6, а последний (сток сети) — из единственной вершины 7. Изображаем ту же сеть по уровням (рис. 4.12).

Рис. 4.12

    Остаточные сети 

Остаточная сеть (residual network) — граф  , где   — множество рёбер с положительной остаточной пропускной способностью. В остаточной сети может быть ребро из   в  , даже если его нет в исходной сети. Это выполняется, когда в исходной сети есть обратное ребро   и поток по нему положителен.

    Увеличивающие пути

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

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

Приведём сначала теорему Бержа, из которой следует, что, как и в случае двудольных графов, наибольшее паросочетание можно находить при помощи увеличивающих путей.