Структуры данных и алгоритмы (1021739), страница 52
Текст из файла (страница 52)
Пусть ациклический орграф имеет е дуг. Зафиксируем две различные вершины s и t этого графа. Постройте алгоритм с временем выполнения О(е) для нахождения максимального множества вершин, составляющих пути от вершиныs к вершине t.6.12. Постройте алгоритм преобразования в ациклический орграф арифметическихвыражений с операторами сложения и умножения, используя повторяющиеся подвыражения. Какова временная сложность (время выполнения) этогоалгоритма?6.13. Постройте алгоритм чтения-арифметических выражений, представленных ввиде ациклического орграфа.6.14. Напишите программу нахождения самого длинного пути в ациклическом орграфе.
Какова временная сложность этого алгоритма?6.15. Найдите сильно связные компоненты графа, представленного на рис. 6.29.*6.16. Докажите, что редуцированный граф строго связных компонент (см. раздел 6.7)обязательно должен быть ациклическим орграфом.6.17. Нарисуйте первый остовный лес, обратный граф и второй остовный лес впроцессе определения сильно связных компонент орграфа, показанного нарис.
6.29.6.18. Реализуйте алгоритм нахождения сильно связных компонент, рассмотренныйв разделе 6.7.*6.19. Покажите, что алгоритм нахождения сильно связных компонент требуетвремени порядка О(е) на ориентированном графе, имеющем е дуг и п вершин, если п < е.*6.20. Напишите программу, на входе которой задается орграф и две его вершины.Программа должна распечатывать все простые пути, ведущие от одной вершинык другой. Какова временная сложность (время выполнения) этой программы?*6.21.
Транзитивная редукция ориентированного графа G = (V, Е) определяется какпроизвольный граф G' = (V, Е'), имеющий то же множество вершин, но с минимально возможным числом дуг, транзитивное замыкание которого совпадаетс транзитивным замыканием графа G. Покажите, что если граф G ацикличен,то его транзитивная редукция единственна.*6.22. Напишите программу нахождения транзитивной редукции орграфа. Каковавременная сложность этой программы?206ГЛАВА 6. ОРИЕНТИРОВАННЫЕ ГРАФЫ*6.23. Орграф G' = (V, Е") называется минимальным эквивалентным орграфом дляорграфа G = (V, £), если Е' — наименьшее подмножество множества Е такое,что транзитивные замыкания обоих орграфов G и G' совпадают. Покажите, чтоесли граф G ацикличен, то для него существует только один минимальный эквивалентный орграф, а именно — его транзитивная редукция.*6.24.
Напишите программу нахождения минимального эквивалентного орграфа. Какова временная сложность этой программы?*6.25. Напишите программу нахождения самого длинного простого пути от заданнойвершины орграфа. Какова временная сложность этой программы?Библиографические примечанияХорошими источниками дополнительных сведений по теории графов могут служить монографии [11] и [47]1. В книгах [24], [28] и [110] рассматриваются различные алгоритмы на графах.Алгоритм нахождения кратчайших путей от одного источника, описанный в разделе 6.3, взят из работы Дейкстры [26].
Алгоритм нахождения всех кратчайших путей описан Флойдом [33], а алгоритм транзитивного замыкания — Уоршеллом [114].В работе [57] приведен эффективный алгоритм нахождения кратчайших путей в разреженных графах. В книге [63] можно найти дополнительный материал по топологической сортировке.Алгоритм определения сильно связных компонент, описанный в разделе 6.7, подобен алгоритму, предложенному Косерейю (R. Kosaraju) в 1978 г. (неопубликовано),и алгоритму, опубликованному в статье [99]. Тарьян (Tarjan) [107] предложил другойалгоритм определения сильно связных компонент, который требует только одногообхода графа методом поиска в глубину.В [19] приведено много примеров использования графов для решения задач планирования и расписаний, подобных упражнению 6.2.
В работе [2] доказана единственность транзитивной редукции для ациклического орграфа и что нахождение транзитивной редукции орграфа вычислительно эквивалентно нахождению транзитивногозамыкания (упражнения 6.21 и 6.22). С другой стороны, нахождение минимальногоэквивалентного орграфа (упражнения 6.23 и 6.24) является вычислительно болеесложной задачей — это NP-полная задача [93].1Обе книги переведены на русский язык (см. библиографию в конце книги). — Прим.
ред.УПРАЖНЕНИЯ207ГЛАВА 7НеориентированныеграфыНеориентированный граф G — (V, Е) состоит из конечного множества вершин V и множества ребер Е. В отличие от ориентированного графа, здесь каждое ребро (v, w) соот1ветствует неупорядоченной паре вершин : если (v, w) — неориентированное ребро, то(v, w) = (w, v). Далее неориентированный граф мы будем называть просто графом.Графы широко используются в различных областях науки и техники для моделирования симметричных отношении между объектами.
Объекты соответствуют вершинам графа, а ребра — отношениям между объектами. В этой главе будут описаныразличные структуры данных, которые применимы для представления графов. Мытакже рассмотрим алгоритмы решения трех типовых задач, возникающих при работес графами: построения минимальных остовных деревьев, определения двусвязныхкомпонент и нахождения максимального паросочетания графа.7.1. Основные определенияМногое из терминологии ориентированных графов применимо к неориентированным графам. Например, вершины v и w называются смежными, если существуетребро (v, w). Мы будем также говорить, что ребро (v, w) инцидентно вершинам и и w.Путем называется такая последовательность вершин vit v2vn, что для всех i,1 < i < n, существуют ребра (v,, i>, + 1 ) .
Путь называется простым, если все вершиныпути различны, за исключением, возможно, вершин Vi и ип. Длина пути равна количеству ребер, составляющих путь, т.е. длина равна п - 1 для пути из га вершин. Еслидля вершин Ui и ип существует путь vlt v2и„, то эти вершины называются связанными. Граф называется связным, если в нем любая пара вершин связанная.Пусть есть граф G = (V, Е) с множеством вершин V и множеством ребер Е. ГрафG' — (V, Е') называется подграфом графа G, если1.2.множество V является подмножеством множества V,множество Е' состоит из ребер (v, w) множества Е таких, что обе вершины v и wпринадлежат V.Если множество Е' состоит из всех ребер (v, w) множества Е таких, что обе вершины v и w принадлежат V, то в этом случае граф G' называется индуцированнымподграфом графа G.Пример 7.1.
На рис. 7.1,а показан граф G = (V, Е) с множеством вершин V = (а, Ь,с. d} и множеством дуг Е = {(a, b), (a, d), (b, с), (Ь, d), (с, d)}. Ha рис. 7.1,6 представлен один из его индуцированных подграфов, заданный множеством вершин V = {а, Ь,с) и содержащий все ребра, не инцидентные вершине d. ОСвязной компонентой графа G называется максимальный связный индуцированный подграф графа G.Пример 7.2. Граф, показанный на рис. 7Л,а, является связным графом и имееттолько одну связную компоненту, а именно — самого себя. На рис. 7.2 представленнесвязный граф, состоящий из двух связных компонент. D1Пока не будет сказано другое, будем считать, что ребро всегда соответствует паре различных вершин.. G>абРис.
7.1. Граф и один их его подграфовРис. 7.2. Несвязный графЦиклом (простым) называется путь (простой) длины не менее 3 от какой-либовершины до нее самой. Мы не считаем циклами пути длиной 0, длиной 1 (петля отвершины v к ней самой) и длиной 2 (путь вида v, w, и). Граф называется циклическим, если имеет хотя бы один цикл. Связный ациклический граф, представляющийсобой "дерево без корня", называют свободным деревом.
На рис. 7.2 показан граф,состоящий из двух связных компонент, каждая из которых является свободным деревом. Свободное дерево можно сделать "обычным" деревом, если какую-либо вершину назначить корнем, а все ребра сориентировать в направление от этого корня.Свободные деревья имеют два важных свойства, которые мы будем использовать вследующих разделах.1.2.Каждое свободное дерево с числом вершин n, n > 1, имеет в точности п - 1 ребер.Если в свободное дерево добавить новое ребро, то обязательно получится цикл.Мы докажем первое утверждение методом индукции по п.
Очевидно, что утверждение справедливо для п = 1, поскольку в этом случае имеем только одну вершинуи не имеем ребер. Пусть утверждение 1 справедливо для свободного дерева с п - 1вершинами. Рассмотрим дерево G e n вершинами.Сначала покажем, что в свободном дереве существуют вершины, имеющие одноинцидентное ребро. Заметим, что G не содержит изолированных вершин (т.е. вершин, не имеющих инцидентных ребер), иначе граф G не был бы связным. Теперьсоздадим путь от некоторой вершины DI, следуя по произвольному ребру, инцидентному вершине uj.
На каждом шаге построения этого пути, достигнув какой-либовершины, выбираем инцидентное ей ребро, которое ведет к вершине, еще не участвовавшей в формировании пути. Пусть таким способом построен путь v\, V2, •••, vt.Вершина i>, будет смежной либо с одной вершиной u,-i, либо еще с какой-нибудь, невходящей в построенный путь (иначе получится цикл). В первом случае получаем,что вершина vt имеет только одно инцидентное ей ребро, и значит, наше утверждение о том, что в свободном дереве существуют вершины, имеющие одно инцидентноеребро, будет доказано. Во втором случае обозначим через u,+i вершину, смежную свершиной и 4 , и строим путь i>1( v2vt, v,+i. В этом пути все вершины различны(иначе опять получится цикл).
Так как количество вершин конечно, то этот процесс7.1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ209закончится за конечное число шагом и мы найдем вершину, имеющую одно инцидентное ребро. Обозначим такую вершину через и, а инцидентное ей ребро — (и, ш).Теперь рассмотрим граф G', полученный в результате удаления из графа G вершины v и ребра (v.
w). Граф G' имеет и - 1 вершину, для него выполняется утверждение 1 и поэтому он имеет п - 2 ребра. Но граф G имеет на одну вершину и на одно ребро больше, чем граф G', поэтому для него также выполняется утверждение 1.Следовательно, утверждение 1 доказано.Теперь мы легко докажем утверждение 2 о том, что добавление ребра в свободноедерево формирует цикл.
Применим доказательство от противного, т.е. предположим,что добавление ребра в свободное дерево не формирует цикл. Итак, после добавлениянового ребра мы получили граф с п вершинами и п ребрами. Этот граф остался связным и, по нашем предположению, ацикличным. Следовательно, этот граф — свободное дерево. Но в таком случае получаем противоречие с утверждением 1. Отсюда вытекает справедливость утверждения 2.Представление неориентированных графовДля представления неориентированных графов можно применять те же методы,что и для представления ориентированных графов, если неориентированное ребромежду вершинами v и w рассматривать как две ориентированных дуги от вершины ик вершине ш и от вершины w к вершине и.Пример 7.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
