анти. Guide to Competitive

• Название: Guide to Competitive
• Дата: 20.12.2022
• Размер: 2.39 Mb.
• Имя файла: анти.pdf
• Тип: Guide; #854732
• страница: 18 из 26

Рис. 12.14. Построение последовательности де Брёйна по эйлерову пути
Маршруты шахматного коня. Маршрутом шах-
матного коня называется такая последовательность ходов коня на доске n×n в соответствии с шахматны- ми правилами, при которой каждое поле посещает- ся ровно один раз. Маршрут называется замкнутым, если конь возвращается в исходное поле, и незамк-
нутым в противном случае. На рис. 12.15 показан незамкнутый маршрут шахматного коня.
Маршрут шахматного коня соответствует гамиль- тонову пути в графе, вершины которого представляют поля доски, а две вершины соединены ребром, если конь может перейти из одного поля в другое за один ход. Для построения маршрута естественно приме- нить перебор с возвратом. Поскольку количест во возможных ходов велико, эффективность поиска можно повысить с помощью эвристик, т. е. попыток предложить такие ходы, при которых маршрут будет найден быстрее.
Правило Варнсдорфа – простая и эффективная эв- ристика для нахождения маршрута коня. Оно по- зволяет построить маршрут даже на большой доске.
Идея в том, чтобы всегда ставить коня на поле, с ко- торого можно пойти на минимальное число еще не пройденных полей. На рис. 12.16 конь может пойти
1 4
11 16 25 12 17 2
5 10 3
20 7
24 15 18 13 22 9
6 21 8
19 14 23
Рис. 12.15.
Незамкну тый марш- рут шахматного коня на доске 5×5 1
2
a b
e c
d
Рис. 12.16. При- менение правила
Варнсдорфа для построения маршрута коня

228 
Глава 12. Дополнительные алгоритмы на графах на любое из пяти полей (поля a…e). В этом случае правило Варнсдорфа требует, чтобы конь пошел на поле a, поскольку после этого будет возмо- жен единственный ход. При любом другом выборе конь попал бы на поле, с которого можно пойти на три поля.
12.3. Максимальные потоки
В задаче о максимальном потоке дан ориен- тированный взвешенный граф, содержа- щий две специальные вершины: источник, в который не входит ни одно ребро, и сток, из которого не исходит ни одно ребро. За- дача заключается в том, чтобы отправить максимальный поток из источника в сток.
У каждого ребра имеется пропускная спо- собность, и во всех промежуточных верши- нах входящий и исходящий потоки долж- ны быть равны.
В графе на рис. 12.17 вершина 1 является источником, а вершина 6 – стоком. Макси- мальный поток в этом графе равен 7, как показано на рис. 12.18. Нотация v/k означа- ет, что через ребро с пропускной способно- стью k единиц проходит поток величиной
v единиц. Величина потока равна 7, потому что источник отправляет 3 + 4 единиц потока, а сток получает 5 + 2 единиц.
Легко видеть, что этот поток максимален, потому что суммарная пропуск- ная способность ребер, входящих в сток, равна 7.
Оказывается, что задача о максимальном потоке связана с другой зада- чей на графах – задачей о минимальном разрезе, в которой наша цель – уда- лить из графа такое множество ребер, чтобы не осталось ни одного пути из источника в сток и при этом суммарная пропускная способность удален- ных ребер была минимальна.
В графе на рис. 12.17 величина минимального разреза равна 7, поскольку достаточно удалить ребра 2 → 3 и 4 → 5, как показано на рис. 12.19. После удаления этих ребер путей из источника в сток не останется. Величина разреза равна
6 + 1 = 7, и этот разрез минимален, потому что не существует разреза с пропускной способностью меньше 7.
То, что максимальный поток в нашем примере равен минимальному разрезу, – не случайность. На самом деле они равны x
3
x
2
¬x
2
¬x
3
¬x
1
x
1 1
2 3
6 4
5 3/5 6/6 5/5 4/4 1/1 2/2 3/3 1/8 1
2 3
6 4
5 5
6 5
4 1
2 3
8
Рис. 12.17. Граф с источником 1 и стоком 6
Рис. 12.18. Максимальный поток в графе равен 7
Рис. 12.19. Минимальный раз- рез в графе равен 7

12.3. Максимальные потоки

