Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Упражнения
|
|
> 19.120. Опишите, что произойдет, когда вы воспользуетесь алгоритмом Косарайю, что
бы найти сильные компоненты графа DAG.
> 19.121. Опишите, что произойдет, когда вы воспользуетесь алгоритмом Косарайю, что
бы найти сильные компоненты орграфа, который состоит из одного цикла.
•• 19.122. Можно ли избежать вычислений обращения орграфа в версии метода Косарайю, ориентированной на представление графов в виде списка смежных вершин (программа 19.10), за счет использования одной из трех технологий, отмеченных в разделе 19.4, с целью избежать вычисления обращения при выполнении топологической сортировки? Для каждой технологии дайте либо доказательство того, что она работает, либо контрпример, показывающий, что она не работает.
о 19.123. Покажите в стиле рис. 19.28 леса DFS и содержимое вспомогательных векторов, индексированных именами вершин, которые получаются, когда вы используете алгоритм Косарайю для вычисления сильных компонент обращения орграфа, представленного на рис. 19.5. (Вы должны получить те же сильные компоненты.)
19.124. Покажите в стиле рис. 19.28 леса DFS и содержимое вспомогательных векторов, индексированных именами вершин, которые получаются, когда вы используете алгоритм Косарайю для вычисления сильных компонент орграфа
3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.
о 19.125. Реализуйте алгоритм Косарайю с целью определения сильных компонент орграфа в представлении, которое поддерживает проверку edge существования ребра. Явное вычисление обращения графа исключается. Указание: Рассмотрите возможность использования двух различных рекурсивных функций DFS.
о 19.126. Опишите, что произойдет, когда вы воспользуетесь алгоритмом Тарьяна, чтобы найти сильные компоненты графа DAG.
> 19.127. Опишите, что произойдет, когда вы воспользуетесь алгоритмом Тарьяна, чтобы
найти сильные компоненты орграфа, который состоит из одного цикла.
Часть 5. Алгоритмы на графах
о 19.128. Покажите в стиле рис. 19.28 леса DFS, содержимое стека во время выполнения алгоритма и завершающее состояние вспомогательных векторов, индексированных именами вершин, которые получаются, когда используется алгоритм Тарьяна для вычисления сильных компонент обращения орграфа, представленного на рис. 19.5. (Вы должны получить те же сильные компоненты.)
19.129. Покажите в стиле рис. 19.29 леса DFS, содержимое стека во время выполнения алгоритма и окончательное содержимое векторов, индексированных именами вершин, которые получаются, когда вы используете алгоритм Тарьяна для вычисления сильных компонент орграфа
3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.
о 19.130. Внесите такие изменения в реализацию алгоритма Тарьяна в программе 19.11 и алгоритма Габова в программе 19.12, чтобы они могли использовать сигнальные значения с тем, чтобы избежать необходимости явной проверки поперечных связей.
19.131. Покажите в стиле рис. 19.29 леса DFS, содержимое обоих стеков во время выполнения алгоритма и окончательное содержимое вспомогательных векторов, индексированных именами вершин, которые получаются, когда вы используете алгоритм Габова для вычисления сильных компонент орграфа
3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.
• 19.132. Дайте полное доказательство свойства 19.16.
о 19.133. Разработайте версию алгоритма Габова, который находит мосты и реберно-связные компоненты в неориентированных графах.
• 19.134. Разработайте версию алгоритма Габова, который находит точки сочленения и
двусвязные компоненты в неориентированных графах.
19*135. Разработайте таблицу в духе табл. 18.1 с целью изучения сильных компонент в случайных графах (см. табл. 19.2). Пусть S есть множество набор в наибольшей сильной компоненте. Следите за изменением размера набора S проведите анализ процентного отношения ребер следующих четырех классов: те, которые соединяют две вершины из 5; те, которые указывают на вершины, не входящие в S; те, которые указывают на вершины, входящие в 5, и соединяют две вершины, не входящие в S.
19.136. Проведите эмпирические исследования с тем, чтобы сравнить метод решения " в лоб" задачи вычисления сильных компонент, описанный в начале этого раздела, с алгоритмом Косарайю, с алгоритмом Тарьяна и с алгоритмом Габова для различных типов орграфов.
•••19.137. Разработайте линейный по времени алгоритм для сильной двусвязности (strong 2-connectivity): Определите, обладает ли сильно связанный орграф тем свойством, что он остается сильно связным после удаления любой из вершин (и всех инцидентных ей ребер).