Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 142
Текст из файла (страница 142)
Кроме того, поскольку вершина и открыта позже, чем и, перед тем как вернуться для завер- Часть ЕЕ Алгоритмы для работы с йза(зама (а) 1 2 3 4 5 б 7 8 9 10 11 12 13 14 15 1б (л (х (у (х х) у) (м и) х) л) (г (ь ь) (и и) Г) (а) Рнс. 22.5. Свойспм поиска в глубину. (а) Результат поиска в глубину в ориентированном графе. Метки времени вершин и типы ребер указаны, как на рис. 22.4. (6) Интервалы между временами открытия и завершения для каждой вершины соответствуют показанной структуре скобок.
Каждый прямоугольник окватываст интервал, задаваемый временами открьпня и завершение соствстствуюшей вершины. Показаны тольао три ребра. Если дяа интервала перекрываются, то один из нях вложен в другой, и вершина, соответствующая меньшему интервалу, является потомком вершины, соответствующей большему интервалу, (в) Граф из части (а), перерисованный таким образом, чтобы ребра яеревьев и прямые ребра были направлены вниз, а обратные шли вверх от потомков к предкам. Глава л2. Элементарные алгоритмы длл работы с графами щения поиска к вершине и, алгоритмом будут исследованы все выходящие из э ребра.
В таком случае, следовательно, отрезок [и. г(, и. (] полностью содержится в отрезке [и. Ы, и. (]. В другом подслучае и. г' < и. с(, и из неравенства (22.2) следует, что и. а < и. ( < и. а < и. (; таким образом, отрезки [и. с(, и, (] и [и, б, и.) ] не пересекаются. Поскольку отрезки не пересекаются, открытие одной вершины не происходит до тех пор, пока другая имеет серый цвет, так что ни одна вершина не является потомком другой. Случай, когда и.
с( < и. И, рассматривается аналогично, происходит только смена ролей и и и. Следствие 22.8 ~Вложенность интервалов потомков) Вершина и является истинным (отличным от самого и) потомком и в лесу поиска в глубину (ориентированного или неориентированного) графа С тогда и только тогда, югда и. а' < и. с( < и.7' < и.,(. Доказательство. Непосредственно вытекает из теоремы 22.7. Следующая теорема дает еще одно важное указание о том, когда одна вершина в лесу поиска в глубину является потомком другой.
Теорема 22.9 (Теорема о белом пути) В лесу поиска в глубину (ориентированного или неориентированного) графа С = (1', Е) вершина и является потомком вершины и тогда и только тогда, когда в момент времени и. г( (открытие вершины и) вершина и достижима из и по пути, состоящему толью из белых вершин. Доказательство. =ь: Если и = и, то путь от и к и содержит единственную вершину и, юторая все еще является белой в момент, югда мы устанавливаем значение атрибута и. г(. Теперь предположим, что и является истинным потомком и в лесу поиска в глубину.
Согласно следствию 22.8 и. И < и. Ы, и, таким образом, вершина и является белой в момент и. б. Поскольку и может быть любым потомюм и, все вершины на единственном простом пути от и до и в лесу поиска в глубину в момент и. Ы белые. г=: Предположим, что в момент времени и, с( вершина и достижима из и вдоль пути, состоящего из белых вершин, но и не становится потомком и в дереве поиска в глубину.
Без потери общности предположим, что все остальные вершины вдоль пути становятся потомюми и (в противном случае в качестве и выберем на пути ближайшую к и вершину, которая не становится потомком и). Пусть ш— предшественник и на пути, так что го является потомком и (ш и и в действительности могут быть одной и той же вершиной).
Согласно следствию 22.8 го. ( < и. (. Посюльку вершина и должна быть открыта после того, как открыта и„но перед тем, как завершена обработка ло, мы имеем и. б < и, г( < го.~ < и.7'. Тогда из теоремы 22.7 следует, что отрезок [и. с(, и.~] полностью содержится внутри отрезка [и.
И, и.Д. Согласно следствию 22.8 вершина и должна в конечном итоге быть потомком вершины и. Часть Л. Алгоритмы для работы с гра4ами Классификации ребер Еще одно интересное свойство поиска в глубину заключается в том, что поиск может использоваться для классификации ребер входного графа С = ()г, Е).
Эта классификация ребер может использоваться для получения важной информации о графе. Например, в следующем разделе мы увидим, что ориентированный граф ацикличен тогда и только тогда, когда при поиске в глубину в нем не обнаруживается "обратных" ребер (лемма 22.11). Мы можем определить четыре типа ребер в терминах леса С, полученного при поиске в глубину в ~рафе С. 1. Ребра деревьев (пее ебйез) — это ребра леса С . Ребро (и, и) является ребром дерева, если при исследовании этого ребра была впервые открыта вершина о. 2.
Обралгиые ребра (васк ебйеа) — зто ребра (н, с), соединяющие вершину и с ее предком и в дереве поиска в глубину Петли (ребра-циклы), которые могут встречаться в ориентированных графах, рассматриваются как обратные ребра. 3. Прямые ребра (Гогьиагд еддеа) — это ребра (и,и), не являющиеся ребрами дерева и соединяющие вершину и с ее потомком е в дереве поиска в глубину. 4. Перекрестные ребра (сгоаз ебйез) — все остальные ребра графа.
Они могут соединять вершины одного и того же дерева поиска в глубину, когда ни одна из вершин не является предком другой, или соединять вершины в разных деревьях поиска в глубину. На рис.22.4 и 22.5 ребра помечены в соответствии с их типом. На рнс.22.5,(в) показан граф с рис.22.5,(а), перерисованный так, что все прямые ребра и ребра деревьев направлены вниз, а обратные ребра — вверх. Таким способом можно перерисовать любой граф.
Алгоритм 13РЗ можно модифицировать так, что он будет классифицировать встречающиеся при работе ребра. Ключевая идея состоит в том, что каждое ребро (и, и) можно классифицировать с помощью цвета вершины и при первом его исследовании (правда, при этом не различаются прямые и перекрестные ребра). 1, чн~тк говорит о том, что это ребро дерева. 2. силу определяет обратное ребро.
3. в~.лск указывает на прямое или перекрестное ребро. Первый случай следует непосредственно из определения алгоритма. Рассматривая второй случай, заметим, что серые вершины всегда образуют линейную цепочку потомков, соответствующую стеку активных вызовов процедуры 13РБЧ1з1т; количество серых вершин на единицу больше глубины последней открытой вершины в дереве поиска в глубину.
Исследование всегда начинается с самой глубокой серой вершины, так что ребро, которое достигает другой серой вершины, достигает предка исходной вершины. В третьем случае мы имеем дело с остальными ребрами, не подпадающими под первый или второй случай. Можно показать, что ребро (и, и) является прямым, если и. с( < о. Н, и перекрестным, если и. д ) е. д (см. упр. 22.3.5). Глана 12. Элементарные алгоритмы длл ртйаты е графами В неориентированном графе при классификации ребер может возникнуть определенная неоднозначность, поскольку (и,и) и (и,и) в действительности являются одним ребром.
В таком случае, когда ребро соответствует нескольким категориям, оно классифицируется в соответствии с лервой категорией в списке, применимой для данного ребра. Тот же результат получается, если выполнять классификацию в соответствии с тем, в каком именно виде — (и, и) или (и, и) — ребро встречается в первый раз в процессе выполнения алгоритма (см.
упр. 22.3.6). Теперь мы покажем, что прямые и перекрестные ребра никогда не встречаются при поиске в глубину в неориентированном графе. Теорема 22.10 При поиске в глубину в неориентированном графе С любое ребро С является либо ребром дерева, либо обратным ребром. 2Гоказагаельсгаво. Пусть (и, и) — произвольное ребро графа С, и предположим без потери общности, что и. И < и. И. Тогда вершина и должна быть открыта и завершена до того, как будет завершена работа с вершиной и (пока и — серая), так как и находится в списке смежности и.
Если ребро (и, и) исследуется сначала в направлении от и к и, то и до этого момента была неоткрытой (белой) — так как в противном случае мы бы уже исследовали зто ребро в направлении от и к и. Таким образом, (и, и) становится ребром дерева. Если же ребро (и, и) исследуется сначала в направлении от и к и, то оно является обратным, поскольку вершина и при первом исследовании ребра — серая. Мы ознакомимся с некоторыми применениями этой теоремы в последующих разделах. Упражнении гг.з.г Нарисуйте таблицу размером 3 х 3 со строками и столбцами, помеченными как зугнтп (белый), пкАу (серый) и вьлск (черный). В каждой ячейке (л,з) пометьте, может ли быть обнаружено в процессе поиска в глубину в ориентированном графе ребро из вершины цвета л' в вершину цвета з.
Для каждого возможного ребра укажите его возможный тип. Постройте такую же таблицу для неориентированного графа. 22З.2 Покажите, как работает поиск в глубину для графа, изображенного на рис. 22.6. Считаем, что цикл Гвг в строках 5-7 процедуры РРБ сканирует вершины в алфавитном порядке, а также что все списки смежности упорядочены по алфавиту. Для каждой вершины укажите время открытия н завершения, а для каждого ребра — его тип. Часть И.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