229
всегда, так что эти понятия – две стороны одной медали. Далее мы обсу- дим алгоритм Форда–Фалкерсона для нахождения максимального потока и минимального разреза. А заодно поймем, почему они равны.
12.3.1. Алгоритм Форда–Фалкерсона
Алгоритм Форда–Фалкерсона находит максимальный поток в графе.
Вначале поток пуст, а на каждом шаге ищется путь от источника к стоку, на котором поток больше. Если алгоритм не может увеличить поток, значит, найденный к этому моменту поток максимален.
В алгоритме используется специальное представление графа, в кото- ром для каждого исходного ребра добав- лено обратное ребро между теми же вер- шинами, направленное противоположно.
Вес ребра показывает, какой еще поток можно было бы пропустить через него.
В начале работы алгоритма вес каждого исходного ребра равен его пропускной способности, а вес каждого обратного ребра равен нулю. На рис. 12.20 показа- но новое представление графа из нашего примера.
Алгоритм Форда–Фалкерсона состоит из нескольких раундов. На ка- ждом раунде ищется путь от источника к стоку, для которого веса всех ребер положительны. Если таких путей несколько, можно выбрать про- извольный. После выбора пути поток увеличивается на x единиц, где x – наименьший вес принадлежащего пути ребра. Одновременно вес каждого ребра на пути уменьшается на x, а вес каждого обратного ребра увеличи- вается на x.
Идея заключается в том, что увеличение потока уменьшает величину по- тока, который можно пропустить по ребрам в будущем. С другой стороны, обратные ребра позволяют впоследствии отменить поток, если окажется, что было бы выгоднее пустить поток по-другому. Алгоритм увеличивает поток, пока существуют пути от источника к стоку по ребрам с положи- тельными весами. Если таких путей не осталось, алгоритм завершается – найденный поток максимален.
На рис. 12.21 показано, как алгоритм Форда–Фалкерсона находит мак- симальный поток в нашем графе. В данном случае понадобилось четыре раунда. На первом раунде выбирается путь 1 → 2 → 3 → 5 → 6. Мини- мальный вес ребра на этом пути равен 2, поэтому поток увеличивается на 2 единицы. Затем алгоритм выбирает еще три пути, которые увеличи- вают поток на 3, 1 и 1 единицу. После этого путей с ребрами положитель- ного веса не осталось, поэтому максимальный поток равен 2 + 3 + 1 + 1 = 7.
1 2
3 6
4 5
5 0
6 0
5 0
4 0
1 0
2 0
3 0
8 0
Рис. 12.20. Представление графа в алгоритме Форда–Фалкерсона

230 
Глава 12. Дополнительные алгоритмы на графах
Нахождение путей. Алгоритм Форда–Фалкерсона не говорит, как сле- дует выбирать пути, увеличивающие поток. В любом случае
1
, алгоритм рано или поздно закончится и правильно вычислит максимальный поток.
Однако от способа выбора путей зависит его эффективность. Проще всего воспользоваться поиском в глубину. Обычно этот подход работает хорошо, но в худшем случае может оказаться, что каждый путь увеличивает поток только на одну единицу, и алгоритм будет работать медленно. По счастью, такой ситуации можно избежать, прибегнув к одному из описанных ниже методов.
Шаг 1
Шаг 2
Шаг 3
Шаг 4
1 2
3 6
4 5
5 0
6 0
5 0
4 0
1 0
2 0
3 0
8 0
1 2
3 6
4 5
3 2
4 2
5 0
4 0
1 0
0 2
3 0
6 2
1 2
3 6
4 5
3 2
4 2
5 0
4 0
1 0
0 2
3 0
6 2
1 2
3 6
4 5
3 2
1 5
2 3
1 3
1 0
0 2
0 3
6 2
1 2
3 6
4 5
3 2
1 5
2 3
1 3
1 0
0 2
0 3
6 2
1 2
3 6
4 5
3 2
1 5
1 4
0 4
0 1
0 2
0 3
7 1
1 2
3 6
4 5
3 2
1 5
1 4
0 4
0 1
0 2
0 3
7 1
1 2
3 6
4 5
2 3
0 6
0 5
0 4
0 1
0 2
0 3
7 1
Рис. 12.21. Алгоритм Форда–Фалкерсона
1
Утверждение верно только в случае, когда все пропускные способности целочисленные или рацио- нальные − если это не так, то существуют примеры сетей и выбора путей в них, когда алгоритм не закончится никогда, а величина потока не будет сходиться к максимальной. − Прим. ред.

12.3. Максимальные потоки

231
Алгоритм Эдмондса–Карпа выбирает путь с наименьшим числом ре- бер. Это можно сделать, применив для нахождения путей поиск в ширину вмес то поиска в глубину. Можно доказать, что при этом поток возрастает быстро, а временная сложность равна O(m
2
n
).
Алгоритм масштабирования пропускной способности
2
применяет по- иск в глубину для нахождения путей, для которых вес каждого ребра не меньше некоторого целочисленного порога. Первоначально порог равен большому числу, например сумме весов всех ребер графа. Если путь найти не удается, величина порога делится на 2. Алгоритм завершается, когда величина порога станет равна 0. Временная сложность равна O(m
2
log c), где c – начальное значение порога.
На практике алгоритм масштабирования пропускной способности реа- лизовать проще, потому что для нахождения путей применяется поиск в глубину. Оба алгоритма достаточно эффективны для решения задач, обычно предлагаемых на олимпиадах.
Минимальные разрезы. Оказывается, что одновременно с вычис- лением максимального потока алгоритм Форда–Фалкерсона находит и минимальный разрез. Рассмотрим граф, порожденный алгоритмом, и обозначим A множество вершин, достижимых из источника по ребрам по- ложительного веса. Тогда минимальный разрез состоит из ребер исходного графа, которые начинаются в некоторой вершине, принадлежащей A, заканчива- ются в некоторой вершине, не принад- лежащей A, и таких, что их пропускная способность использована в максималь- ном потоке целиком. В графе на рис. 12.22 множество A состоит из вершин 1, 2 и 4, а в минимальный разрез входят ребра 2 → 3 и
4 → 5 с суммарным весом 6 + 1 = 7.
Почему поток, вычисленный этим алго- ритмом, максимален, а разрез минимален? Потому что в графе не может быть потока, величина которого больше величины любого разреза. Следо- вательно, если величины потока и разреза равны, то поток максимален, а разрез ми- нимален.
Чтобы понять, почему это так, рассмо- трим любой разрез графа – такой, что источник принадлежит A, сток принадле- жит B и существуют ребра между этими множествами (рис. 12.23). Величина разре-
2
Этот элегантный алгоритм не слишком хорошо известен, его детальное описание можно найти в книге
Ahuja, Magnanti, Orlin [1].
1 2
3 6
4 5
2 3
0 6
0 5
0 4
0 1
0 2
0 3
7 1
Рис. 12.22. Вершины 1, 2 и 3 принадлежат множеству A
A
B
Рис. 12.23. Пропуск потока из A в B

