1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 43
Текст из файла (страница 43)
Е4. ПОИСК В ГЛУБИНУ В ОРИЕНТИРОВАННОМ ГРАФЕ Чтобы построить остовный лес, начнем с узла ои ПОИСК(о,) вызывает ПОИСК(О4), а тот вызывает ПОИСК(о,). Последний вызов ничего не добавляет к дереву, ибо единственное ребро с началом о4 идет в узел и„уже помеченный как "старый". Поэтому возвращаемся к ПОИСК(о,), который добавляет о, в качестве второго сына узла о,. ПОИСК(о4) заканчивает работу, ничего не добавляя к лесу, поскольку узел о, уже "старый". Затем заканчивается ПОИСК(о,), ибо все ребра, выходящие из и„к данному моменту просмотрены, Поэтому возвращаемся обратно в О4 и вызываем ПОИСК(О4).
Последний вызов ничего не добавляет к дереву; аналогично ничего не может добавить и ПОИСК(О,). Теперь возьмем о, в качестве корня нового глубинного остов- ного дерева. Его построение аналогично предыдущему, и мы оставляем его читателю. Заметим, что узлы посещались в порядке о„о„..., О,. Следовательно, в процессе поиска в глубину узлу о, был приписан номер 4', 1~1(8. П При поиске в глубину на ориентированном графе в дополнение к древесным ребрам возникает еще три типа ребер. Это обратные ребра, такие, как (о„ о,) на рис. 5.13,б, поперечные справа налево, такие, как (РО о4) на том же рисунке, и прямые ребра, такие, как (ьп о„).
Однако никакое ребро не идет из узла с меньшим номером, присвоенным в процессе поиска в глубину, в ребро с ббльшим номером, если только последнее не является потомком первого. Это не случайно. Объяснение аналогично объяснению того, почему в неориентированном случае нет поперечных ребер. Пусть (о, Н4) — ребро и узел О был посещен до п4 (т. е. О(ге). Каждый узел, которому приписывается номер в период между началом и концом процедуры ПОИСК(о), становится потомком узла о.
Но узел ге должен получить свой номер, когда рассматривается ребро (о, ге), если только он уже не получил номер раньше. Если ге получает номер в то время, когда рассматривается ребро (о, ге), то (о, п4) становится древесным ребром, а в противном случае прямым ребром. Таким образом, не может быть такого поперечного ребра (О, п4), что о п4, Поиск в глубину в графе 6 разбивает множество его ребер на четыре класса.
1) Древесные ребра, идущие к новым узлам в процессе поиска. 2) Прямые ребра, идущие от предков к подлинным потомкам, но не являющиеся древесными ребрами. 3) Обратные ребра, идущие от потомков к предкам (возможно, из узла в себя). 4) Поперечные ребра, соединяющие узлы, которые не являются ни предками, ни потомками друг друга. Ключевое свойство поперечных ребер устанавливается в следуклцсй лемме. 34$ Гл.
ь. Ал! ОРитмы нА ГРАФАХ Лемма Б.В. Если (о, иГ) — поперечное ребро, то о~Ге, т. е. поперечные ребра идут справа налево. До к аз а тел ь от в о. Доказательство аналогично доказательству леммы 5.3 и остается в качестве упражнения. П 5.5. СИЛЬНАЯ СВЯЗНОСТЬ В качестве примера эффективного алгоритма, который стал возможным благодаря поиску в глубину на ориентированном графе, рассмотрим задачу распознавания сильной связности ориентированного графа, т. е.
существования на нем пути из каждого узла в любой другой. Определение. Пусть 6=((Г, Е) — ориентированный граф. Разобьем множество его вершин )Г на такие классы эквивалентности 1ГГ, 1(Г~~Г, что узлы о и иГ эквивалентны тогда и только тогда, когда на графе есть пути из о в иГ и обратно. Пусть ЕГ, 1(1(г,— множество ребер, соединяющих пары узлов в )ГГ. Графы 6, = (РГ, Е,) называются сильно связными компонентиии графа 6. Хотя каждый узел графа 6 принадлежит некоторому множеству 1Г„у графа 6 могут быть ребра, не принадлежащие ни одному множеству Еь Граф называется сильно связным, если он имеет только одну сильно связную компоненту.
Применим поиск в глубину для нахождения сильно связных компонент графа. Сначала покажем, что узлы каждой сильно связной компоненты образуют связный подграф в глубинном остовиом лесу. Этот связный подграф представляет собой дерево, и его корень называется корнем сильно связной компоненпГЫ. Однако не каждое дерево в глубинном остовном лесу непременно представляет какую-то сильно связную компоненту, Лемма 6.7. 17усть 61= (ТГГ, ЕГ) — сильно связная компонента ориентированного графа 6, а 5= ()Г, Т) — глубинный остовный лес для 6.
Тогда узлы графа 61 вместе с ребрами, входящими в пересечение ЕГ () Т, образуют дерево. Доказательство. Пусть о и ш — узлы из 1'1. (Мы предполагаем, что именами узлов являются номера, присвоенные им в процессе поиска в глубину.) Без потери общности будем считать, что о(Гс. Так как узлы о и иГ оба принадлежат одной и той же сильно связной компоненте, то существует путь Р в 61, идущий из о в ш. Пусть х — узел на Р с наименьшим номером (возможио, это сам узел о). Путь Р, дойдя до какого-нибудь потомка узла х, уже не сможет выйти за пределы поддерева потомков узла х, ибо за пределы этого поддерева выходят лишь поперечные ребра и обратные ребра, идущие в узлы с номерами, меньшими х.
(Так КХ СИЛЬНАЯ СВЯЗНОСТЬ как потомки узла х занумерованы последовательно, начиная с х, то поперечное или обратное ребро, выходящее из поддерева потомков узла х, должно идти в узел с номером, меньшим х.) Следовательно, ш — потомок узла х. Поскольку узлы занумерованы в прямом порядке, то все узлы, номера которых заключены между х и ш, также являются потомками узла х. Так как х(о(ш, то о — потомок узла х. Мы только что показали, что любые два узла в 6; имеют общего предка в бь Пусть г — общий предок узлов графа б; с наименьшим номером. Если о — узел графа бн то любой узел на пути из г в о, проходящем в остовном дереве, также является узлом графа бь Сильно связные компоненты ориентированного графа 6 можно найти, построив корни компонент в том порядке, в каком онн встретились в последний раз в процессе поиска в глубину на 6.
ПУсть гн гь ..., ㄠ— эти коРни в том поРЯдке, в каком заканчивался их поиск в глубину (т. е. поиск узла г, заканчивался перед поиском гг,т). ТогДа ДлЯ кажДого ((1 либо г, лежит слева от гь либо г, — потомок узла г~ в глубинном остовном лесу, Пусть 6; — сильно связная компонента с корнем гь 1«='1(й. Тогда б, состоит из всех потомков узла г„поскольку никакой узел гь 1 1, не может быть потомком узла г,.
Аналогично можно доказать следующую лемму. Лемма 5.8. Для любого 1, 1(1(й, граф б~ состоит из узлов, являющихся потомками узла т, и нг принадлежащих ни одному из графов 6„6„..., бг о Доказательство. Корень гт для 1)1 не может быть потомком узла гь поскольку вызов процедуры ПОИСК(О) завершается после работы процедуры ПОИСК(г~). П Для нахождения корней введем функцию„называемую НИЖНЯЯСВЯЗЬ: НИЖНЯЯСВЯЗЬ 1о) = М1(т( (1о) () 1ш ( есть поперечное или обратное ребро из некоторого потомка узла ив узел ш, а корень той сильно связной компоненты, которая содержит ш, является предком узла о)). (5 3) На рис. 5.14 изображено поперечное ребро из потомка узла о в узел ш, а корень г сильно связной компоненты, содержащей ш, является предком узла и.
Мы скоро увидим, как в процессе поиска в глубину вычислять функцию НИЖНЯЯСВЯЗЬ. Но прежде охарактеризуем корни сильно связных компонент в терминах значений этой функции. 2ТУ Гл. 5, ллговитмы НА ГРЛФАх Рис. 5.14. Поперечное ребро, удовлетворвивпее условию из определевив функции ННЖНЯЯСНЯЗЬ. Лемма 5.9.
Пусть 6 — ориентированный ераф. Для того чпюбы узел о был корнем сильно связной компонента грагра 6, необходимо и достаточно, чтобы НИЖНЯЯСВЯЗЬ[о)=о. Д о к а з а т е л ь с т в о. Необходимость. Пусть о — корень сильно связной компоненты графа 6. По определению НИЖНЯЯСВЯЗЬ[о[(о.
Допустим, что НИЖНЯЯСВЯЗЬ[о)< о. Тогда найдутся такие узлы в и г, что 1) в гз входит поперечное или обратное ребро, выходящее из потомка узла о, 2) г — корень сильно связной компоненты, содержащей в, 3) г — предок узла о, 4) 1оСо. По условию 2 г — предок узла го, так что г гз. Следовательно, по условию 4 г(о, откуда в силу условия 3 вытекает, что г — подлинный предок узла о. Но г и о должны принадлежать одной и той же сильно связной компоненте, поскольку в 6 идут пути из г в о и из о в г через ы.
Поэтому о не корень сильно связной компоненты; получили противоречие. Таким образом, НИЖНЯЯСВЯЗЬ[о!=о. Достаточность. Пусть НИЖНЯЯСВЯЗЬ[о[=о. Если о — не корень сильно связной компоненты, содержащей о, то корнем будет некоторый подлинный предок г узла о.
Следовательно, есть путь Р из о в г. Рассмотрим первое ребро в Р, идущее из потомка узла о в узел го, не являющийся потомком узла о. Это ребро либо обратное и идет к предку узла о, либо поперечное и идет в узел, номер которого меньше о. В любом случае го<о.
Осталось показать, что г и в принадлежат одной и той же сильно связной компоненте графа 6. Из г в о должен идти путь, поскольку г — предок узла о. Путь Р идет из о через ю в г. Следовательно, зев 5.к сильнАя связность г и ш принадлежат одной и той же сильно связной компоненте. Таким образом, НИЖНЯЯСВЯЗЬ[о[(ш<п; получили противоречие. П При поиске в глубину легко вычислить значения функции НИЖНЯЯСВЯЗЬ. Сами сильно связные компоненты также легко нанти.
Для этого узлы графа 6 помещаются в стек в том порядке, в каком они посещаются во время поиска. Всякий раз, когда обнаруживается корень, все узлы соответствующей сильно связной компоненты находятся в верхней части стека и выталкиванпся наружу. Эта стратегия "работает" в силу леммы 5.8 и свойств нумерации, порождаемой поиском в глубину. Попав в узел о в первый раз, полагаем НИЖНЯЯСВЯЗЬ[о)=о. Когда встречается обратное или поперечное ребро [и, в) и ш принадлежит той же сильно связной компоненте, что и некоторый предок узла о, то полагаем значение функции НИЖНЯЯСВЯЗЬ в узле о равным меньшему из двух чисел: ее текущего значения и пА Когда встречается древесное ребро [и, ш), рекурсивно просматривается поддерево с корнем ш и вычисляется НИЖНЯЯСВЯЗЬЫ.
По возвращении к и значение функции НИЖНЯЯСВЯЗЬ в узле о полагается равным меньшему из чисел: ее текущего значения и НИЖНЯЯСВЯЗЬЫ. Чтобы проверить, принадлежит ли щ той же компоненте, что и некоторый предок узла и, достаточно посмотреть, находится ли еще узел ш в стеке для узлов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
