анти. Guide to Competitive

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

Глава
12
Дополнительные алгоритмы
на графах
В этой главе обсуждаются некоторые дополнительные алгоритмы на гра- фах.
В разделе 12.1 описан алгоритм нахождения компонент сильной связ- ности графа. Затем мы покажем, как с помощью этого алгоритма эффек- тивно решить задачу 2-выполнимости.
Раздел 12.2 посвящен эйлеровым и гамильтоновым путям. Эйлеров путь проходит по всем ребрам графа в точности один раз, а гамильтонов путь заходит в каждую вершину графа ровно один раз. Хотя на первый взгляд эти задачи очень схожи, их вычислительная сложность отличается кардинально.
В разделе 12.3 мы сначала покажем, как найти максимальный поток между источником и стоком в графе, а затем увидим, как можно свести несколько других задач на графах к задаче о максимальном потоке.
В разделе 12.4 рассматриваются свойства поиска в глубину и задачи, от- носящиеся к двусвязным графам.
12.1. Сильная связность
Ориентированный граф называется сильно связным, если существует путь из любой вершины в любую другую вершину. Так, левый граф на рис. 12.1 сильно связный, а правый – нет. Правый граф не является сильно связным, например потому, что не существует пути из вершины 2 в вершину 1.
1 2
3 4
1 2
3 4
Рис. 12.1. Граф слева является сильно связным, а граф справа – нет
Любой ориентированный граф можно разбить на компоненты сильной связности. Каждая такая компонента состоит из максимального множест-

220 
Глава 12. Дополнительные алгоритмы на графах ва вершин – такого, что существует путь из любой вершины, принадлежащей мно- жеству, в любую другую. Эти компоненты образуют ациклический граф компонент, представляющий глубинную структуру исходного графа. На рис. 12.2 показаны граф, его компоненты сильной связности и соответствующий граф компонент. Ком- понентами являются A = {1, 2}, B = {3, 6, 7},
C = {4} и D = {5}.
Поскольку граф компонент ацикличес- кий, обработать его проще, чем исходный.
Благодаря отсутствию циклов мы можем построить для него топологичес кую сор- тировку и обработать ее, применив дина- мическое программирование.
12.1.1. Алгоритм Косарайю
Алгоритм Косарайю дает эффективный способ нахождения компонент сильной связности графа. Он включает два поиска в глубину: первый строит список вершин, отражающий структуру графа, а второй формирует компоненты сильной связности.
На первом этапе алгоритма Косарайю строится список вершин в порядке их посещения в процессе поиска в глубину. Алгоритм перебирает все вер- шины и начинает поиск в глубину из каж- дой еще не обработанной. По завершении обработки вершина добавляется в список.
На рис. 12.3 показан порядок обработки вершин графа из нашего примера. Нота- ция x/y означает, что обработка вершины началась в момент x и закончилась в мо- мент y. В результате получается список
[4, 5, 2, 1, 6, 7, 3].
На втором этапе алгоритма Косарайю формируются компоненты сильной связ- ности. Сначала все ребра графа инверти- руются. Тем самым гарантируется, что в процессе второго поиска будут найдены правильные компоненты сильной связно- сти. На рис. 12.4 показан наш граф с инвер- тированными ребрами.
7 3
2 1
6 5
4 7
3 2
1 6
5 4
B
A
D
C
Рис. 12.2. Граф, его компоненты сильной связности и граф компонент
7 3
2 1
6 5
4 1
/8 2
/7 9
/14 4
/5 3
/6 11
/12 10
/13
Рис. 12.3. Порядок обработки вершин
7 3
2 1
6 5
4
Рис. 12.4. Граф с инвертированными ребрами

12.1. Сильная связность