232 
Глава 12. Дополнительные алгоритмы на графах за равна сумме весов ребер, идущих из A в B. Это верхняя граница потока в графе, потому что поток должен течь из A в B. Следовательно, величина максимального потока меньше либо равна величине любого разреза гра- фа. С другой стороны, алгоритм Форда–Фалкерсона находит поток, вели- чина которого в точности равна величине некоторого разреза. Поэтому такой поток должен быть максимален, а разрез минимален.
12.3.2. Непересекающиеся пути
Многие задачи на графах можно решить, сведя их к задаче о макси- мальном потоке. В качестве первого примера рассмотрим следующую задачу: дан ориентированный граф с источником и стоком, и требуется найти максимальное число непересекающихся путей от источника к сто- ку.
Реберно не пересекающиеся пути. Сначала решим задачу о нахожде- нии максимального числа реберно не пересекающихся путей, когда каждое ребро может встречаться не более чем в одном пути. В графе на рис. 12.24 максимальное число реберно не пересекающихся путей равно 2 (1 → 2 →
4 → 3 → 6 и 1 → 4 → 5 → 6).
1 2
3 4
5 6
1 2
3 4
5 6
Рис. 12.24. Два реберно не пересекающихся пути из вершины 1 в вершину 6
Оказывается, что максимальное число реберно не пересекающихся пу- тей всегда равно максимальному потоку в графе в случае, когда пропуск- ная способность каждого ребра равна 1. После того как максимальный поток построен, реберно не пересекающиеся пути можно найти жадно, следуя по путям от источника к стоку.
Вершинно не пересекающиеся пути. Далее рассмотрим задачу о нахождении максимального числа вершинно не пересекающихся путей от источника к стоку. В этом случае каждая вершина, кроме источника и сто- ка, должна встречаться не более чем в одном пути, вследствие чего мак- симальное число таких путей может оказаться меньше. Действительно, в

12.3. Максимальные потоки

233
1 2
3 4
5 6
Рис. 12.25. Вершинно не пере- секающийся путь из вершины 1 в вершину 6
нашем примере графа максимальное число вершинно не пересекающихся путей рав- но 1 (рис. 12.25).
Эту задачу тоже можно свести к задаче о максимальном потоке. Поскольку каждая вершина встречается самое большее в од- ном пути, мы должны ограничить поток, протекающий через вершины. Стандарт- ный способ добиться этого – расщепить каждую вершину на две, так чтобы в первую входили те же ребра, что в исходную, а из второй исходили те же ребра, что из исходной. Кроме того, мы добавляем новое ребро, идущее из первой вершины во вторую.
На рис. 12.26 показаны получившийся граф и максимальный поток в нем.
1 2
3 4
5 2
3 4
5 6
Рис. 12.26. Построение, ограничивающее поток через вершины
12.3.3. Максимальные паросочетания
Максимальным паросочетанием в графе называется множество макси- мального размера, состоящее из пар вершин, соединенных ребрами, и такое, что каждая вершина графа принадлежит не более чем одной паре.
Для решения задачи о максимальном паросочетании в графе общего вида нужны хитроумные алгоритмы, но она становится гораздо проще, если предполо- жить, что граф двудольный. В таком случае задачу можно свести к задаче о максимальном потоке.
Вершины двудольного графа можно разбить на две группы, так что любое ребро соединяет какую-то вершину из левой группы с какой-то вершиной из правой. На рис. 12.27 показано максимальное па- росочетание в двудольном графе с левой группой
{1, 2, 3, 4} и правой группой {5, 6, 7, 8}.
Чтобы свести задачу к задаче о максимальном потоке, добавим в граф еще две вершины: источник и сток. Тогда величина максимального потока в получившемся графе будет равна размеру максимального паросочета- ния в исходном графе. На рис. 12.28 показаны это сведение и максималь- ный поток для нашего примера графа.
1 2
3 4
5 6
7 8
Рис. 12.27. Макси- мальное паросоче- тание

234 
Глава 12. Дополнительные алгоритмы на графах
1 2
3 4
5 6
7 8
Рис. 12.28. Максимальное паросочетание как максимальный поток
Теорема Холла. Эту теорему можно использовать, чтобы узнать, сущест- вует ли в двудольном графе паросочетание, содержащее все левые или все правые вершины. Если количество левых и правых вершин одинаково, то теорема Холла дает ответ на вопрос, можно ли построить совершенное
паросо четание, содержащее все вершины графа.
Пусть требуется найти паросочетание, содержащее все левые вершины.
Обозначим X произвольноемножество левых вершин, а f(X)– множество их соседей. Согласно теореме Холла, паросочетание, содержащее все левые вершины, существует тогда и только тогда, когда для любого множества X имеет место неравенство |X| ≤ |f(X)|.
Продемонстрируем теорему Холла на нашем примере. Сначала возьмем
X = {1, 3} и соответственно f(X)= {5, 6, 8} (рис. 12.29). Для них условие теоре- мы Холла выполняется, потому что |X| = 2 и |f(X)| = 3. Теперь пусть X = {2, 4} и f(X)= {7} (рис. 12.30). Для них |X| = 2 и |f(X)| = 1, так что условие теоремы
Холла не выполняется. Значит, для этого графа совершенного паросоче- тания не существует. Это и неудивительно, поскольку мы уже знаем, что размер максимального паросочетания для него равен 3, а не 4.
1 2
3 4
5 6
7 8
1 2
3 4
5 6
7 8
Рис. 12.29. X = {1,3} и f(X) = {5, 6, 8} Рис. 12.30. X = {2,4} и f(X) = {7}
Если условие теоремы Холла не выполняется, то множество X объясня- ет, почему такое паросочетание невозможно. Поскольку X содержит боль- ше вершин, чем f(X), пары существуют не для всех вершин из X. Так, на рис. 12.30 обе вершины 2 и 4 следовало бы соединить с вершиной 7, что недопустимо.
Теорема Кёнига. Минимальным вершинным покрытием графа называ- ется минимальное множество вершин – такое, что для любого ребра графа

12.3. Максимальные потоки

235
хотя бы одна его вершина входит в это множество. В общем случае задача о нахождении минимального вершинного покрытия является NP-труд- ной. Но если граф двудольный, то по теореме Кёнига размер минимально- го вершинного покрытия равен размеру максимального паросочетания.
А раз так, то мы можем вычислить этот размер с помощью алгоритма на- хождения максимального потока.
Поскольку размер максимального паросочетания в нашем примере графа равен 3, то по теореме Кёнига размер минимального вершинного покрытия тоже равен 3. На рис. 12.31 показан пример такого покры- тия.
Вершины, не принадлежащие минимальному вершинному покрытию, образуют максимальное независимое множество. Это максимальное мно- жество вершин – такое, что никакие две принадлежащие ему вершины не соединены ребром. Задача о нахождении максимального независимого множества в графе общего вида также является NP-трудной, но для дву- дольного графа ее можно эффективно решить, пользуясь теоремой Кё- нига. На рис. 12.32 показано максимальное независимое множество для нашего графа.
1 2
3 4
5 6
7 8
1 2
3 4
5 6
7 8
Рис. 12.31. Минимальное вершинное покрытие
Рис. 12.32. Максимальное независимое множество
12.3.4. Покрытие путями
Покрытием путями называется такое множество путей, что любая вер- шина графа принадлежит, по крайней мере, одному пути. Оказывается, что для ориентированного ациклического графа задачу о нахождении ми- нимального покрытия путями можно свести к задаче о нахождении мак- симального потока в другом графе.
Покрытия вершинно не пересекающимися путями. В случае покры- тия вершинно не пересекающимися путями каждая вершина принадлежит ровно одному пути. Для примера рассмотрим граф на рис. 12.33. Его ми- нимальное покрытие вершинно не пересекающимися путями состоит из трех путей (рис. 12.34).

236 
Глава 12. Дополнительные алгоритмы на графах
1 2
3 4
5 6
7 1
5 6
7 2
3 4
Рис. 12.33. Пример графа для построения покрытия путями
Рис. 12.34. Минимальное покрытие вершинно не пересекающимися путями
Чтобы найти минимальное покрытие вершинно не пересекающимися путями, построим граф паросочетаний, в котором каждая вершина ис- ходного графа представлена двумя вершинами: левой и правой. Между вершиной слева и вершиной справа проведено ребро, если такое ребро существует в исходном графе. Кроме того, граф паросочетаний содержит источник и сток, причем источник соединен ребрами со всеми левыми вершинами, а все правые вершины соединены ребрами со стоком. Каж- дому ребру, принадлежащему максимальному паросочетанию в графе па- росочетаний, соответствует ребро в минимальном покрытии вершинно не пересекающимися путями исходного графа. Следовательно, размер мини- мального покрытия вершинно не пересекающимися путями равен n − c, где n – количество вершин исходного графа, а c – размер максимального паросочетания.
На рис. 12.35 показан граф паросочетаний для графа на рис. 12.33. Раз- мер максимального паросочетания в нем равен 4, поэтому минимальное покрытие вершинно не пересекающимися путями состоит из 7 − 4 = 3 путей.
1 2
3 4
5 6
7 1
2 3
4 5
6 7
Рис. 12.35. Граф паросочетаний для нахождения минимального покрытия вершинно не пересекающимися путями
Покрытие общими путями. Так называется покрытие путями, в кото- ром допускаются вершины, принадлежащие сразу нескольким путям. Ми-

12.3. Максимальные потоки

