Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 129

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 129)

Время работы процедуры ПРБ, таким образом, равно О (У+ Е). Свойства Поиска в глубину Поиск в глубину дает нам важную информацию о структуре графа. Вероятно, наиболее фундаментальное свойство поиска в глубину заключается в том, что подграф предшествования С образует лес деревьев, поскольку структура деревьев поиска в глубину в точности отражает структуру рекурсивных вызовов процедуры 0РБ Ч!вгГ. То есть и = к (и] тогда и только тогда, когда ПРБ Ч|вгг(и) была вызвана при сканировании списка смежности вершины и. Кроме того, вершина в является потомком вершины и в лесу поиска в глубину тогда и только тогда, когда вершина и была серой в момент открытия вершины и.

Еще одно важное свойство поиска в глубину заключается в том, что времена открытия и завершения образуют скабачаую саврукавуру (рагешлев1в вппсшге). Если мы представим открытие вершины и при помощи отрывающейся скобки "(и", а завершение — при помощи закрывающейся скобки "и)", то перечень открытий и завершений образует корректное выражение в смысле вложенности скобок. Например, поиск в глубину на рис. 22.5а соответствует скобочному выражению на рис.

22.5б. Еще одно утверждение о скобочной структуре приведено в следующей теореме. Теорема 22.7 (Теорема о скобках). В любом поиске в глубину в (ориентированном или неориентированном) графе С = (У, Е) для любых двух вершин и и с выполняется ровно одно из трех следующих утверждений. ° Отрезки (0[и], 7 [и]] и [о[и], Г'[и]] не пересекаются, и ни и не является потомком и в лесу поиска в глубину, ни и не является потомком и. ° Отрезок (И(и], ДиЦ полностью содержится в отрезке (сЦи], 7" [и]], и и является потомком и в дереве поиска в глубину. ° Отрезок (И[и], 7" [и]] полностью содержится в отрезке (а[и], 7" [и]], и и является потомком и в дереве поиска в глубину.

Доказательство. Начнем со случая, когда И [и] < Н (и]. При этом нам надо рассмотреть два подслучая, в зависимости от того, справедливо неравенство П [и] < < У [и] или нет. Первый подслучай соответствует справедливости неравенства а' (и] < 7" (и], так что вершина и была открыта, когда вершина и была окрашена Глава 22. Элементарные алгоритмы для работы с графами 627 3 4 5 6 ) 8 9 )0 1) )з )3 )4 )з !ь О (г )у ,'х к ) у) )в в ) г) г) () Н ~ ) ) и в ) Рис. 22.5.

Свойства поиска в гпубииу в серый цвет. Отсюда следует, что о является потомком и. Кроме того, поскольку вершина о открыта позже, чем и, перед тем как вернуться для завершения поиска к вершине и, алгоритмом будут исследованы все выходящие из )) ребра. В таком случае, следовательно, отрезок [о[о], Г"[и]] полностью содержится в отрезке [И[и], Г" [и]].