221
После этого алгоритм пробегает по списку вершин, созданному на пер- вом этапе, в обратном порядке. Если вершина еще не принадлежит ника- кой компоненте, то создается новая компонента, для чего алгоритм начи- нает поиск в глубину, который добавляет все найденные новые вершины в новую компоненту. Отметим, что поскольку все ребра инвертированы, компоненты не «просачиваются» в другие части графа.
На рис. 12.5 показано, как алгоритм обрабатывает наш граф. Вершины обрабатываются в порядке [3, 7, 6, 1, 2, 5, 4]. Сначала по вершине 3 генери- руется компонента {3, 6, 7}. Затем вершины 7 и 6 пропускаются, поскольку уже принадлежат некоторой компоненте. После этого по вершине 1 гене- рируется компонента {1, 2}, а вершина 2 пропускается. Наконец, по верши- нам 5 и 4 генерируются компоненты {5} и {4}.
7 3
2 1
6 5
4
Шаг 1
7 3
2 1
6 5
4
Шаг 2
7 3
2 1
6 5
4 7
3 2
1 6
5 4
Шаг 4
Шаг 3
Рис. 12.5. Построение компонент сильной связности
Временная сложность алгоритма равна O(n + m), поскольку выполняется два поиска в глубину.
12.1.2. Задача 2-выполнимости
В задаче 2-выполнимости, или 2SAT, дана логическая формула
(a
1
∨ b
1
)∧ (a
2
∨ b
2
)∧ … ∧ (a
m
∨ b
m
),
где a
i
и b
i
– либо логическая переменная (x
1
, x
2
, …, x
n
), либо отрицание ло- гической переменной(¬x
1
, ¬x
2
, …, ¬x
n
). Символами «∧» и «∨» обозначаются логические операторы И и ИЛИ. Задача состоит в том, чтобы присвоить каждой переменной значение, так чтобы формула была истинной, или до- казать, что это невозможно.
Например, формула

222 
Глава 12. Дополнительные алгоритмы на графах
L
1
= (x
2
∨ ¬x
1
)∧ (¬x
1
∨ ¬x
2
)∧ (x
1
∨ x
3
)∧ (¬x
2
∨ ¬x
3
) ∧ (x
1
∨ x
4
)
истинна, если переменным присвоены следующие значения:
⎧x
1
= false
⎨
x
2
= false .
⎩
x
3
= true
x
4
= true
Однако формула
L
2
= (x
1
∨ x
2
) ∧ (x
1
∨ ¬x
2
) ∧ (¬x
1
∨ x
3
) ∧ (¬x
1
∨ ¬x
3
)
ложна при любых значениях переменных. Дело в том, что мы не можем выбрать значение x
1
, не приводящее к противоречию. Если x
1
равно false
, то x
2
и ¬x
2
должны быть равны true
, что невозможно, а если x
1
равно true
, то x
3
и ¬x
3
должны быть равны true
, что также невозможно.
Задачу 2SAT можно представить графом
импликаций, вершины которого соответ- ствуют переменным x
i
и отрицаниям ¬x
i
, а ребра определяют связи между этими пе- ременными. Каждая пара (a
i
∨ b
i
)порожда- ет два ребра: ¬a
i
→ b
i
и ¬b
i
→ a
i
. Это означа- ет, что если a
i
не выполняется, то должно выполняться b
i
,и наоборот. На рис. 12.6 по- казан граф импликаций для формулы L
1
, а на рис. 12.7 – для формулы L
2
Из структуры графа импликаций понят- но, можно ли присвоить переменным зна- чения, так чтобы формула была истинной.
Это возможно тогда и только тогда, когда не существует вершин x
i
и ¬x
i
– таких, что обе они принадлежат одной и той же ком- поненте сильной связности. Если такие вершины существуют, то граф содержит как путь из x
i
в ¬x
i
, так и путь из ¬x
i
в x
i
, поэтому x
i
и ¬x
i
должны быть равны true одновременно, что невозможно. В графе импликаций для L
1
не существует вершин x
i
и ¬x
i
, принадлежащих одной и той же компонен- те сильной связности, поэтому задача имеет решение. Напротив, в графе импликаций для L
2
все вершины принадлежат одной компоненте сильной связности, так что решений нет.
Если решение существует, то значения переменных можно найти, обой- дя вершины графа компонент в порядке обратной топологической сорти- ровки. На каждом шаге обрабатывается компонента, которая не содержит ребер, ведущих в необработанную компоненту. Если переменным, попав-
¬x
3
x
2
¬x
4
x
1
¬x
1
x
4
¬x
2
x
3
Рис. 12.6. Граф импликаций для L
1
x
3
x
2
¬x
2
¬x
3
¬x
1
x
1
Рис. 12.7. Граф импликаций для L
2

12.2. Полные пути