237
нимальное покрытие общими путями может быть меньше минимального покрытия вершинно не пересекающимися путями, потому что одну вер- шину можно использовать в путях не- сколько раз. Снова рассмотрим граф на рис. 12.33. Для него минимальное покрытие общими путями состоит из двух путей (рис. 12.36).
Минимальное покрытие общими путями можно найти почти так же, как минимальное покрытие вершин- но не пересекающимися путями. Достаточно добавить несколько ребер в граф паросочетаний, так чтобы реб ро a → b существовало всегда, когда существует путь из a в b в исходном графе (возможно, проходящий через несколько вершин). На рис. 12.37 показан такой граф паросочетаний для нашего примера.
1 2
3 4
5 6
7 1
2 3
4 5
6 7
Рис. 12.37. Граф паросочетаний для нахождения минимального покрытия общими путями
Теорема Дилуорса. Антицепью называется множество вершин гра- фа – такое, что между любыми двумя принадлежащими ему вершина- ми не существует пути, проходящего по ребрам графа. Теорема Дилуор- са утверждает, что в ориентированном ациклическом графе размер минималь- ного покрытия общими путями равен размеру максимальной антицепи. В гра- фе на рис. 12.38 вершины 3 и 7 образуют анти цепь из двух вершин. Это максималь- ная антицепь, потому что минимальное покры тие этого графа общими путями состо ит из двух путей (рис. 12.36).
1 5
6 3
4 2
6 7
Рис. 12.36. Минимальное покрытие общими путями
1 2
3 4
5 6
7
Рис. 12.38. Вершины 3 и 7 образуют максимальную антицепь

238 
Глава 12. Дополнительные алгоритмы на графах
12.4. Деревья поиска в глубину
В процессе обработки связного графа поиск в глубину попутно создает корневое ориентированное остовное дерево, которое называется деревом
поиска в глубину. Ребра графа можно классифицировать по их роли в по- иске. В неориентированном графе могут встречаться ребра двух типов:
ребра дерева, принадлежащие дереву поиска в глубину, и обратные ребра, ведущие в уже посещенные вершины. Отметим, что обратное ребро всегда ведет в предок вершины.
На рис. 12.39 показаны граф и его дерево поиска в глубину. Сплошными линиями изображены ребра дерева, а штриховыми – обратные ребра.
1 2
3 4
5 6
7 1
2 3
4 5
6 7
Рис. 12.39. Граф и его дерево поиска в глубину
В этом разделе мы обсудим некоторые применения деревьев поиска в глубину при обработке графов.
12.4.1. Двусвязность
Связный граф называется двусвязным, если он остается связным пос- ле удаления любой вершины (и инцидентных ей ребер). Левый граф на рис. 12.40 является двусвязным, а правый – нет, поскольку после удаления вершины 3 граф распадается на две компоненты: {1, 4} и {2, 5}.
1 2
3 4
5 6
1 2
3 4
5
Рис. 12.40. Граф слева двусвязный, а граф справа – нет
Вершина называется точкой сочленения, если в результате ее удаления граф перестает быть связным. Следовательно, в двусвязном графе нет то- чек сочленения. Аналогично ребро называется мостом, если его удаление нарушает связность графа. На рис. 12.41 вершины 4, 5 и 7 являются точка- ми сочленения, а ребра 4–5 и 7–8 – мостами.

12.4. Деревья поиска в глубину

239
1 2
3 4
5 6
7 8
Рис. 12.41. Граф с тремя точками сочленения и двумя мостами
Для эффективного нахождения всех точек сочленения и мостов можно воспользоваться поиском в глубину. Чтобы найти мосты, мы начинаем поиск из произвольной вершины и строим дерево поиска в глубину. На рис. 12.42 показано дерево поиска в глубину для нашего графа.
Ребро a → b является мостом тогда и только тогда, когда это ребро де- рева и не существует обратных ребер из поддерева b в a или в любой пре- док a. Так, на рис. 12.42 ребро 5 → 4 является мостом, потому что не су- ществует обратных ребер из вершин {1, 2, 3, 4} в вершину 5. Однако ребро
6 → 7 мостом не является, потому что существует обратное ребро 7 → 5, а вершина 5 является предком вершины 6.
1 2
3 4
5 6
7 8
Рис. 12.42. Нахождение мостов и точек сочленения с помощью поиска в глубину
Найти точки сочленения несколько труднее, но дерево поиска в глубину поможет и в этом случае. Во-первых, если вершина x – корень дерева, то она является шарниром тогда и только тогда, когда имеет две или более дочерние вершины. Если же x – не корень, то она является точкой сочле- нения тогда и только тогда, когда имеет дочернюю вершину, поддерево которой не содержит обратного ребра в вершину-предок x.
В графе на рис. 12.42 вершина 5 является точкой сочленения, поскольку она корневая и имеет две дочерние вершины, а вершина 7 – точка сочле- нения, потому что дерево ее дочерней вершины 8 не содержит обратного ребра в вершину-предок 7. Однако вершина 2 не является точкой сочлене- ния, потому что сущест вует обратное ребро 3 → 4, а вершина 8 – не точка сочленения, потому что у нее вообще нет дочерних вершин.

