Учебно-методический комплекс по дисциплине «Теория конечных графов и ее приложения» Алексеев В. Е, Захарова Д. В

9. Оптимальные каркасы и пути

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

Алгоритм Прима

Будем предполагать, что граф G связен, так что решением задачи всегда будет дерево. В алгоритме Прима (R. Prim) на каждом шаге рассматривается частичное решение задачи, представляющее собой дерево. Вначале это дерево состоит из единственной вершины, в качестве которой может быть выбрана любая вершина графа. Затем к дереву последовательно добавляются ребра и вершины, пока не получится остовное дерево, т.е. каркас. Для того чтобы из текущего дерева при добавлении нового ребра опять получилось дерево, это новое ребро должно соединять вершину дерева с вершиной, еще не принадлежащей дереву. Такие ребра будем называть подходящими относительно рассматриваемого дерева. В алгоритме Прима применяется следующее правило выбора: на каждом шаге из всех подходящих ребер выбирается ребро наименьшего веса. Это ребро вместе с одной новой вершиной добавляется к дереву. Если обозначить через U и F множества вершин и ребер строящегося дерева, то алгоритм Прима можно представить следующим образом. Через обозначаем дополнение множества U до множества V.
Алгоритм Прима.

, где a – произвольная вершина графа;
;
while do
найти ребро наименьшего веса среди всех ребер, у которых , ;
добавить к F ребро , а к U вершину y.

Теорема об алгоритме Прима. Подграф , построенный с помощью алгоритма Прима, является каркасом наименьшего веса для данного графа.
Оценим время работы алгоритма Прима. Цикл while в строке 3 повторяется раз. Внутри этого цикла есть еще скрытый цикл в строке 4, где ищется ребро наименьшего веса среди подходящих ребер. Допустим, что этот поиск производится самым бесхитростным образом, т.е. просматриваются все пары вершин с , . Если , то имеется таких пар. Всего получаем

пар, которые нужно рассмотреть. Таким образом, трудоемкость алгоритма будет .

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

.
В этом случае, однако, необходимы дополнительные действия для обновления таблицы значений функции f при добавлении новой вершины к дереву, т.е. при переносе одной вершины из множества в множество U. Сначала, когда множество U состоит из единственной вершины a, полагаем для всех . В дальнейшем эти значения могут меняться. Допустим, на некотором шаге к дереву присоединяется вершина y. Тогда для каждой вершины либо сохраняется старое значение , либо устанавливается новое , в зависимости от того, какое из ребер и имеет меньший вес. По окончании работы алгоритма массив f будет массивом отцов построенного дерева относительно корня а. Поэтому отпадает необходимость отдельно запоминать добавляемые к дереву ребра. Алгоритм теперь можно записать следующим образом.
Алгоритм Прима усовершенствованный.

, где a – произвольная вершина графа;
for do ;
while do
найти вершину с наименьшим значением ;
добавить к U вершину y;
for do if then .

При цикл в строке 6 повторяется раз. Таким образом, дополнительное время, необходимое для обслуживания массива f, тоже оценивается сверху квадратичной функцией от n и общая оценка трудоемкости усовершенствованного алгоритма Прима будет .

Алгоритм Краскала

Другой алгоритм для задачи об оптимальном каркасе известен как алгоритм Краскала (J. Kruskal). В нем тоже на каждом шаге рассматривается частичное решение. Отличие от алгоритма Прима состоит в том, что в алгоритме Краскала частичное решение всегда представляет собой остовный лес F графа G, т.е. лес, состоящий из всех вершин графа G и некоторых его ребер. Вначале F не содержит ни одного ребра, т.е. состоит из изолированных вершин. Затем к нему последовательно добавляются ребра, пока не будет построен каркас графа G. Пусть F – лес, построенный к очередному шагу. Новое ребро можно добавить к этому лесу так, чтобы он остался лесом, только если оно соединяет вершины из разных компонент связности леса F. Теперь именно такие ребра будем называть подходящими. Для выбора добавляемого ребра применяется тот же принцип, что и в алгоритме Прима – из всех подходящих ребер выбирается ребро наименьшего веса. Для того чтобы облегчить поиск этого ребра, вначале все ребра графа упорядочиваются по возрастанию весов: . Теперь последовательность ребер достаточно просмотреть один раз и для очередного рассматриваемого ребра нужно определить, является ли оно подходящим относительно построенного к этому моменту леса F. Подходящие ребра добавляются к F , остальные просто пропускаются.
Теорема об алгоритме Краскала. Лес F, построенный с помощью алгоритма Краскала, является каркасом наименьшего веса для данного графа.

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