223
шим в компоненту, еще не были присвоены значения, то их значения за- даются в соответствии со значениями в компоненте, а ранее присвоенные значения не изменяются. Процесс продолжается до тех пор, пока каждой переменной не будет присвоено значение.
На рис. 12.8
показан граф компонентов для L
1
. Компонентами являются
A = {¬x
4
}, B = {x
1
, x
2
, ¬x
3
}, C = {¬x
1
, ¬x
2
, x
3
} и D = {x
4
}. При построении реше- ния сначала обрабатывается компонента D, и x
4
получает значение true
Пос ле этого обрабатывается компонента C, в результате чего x
1
и x
2
полу- чают значения false
, а x
3
– значение true
Теперь всем переменным присвоены зна- чения, поэтому обработка оставшихся ком- понент A и B ничего не изменит.
Этот метод работает в силу одной особенности структуры графа импли- каций: если существует путь из вершины x
i
в вершину x
j
и из вершины x
j
в вершину ¬x
j
, то x
i
никогда не получит значения true
. Причина в том, что существует также путь из вершины ¬x
j
в вершину ¬x
i
, и как x
i
, так и x
j
полу- чают значение false
Более трудна задача о 3-выполнимости (3SAT), в которой каждая часть формулы имеет вид (a
i
∨ b
i
∨ c
i
). Она является NP-трудной, т. е. для нее неизвестен эффективный алгоритм решения.
12.2. Полные пути
В этом разделе мы рассмотрим два специальных типа путей в графах: эй- леров путь, проходящий по всем ребрам графа ровно один раз, и гамильто- нов путь, заходящий в каждую вершину ровно один раз. На первый взгляд, эти пути очень похожи, но вычислительная сложность их нахождения ра- зительно отличается.
12.2.1. Эйлеровы пути
Эйлеровым путем называется путь, который проходит по каждому реб- ру графа ровно один раз. Если такой путь начинается и заканчивается в одной и той же вершине, то он называется эйлеровым циклом. На рис. 12.9 показан эйлеров путь из вершины 2 в вершину 5, а на рис. 12.10 – эйлеров цикл, начинающийся в вершине 1.
1 2
3 4
5 1
2 3
4 5
1.
2.
3.
4.
5.
6.
Рис. 12.9. Граф и его эйлеров путь
A
B
C
D
Рис. 12.8. Граф компонент для L
1

224 
Глава 12. Дополнительные алгоритмы на графах
1 2
3 4
5 1
2 3
4 5
1.
2.
3.
4.
5.
6.
Рис. 12.10. Граф и его эйлеров цикл
Существование эйлеровых путей и циклов зависит от степеней вершин.
В неориентированном графе эйлеров путь существует тогда и только тог- да, когда все ребра принадлежат одной и той же компоненте связности и
• степень каждой вершины четна или
• существует ровно две вершины нечетной степени, а степени всех остальных четны.
В первом случае каждый эйлеров путь является эйлеровым циклом. Во втором случае конечными точками эйлерова пути являются вершины не- четной степени, и этот путь не является циклом. На рис. 12.9 вершины 1,
3 и 4 имеют степень 2, а вершины 2 и 5 – степень 3. Имеется ровно две вершины нечетной степени, поэтому между вершинами 2 и 5 существует эйлеров путь, не являющийся циклом. На рис. 12.10 степени всех вершин четны, поэтому в графе существует эйлеров цикл.
Чтобы понять, существуют ли эйлеровы пути в ориентированном гра- фе, будем рассматривать полустепени захода и исхода. Ориентированный граф содержит эйлеров путь тогда и только тогда, когда все ребра принад- лежат одной и той же компоненте сильной связности и
• полустепени захода и исхода каждой вершины равны или
• существует одна вершина, для которой полустепень захода на еди- ницу больше полустепени исхода, еще одна вершина, для которой полустепень исхода на единицу больше полустепени захода, а во всех остальных вершинах полустепени захода и исхода равны.
В первом случае каждый эйлеров путь является эйлеровым циклом, а во втором случае в графе существует эйлеров путь, начинающийся в вер- шине, где полустепень исхода больше, и заканчивающийся в вершине, где полустепень захода больше. На рис. 12.11 у вершин 1, 3 и 4 полустепени захода и исхода равны 1, у вершины 2 полустепень захода равна 1, а по- лустепень исхода равна 2, и у вершины 5 полустепень захода равна 2, а полустепень исхода равна 1. Следовательно, граф содержит эйлеров путь из вершины 2 в вершину 5.
Построение. Эффективный способ построения эйлерова цикла графа дает
алгоритм Хирхольцера. Он состоит из нескольких раундов, на каждом из ко- торых в цикл добавляются новые ребра. Конечно, предполагается, что граф содержит эйлеров цикл, иначе алгоритм Хирхольцера не сможет его найти.