240 
Глава 12. Дополнительные алгоритмы на графах
12.4.2. Эйлеровы подграфы
Эйлеров подграф графа содержит все его вершины и часть ребер – такую, что степень каждой вершины четна. На рис. 12.43 показаны граф и его эй- леров подграф.
Рассмотрим задачу о вычислении количества эйлеровых подграфов связного графа. Оказывается, что существует простая формула: количест- во эйлеровых подграфов равно 2
k
, где k – число обратных ребер в дереве поиска графа в глубину. Отметим, что k = m − (n − 1), где n – число вершин, а m – число ребер.
Дерево поиска в глубину помогает понять, что эта формула справедлива.
Рассмотрим произвольное фиксированное подмножество обратных ребер в дереве поиска в глубину. Чтобы создать эйлеров граф, содержащий эти ребра, мы должны выбрать подмножество ребер дерева, так чтобы степень каждой вершины была четна. Для этого мы будем обрабатывать дерево снизу вверх и включать ребро дерева в подграф тогда и только тогда, когда оно ведет в вершину, степень которой с учетом этого ребра станет четной.
Тогда, поскольку сумма степеней вершин всегда четна, степень корневой вершины тоже будет четна.
1 2
3 4
5 6
7 8
1 2
3 4
5 6
7 8
Рис. 12.43. Граф и его эйлеров подграф
12.5. Потоки минимальной стоимости
В задаче о потоке минимальной стоимости задан ориентированный граф с источником и стоком. С каждым ребром ассоциировано две величины:
пропускная способность, т. е. максимальный поток, который можно про- пустить по этому ребру, и стоимость – цена за единицу потока через это ребро. Задача заключается в том, чтобы пропустить k единиц потока из источника в сток, минимизировав полную стоимость потока.
Задача о потоке минимальной стоимости похожа на задачу о макси- мальном потоке (раздел 12.3), но имеет два отличия. Во-первых, мы хотим

12.5. Потоки минимальной стоимости

241
пропустить ровно k единиц потока, даже если есть возможность пропус- тить больше. Во-вторых, у ребер есть стоимости, и требуется найти реше- ние, минимизирующее полную стоимость потока.
Например, на рис. 12.44 показан граф, в котором вершина 1 является источником, а вершина 4 – стоком. Запись a; b означает, что пропускная способность ребра равна a, а его стоимость равна b. В частности, мы можем пропустить не более 5 единиц потока из вершины 2 в вершину 3, при этом цена за единицу потока будет равна 3. На рис. 12.45 показан оптимальный способ пропустить k = 4 единицы потока из источника в сток. Стоимость этого решения равна 29, и вычисляется она следую щим образом:
• пропустить 2 единицы потока из вершины 1 в вершину 2 (стои- мость 2 · 1 = 2);
• пропустить 1 единицу потока из вершины 2 в вершину 3 (стои- мость 1 · 3 = 3);
• пропустить 1 единицу потока из вершины 2 в вершину 4 (стои- мость 1 · 8 = 8);
• пропустить 2 единицы потока из вершины 1 в вершину 3 (стои- мость 2 · 5 = 10);
• пропустить 3 единицы потока из вершины 3 в вершину 4 (стои- мость 3 · 2 = 6).
1 2
3 4
2;1 6;8 5;5 3;2 5;3
Рис. 12.44. Задача о потоке мини- мальной стоимости
1 2
3 4
2/2;1 1/6;8 2/5;5 3/3;2 1/5;3
Рис. 12.45. Оптимальный способ пропустить 4 единицы потока
Заметим, что задача о потоке минимальной стоимости поставлена в очень общем виде, и у нее есть ряд частных случаев. Если требуется опре- делить максимальное значение k, не обращая внимания на стоимости, то получаем задачу о максимальном потоке. А если пропускная способность каждого ребра бесконечна (или, по крайней мере, не меньше k), то задача сводится к нахождению пути минимальной стоимости из источника в сток.
12.5.1. Алгоритм путей минимальной стоимости
В предположении, что входной граф не содержит циклов, имеющих от- рицательную стоимость, то задачу о потоке минимальной стоимости мож- но решить, воспользовавшись модифицированным вариантом алгоритма
Форда–Фалкерсона (раздел 12.3). Как и в задаче о максимальном потоке,