В другом подслучае у [и] < И [о], и из неравенства следует, что отрезки [И[и], Г[и]] и фо], ~[э]] не пересекаются. Посшльку отрезки не пересекаются, не происходит открьггие одной вершины, пока другая имеет серый цвет, так что ни одна вершина не является потомком другой. Часть Ч1. Алгоритмы для работы с графами 628 Случай, когда с([и) < а [и), рассматривается аналогично, происходит только смена ролей и и ю Следствие 22.8 (Вложенность интервалов потомков). Вершина и является потомком и (отличным от самого и) в лесу поиска в глубину в (ориентированном нли неориентированном) графе С тогда и только тогда, когда а [и] < ц [и) < з [и] < < Х [и]. Доказаазельсглео.

Непосредственно вытекает из теоремы 22.7. Следующая теорема дает еще одну важное указание о том, когда одна вершина в лесу поиска в глубину является потомком другой. Теорема 22.9 (Теорема о белом пути). В лесу поиска в глубину (ориентированного или неориентированного) графа С = (1; Е) вершина и является потомком вершины и тогда и только тогда, когда в момент времени а' [и] (открытне вершины и) вершина и достижима из и по пути, состоящему только из белых вершин. Доказаагельсзаео. =ь: Предположим, что и является потомком и. Пусть ю — произвольная вершина на пути между и н и в дереве поиска в глубину, так что и является потомком и.

Согласно следствию 22.8, а [и] < а [ю), так что в момент времени с( [и] вершина ю — белая. с=: Предположим, что в момент времени а'[и) вершина и достижима нз и вдоль пути, состоящего из белых вершин, но и не становится потомком и в дереве поиска в глубину. Без потери общности предположим, что все остальные вершины вдоль пути становятся потомками и (в противном случае в качестве и выберем на пути ближайшую к и вершину, которая не становится потомком и). Пусть ю— предшественник и на пути, так что ю является потомком и (ю и и могут быть в действительности одной вершиной) и, согласно следствию 22.8, г" [ю) < ~ [и).

заметим, что вершина и должна быть открыта после того, как открыта и, но перед тем, как завершена обработка ю. Таким образом, Н [и] < г([и] < г" [ю] < з' [и]. Из теоремы 22.7 следует, что отрезок [г([и), Г" [и]] полностью содержится внутри отрезка [с1[и), г" [и]]. Согласно следствию 22.8, вершина и должна в конечном итоге быть потомком вершины и. И Классификация ребер Еще одно интересное свойство поиска в глубину заключается в том, что поиск может использоваться для классификации ребер входного графа С = ()г, Е). Эта классификация ребер может использоваться для получения важной информации о графе.

Например, в следующем разделе мы увидим, что ориентированный граф ацикличен тогда и только тогда, когда при поиске в глубину в нем не обнаруживается "обратных" ребер (лемма 22.11). Глава 22. Элементарные алгоритмы для работы с графами 629 Мы можем определить четыре типа ребер с использованием леса С , полученного при поиске в глубину в графе С. 1. Ребра деревьев (атее едйез) — это ребра графа С . Ребро (и,и) является ребром дерева, если при исследовании этого ребра открыта вершина и.

2. Обратные ребра (Ьаск едйез) — это ребра (и, и), соединяющие вершину и с ее предком и в дереве поиска в глубину. Ребра-циклы, которые могут встречаться в ориентированных графах, рассматриваются как обратные ребра. 3. Прямые ребра ((Ьттчатб ебйез) — это ребра (и, и), не являющиеся ребрами дерева и соединяющие вершину и с ее потомком и в дереве поиска в глубину. 4.

Перекрестные ребра (егозя ебдез) — все остальные ребра графа. Они могут соединять вершины одного и того же дерева поиска в глубину, когда ни одна нз вершин не является предком другой, или соединять вершины в разных деревьях. На рис. 22.4 и рис.

22.5 ребра помечены в соответствии с их типом. На рнс. 22.5в показан граф на рис. 22.5а, нарисованный так, что все прямые ребра и ребра деревьев направлены вниз, а обратные ребра — вверх. Любой граф можно перерисовать таким способом. Алгоритм ОРИ можно модифицировать так„что он будет классифицировать встречающиеся при работе ребра. Ключевая идея заключается в том, что каждое ребро (и, и) можно классифицировать при помощи цвета вершины и при первом его исследовании (правда, при этом не различаются прямые и перекрестные ребра). 1.

Белый цвет говорит о том, что это ребро дерева. 2. Серый цвет определяет обратное ребро. 3. Черный цвет указывает на прямое или перекрестное ребро. Первый случай следует непосредственно из определения алгоритма. Рассматривая второй случай, заметим, что серые вершины всегда образуют линейную цепочку потомков, соответствующую стеку активных вызовов процедуры 13РБ Ият; количество серых вершин на единицу больше глубины последней открытой вершины в дереве поиска в глубину. Исследование всегда начинается от самой глубокой серой вершины, так что ребро, которое достигает другой серой вершины, достигает предка исходной вершины. В третьем случае мы имеем дело с остальными ребрами, не подпадающими под первый или второй случай.

Можно показать, что ребро (и, и) является прямым„если б [и] < И [и], и перекрестным, если Ы [и] > д [и] (см. упражнение 22.3-4). В неориентированном графе при классификации ребер может возникнуть определенная неоднозначность, поскольку (и, и) и (и, и) в действительности являются одним ребром. В таком случае, когда ребро соответствует нескольким Часть ЧЕ Алгоритмы для работы с графами 630 категориям, оно классифицируется в соответствии с лервой категорией в списке, применимой для данного ребра.

Тот же результат получается, если выполнять классификацию в соответствии с тем, в каком именно виде — (и, о) или (о, и)— ребро встречается в первый раз в процессе выполнения алгоритма (см. упражнение 22.3-5). Теперь мы покажем, что прямые и перекрестные ребра никогда не встречаются при поиске в глубину в неориентированном графе. Теорема 22.10. При поиске в глубину в неориентированном графе С любое ребро С является либо ребром дерева, либо обратным ребром.

Доказательслгво. Пусть (и, о) — произвольное ребро графа О, и предположим без потери общности, что Н(и~ ( 0 [о~. Тогда вершина и должна быть открыта и завершена до того, как будет завершена работа с вершиной и (пока и — серая), так как е находится в списке смежности и. Если ребро (и, и) исследуется сначала в направлении от и к п, то е до этого момента была неоткрытой (белой) — так как в противном случае мы бы уже исследовали это ребро в направлении от о к и. Таким образом, (и, и) становится ребром дерева.

Характеристики

Список файлов книги