Свойства операций над множествами (стр. 2 из 2)

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

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

. Следовательно, сумма всех потоков из всех вершин, принадлежащих А, равна сумме потоков из s. Следовательно, поток через разрез (A,B) равен сумме потоков из s, что и требовалось доказать.

2.Сумма потоков из источника равна сумме потоков в сток.

Доказательство: рассмотрим разрез

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

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

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

, , то (A,B) является разрезом. Кроме того, не существует ребра (a,b) с положительной пропускной способностью, такого что , , иначе b было бы достижимо из s. Следовательно, пропускная способность разреза (A,B) равна нулю, а значит и поток через него всегда равен нулю. Следовательно, сумма потоков из источника всегда равна нулю.

4.Поток максимален тогда и только тогда, когда нет увеличивающего пути в остаточной сети.

Доказательство: пускай такой путь P есть. Пусть c - минимальная из пропускных способностей рёбер, принадлежащих P, в остаточной сети. Для всех пар

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

5.Теорема Форда-Фалкерсона. Величина максимального потока равна пропускной способности минимального разреза.

Доказательство: сумма потоков из s всегда равна потоку через любой, в том числе минимальный, разрез, следовательно, не превышает пропускной способности минимального разреза. Следовательно, максимальный поток не больше пропускной способности минимального разреза. Осталось доказать, что он и не меньше её. Пускай поток максимален. Тогда в остаточной сети сток не достижим из источника. Пусть A - множество вершин, достижимых из источника в остаточной сети, B - недостижимых. Тогда, поскольку

, , то (A,B) является разрезом. Кроме того, в остаточной сети не существует ребра (a,b) с положительной пропускной способностью, такого что , , иначе бы b было достижимо из s. Следовательно, в исходной сети поток по любому такому ребру равен его пропускной способности, и, значит, поток через разрез (A,B) равен его пропускной способности. Но поток через любой разрез равен суммарному потоку из источника, который в данном случае равен максимальному потоку. С другой стороны, пропускная способность любого разреза не меньше пропускной способности минимального разреза. Комбинируя эти три утверждения, получаем, что максимальный поток не меньше пропускной способности минимального разреза. Теорема доказана.

Пример.

Транспортная сеть с указанием потока и пропускной способности.

Здесь изображена транспортная сеть с источником

, стоком и четырьмя дополнительными узлами. Поток и пропускная способность обозначены соответственно . Поток из источника к стоку равен 5, что легко видно, так как поток из равен 5, что есть также в .

Ниже показана остаточная сеть для данного выше потока. Существует ограничивающая пропускная способность для некоторых ребер, тогда как в исходной сети она равна нулю.

Например, ребро

. Этот поток не максимален. Есть увеличивающие пути , и . Остаточная пропускная способность первого пути

.

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

не существует в исходной сети, но можно пропустить по нему правильный поток.

Остаточная сеть для показанного сверху потока, показывающая остаточные пропускные способности.

Самый частый пример использования транспортных сетей — нахождение максимального потока, который означает максимальный суммарный поток от s к t. Для нахождения максимального потока в сети может быть использован алгоритм Форда — Фалкерсона, алгоритм Эдмондса — Карпа и другие.

Алгоритм Форда — Фалкерсона решает задачу нахождения максимального потока в транспортной сети.

Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех

. Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.

Алгоритм Эдмондса — Карпа решает задачу нахождения максимального потока в транспортной сети. Алгоритм представляет собой частный случай метода Форда — Фалкерсона и работает за время O(VE²).

Алгоритм Эдмондса — Карпа — это вариант алгоритма Форда — Фалкерсона, при котором на каждом шаге выбирают кратчайший дополняющий путь из s в t в остаточной сети (полагая, что каждое ребро имеет единичную длину). Кратчайший путь находится поиском в ширину.

В задаче о потоке минимальной стоимости, каждому ребру (u,v) сопоставляется цена k(u,v), цена пересылки потока f(u,v) через ребро

. Задача — послать заданное количество потока от s к t с наименьшей ценой.