Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 143
Текст из файла (страница 143)
Алгоритмы длл работы е графаии Рие. 22.6. Ориентированный граф к тир. 22гй2 и 223.2. 22.3.3 Напишите скобочное выражение, соответствующее поиску в глубину, показанному на рис. 22.4. 223.4 Покажите, что в каждой вершине достаточно только одного бита для хранения цвета, доказав, что результат работы процедуры РРБ не изменится при удалении строки 8 из процедуры РРБ-Уццт. 22.3.3 Покажите, что ребро (и, и) является и.
ребром дерева или прямым ребром тогда и только тогда, когда и. 6 < и. И < о.з < и.7; 6. обратным ребром тогда и только тогда, когда о. д < и. д < и.7' < с.З'; го перекрестным ребром тогда и только тогда„когда и. 6 < ш7 < и. И < и.Х. 22.3.6 Покажите, что в неориентированном графе классификация ребра (и, и) как ребра дерева или обратного ребра в зависимости от того, встречается ли первым ребро (и, о) или (и, и) при поиске в глубину, эквивалентна классификации в соответствии с приоритетами типов в схеме классификации. 22.3. 7 Перепишите процедуру ВЕЗ, используя стек для устранения рекурсии.
гг.з.в Приведите контрпример к гипотезе о том, что если в ориентированном графе С имеется путь от и к о и что если и.в < в. 6 при поиске в глубину в С, то ив потомок и в полученном лесу поиска в глубину. 22.3 р Приведите контрпример к гипотезе, заключающейся в том, что если в ориентированном графе С имеется путь от и к и, то любой поиск в глубину должен дать в результате ю. д < и.7". б49 Глава гг.
Элементарные алгоритмы длл работы с графами 22З.10 Модифицируйте псевдокод поиска в глубину так, чтобы он выводил все ребра ориентированного графа С вместе с их типами. Какие изменения следует внести в псевдокод (если таковые требуются) для работы с неориентированным графом? 22.3.11 Объясните, как вершина и ориентированного графа может оказаться единственной в дереве поиска в глубину, несмотря на наличие у нее как входящих, так и исходящих ребер в С. 22.3.12 Покажите, что поиск в глубину в неориентироаанном графе С может использоваться для определения связных компонентов графа С и что лес поиска в глубину содержит столько деревьев, сюлько в графе связных юмпонентов.
Говоря более точно, покажите, как изменить поиск в глубину так, чтобы каждой вершине с присваивалась целочисленная метка ш сс в диапазоне от 1 до Й (где Й вЂ” юличество связных юмпонентов в С), такая, что и. сс = с. сс тогда и только тогда, когда и и е принадлежат одному и тому же связному юмпоненту. 22.3.13 * Ориентированный граф С = ()г, Е) обладает свойством одиоеалзиосвги (зшя1у соппесзед), если из и и следует, что в С имеется не более одного пути от и к е для всех вершин и, с е Ь'.
Разработайте эффективный алгоритм для определения, является ли ориентированный граф односвязным. 22.4. Топологическаи сортировка В этом разделе показано, каким образом можно использовать поиск в глубину для топологичесюй сортировки ориентированного ациклического графа (йгесих( асусйс йгарп, для которого иногда используется аббревиатура "дай").
Топалогичеекая соргвиловка (1оро!ой(са1 вог1) ориентированного ацикличесюго графа С = (Ъ; Е) представляет собой такое линейное упорядочение всех его вершин, что если граф С содержит ребро (и, а), то и при таком упорядочении располагается до с (если граф содержит цикл, такая сортировка невозможна). Топологическую сортировку графа можно рассматривать как такое упорядочение его вершин вдоль горизонтальной линии, что все ребра направлены слева направо. Таким образом, топологическая сортировка существенно отличается от обычных видов сортировки, рассмотренных в части 11. Ориентированные ациклические графы используются во многих приложениях для указания последовательности событий.
На рис. 22.7 приведен пример графа, построенного профессором Рассеянным для утреннего одевания. Одни вещи обязательно нужно одевать раньше других, например сначала носки, а затем туфли. Другие вещи могут быть одеты в произвольном порядке (например, носки и рубашка). Ребро (и, е) в ориентированном ациклическом графе на рис. 22.7, (а) по- 650 Часть Р!.
Алгоритмы длл работы с графами 11/! 6 ', Трусы (/)/зскг!) /зла ( /(ас/Р 9ло !2/!5 ~~~ — — -- — -- — — Ф,Т)флг/1 13/!4 Рубэзпа/ !/8 ал ( Реналь ' (а) зм (б) фа~~ ( Тр)сы' у~т~~~' Т)ф/ш) *'~йаа ~~~~)з (Резал~~'~~~ц~~~ъ-~а~~ 12/15 1ЗЛ4 9ЛО 141 6Л аэ 3/4 11/16 !7/!8 Рис. 22.7. (а) Топологическая сортировка процесса одевания профессора Рассеянного. Кюклое ориентированное ребро (и, о) означает, что аешь и долина быть одета до веши о. Для кюкдой вершины приведены время открытия и время завершения.
(б) Тот лю граф, изображенный с учетом выполненной топологической сортировки; вершины располагаются слева направо в порядке уменыпения времени завершение. Все ориентированные ребра направлены слева направо. казывает, что вещь и должна быть одета раньше вещи и. Топологическая сортировка этого графа дает нам порядок одевания.
На рис. 22.7,(б) показан отсортированный ориентированный ациклический граф, вершины которого расположены вдоль горизонтальной линии так, что все ребра направлены слева направо. Вот простой алгоритм топологической сортировки ориентированного ациклического графа. ТОРОЕОО!САь-БОГАТ (С) 1 Вызвать ПРИ(С) для вычисления времен завершения и.у" для каждой вершины и 2 По завершении работы над вершиной внести ее в начало связанного списка 3 ге(нгп связанный список вершин На рис. 22.7, (б) видно, что топологически отсортированные вершины располагаются в порядке убывания времени завершения.
Мы можем выполнить топологнческую сортировку за время б/((г + Е), поскольку поиск в глубину выполняется именно за это время, а вставка каждой из Щ вершин в начало связанного списка занимает времи О(1). Докажем корректность этого алгоритма с использованием следующей ключе- вой леммы, характеризующей ориентированный ациклический граф. Ле и гг.л Ориентированный граф С является ациклическим тогда и только тогда, когда поиск в глубину в С не находит в нем обратных ребер. Глава 22. Элемеллкрглые алгоритмы длл работы с Чоафамк 651 Докязлтлельслеегь =к: Предположим, что имеется обратное ребро (и,и). Тогда вершина и является предком и в лесу поиска в глубину. Таким образом, в графе С имеется путь от и к и„и обратное ребро (и, и) завершает цикл.
~: Предположим, что граф С содержит цикл с. Покажем, что поиск в глубину обнаружит обратное ребро. Пусть и — первая вершина, открытая в с, и пусть (и, и) — предыдущее ребро в с. В момент времени и. г1 вершины с образуют путь из белых вершин от и к и. В соответствии с теоремой о белом пути вершина и становится потомком и в лесу поиска в глубину. Следовательно, (и, и) — обратное ребро.
Теорана 32. 12 Процедура ТОрО2.ОО|О~.-БОКт выполняет топологическую сортировку переданного ей ориентированного ациклического графа. Доказалвельслеагл Предположим, что над данным ориентированным ациклическим графом С = (К Е) выполняется процедура ПРБ, которая вычисляет времена завершения для его вершин. Достаточно показать, что если для произвольной пары разных вершин и, и е к' в графе С имеется ребро от и к и, то и.5' < и.5'.
Рассмотрим произвольное ребро (и,и), исследуемое процедурой ПР8(С). При исследовании вершина и не может быть серой, поскольку тогда и была бы предком и и ребро (и, и) представляло бы собой обратное ребро, что противоречит лемме 22.11. Следовательно, вершина и должна быть либо белой, либо черной. Если вершина и — белая, то она становится потомком и, так что и.5" < и.5". Если и — черная, значит, работа с ней уже завершена и значение и.5 уже установлено. Поскольку мы все еще работаем с вершиной и, значение и.5 еще не определено, так что, когда это будет сделано, будет выполняться неравенство и.5' < и. Г".
Таким образом, для любого ребра (и, и) ориентированного ациклического графа выполняется условие и. Г' < и. Г', что и доказывает данную теорему. упражнении 22.б..1 Покажите, в каком порядке расположит вершины представленного на рис.22.8 ориентированного ашпогического графа процедура ТОРОьОО1Ом.-БОкт, если считать, что выполняются все предположения, сформулированные в упр. 22.3.2. Рне. 22.й. Ориентированный кпвклнческнй грвф ллн топологической сортировки, Часть Л.
Алгоритмы длл работы с графами ббг 22.4.2 Разработайте алгоритм с линейным временем работы, который для данного ориентированного ациклического графа С = (ьг, Е) и вершин л и ~ определяет количество простых путей от л к Е в графе С. Например, в графе на рис. 22.8 имеется ровно четыре пути от вершины р к вершине ш рои, рогуп, роагуо и ратую. (Ваш алгоритм должен только указать количество путей, не перечисляя их.) 22.4.3 Разработайте алгоритм для определения, содержит ли данный неориентированный граф С = (ьг, Е) простой цикл.
Ваш алгоритм должен выполняться за время 0(ьг) независимо от ~Е1 22.4.4 Докажите или опровергните следующее утверждение: если ориентированный граф С содержит циклы, то процедура ТОРО~.оисм.-Бокт(С) упорядочивает вершины таким образом, что при этом количество "плохих" ребер (идущих в противоположном направлении)минимально. 22.4.5 Еще один алгоритм топологической сортировки ориентированного ациклического графа С = ( ьг, Е) состоит в поиске вершины с входящей степенью О, ее выводе, удалении из графа этой вершины и всех исходящих из нее ребер и повторении этих действий до тех пор, пока в графе остается хоть одна вершина.
Покажите, как реализовать описанный алгоритм, чтобы время его работы составляло 0(Р + Е). Что произойдет, если в графе С будут иметься циклы? 22.5. Сильно связные компоненты Теперь рассмотрим классическое применение поиска в глубину: разложение ориентированного графа на сильно связные компоненты. В этом разделе будет показано, как выполнить такое разложение с помощью двух поисков в глубину. Ряд алгоритмов для работы с графами начинается с выполнения такого разложения графа, и после разложения алгоритм работает с каждым сильно связным компонентом отдельно. Полученные решения затем комбинируются в соответствии со структурой связей между сильно связными компонентами. В приложении Б сказано, что сильно связный компонент ориентированного графа С = ($; Е) представляет собой максимальное множество вершин С С $', такое, что для каждой пары вершин и и о из С справедливо как и» и, так и с» и, т.е.
вершины и и и достижимы одна из другой. На рис. 22.9 приведен соответствующий пример. Наш алгоритм поиска сильно связных компонентов графа С = (~; Е) использует транспонирование С, которое определяется в упр. 22.1.3 как граф Ст = (Р, Е ), где Е = ((и, о): (с, и) е Е), т.е. Ет состоит из ребер С с изменением их направления на обратное. Для представления с использованием списков смеж- Глава 22 3ленемтаряые аморальны для рабаты с лоаЧЬпни 653 МЗЛ4,',:,4'ФггИЛ6 „— зв( )Г О. „::;:""':„: 2)д) (в) <е) (в) Рнс.
22.9. (в) Орнентлроаанный граф С. Каждая заштрнхоаанная область представляет собой сильно связный компонент С. Кажлая вершние помечена ее временем открытка н завершения прн поиске в глубину, а ребра дерека выделены штрнховюй. (6) Граф Ст. транспоннрованный С, с показанным лесом поиска в глубину, вычнсленным в строке 3 процедуры Бткомоьт-СокнестаоСомвонаптз, н выделеннымн ппрнховаой ребрвмн дерева. Каждый сильно связный компонент соответствует одному дереву поиска в глубину. Вершины Ь, с, д н Ь, выделенные темным цветом, представляют собой корин деревьев поиска в глубину, сгенернроаанных панском в глубину в графе Ст. (в) Ацшошческнй граф компонентов Скос, полученный путем статна всех ребер в пределах сильно связных компонентов С, так что в каждом компоненте остается только по одной мршнне. ности данного графа С получить граф Ст можно за время 0(Ъ'+ Е).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