242 
Глава 12. Дополнительные алгоритмы на графах мы строим пути, генерирующие поток из источника в сток. Оказывается, что если всегда выбирать путь с минимальной полной стоимостью, то по- лучающийся поток будет оптимальным решением задачи о потоке мини- мальной стоимости [9].
Чтобы воспользоваться алгоритмом Форда–Фалкерсона, мы сначала для каждого ребра добавим ребро, идущее в противоположном направлении и имеющее пропускную способность 0 и стоимость –c, где c – стоимость оригинального ребра
3
В процессе работы алгоритма стоимости ребер не изменяются. Затем мы выполняем алгоритм Форда–Фалкерсона и всегда выбираем путь минимальной стоимости из источника в сток. Мы увели- чиваем поток и обновляем пропускные способности, как в задаче о макси- мальном потоке, со следующим исключением: если текущий поток равен f
и путь привел бы к его увеличению на x, где f + x > k, то мы увеличиваем поток только на k − f и сразу же завершаем работу.
Хотя в графе нет циклов отрицательной стоимости, в нем могут быть ребра отрицательной стоимости. Поэтому мы строим пути минимальной стоимости, применяя алгоритм Беллмана–Форда, поддерживающий отри- цательные стоимости ребер. Результирующий алгоритм работает за время
O(nmk), потому что каждый путь увеличивает поток по крайней мере на единицы, а для нахождения пути с помощью алгоритма Беллмана–Форда требуется время O(nm).
На рис. 12.46 показано, как работает алгоритм для нашего графа в предпо- ложении, что требуемый поток k = 4. Сначала строится путь 1 → 2 → 3 → 4, стоимость которого равна 1 + 3 + 2 = 6. Этот путь увеличивает сам поток на 2, а его стоимость – на 2 · 6 = 12. Затем алгоритм строит путь 1 → 3 → 4, который увеличивает поток 1, а его стоимость – на 7. Наконец, алгоритм строит путь 1 → 3 → 2 → 4, который увеличивает поток 1, а его стоимость – на 10. Заметим, что последний путь мог бы увеличить поток на 2, но уве- личивает только на 1, потому что требуемый поток равен 4. Полная стои- мость решения равна 12 + 7 + 10 = 29, как мы и ожидали.
Почему этот алгоритм работает? Он основан на факте, который мы здесь доказывать не будем: если в графе (с добавленными противоположными ребрами) имеется поток величины f и не существует цикла с отрицатель- ной стоимостью, в котором каждое ребро имеет положительную пропуск- ную способность, то этот поток является потоком величины f минималь- ной стоимости.
Мы знаем, что в исходном графе нет циклов с отрицательной стои- мостью, а поскольку мы всегда строим путь минимальной стоимости из источника в сток, гарантируется, что цикл с отрицательной стоимостью никогда и не возникнет. Поэтому, коль скоро мы можем построить поток
3
Если существует как ребро из a в b, так и ребро из
b в a, то необходимо добавить противоположное ребро для каждого из них. Таким образом, мы не можем комбинировать ребра, как в задаче о мак- симальном потоке, потому что ребра имеют стоимость, которую нужно принимать во внимание.

12.5. Потоки минимальной стоимости

243
величины k, не создавая циклов с отрицательной стоимостью, результи- рующий поток обязан быть потоком минимальной стоимости величины k.
Шаг 1
Шаг 2 3
1 2
3 4
2;1 0;-1 6;8 0;-8 5;5 0;-5 3;2 0;-2 5;3 0;-3 1
2 3
4 0;1 2;-1 6;8 0;-8 5;5 0;-5 1;2 2;-2 3;3 2;-3 1
2 3
4 0;1 2;-1 6;8 0;-8 5;5 0;-5 1;2 2;-2 3;3 2;-3 1
2 3
4 0;1 2;-1 6;8 0;-8 4;5 1;-5 0;2 3;-2 3;3 2;-3 1
2 4
0;1 2;-1 6;8 0;-8 4;5 1;-5 0;2 3;-2 3;3 2;-3 1
2 3
4 0;1 2;-1 5;8 1;-8 3;5 2;-5 0;2 3;-2 4;3 1;-3
Шаг 3
Рис. 12.46. Вычисление потока минимальной стоимости (k = 4) с помощью алгоритма путей минимальной стоимости
12.5.2. Паросочетания минимального веса
Одно из приложений потоков минимальной стоимости – решение зада- чи о паросочетаниях минимального веса в двудольном графе. Пусть дан взве- шенный двудольный граф, требуется найти паросочетание величины k с минимальным полным весом. Эта задача является обобщением задачи о максимальном паросочетании в двудольном графе, и решить ее можно ана- логично, воспользовавшись алгоритмом потока минимальной стоимости.
Например, предположим, что в компании имеется n работников и n за- дач, что каждому работнику можно назначить ровно одну задачу и что для каждого работника известна стоимость выполнения им каждой зада-

244 
Глава 12. Дополнительные алгоритмы на графах чи. Какова минимальная полная стоимость при оптимальном назначении работ? Например, для следующих входных данных
Работник
Задача 1
Задача 2
Задача 3
Анна
150 400 200
Джон
400 350 200
Мария
500 100 250
оптимальное решение таково: назначить задачу 1 Анне, задачу 2 – Ма- рии и задачу 3 – Джону. Полная стоимость этого решения равна 150 +
100 + 200 = 450.
На рис. 12.47 показано, как эту задачу можно представить в виде зада- чи о потоке минимальной стоимости. Создаем граф с 2n + 2 вершинами: источник, сток и по одной вершине для каждого работника и каждой за- дачи. Пропускная способность каждого ребра равна 1, стоимость каждого реб ра, исходящего из источника или входящего в сток, равна 0, а стоимость ребра, соединяющего работника с задачей, равна стоимости назначения этой задачи данному работнику. Тогда поток минимальной стоимос ти вели чины n в этом графе соответствует оптимальному решению.
A
J
M
1 2
3
Рис. 12.47. Нахождение оптимального назначения путем представления паросочетания минимального веса в виде потока минимальной стоимости
12.5.3. Улучшение алгоритма
Если бы мы знали, что в графе, который используется в алгоритме путей минимальной стоимости, нет ребер с отрицательной стоимостью и поло- жительной пропускной способностью, то могли бы улучшить алгоритм, воспользовавшись алгоритмом Дейкстры вместо алгоритма Беллмана–
Форда. Оказывается, что это можно сделать, модифицировав граф, так что в нем не будет ребер с отрицательной стоимостью и положительной пропускной способностью, но в то же время каждому пути минимальной стои мости в новом графе будет соответствовать путь минимальной стои- мости в исходном графе.
Мы применим следующий прием, который используется также в алго- ритме Джонсона [18]. Предположим, что каждой вершине x сопоставлено

12.5. Потоки минимальной стоимости

245
значение p[x], которое может быть любым числом. Тогда можно модифи- цировать граф, так что стоимость ребра из вершины a в вершину b станет равна c(a, b) + p[a] − p[b], где c(a, b)– его первоначальная стоимость. При та- кой модификации ни один путь минимальной стоимости не изменяется: если стоимость пути из вершины x в вершину y в исходном графе равна k, то стоимость того же пути в новом графе равна k + p[x] − p[y], где p[x] − p[y] постоянно для всех путей из x в y. Это так, потому что значения p в проме- жуточных вершинах пути взаимно уничтожаются.
Идея заключается в том, чтобы выбрать значения p таким образом, что- бы после модификации не осталось ребер отрицательной стоимости. Для этого достаточно положить p[x] равным минимальной стоимости пути из источника в вершину x. После этого для любого ребра из a в b имеем
p[b] ≤ p[a] + c(a, b),
а это означает, что
c(a, b) + p[a] − p[b] ≥ 0,
т. е. новая стоимость ребра неотрицательна.
Теперь можно реализовать алгоритм путей минимальной стоимости сле- дующим образом. Сначала выполняем один раз алгоритм Беллмана–Фор- да, начиная из источника, и строим пути минимальной стоимости во все вершины, которых можно достичь по ребрам с положительной пропускной способностью. Затем модифицируем стоимости ребер, выбирая значения p
так, чтобы все ребра с положительной пропускной способностью получи- ли неотрицательную стоимость. После этого запускаем основной алгоритм, который генерирует поток и использует алгоритм Дейкстры для нахожде- ния путем минимальной стоимости. Мы всегда строим пути минимальной стоимости во все вершины, которых можно достичь по ребрам с положи- тельной пропускной способностью, а потом обновляем стоимости ребер в соответствии со значениями p. Затем используем первоначальные стои- мости ребер при вычислении стоимости нового пути. Итоговый алгоритм работает за время O(nm + k(m log n)), поскольку мы один раз выполнили алгоритм Беллмана–Форда и не более k раз алгоритм Дейкстры.
На рис. 12.48 показано, как улучшенный алгоритм находит поток мини- мальной стоимости в нашем графе. Мы уже модифицировали начальные стоимости ребер с помощью алгоритма Беллмана–Форда, а теперь три раза выполнили алгоритм Дейкстры для построения путей минималь- ной стоимости. Стоимость каждого ребра с положительной пропускной способностью неотрицательна, поэтому алгоритм Дейкстры работает пра- вильно. Заметим, что каждый путь соответствует пути на рис. 12.46; раз- личаются только стоимости ребер, поэтому мы должны использовать ис- ходные стоимости при вычислении стоимости результирующего потока.

246 
Глава 12. Дополнительные алгоритмы на графах
В первый раз мы используем алгоритм Беллмана–Форда, потому что в ис- ходном графе могут существовать ребра с положительной пропускной способ- ностью и отрицательной стоимостью. Но после этого мы уверены, что таких ребер нет, поэтому можем использовать алгоритм Дейкстры. Отметим, что пропускные способности некоторых ребер изменяются, когда поток увеличи- вается после построения пути, но это никогда не приводит к появлению ре- бер отрицательной стоимости, потому что все такие ребра принадлежат пути минимальной стоимости из источника в сток: если путь ведет из вершины a
в вершину b, то мы знаем, что p[b] = p[a] + c(a, b), а это означает, что как новая стоимость пути из a в b, так и новая стоимость пути из b в a будут равны 0.
3 1
2 3
4 2;0 0;0 6;3 0;-3 5;1 0;-1 3;0 0;0 5;0 0;0 1
2 3
4 0;0 2;0 6;3 0;-3 5;1 0;-1 1;0 2;0 3;0 2;0 1
2 3
4 0;0 2;0 6;3 0;-3 5;1 0;-1 1;0 2;0 3;0 2;0 1
2 3
4 0;-1 2;1 6;3 0;-3 4;0 1;0 0;0 3;0 3;0 2;0 1
2 4
0;-1 2;1 6;3 0;-3 4;0 1;0 0;0 3;0 3;0 2;0 1
2 3
4 0;-1 2;1 5;0 1;0 3;0 2;0 0;-3 3;3 4;0 1;0
Шаг 2
Шаг 1
Шаг 3
Рис. 12.48. Нахождение потока минимальной стоимости (k = 4) с помощью улучшенного алгоритма
При практической реализации улучшенного алгоритма путей мини- мальной стоимости необязательно модифицировать стоимости ребер.
Можно просто прибавлять и вычитать значения p в момент построения путей, а затем обновлять значения p после каждого раунда.