Кратчайшие пути

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

Рассмотрим задачу отыскания путей наименьшей длины от заданной вершины a до всех остальных вершин графа. Возможно, более естественной постановкой задачи кажется поиск кратчайшего пути между двумя заданными вершинами. Однако в настоящее время не известно никакого способа решения этой задачи, существенно лучшего, чем поиск кратчайших путей от начальной вершины до всех остальных. Наиболее известным способом решения этой задачи является описываемый далее алгоритм Дейкстры (E. Dijkstra).

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

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

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

Теорема об алгоритме Дейкстры. Дерево, построенное с помощью алгоритма Дейкстры, является деревом кратчайших путей.
Алгоритм Дейкстры для ускорения работы модифицируется так же, как алгоритм Прима. Распространим определение функции L на множество : для положим равным наименьшему значению величины по всем . Через обозначим то значение z, на котором этот минимум достигается. Таким образом, – это длина кратчайшего пути из а в y, проходящего только через вершины множества U (кроме вершины y), а – предпоследняя вершина этого пути. Теперь алгоритм Дейкстры можно записать следующим образом.
Алгоритм Дейкстры.

; ;
for do {; };
while do
найти вершину с наименьшим значением ;
добавить к U вершину y;
for do if then {; }.

Задачи

9.1. Найдите оптимальный каркас по матрице весов ребер с помощью алгоритма Прима

(прочерк означает отсутствие ребра).

9.2. Найдите оптимальный каркас с помощью алгоритма Краскала.

9.3. Какие из следующих утверждений верны для любого взвешенного графа?

Если в графе имеется единственное ребро наименьшего веса, то оно принадлежит каждому оптимальному каркасу.
Если в графе имеются точно два ребра наименьшего веса, то они оба принадлежат каждому оптимальному каркасу.
Если в графе имеются точно три ребра наименьшего веса, то все они принадлежат каждому оптимальному каркасу.
Каждое ребро минимального веса принадлежит какому-нибудь оптимальному каркасу.

9.4. Вершины полного графа размещаются в в целочисленных точках

прямоугольника . Вес каждого ребра равен евклидовой длине

отрезка, соединяющего вершины этого ребра.

1) Чему равен вес оптимального каркаса для этого графа?

2) Каков будет вес оптимального каркаса, если из графа удалить все ребра длины 1?

3) Каков будет вес оптимального каркаса, если из графа удалить все ребра с длинами

1, 2 и , а ?

4) Каков будет вес оптимального каркаса, если из графа удалить все ребра с длинами

1 и , а ?

9.5. По матрице длин ребер графа с помощью алгоритма Дейкстры найдите

1) кратчайшие пути от вершины 7 до всех остальных вершин

2) кратчайший путь между вершинами 1 и 4;

9.6. Каркасы, построенные для некоторого графа с помощью алгоритмов Прима, Краскала и Дейкстры, имеют соответственно веса a, b и c. Какое из следующих соотношений обязательно выполняются для этих чисел?

1) ; 2) ; 3) ; 4) .

10. Потоки

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

каждому ребру e приписано положительное число , называемое пропускной способностью ребра;
выделены две вершины s и t, называемые соответственно источником и стоком, при этом .

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

Пусть задана сеть N с множеством вершин V и множеством ребер Е. Пусть f –функция с вещественными значениями, определенная на множестве Е. Для вершины х обозначим , . Функция f называется потоком в сети N, если она удовлетворяет условиям:

(1) для каждого ребра e;

(2) для каждой внутренней вершины x.

На рисунке 11 показан пример сети и потока в ней. В дроби, приписанной каждому ребру, числитель представляет пропускную способность ребра, а знаменатель – величину потока на этом ребре.

Рис. 11.
Условие (2) называется условием сохранения потока. Так как каждое ребро является входящим для одной вершины и выходящим для другой, то

Из этого равенства и условия сохранения потока следует, что

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

Поток на рисунке 11 не является максимальным – можно, например, добавить по единице на ребрах пути . Получится поток величины 5, показанный на рисунке 12 слева. Но и он не максимален. Можно увеличить поток на 1 на ребрах , , и уменьшить на 1 на ребре . Условие сохранения останется выполненным, а величина потока станет равной 6 (рисунок 12, справа).

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

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

