Структуры данных и алгоритмы (1021739), страница 55
Текст из файла (страница 55)
7.8,а, полученное методом поиска в ширинуВремя выполнения алгоритма поиска в ширину такое же, как и для алгоритмапоиска в глубину. Каждая пройденная вершина помещается в очередь только одинраз, поэтому количество выполнений цикла while совпадает с количеством просмотренных вершин. Каждое ребро (х, у) просматривается дважды, один раз для вершины х и один раз для вершины у. Поэтому, если граф имеет п вершин и е ребер, атакже если для представления ребер используются списки смежности, общее времяобхода такого графа составит О(тах(л, е)). Поскольку обычно е > п, то получаем время выполнения алгоритма поиска в ширину порядка О(е), т.е. такое же, как и дляалгоритма поиска в глубину.7.3. ОБХОД НЕОРИЕНТИРОВАННЫХ ГРАФОВ219Методы поисков в глубину и в ширину часто используются как оснрва при разработке различных эффективных алгоритмов работы с графами.
Например, оба этихметода можно применить для нахождения связных компонент графа, посколькусвязные компоненты представимы отдельными деревьями в остовном лесу графа.Метод поиска в ширину можно использовать для обнаружения циклов в произвольном графе, причем за время О(п) (п — количество вершин графа), которое не зависит от количества ребер. Как показано в разделе 7.1, граф с п вершинами и с пили большим количеством ребер обязательно имеет цикл. Однако если в графе п - 1или меньше ребер, то цикл может быть только в том случае, когда граф состоит издвух или более связных компонент.
Один из способов нахождения циклов состоит впостроении остовного леса методом поиска в ширину. Тогда каждое поперечное ребро(v, w) замыкает простой цикл, состоящий из ребер дерева, ведущих к вершинам v иw от общего предка этих вершин, как показано на рис. 7.10.Корень1Рис. 7.10. Цикл, найденный методом поиска в ширину''•7.4. Точки сочленения и двусвязные компонентыТочкой сочленения графа называется такая вершина v, когда при удалении этой вершины и всех ребер, инцидентных вершине v, связная компонента графа разбивается надве или несколько частей.
Например, точками сочленения для графа из рис. 7.8,а являются вершины а и с. Если удалить вершину а, то граф, который является одной связнойкомпонентой, разбивается на два "треугольника" {b, d, e} и {с, /, g}. Если удалить вершинус, то граф расчленяется на подграфы {a, b, d, e) и {/, g}. Но если удалить какую-либо другую вершину, то в этом случае не удастся разбить связную компоненту на несколько частей. Связный граф, не имеющий точек сочленения, называется двусвязным. Для нахождения двусвязных компонент графа часто используется метод поиска в глубину.Метод нахождения точек сочленения часто применяется для решения важнойпроблемы, касающейся k-связности графов. Граф называется k-связным, если удаление любых k - 1 вершин не приведет к расчленению графа.1 В частности, граф имеетсвязность 2 или выше тогда и только тогда, когда он не имеет точек сочленения, т.е.только тогда, когда он является двусвязным.
Чем выше связность графа, тем большеможно удалить вершин из этого графа, не нарушая его целостности, т.е. не разбиваяего на отдельные компоненты.1Существует другое, более конструктивное определение fe-связности. Граф называется kсвязным, если между любой парой вершин v и w существует не менее k разных путей, таких,что, за исключением вершин и и w, ни одна из вершин, входящих в один путь, не входит ни вкакой другой из этих путей. — Прим. ред.220ГЛАВА 7.
НЕОРИЕНТИРОВАННЫЕ ГРАФЫОпишем простой алгоритм нахождения всех точек сочленения связного графа, основанный на методе поиска в глубину. При отсутствии этих точек граф, естественно,будет двусвязным, т.е. этот алгоритм можно рассматривать так же, как тест на двусвязность неориентированного графа.1.Выполняется обход графа методом поиска в глубину, при этом для всех вершинv вычисляются числа dfnumber[v], введенные в разделе 6.5.
В сущности, этичисла фиксируют последовательность обхода вершин в прямом порядке вершинглубинного остовного дерева.2. Для каждой вершины v вычисляется число low[v], равное минимуму чиселdfnumber потомков вершины i», включая и саму вершину v, и предков w вершины v, для которых существует обратное ребро (х. w), где х — потомок вершиныv. Числа low[v] для всех вершин v вычисляются при обходе остовного дерева вобратном порядке, поэтому при вычислении low\y] для вершины v уже подсчитаны числа low[x] для всех потомков х вершины v. Следовательно, low[v] вычисляется как минимум следующих чисел:а) dfnumber[y];б) dfnumber[z] всех вершин г, для которых существует обратное ребро (u, z);в) low[x] всех потомков х вершины v.3.
Теперь точки сочленения определяются следующим образом:а) корень остовного дерева будет точкой сочленения тогда и только тогда, когдаон имеет двух или более сыновей. Так как в остовном дереве, которое получено методом поиска вглубь, нет поперечных ребер, то удаление такого корнярасчленит остовное дерево на отдельные поддеревья с корнями, являющимисясыновьями корня построенного остовного дерева;б) вершина v, отличная от корня, будет точкой сочленения тогда и только тогда,когда имеет такого сына w, что low[w] > dfnumber[v]. В этом случае удалениевершины v (и, конечно, всех инцидентных ей ребер) отделит вершину w ивсех ее потомков от остальной части графа.
Если же low[w\ < dfnumberfv], тосуществует путь по ребрам дерева к потомкам вершины w и обратное ребро откакого-нибудь из этих потомков к истинному предку вершины v (именно значению dfnumber для этого предка равно low[w]). Поэтому в данном случаеудаление вершины v не отделит от графа поддерево с корнем w.Пример 7.8. Числа dfnumber и low, подсчитанные для вершин графа из рис. 7.8,а,показаны на рис. 7.11. В этом примере вычисление чисел low начато в обратном порядке с вершины е. Из этой вершины выходят обратные ребра (е, а) и (е, Ь), поэтомуlow[e] = min(dfnumber[e], dfnumber[a], dfnumber[b]) = 1.
Затем рассматривается вершина d, для нее low[d] находится как минимум чисел dfnumber[d], low[e] и dfnumber[a].Здесь число low[e] участвует потому, что вершина е является сыном вершины d, а число dfnumber[a] — из-за того, что существует обратное ребро (d, a).Для определения точек сочленения после вычисления всех чисел low просматривается каждая вершина остовного дерева. Корень а является точкой сочленения, таккак имеет двух сыновей. Вершина с также является точкой сочленения — для еесына, вершины f, выполняется неравенство low[f] > dfnumber[c]. Другие вершины неявляются точками сочленения.
ПВремя выполнения описанного алгоритма на графе с п вершинами и е ребрамиимеет порядок О(е). Читатель легко проверит, что время, затрачиваемое на выполнение каждого этапа алгоритма, зависит или от количества посещаемых вершин, илиот количества ребер, инцидентных этим вершинам, т.е. в любом случае время выполнения, с точностью до константы пропорциональности, является функцией какколичества вершин, так и количества ребер.
Поэтому общее время выполнения алгоритма имеет порядок О(п + е) или О(е), что то же самое при п < е.7.4. ТОЧКИ СОЧЛЕНЕНИЯ И ДВУСВЯЗНЫЕ КОМПОНЕНТЫ221dl'number[a] = 1low [a] = 1d1 'number [b] = 2dfnumber [c] = 5low [o] - 5dfnumber [d] = 3low [d] = 1dfnumber [f\ =low(f\ = 5dfnumber [e] = 4low [e] = 1dfnumber [g] = 7low [g] = 5Рис. 7.11. Числа dfnumber и low, подсчитанные для графа изрис. 7.8.а7.5. Паросочетания графовВ этом разделе мы опишем алгоритм решения "задачи о паросочетании" графов.Простым примером, приводящим к такой задаче, может служить ситуация распределения преподавателей по множеству учебных курсов.
Надо назначить на чтение каждого курса преподавателя определенной квалификации так, чтобы ни на какойкурс не было-назначено более одного преподавателя. С другой стороны, желательноиспользовать максимально возможное количество преподавателей из их состава.Рис. 7.12.
Двудольный графОписанную ситуацию можно представить в виде графа, показанного на рис. 7.12,где все вершины разбиты на два множества Ft и V2 так, что вершины из множества YIсоответствуют преподавателям, а вершины из множества V2 — учебным курсам. Тотфакт, что преподаватель и может вести курс w, отражается посредством ребра (v, w).Граф, у которого множество вершин распадается на два непересекающихся подмноже222ГЛАВА 7. НЕОРИЕНТИРОВАННЫЕ ГРАФЫства FI и V2 таких, что каждое ребро графа имеет один конец из Vlt а другой — из V2,называется двудольным.
Таким образом, задача распределения преподавателей поучебным курсам сводится к задаче выбора определенных ребер в двудольном графе,имеющем множество вершин-преподавателей и множество вершин-учебных курсов.Задачу паросочетания можно сформулировать следующим образом. Есть графG = (V, Е). Подмножество его ребер, такое что никакие два ребра из этого подмножества не инциденты какой-либо одной вершине из V, называется паросочетанием. Задача определения максимального подмножества таких ребер называется задачей нахождения максимального паросочетания. Ребра, выделенные толстыми линиями нарис. 7.12, составляют одно возможное максимальное паросочетание для этого графа.Полным паросочетанием называется паросочетание, в котором участвуют (в качестве концов ребер) все вершины графа. Очевидно, что любое полное паросочетание является также максимальным паросочетанием.Существуют прямые способы нахождения максимальных паросочетаний.
Например, можно последовательно генерировать все возможные паросочетания, а затем выбрать то, которое содержит максимальное количество ребер. Но такой подход имеетсущественный недостаток — время его выполнения является экспоненциальнойфункцией от числа вершин.а. Паросочетание,б. Чередующаяся цепьРис. 7.13. Паросочетание и чередующаяся цепьВ настоящее время разработаны более эффективные алгоритмы нахождения максимальных паросочетаний. Эти алгоритмы используют в основном метод, известныйкак "чередующиеся цепи".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
