Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 130
Текст из файла (страница 130)
Если же ребро (и, е) исследуется сначала в направлении от о к и, то оно является обратным, поскольку вершина и при первом исследовании ребра — серая. Мы ознакомимся с некоторыми применениями этой теоремы в последующих разделах. Упражнения 22.3-1. Нарисуйте таблицу размером 3 х 3, со строками и столбцами, помеченными как туп)те (белый), скАу (серый) и в~.лск (черный).
В каждой ячейке (т, т') пометьте, может ли быть обнаружено в процессе поиска в глубину в ориентированном графе ребро из вершины цвета з в вершину цвета 2. Для каждого возможного ребра укажите его возможный тип. Постройте такую же таблицу для неориентированного графа. 22.3-2.
Покажите, как работает поиск в глубину для графа, изображенного на рис. 22.6. Считаем, что цикл Гог в строках 5-7 процедуры РРБ сканирует вершины в алфавитном порядке, а также что все списки смежности упорядочены по алфавиту. Для каждой вершины укажите время открытия и завершения, а для каждого ребра — его тип. 22.3-3.
Напишите скобочное выражение, соответствующее поиску в глубину, показанному на рис. 22.4. 22.3-4. Покажите, что ребро (и, е) является Глава 22. Элементарные алгоритмы для работы с графами 631 Рис. 22.6. Ориентированный граф для упражнений 22.3-2 н 22.5-2 а) ребром дерева или прямым ребром тогда и только тогда, югда 1[и] < 1[и] < У [и] < .г [и]' б) обратным ребром тогда и только тогда, югда д [и] < г1 [и] < г" [и] < < ~[и]' в) перекрестным ребром тогда и только тогда, когда И[и] < г' [и] < < Н [и] < г" [и!.
22.3-5. 22.3-6. 22.3-7. 22.3-8. 22.3-9. 22.3-10. 22.3-11. Покажите, что в неориентированном графе классификация ребра (и, и) как ребра дерева или обратного ребра в зависимости от того, встречается ли первым ребро (и, и) или (и, и) при поиске в глубину, эквивалентна классификации в соответствии с приоритетами типов в схеме классифи- кации.
Перепишите процедуру РРЯ с использованием стека для устранения ре- курсии. Приведите юнтрпример к гипотезе, заключающейся в том, что если в ориентированном графе С имеется путь от и к и и что если И [и] < с1 [и] при поиске в глубину в С, то и — потомок и в лесу поиска в глубину. Приведите юнтрпример к гипотезе, заключающейся в том, что если в ориентированном графе С имеется путь от и к и, то любой поиск в глубину должен дать в результате И [и] < )' [и].
Модифицируйте псевдокод поиска в глубину так, чтобы он выводил все ребра ориентированного графа С вместе с их типами. Какие измене- ния следует внести в псевдокод (если таювые требуются) для работы с неориентированным графом? Объясните, как вершина ориентированного графа может оказаться един- ственной в дереве поиска в глубину, несмотря на наличие у нее как входящих, так и исходящих ребер. Покажите, что поиск в глубину в неориентированном графе С может использоваться для определения связных компонентов графа С и что Часть Ч1. Алгоритмы для работы с графами 632 лес поиска в глубину содержит столько деревьев, околыш в графе связных юмпонентов. Говоря более точно, покажите, как изменить поиск в глубину так, чтобы каждой вершине о присваивалась целая метка сс [а[ в диапазоне от 1 до lс (где Й вЂ” количество связных компонентов), такая что сс [и] = сс [о[ тогда и только тогда, когда и и о принадлежат одному связному компоненту.
* 22.3-12. Ориентированный граф С = (У, Е) обладает свойством односвязности (з1пя1у соппес~ед), если из и о следует, что имеется не более одного пути от и к о для всех вершин и, е е 1'. Разработайте эффективный алгоритм для определения, является ли ориентированный граф односвязным. 22.4 Топологическая сортировка В этом разделе показано, каким образом можно использовать поиск в глубину для топологической сортировки ориентированного ациклического графа (гйгес1ед асус11с ягарЬ, для которого иногда используется аббревиатура "дая"). Топологическая сортлировка (юро!оя(са! зотт) ориентированного ациклического графа С = = (К Е) представляет собой таюе линейное упорядочение всех его вершин, что если граф С содержит ребро (и, и), то и при таюм упорядочении располагается до е (если граф не является ацикличным, такая сортировка невозможна).
Топо- логическую сортировку графа можно рассматривать как такое упорядочение его вершин вдоль горизонтальной линии, что все ребра направлены слева направо. Таким образом, топологическая сортировка существенно отличается от обычных видов сортировки, рассмотренных в части 1Н. Ориентированные ациклические графы используются во многих приложениях для указания последовательности событий.
На рис. 22.7 приведен пример графа, построенного профессором Рассеянным для утреннего одевания. Некоторые вещи надо обязательно одевать раньше других, например, сначала носки, а затем туфли. Другие вещи могут быть одеты в произвольном порядке (например, носки и рубашка). Ребро (и, и) в ориентированном ациклическом графе на рис. 22.7а показывает, что вещь и должна быть одета раньше вещи и.
Топологическая сортировка этого графа дает нам порядок одевания. На рис. 22.7б показан отсортированный ориентированный ациклический граф, вершины которого расположены вдоль горизонтальной линии так, что все ребра направлены слева направо. Вот простой алгоритм топологической сортировки ориентированного ациклического графа: Глава 22. Элементарные алгоритмы для работы с графами 633 тгуса Йоа;к11'лз 1, "'..--.. 'ю' [Часы) '~, ы ;Ру5кс1уа'~, ~ГЬ' .~ч' 4ь у ~Гас ",,а<~ «'4 ~несси\ у трусы 1 у Гьлужа)-~-(туат' ~,часы,,' ~Рубыту~-(Гсчс.ту ~~~ж~уУк~-у,,йклж1уу ~,';С !!Га пп )У,'~4 УЛО Щ УД УД Чу Рис.
22.7. Топологическая сортировка одежды ТОРОь00!сАь ЯОкт(С) 1 Вызов РРЗ(С) для вычисления времени завершения 1[уу] для каждой вершины уу 2 По завершении работы над вершиной внести ее в начало связанного списка 3 ге1пги Связанный список вершин На рис. 22.76 видно, что топологически отсортированные вершины располагаются в порядке убывания времени завершения. Мы можем выполнить топологическую сортировку за время 9 ('ту+ Е), поскольку поиск в глубину выполняется именно за это время, а вставка каждой из [1У[ вершин в начало связанного списка занимает время 0 (1). Докажем корректность этого алгоритма с использованием следующей ключевой леммы, характеризующей ориентированный ациклический граф.
Лемма 22.11. Ориентированный граф С является ациклическим тогда и только тогда, когда поиск в глубину в С не находит в нем обратных ребер. Доказавувльсвуво. ~: Предположим, что имеется обратное ребро (и,е). Тогда вершина уу является предком и в лесу поиска в глубину. Таким образом, в графе С имеется путь из е в и, и ребро (и, и) завершает цикл. ч=: Предположим, что граф С содержит цикл с. Покажем, что поиск в глубину обнаружит обратное ребро.
Пусть е — первая вершина, открытая в с, и пусть (и, е) — предыдущее ребро в с. В момент времени с~ [уу[ вершины с образуют путь из белых вершин от уу к и. В соответствии с теоремой о белом пути, вершина и Часть Ч!. Алгоритмы для работы с графами 634 Рис. 22.8.
Ориентированный ацнклический граф для топологической сортировки становится потомком ц в лесу поиска в глубину. Следовательно, (и, ц) — обратное ребро. И Теорема 22.12. Процедура Товоьоо~сль Болт(С) выполняет топологическую сортировку ориентированного ациклического графа С. Доказательсиио. Предположим, что над данным ориентированным ациклическим графом С = (У, Е) выполняется процедура 13РБ, которая вычисляет время завершения его вершин. Достаточно показать, что если для произвольной пары разных вершин и, с е г' в графе С имеется ребро от и к и, то г [ц] < г [и].
Рассмотрим произвольное ребро (и, ц), исследуемое процедурой 13РБ(С). При исследовании вершина и не может быть серой, поскольку тогда и была бы предком и и (и, ц) представляло бы собой обратное ребро, что противоречит лемме 22.11. Следовательно, вершина с должна быть белой либо черной. Если вершина ц — белая, то она становится потомком и, так что Г" [ц] < г" [и]. Если ц — черная, значит, работа с ней уже завершена и значение 7' [о] уже установлено. Поскольку мы все еше работаем с вершиной и, значение Г" [и] еще не определено, так что, когда это будет сделано, будет выполняться неравенство Г" [ц] < Г' [и]. Следовательно, для любого ребра (и, ц) ориентированного ациклического графа выполняется условие 7 [с] < 1 [и], что и доказывает данную теорему. И Упражнения 22.4-1. Покажите, в каком порядке расположит вершины представленного на рис.
22.8 ориентированного ациклического графа процедура Товоьос!ель Болт, если считать, что цикл 1ог в строках 5-7 процедуры 13РБ сканирует вершины в алфавитном порядке, а также что все списки смежности упорядочены по алфавиту. 22.4-2. Разработайте алгоритм с линейным временем работы, который для данного ориентированного ациклического графа С = (Ъ; Е) и двух вершин Глава 22.
Элементарные алгоритмы для работы с графами 635 з и г определяет количество путей из а к 1 в графе С. Например, в графе на рис. 22.8 имеется ровно 4 пути от вершины р к вершине гл ров, ромул, роагре и рапге. Ваш алгоритм должен только указать количество путей, не перечисляя их. 22.4-3. Разработайте алгоритм для определения, содержит ориентированный граф С = (У,Е) цикл или нет. Ваш алгоритм должен выполняться за время О (У), независимо от 1Е~. 22.4-4. Докажите или опровергните следующее утверждение: если ориентированный граф С содержит циклы, то процедура Того1.осси.
Бокт(С) упорядочивает вершины таким образом, что при этом количество "плохих" ребер (идущих в противоположном направлении) минимально. 22.4-5. Еще один алгоритм топологической сортировки ориентированного ациклического графа С = (У, Е) состоит в поиске вершины со входящей степенью О„выводе ее, удалении из графа этой вершины и всех исходящих из нее ребер, и повторении этих действий до тех пор, пока в графе остается хоть одна вершина. Покажите, как реализовать описанный алгоритм, чтобы время его работы составляло О (У + Е).
Что произойдет, если в графе С будут иметься циклы? 22.5 Сильно связные компоненты Теперь мы рассмотрим классическое применение поиска в глубину: разложение ориентированного графа на сильно связные компоненты. В этом разделе будет показано„как выполнить такое разложение при помощи двух поисков в глубину. Ряд алгоритмов для работы с графами начинаются с выполнение такого разложения графа, и после разложения алгоритм отдельно работает с каждым сильно связным компонентом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
