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

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

Файл №1123758 Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.)) 130 страницаТ. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758) страница 1302019-05-10СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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 Сильно связные компоненты Теперь мы рассмотрим классическое применение поиска в глубину: разложение ориентированного графа на сильно связные компоненты. В этом разделе будет показано„как выполнить такое разложение при помощи двух поисков в глубину. Ряд алгоритмов для работы с графами начинаются с выполнение такого разложения графа, и после разложения алгоритм отдельно работает с каждым сильно связным компонентом.

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

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

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6418
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее