5.5. СИЛЬНАЯ СВЯЗНОСТЬ

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

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

Применим поиск в глубину для нахождения сильно связных компонент графа. Сначала покажем, что узлы каждой сильно связной компоненты образуют связный подграф в глубинном остовном лесу. Этот связный подграф представляет собой дерево, и его корень называется корнем сильно связной компоненты. Однако не каждое дерево в глубинном остовном лесу непременно представляет какую-то сильно связную компоненту.

Лемма 5.7. Пусть сильно связная компонента ориентированного графа -глубинный остовный лес для Тогда узлы графа вместе с ребрами, входящими в пересечение образуют дерево.

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

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

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

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

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

Лемма 5.8. Для любого граф состоит из узлов, являющихся потомками узла и не принадлежащих ни одному из графов

Доказательство. Корень для не может быть потомком узла поскольку вызов процедуры завершается после работы процедуры

Для нахождения корней введем функцию, называемую

На рис. 5.14 изображено поперечное ребро из потомка узла в узел а корень сильно связной компоненты, содержащей является предком узла

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

Рис. 5.14. Поперечное ребро, удовлетворяющее условию из определения функции нижняясвязь.

Лемма 5.9. Пусть ориентированный граф. Для того чтобы узел был корнем сильно связной компоненты графа необходимо и достаточно, чтобы

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

По условию предок узла так что Следовательно, по условию откуда в силу условия 3 вытекает, что подлинный предок узла Но должны принадлежать одной и той же сильно связной компоненте, поскольку в идут пути из гвуиизувг через Поэтому не корень сильно связной компоненты-, получили противоречие. Таким образом,

Достаточность. Пусть Если не корень сильно связной компоненты, содержащей то корнем будет некоторый подлинный предок узла Следовательно, есть путь из Рассмотрим первое ребро в идущее из потомка узла в узел не являющийся потомком узла Это ребро либо обратное и идет к предку узла либо поперечное и идет в узел, номер которого меньше В любом случае

Осталось показать, что принадлежат одной и той же сильно связной компоненте графа Из должен идти путь, поскольку предок узла Путь идет из через Следовательно,

принадлежат одной и той же сильно связной компоненте. Таким образом, получили противоречие.

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

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

Чтобы проверить, принадлежит ли той же компоненте, что и некоторый предок узла у, достаточно посмотреть, находится ли еще узел в стеке для узлов. Эта проверка осуществляется с помощью массива, указывающего наличие узла в стеке. Заметим, что по лемме 5.8 если еще в стеке, то корень сильно связной компоненты, содержащей является предком узла у.

Изложим модификацию процедуры ПОИСК, которая вычисляет функцию Она использует магазинный список для узлов. Эта процедура приведена на рис. 5.15.

Функция вычисляется в строках 4, 9 и 11. В строке 4 в качестве начального значения для берется номер узла у, присвоенный ему поиском в глубину. В строке 9 полагаем если для некоторого сына узел оказался меньше текущего значения В строке 10 узнаем, является обратным или поперечным ребром, и проверяем, не найдена ли уже сильно связная компонента, содержащая Если нет, то корень сильно связной компоненты, содержащей будет предком узла у. По необходимости полагаем в строке 11 значение равным номеру узла присвоенному ему поиском в глубину, если оно раньше не получило меньшее значение.

Теперь сформулируем весь алгоритм нахождения сильно связных компонент ориентированного графа.

Рис. 5.15. (см. скан) Процедура для вычисления функции

Алгоритм 5.4. Нахождение сильно связных компонент ориентированного графа

Вход. Ориентированный граф

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

Метод.

Пример 5.8. Рассмотрим глубинный остовный лес на рис. 5.13. Этот лес воспроизведен на рис. 5.16, где указаны также значения функции Вызов заканчивает работу первым среди всех вызовов процедуры Когда мы исследуем ребро (3,1), полагаем По возвращении к полагаем Затем вызываем для исследования ребра Так как и 3 еще находится в СТЕКе, полагаем

Затем возвращаемся к вызову и полагаем равным меньшему из чисел: и текущего значения (равного 1). Поскольку последнее значение меньше, то не меняется. Возвращаемся к вызову полагая Исследовав далее ребро ничего не делаем, ибо (1,4) — прямое ребро, и условие строки 10 процедуры не выполняется, так как

Теперь вызываем и поперечное ребро вынуждает нас положить ибо Когда снова возвращаемся к вызову полагаем значение равным меньшему из чисел (предыдущее значение) и т. е.

Затем, поскольку все ребра, выходящие из 1, уже рассмотрены и мы обнаруживаем, что 1 — корень сильно связной компоненты. Эта компонента состоит из 1 и всех узлов, находящихся в стеке выше 1. Так как узел 1 посещался первым, то узлы 2, 3, 4 и 5 находятся выше 1 и именно в этом

Рис. 5.16. Остовный лес с вычисленной функцией

порядке. Поэтому стек опустошается и список узлов 1, 2, 3, 4, 5 печатается в качестве сильно связной компоненты графа

Другие сильно связные компоненты — это Оставляем читателю закончить вычисление функции и сильно связных компонент, отправляясь от узла 6. Заметим, что последние встречи с корнями сильно связных компонент происходили в порядке 1, 7,

Теорема 5.4. Алгоритм 5.4 правильно находит сильно связные компоненты графа за время где число узлов, число ребер ориентированного графа

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

Чтобы доказать корректность алгоритма, достаточно показать индукцией по числу тех вызовов процедуры которые завершили работу, что по окончании значение вычислено правильно. После строк 12—16 процедуры узел становится корнем сильно связной компоненты тогда и только тогда, когда Далее, в качестве результата печатаются в точности потомки узла и, не входящие в компоненты, корни которых были найдены раньше (по лемме 5.8). А именно, узлы, находящиеся в стеке выше узла и, являются его потомками, а их корни не были найдены ранее и, поскольку эти узлы все еще находятся в стеке.

Чтобы доказать корректность вычисления функции заметим, что на рис. 5.15 есть два места, где значение могло быть меньше и; это строки 9 и 11 процедуры В первом случае сын узла Тогда некоторый узел можно достичь из потомка у узла через поперечное или обратное ребро. Кроме того, корень сильно связной компоненты, содержащей х, является предком узла Поскольку то значит, подлинный предок узла Таким образом, значение должно быть не больше, чем

Во втором случае — в строке 11 — из идет поперечное или обратное ребро в узел сильно связная компонента С которого еще не найдена. Вызов процедуры на корне из С еще не закончился, так что должен быть предком узла (Так как то либо лежит слева от и, либо предок узла Но

если бы был слева от то вызов закончился бы.) Снова получаем, что значение должно быть не больше до.

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

Случай В силу предположения индукции и леммы 5.9 можно считать, что все сильно связные компоненты, найденные до сих пор, корректны. Тогда узел у все еще должен быть в СТЕКе, поскольку еще не закончился. Следовательно, в строке 11 значение полагается равным у или меньшему числу.

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