Переводы называний: undershorts - трусы, pants - штаны, belt -ремень, shirt - рубашка, tie - галстук, jacket - пиджак, socks -носки, shoes - ботинки, watch - часы.

Рис. 23.6 23.7 (а) Профессор топологически сортирует свою одежду по утрам. Ребро (u, v) означает, что и должно быть надето до v. Рядом с вершинами показаны времена начала и конца обработки при поиске в глубину. (Ь) Граф топологически отсортирован (вершины расположены в порядке убывания времени окончания обработки). Все рёбра идут слевао направо.

ных компонент), указывающий, в какой связной компоненте находится V. 23.3-10*

Говорят, что ориентированный граф G = (V, Е) обладает свойством единственности пути (is singly connected), если в нём не существует двух разных простых путей, имеющих общее начало и общий конец. Постройте эффективный алгоритм, определяющий, обладает ли граф этим свойством.

23.1.4. Топологическая сортировка

Пусть имеется оринетированный граф без циклов (directed acyclic graph; это английское название иногда сокращают до "dag"). Задача о топологической сортировке (topological sort) этого графа состоит в следующем: надо указать такой линейный порядок на его вершинах, что любое ребро ведет от меньшей вершины к большей (в смысле этого порядка). Очевидно, что если в графе есть циклы, такого порядка не существует. Можно сформулировать задачу о топологической сортировке и так: расположить вершины графа на горизонтальной прямой так, чтобы все рёбра шли слева направо. (Слово «сортировка»не должно вводить в заблуждение: эта задача весьма отличается от обычной задачи сортировки, описанной в части П.)

Вот пример ситуации, в которой возникает такая задача. Рассеянный профессор одевается по утрам, причём какие-то вещи обязательно надо надевать до каких-то других (напрример, носки - до башмаков); в других случаях это всё равно (носки и штаны, например). На рис. 23.7 (а) требуемые соотношения показаны в виде ориентированного графа: ребро (и, v) означает, что предмет и должен быть надет до v. Топологическая сортировка этого графа, тем самым, описывает возможный порядок одевания. Один из таких порядков показан на рис. 23.7 (Ь) (надо одеваться слева направо).

Следующий простой алгоритм топологически сортирует ориентированный ациклический граф.

Topological-Sort($G$)

1Вызвать DFS($G$), при этом,

2завершая обработку вершины (\textsc{DFS-Visit}, строка 8), добавлять е\"~~а5 в начало списка

3вернуть построенный список вершин

На рисунке 23.7 (Ь) показан результат применения такого алгоритма: значения f[v] убывают слева направо.

Топологическая сортировка выполняется за время Q(V + Е), потому что столько времени занимает поиск в глубину, а добавить каждую из \V\ вершин к списку можно за время 0(1).

Правильность этого алгоритма доказывается с помощью такой леммы:

Лемма 23.10

Ориентированный граф не имеет циклов тогда и только тогда, когда поиск в глубину не находит в нём обратных рёбер. Доказательство.

=>: Обратно ребро соединяет потомка с предком и потому замыкает цикл, образованный рёбрами дерева.

-ч=: Пусть в графе имеется цикл с. Докажем, что в этом случае поиск в глубину обязательно найдёт обратное ребро. Среди вершин цикла выберем вершину v, которая будет обнаружена первой, и пусть (и, v) - ведущее в неё ребро цикла. Тогда в момент времени d[v] из v в и ведёт путь из белых вершин. По теореме о белом пути и станет потомком v в лесе поиска в глубину, поэтому (и, v) будет обратным ребром.

Теорема 23.11

Процедура Topological-Sort(O) правильно выполняет топологическую сортировку ориентированного графа G без циклов. Доказательство.

Нужно доказать, что для любого ребра (и, v) выполнено неравенство f[v] < f[u]. В момент обработки этого ребра вершина v не может быть серой (это означало бы, что она является предком и и (и, v) является обратным ребром, что противоречит лемме 23.10). Поэтому v в этот момент должна быть белой или чёрной. Если v - белая, то она становится ребёнком и, так что f[v] < f[u]. Если она уже чёрная, то тем более f[v] < f[u].

Упражнения

23.4-1

В каком порядке расположит вершины графа рис. 23.8 алгоритм Topological-Sort? (Порядок просмотра вершин алфавитный.) 23.4-2

Результат работы алгоритма Topological-Sort зависит от порядка просмотра вершин. Покажите, что различные упорядочения списков смежных вершин могут привести к одному и тому же результату.

23.4-3

Рис. 23.7 23.9 (а) Ориентированный граф G и его сильно связные компоненты (показаны серым). (Ь) Транспонированный граф GT. Показано дерево поиска в глубину, вычисляемое в строке 3 процедуры STRONGLY-CONNECTED-CoMPONENTS Ребра дерева обведены серым. Вершины b, с,д, h, являющиеся корнями деревьев поиска в глубину (для графа GT), выделены чёрным, (с) Ациклический граф, который получится, если стянуть каждую сильно связную компоненту графа G в точку.

Придумайте алгоритм, определяющий, имеется ли в данном неориентированном графе G = (V, Е) цикл. Можно ли сделать это за время 0(V) (с константой, не зависящей от \Е\)1

23.4-4

Верно ли, что для ориентированного графа с циклами алгоритм Topological-Sort находит порядок, при котором число «плохих» рёбер (идущих в неправильном направлении) будет минимально?

23.4-5

Другой способ топологической сортировки состоит в том, чтобы последовательно находить вершины с входящей степенью 0, печатать их и удалять из графа вместе со всеми выходящими из них рёбрами. Как реализовать эту идею, чтобы время выполнения составило 0(V + Е)1 Что произойдёт, если в исходном графе есть циклы?

23.5 Сильно связные компоненты. 23.1.5. Сильно связные компоненты

Классическое применение поиска в глубину - задача о разложении графа на сильно связные компоненты. Мы покажем, как это можно сделать, дважды выполнив поиск в глубину.

Многие алгоритмы, работающие на ориентированных графах, начинают с отыскания сильно связных компонент: после этого задача решается отдельно для каждой компоненты, а потом решения комбинируются в соотвествии со связями между компонентами. Эти связи можно представлять в виде так называемого «графа компонент» (упр. 23.5-4).

Вспомним (глава 5), что сильно связной компонентой ориентированного графа G = (V, Е) называется максимальное множество вершин С С С с таким свойством: любые две вершины и и v из U достижимы друг из друга (и v и v и).

Пример графа с выделенными сильно связными компонентами показан на рис. 23.9.

Алгоритм поиска сильно связных компонент графа G = (V, Е) будет использовать «транспонированный» граф GT = (V, ЕТ) (упр. 23.1-3), получаемый из исходного обращением стрелок на рёбрах: Ет = {(и, v) : (и, и) £ Е}. Такой граф можно построить за время 0(С + Е) (мы считаем, что исходный и транспонирован-