Если имеется увеличивающий путь для потока f, то поток можно увеличить на величину , равную минимуму из величин «недогрузок» (разностей ) прямых ребер этого пути и величин потока на обратных ребрах. Нужно прибавить к потоку на каждом прямом ребре пути и вычесть из потока на каждом обратном ребре. Условие сохранения останется выполненным, а величина потока увеличится на .

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

Метод увеличивающих путей для задачи о максимальном потоке предложили Форд и Фалкерсон в 1955 г. Известно несколько алгоритмов, реализующих этот метод, они различаются, в частности, стратегией поиска увеличивающих путей. Первый алгоритм, для которого была получена верхняя оценка трудоемкости, предложили Эдмондс и Карп в 1972 г. В этом алгоритме всегда ищется кратчайший (по числу ребер) увеличивающий путь. Удобно этот поиск вести не на исходной сети N, а на остаточной сети R, которая при заданном на сети N потоке f определяется следующим образом. Множество вершин, источник и сток у остаточной сети те же, что у исходной. Пусть e – ребро исходной сети. Тогда

если , то ребро e включается в сеть R и ему в этой сети присваивается пропускная способность ;
если , то к сети R добавляется ребро противоположного направления с пропускной способностью .

Легко видеть, что увеличивающие пути в исходной сети находятся во взаимно однозначном соответствии с ориентированными путями из источника в сток в остаточной сети. В алгоритме Эдмондса-Карпа нужно в остаточной сети искать кратчайший ориентированный путь из s в t. Это можно сделать за линейное время с помощью поиска в ширину. Если увеличивающий путь обнаружен, поток увеличивается. Для нового потока строится остаточная сеть и т.д., пока не будет построен поток, относительно которого нет увеличивающего пути (в остаточной сети нет ориентированного пути из источника в сток. Общая оценка трудоемкости алгоритма Эдмондса-Карпа . В настоящее время известны и более быстрые алгоритмы для задачи о максимальном потоке.
Когда максимальный поток найден, нетрудно найти и минимальный разрез в сети, т.е. разрез с минимальной пропускной способностью. Нужно найти все вершины, достижимые из источника подходящими путями. Пусть Х – множество всех таких вершин, тогда множество всех ребер из Х в является минимальным разрезом.
Алгоритм нахождения максимального потока можно применять для нахождения наибольшего паросочетания в двудольном графе. Пусть А и В – доли такого графа. Ориентируем все ребра графа по направлению от А к В. Добавим источник и ребра из ко всем вершинам доли А. Добавим сток и ребра от всех вершин доли В к . Припишем каждому ребру пропускную способность 1. Найдем в построенной сети целочисленный максимальный поток. Ребра между А и В, на которых поток равен 1, образуют наибольшее паросочетание.

Задачи

10.1. Выясните, является ли данный поток максимальным. Если да, то найдите

минимальный разрез. Если нет, то найдите максимальный поток.

10.2. Найдите наибольшее паросочетание с помощью потокового алгоритма.

Литература

Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Алгоритмы.– Н.Новгород, ННГУ, 2005. 307 с.
Алексеев В.Е., Таланов В.А. Графы и алгоритмы. Структуры данных. Модели вычислений.– М.: Интернет-университет информационных технологий; БИНОМ. Лаборатория знаний, 2006. 320 с.
Берж К. Теория графов и ее применение.– М.: ИЛ, 1962. 319 с.
Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов.– М.: Наука, 1990. 383 с.
Зыков А.А. Основы теории графов.– М.: Вузовская книга, 2004. 664 с.
Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение.– СПб.: БХВ-Петербург, 2003. 1104 с.
Кристофидес Н. Теория графов. Алгоритмический подход . – М.: Мир, 1978. 432 с.
Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ.– М.: Вильямс, 2005. 1296 с.
Липский В. Комбинаторика для программистов. – М.: Мир, 1988. 213 с.
Оре О. Теория графов.– М.: Наука, 1980. 336 с.
Седжвик Р. Фундаментальные алгоритмы на С++. Часть 5. Алгоритмы на графах. – СПб.: DiaSoftЮП, 2002. 496 с.
Харари Ф. Теория графов.– М.: Мир, 1973. 300 с.