Алгоритмы - построение и анализ (1021735), страница 128
Текст из файла (страница 128)
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 [о~.
Тогда вершина и должна быть открыта и завершена до того, как будет завершена работа с вершиной и (пока и — серая), так как е находится в списке смежности и. Если ребро (и, и) исследуется сначала в направлении от и к п, то е до этого момента была неоткрытой (белой) — так как в противном случае мы бы уже исследовали это ребро в направлении от о к и.
Таким образом, (и, и) становится ребром дерева. Если же ребро (и, е) исследуется сначала в направлении от о к и, то оно является обратным, поскольку вершина и при первом исследовании ребра — серая. Мы ознакомимся с некоторыми применениями этой теоремы в последующих разделах. Упражнения 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, "'..--.. к ~~Часы) 9, ы ;Ру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. Следовательно, вершина с должна быть белой либо черной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
