Потоки в сетях

Весам дуг можно дать иную интерпретацию, в результате возникает интересная и важная задача. Пусть в ориентированном взвешенном графе выделены две вершины (b – начальная и e – конечная). Предполагается, что вершина e достижима из b. Содержательный смысл весов дуг это пропускная способность дорог. Нас интересуют перевозки из вершины b в вершину e. Естественным является вопрос: какой максимальный груз можно перевезти из начальной вершины в конечную? В отличие от расстояний вес груза, перевозимого по цепи, не равен сумме весов грузов, перевозимых по отдельным дугам. Поставленную задачу называют задачей о максимальном потоке. Слово «поток» здесь является естественным, поскольку можно говорить о потоке грузов, можно задачу интерпретировать и как анализ потоков жидкости в трубопроводах. Приведем формальное определение. Обозначения Г(v), Г^-1(v) имеют тот же смысл, что и в предыдущем параграфе.

ОПРЕДЕЛЕНИЕ 35. Потоком в сетиот вершины b к вершине e называется определенная на дугах графа неотрицательная числовая функция x(u,v), удовлетворяющая условиям:

x(u,v)≤ c (u,v);

при u¹b,e;

.

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

С понятием потока тесно связано понятие разреза.

ОПРЕДЕЛЕНИЕ 36. Разрезом в графе Г, разделяющим начальную и конечную вершины, называется семейство дуг, после удаления которых в соответствующем неориентированном графе начальная и конечная вершины принадлежат разным компонентам связности (назовем их b -компонентой и e -компонентой).

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

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

Теорема 27 (Форда-Фалкерсона). При заданных начальной и конечной вершинах сети величина максимального потока равна величине минимального разреза.

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

Построение фактически является алгоритмом построения максимального потока и минимального разреза, эффективным при целых весах дуг.

При построении важную роль играет следующая конструкция. Рассмотрим последовательность вершин и дуг, соединяющих b и e, причем направления дуг могут быть разными. Дуги, направленные от b к e, назовем прямыми, в противоположном направлении – обратными. (Отметим, что дуга, которая является прямой в одной цепи, может быть обратной в другой). Такая последовательность называется увеличивающей цепью из b в e, если для прямых дуг x(u,v)< c (u,v), а для обратных x(u,v)>0. Пусть p =min{ c (u,v)-x(u,v)} для прямых дуг, q= min{x(u,v)} для обратных дуг цепи, r =min{ p,q }>0. Поток из b в e можно увеличить по увеличивающей цепи на величину r, положив x(u,v):=x(u,v)+ r на прямых дугах и x(u,v):=x(u,v)- r на обратных. Полученные значения также являются потоком (проверьте это!). После такого преобразования цепь не является увеличивающей, поскольку для некоторой прямой дуги x(u,v)= c (u,v) или (не разделительное) для некоторой обратной – x(u,v)=0.

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

Разобьем множество вершин V на два класса. В первый (V ₁) входят такие вершины v, для которых существует увеличивающая цепь из b в v, во второй (V ₂) – остальные вершины. Оба класса непустые: b Î V ₁, e Î V ₂, т.е. это b и e- компоненты. Дуги, направленные из V ₁ в V ₂ и наоборот, образуют разрез. При этом если (u,v) дуга, u Î V ₁ ,v Î V ₂, то x= c (u,v). Действительно, в противном случае (т.е. при x(u,v)< c (u,v)), присоединив к увеличивающей цепи из b в u дугу (u,v), получим увеличивающую цепь из b в v, что невозможно по построению. Аналогично, если u Î V ₂ ,v Î V ₁, то x(u,v)=0.

Величина построенного разреза равна сумме весов «прямых» дуг. Докажем, что величина построенного максимального потока равна сумме весов тех же дуг. Каждая единица груза доставляется по какой-нибудь из этих дуг, причем по единственной. Если бы таких дуг было более одной, то эта единица груза доставлялась бы по некоторой дуге, ведущей из V ₂ в V ₁, а на этих дугах поток нулевой. Теорема Форда-Фалкерсона доказана.

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

Вопросы для самопроверки

1. Что такое граф? Из чего он состоит? Какие виды графов вы знаете?

2. Какие вершины, дуги называются смежными? Инцидентными?

3. Какие графы называются изоморфными?

4. Что такое подграф? Какие виды подграфов вы знаете?

5. Что такое степень вершины? Полустепень входа и выхода?

6. Чему равна сумма степеней вершин графа?

7. Какие графы называются смежным и дополнительным к данному?

8. Как строятся матрицы смежности и инциденций графа?

9. Что такое маршрут, цепь, цикл, простая цепь, простой цикл?

10. Какие вершины называются достижимыми? Взаимно достижимыми?

11. Что такое компонента сильной связности (связности)?

12. Как строится матрица достижимости?

13. Как определяется взвешенный граф?

14. Что такое лес? Дерево?

15. Какими свойствами обладают деревья?

16. Сколько существует неизоморфных помеченных деревьев с данным числом вершин?

17. Что такое радиус, диаметр, центр графа?

18. Как устроен центр дерева?

19. Что такое минимальное остовное дерево взвешенного графа?

20. Что такое эйлеров цикл, эйлеров путь, эйлеров граф, полуэйлеров граф?

21. Каков критерий эйлеровости графа?

22. Что такое гамильтонов цикл, гамильтонов путь, гамильтонов граф, полугамильтонов граф?

23. Как формулируется теорема Дирака?

24. Как формулируется задача коммивояжера?

25. В чем идея методов поиска с возвращением и ветвей и границ?

26. Что такое графовый вектор?

27. Как проверить, что вектор является графовым?

28. Как устроен графовый вектор дерева?

29. Что такое паросочетание? Максимальное паросочетание?

30. Что такое реберное покрытие? Минимальное реберное покрытие?

31. Как связаны максимальное паросочетание и минимальное реберное покрытие

32. Что такое полное паросочетание в двудольном графе?

33. Каков критерий существования полного паросочетания в двудольном графе?

34. Что такое правильная нумерация вершин и в каких графах она существует?

35. Что такое сетевой график?

36. Какие пути в сетевом графике называются критическими?

37. Что такое поток в сети? Разрез сети?

38. Как связаны максимальный поток и минимальный разрез?