12.2. Полные пути

225
1 2
3 4
5 1
2 3
4 5
1.
2.
3.
4.
5.
6.
Рис. 12.11. Ориентированный граф и его эйлеров путь
Алгоритм начинает работу с пустого цикла, содержащего единствен- ную вершину, а затем расширяет этот цикл, добавляя в него подциклы на каждом шаге. Процесс продолжается, пока в цикл не будут включены все ребра. Для расширения цикла мы находим в цикле вершину x, для кото- рой существует исходящее ребро, не включенное в цикл. Затем строится новый путь из вершины x, содержащий только ребра, еще не включенные в цикл. Рано или поздно этот путь вернется в вершину x, с которой началось создание подцикла.
Если граф не содержит эйлерова цикла, но содержит эйлеров путь, то алгоритм Хирхольцера можно использовать для нахождения этого пути.
Для этого нужно включить в граф дополнительное ребро и исключить его, после того как будет построен цикл. Например, в случае неориентирован- ного графа дополнительное ребро проводится между двумя вершинами нечетной степени.
1 2
3 4
5 6
7
Шаг 1
1 2
3 4
5 6
7 1.
2.
3.
Шаг 2
1 2
3 4
5 6
7 1.
2.
3.
4.
5.
6.
1 2
3 4
5 6
7 1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Шаг 4
Шаг 3
Рис. 12.12. Алгоритм Хирхольцера
На рис. 12.12 показано, как алгоритм Хирхольцера строит эйлеров путь в неориентированном графе. Сначала алгоритм добавляет подпуть 1 → 2 →
3 → 1, затем подпуть 2 → 5 → 6 → 2 и, наконец, подпуть 6 → 3 → 4 → 7 → 6.

226 
Глава 12. Дополнительные алгоритмы на графах
В этот момент в цикл добавлены все ребра, так что мы успешно построили эйлеров цикл.
12.2.2. Гамильтоновы пути
Гамильтоновым путем называется путь, который заходит в каждую вер- шину графа ровно один раз. Если такой путь начинается и заканчивается в одной и той же вершине, то он называется гамильтоновым циклом. На рис. 12.13 показаны граф и его гамильтонов цикл.
1 2
3 4
5 1
2 3
4 5
1.
3.
4.
1 2
3 4
5 1.
2.
3.
4.
5.
Рис. 12.13. Граф, гамильтонов путь и гамильтонов цикл
Задачи, относящиеся к гамильтоновым путям, являются NP-трудными: в общем случае неизвестно, как эффективно проверить, существует ли в графе гамильтонов путь или цикл. Конечно, в некоторых частных случа- ях гамильтонов путь заведомо существует. Например, если граф полный, т. е. между любой парой вершин имеется ребро, то гамильтонов путь есть наверняка.
Простой метод нахождения гамильтонова пути – алгоритм перебора с возвратом, который перебирает все возможные способы построения пути.
Временная сложность такого алгоритма не меньше O(n!), потому что вы- брать порядок n вершин можно n! разными способами. Но, воспользовав- шись динамическим программированием, можно создать более эффек- тивный алгоритм с временной сложностью O(2
n
n
2
), который для каждого подмножества вершин S и каждой вершины x ∈ S определяет, существует ли путь, заходящий в каждую вершину S ровно один раз и заканчиваю- щийся в вершине x.
12.2.3. Применения
Последовательности де Брёйна. Последовательностью де Брёйна на- зывается строка над фиксированным алфавитом из k символов, которая содержит в качестве подстроки любую строку длины n ровно один раз.
Длина такой строки равна k
n
+ n − 1. При n = 3 и k = 2 примером последова- тельности де Брёйна может служить строка
0001011100.
Ее подстроками являются все комбинации трех бит: 000, 001, 010, 011,
100, 101, 110 и 111.

12.2. Полные пути

227
Последовательность де Брёйна соответствует эйлерову пути в графе, вершины которого содержат строки из n − 1 символов, а каждое ребро добавляет в строку один символ. Граф на рис. 12.14 соответствует случаю
n = 3, k = 2. Чтобы создать последовательность де Брёйна, мы начинаем с произвольной вершины и, следуя эйлерову пути, проходим по каждому ребру ровно один раз. Сложив символы в начальной вершине с символа- ми на ребрах, мы получим строку из k
n
+ n – 1 символов, которая является последовательностью де Брёйна.
00 11 01 10 1
1 0
0 0
1 0
1