Задача построение максимального потока. Связь с минимальными разрезами. Теорема Форда-Фалкерсона и теорема Менгера

§ Разрез графа — множество рёбер, удаление которых делит граф на два изолированных подграфа, один из которых, в частности, может быть отдельным узлом.

§ Разрез графа — линия, делящая граф на две несвязанные части.

Теорема Форда—Фалкерсо́на — теорема о максимальном потоке в графе.

Звучит так: величина максимального потока равна величине минимального разреза.

Теорема Менгера о вершинной связности:

Пусть G — конечный неориентированный граф и x, y — две несмежные вершины. Наименьшее число вершин, разделяющих x и y равно наибольшему числу попарно независимых (x,y)-цепей.

Эквивалентная формулировка:

Пусть G — конечный неориентированный граф и x, y — две несмежные вершины. x и y k-отделимы тогда и только тогда, когда x и y k-соединимы.

Теорема Менгера о реберной связности:

Пусть G — конечный неориентированный граф и x, y — различные вершины. x и y реберно k-отделимы тогда и только тогда, когда x и y реберно k-соединимы.

 

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

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

Дана транспортная сеть с источником , стоком и пропускными способностями .

Величиной потока (value of flow) называется сумма потоков из источника . В статье «Транспортная сеть» доказано, что она равна сумме потоков в сток .

Задача о максимальном потоке заключается в нахождении потока такого, что величина потока максимальна.

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

 

 

Алгоритм проталкивания предпотока

 

 

 

 

Эйлеров цикл. Алгоритм построения.

Построение эйлерова цикла

Напомним, что эйлеровым циклом называется замкнутый маршрут, в котором каждое ребро графа встречается точно один раз. Согласно теореме 5 из лекции 2, для существования такого маршрута в связном графе необходимо и достаточно, чтобы степени всех вершин были четными. Теперь рассмотрим алгоритм, который находит эйлеров цикл в заданном графе при условии, что условия связности и четности степеней выполнены.

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

Алгоритм 1. Построение эйлерова цикла

1. выбрать произвольно вершину
2. 
3. while do
4. 
5. if имеется непройденное ребро
6. then пометить ребро как пройденное
7. 
8. else переместить вершину из в

Для обоснования алгоритма заметим сначала, что первой в стек помещается вершина , и она будет последней перемещена из в . Следовательно, она будет последней вершиной в стеке . Далее, как было отмечено выше, первый раз, когда обнаружится, что все инцидентные активной вершине ребра пройдены (т.е. будет выполняться ветвь else в строке 8), активной будет стартовая вершина . Значит, эта вершина будет первой перемещена из в . Итак, по окончании работы алгоритма в начале и в конце последовательности вершин, содержащейся в стеке , находится вершина . Иначе говоря, если эта последовательность представляет маршрут (а далее будет показано, что так оно и есть), то этот маршрут замкнут.

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

Будем говорить, что ребро представлено в стеке ( или ), если в какой-то момент работы алгоритма в стеке рядом находятся вершины и . Ясно, что каждое ребро графа будет представлено в стеке и что каждые две вершины, расположенные рядом в этом стеке, образуют ребро. Допустим, в какой-то момент из стека в стек перемещается вершина , а непосредственно под ней в стеке находится вершина . Возможно, что вершина будет перемещена из в при следующем повторении цикла while, тогда ребро будет представлено в стеке . Другая возможность - между перемещением вершины и следующим перемещением, т.е. следующим выполнением ветви else, будет несколько раз выполнена ветвь then (строки 6,\,7). Это означает, что будет пройдена некоторая последовательность ребер, начинающаяся в вершине . Ввиду четности степеней эта последовательность может закончиться только в вершине . Значит, и в этом случае следующей за вершиной будет перемещена из в вершина . В любом случае ребро будет представлено в стеке . Из этого рассуждения видно, что последовательность вершин в стеке является маршрутом и что каждое ребро графа в конечном итоге будет содержаться в этом маршруте, причем один раз.

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