Размещено на http://www.allbest.ru/

Донской государственный технический университет

Учебное пособие

для студентов специальности 075200 - "Компьютерная безопасность"

Алгоритмы на графах

Землянухин В.Н.,Землянухина Л.Н.

г. Ростов-на-Дону 2004

УДК 519.17(075.8)

Землянухин В.Н., Землянухина Л.Н. Алгоритмы на графах: Учеб. пособие. Ростов н/Д: Издательский центр ДГТУ, 2004.- 52с.

ISBN

В учебном пособии рассматриваются возможные представления графов в ЭВМ, методы систематического обхода вершин и ребер графа: поиск в ширину и глубину, алгоритмы нахождения некоторых подграфов графа и орграфа, алгоритмы построения остова графа минимальной стоимости (Крускала, Прима), кратчайшие пути в графе (Алгоритмы Дейкстры и Форда - Беллмана), эйлеровы циклы, цикломатическое число графа, фундаментальные циклы и разрезы графа.

Пособие разработано на основе курсов лекций ("Методы программирования", "Алгоритмы, построение и анализ"), читаемых авторами на кафедре "Программное обеспечение вычислительной техники и автоматизированных систем" ДГТУ.

Предназначено для студентов специальности 075200 "Компьютерная безопасность", может быть полезна магистрантам направления 552800 "Информатика и вычислительная техника".

Печатается по решению редакционно-издательского совета Донского государственного технического университета

Научный редактор канд. физ.-мат. наук, доцент Виноградова Г.Ю.

Рецензенты: канд.техн.наук, доцент Е.Н. Остроух; д-р техн. наук, проф. Р.А. Найдорф

Содержание

• Введение
• 1. Основные определения. Возможные представления графов в ЭВМ
• 2. Поиск в графе
• 2.1 Поиск в ширину
• 2.2 Поиск в глубину
• 3. Алгоритмы нахождения некоторых подграфов графа и орграфа
• 3.1 Компоненты связности графа
• 3.2 Точки раздела, мосты, блоки
• 3.3 Сильно связные компоненты орграфа
• 4. Алгоритмы построения остова графа минимальной стоимости
• 4.1 Алгоритм Краскала
• 4.2 Алгоритм Прима
• 5. Кратчайшие пути в графе
• 5.1 Случай неотрицательных весов. Алгоритм Дейкстры
• 5.2 Общий случай. Алгоритм Форда-Беллмана
• 6. Эйлеровы циклы
• 7. Цикломатическое число графа. Фундаментальные циклы и разрезы графа
• Рекомендуемая литература

Введение

Графы встречаются в различных задачах, и алгоритмы обработки графов очень важны. В данном пособии рассматриваются несколько основных алгоритмов на графах, оценивается время обработки графа в зависимости от числа его вершин и ребер (дуг).

Каждая рассматриваемая задача характеризуется размером, задаваемым целочисленными параметрами, определяющими объем входных данных. Например, размерностью задачи о кратчайшем остове является число вершин и число ребер.

Под алгоритмом понимается формально описанная вычислительная процедура, на вход которой подаются исходные данные (аргумент), а на выходе выдается результат. Для записи алгоритма будем использовать упрощенный Паскаль как неформальную версию языка высокого уровня.

Важной характеристикой качества алгоритма решения задачи размером n₁,…,n_k является сложность алгоритма T(n₁,…,n_k) (временная сложность в худшем случае), определяемая как максимальное число действий или шагов выполняемых алгоритмом при решении указанной задачи. При этом, под действием алгоритма понимают выполнение аппаратно реализованных на ЭВМ таких операций, как арифметические, логические, пересылки и т.п. Чтобы не зависеть от вида машинных команд вычисляют порядок роста сложности алгоритма при неограниченном возрастании размера задачи (асимптотическая сложность).

При сравнении скорости роста неотрицательных функций f(n) и g(n) будем говорить, что f(n)=O(g(n)), если существуют константы c>0 и n₀ >0, что f(n)сg(n) при n> n₀ . Также говорят, что f(n)=(g(n)), если существуют константы c>0 и n₀ >0, что f(n)сg(n) при n> n₀ .

Алгоритм называют полиномиальным, если его сложность есть O(n^p) при p>0. При p=1 алгоритм называется линейным. Алгоритм называют экспоненциальным, если его сложность есть (aⁿ) при a>1. В данном пособии рассматриваются только полиномиальные алгоритмы.

Перечислим соглашения и дополнительные операторы, которые будут использоваться при записи алгоритма на упрощенном Паскале:

- оператор цикла for xX do P (для каждого элемента из X выполнить оператор P);

- оператор xy (обмен значениями между x и y);

- операторные скобки begun и end не используются, их заменяет отступ от левого поля, указывающий на уровень вложенности;

- если S =(s₁,…,s_k) стек, то процедура Sx помещает элемент x в стек, т.е. получается список S=(s₁,…,s_k,x);

- если S =(s₁,…,s_k) стек, то процедура xS помещает в x элемент из стека, т.е. получается список S=(s₁,…,s_k-1), а x равно s_k,т.е. значению функции top(S), где top(S) считывает вершину стека;

- если Q =(q₁,…,q_k) очередь, то процедура Qx помещает элемент x в очередь, т.е. получается список Q=(q₁,…,q_k,x);

- если Q =(q₁,…,q_k) очередь, то процедура xQ помещает в x элемент из очереди, т.е. получается список S=(q₂,…,q_k), а x равно q₁;

- при записи алгоритма строки нумеруются.

1. Основные определения. Возможные представления графов в ЭВМ

Пусть X - непустое конечное множество. Обозначим через (X,X) множество неупорядоченных пар элементов из X, т.е.

(X,X) = {(i,j) | i,j X}.

Неориентированным графом (графом) G называется пара множеств (X,U), где U (X,X). Элементы множества X называются вершинами, элементы множества U - ребрами. Пусть число вершин равно n, а число ребер равно m. Если занумеровать вершины графа числами от 1 до n, то получаем помеченный граф с множеством X={1,2,…,n}. Нумерация ребер позволяет рассматривать множество U={u ₁,…,u _m} . При изображении графа на рисунке вершины отражаются кружками или точками, а ребра - линиями.

Две вершины графа i,j называются смежными, если неупорядоченная пара (i,j) есть ребро u. Вершины i и j называют концами этого ребра. Ребро, у которого концевые вершины совпадают, называется петлей. Ребро u и вершина i называются инцидентными, если i является концом ребра u. Два ребра u _i и u _j называются смежными, если они имеют общую концевую вершину.

Степенью d _i вершины i называется число ребер, инцидентных этой вершине. Списком смежности Гi вершины i называется множество всех вершин, смежных с i. Количество элементов множества называют мощностью этого множества и обозначают - |Гi|. Ясно, что |Гi|= d _i .

Лемма 1. Пусть G=(X,U) - произвольный граф с n вершинами и m ребрами. Тогда

.

Следствие. Произвольный граф содержит четное число вершин нечетной степени.

Граф называется полным, если любые две его вершины смежны. Полный граф с n вершинами без петель будем обозначать K_n, число ребер в нем равно .

Граф называется пустым, если в нем нет ребер. Пустой граф с n верши-нами обозначается через O_n .

Для представления графов в ЭВМ используют следующие структуры данных:

- массив ребер;

- матрица смежности или матрица инцидентности;

- списки смежности вершин.

Опишем каждый из этих способов с указанием характеристики v(n,m) - объем памяти для каждого представления.

Для представления графа массивом ребер используется массив структур U : array [1..m] of record i,j: 1..n endrecord, отражающий список пар смежных вершин. Для массива ребер v(n,m)=O(2m).

Для матричного представления используется одна из двух матриц: матрица смежности A или матрица инцидентности B. Матрицей смежности графа G называется бинарная nn матрица A=(a_ij), где a_ij =1, если вершины i и j смежны, т.е. есть ребро (i,j)U, иначе a_ij =0 . Для матрицы смежности A:array[1..n,1..n] of 0..1 характеристика v(n,m)=O(n²). Матрицей инцидентности графа G называется бинарная nm матрица B=(b_ij), где b_ij =1, если вершина i является концом ребра u_j, b_ij =0 в противном случае. Для матрицы инцидентности B:array[1..n,1..m] of 0..1 характеристика v(n,m)=O(nm).

Представление графа в виде списков смежности использует массив указателей Г: array[1..n] of N на списки смежных вершин, где элемент списка представлен структурой N: record v:1..n;r:N. В случае представления неориентированного графа списками смежности v(n,m)=O(n+2m).

На рис.1 показаны различные представления графа G с 5 вершинами и 7 ребрами.

Граф G₁=(X₁,U₁) называется подграфом графа G=(X,U), если X₁ X, U₁ U. Если U₁ содержит все ребра из U, оба конца которых принадлежат X₁, то граф G₁ называется подграфом, порожденным множеством вершин X₁. Если граф G₁ содержит только вершины, инцидентные ребрам из U₁, то он называется подграфом, порожденным множеством ребер U₁.

Маршрутом в графе G=(X,U) называется чередующаяся последовательность вершин и ребер , в которой

.

Маршрут полностью определяется последовательностью вершин , в которой любые две соседние смежны. При этом говорят, что маршрут длины k соединяет вершины .Такой маршрут называют ()-маршрутом.

Если , то маршрут называется замкнутым. Маршрут, в котором все ребра различны, называется цепью. Простая цепь - это цепь, в которой нет повторяющихся вершин. Циклом называется замкнутая цепь. Длина кратчайшей (i,j)-цепи определяет расстояние между вершинами i и j.

Лемма 2. Если в графе G существует маршрут, соединяющий вершины i и j, то существует простая (i,j)-цепь.

Граф называется связным, если любые две вершины можно соединить маршрутом. Компонентой связности графа G называется максимальный по включению (максимальный по числу ребер и вершин) связный подграф.



Рис.1. Представления неориентированного графа: а - неориентированный граф G; б - представление массивом ребер; в - представление матрицей смежности; г - представление матрицей инцидентности; д - представление списками смежности.

Теорема 1. Каждый граф G является объединением своих компонент связности.

Теорема 2. Пусть G - граф с n вершинами, m ребрами, p компонентами связности. Тогда выполняется условие

.

Связный ациклический граф называется деревом. Ациклический граф называется лесом. Каждая компонента такого графа - дерево.

Теорема 3. Для графа с n вершинами и m ребрами следующие условия эквивалентны:

1) G - дерево;

2) G - связный граф и m=n-1;

3) G - ациклический граф и m=n-1;

4) G - граф, в котором любые две вершины соединены единственной простой цепью;

5) G - ациклический граф, а добавление ребра между несмежными вершинами приводит к появлению одного простого цикла.

Следствие. Любое дерево с числом вершин больше 1 имеет по крайне мере две висячие вершины.

Дерево, в котором выделена одна из вершин r, называемая корнем, есть корневое дерево или дерево с корнем r. Пусть j произвольная вершина дерева с корнем r, а i - некоторая вершина (r,j)-цепи. Тогда все вершины (i,j)-цепи называют потомками вершины i или предками вершины j. Подграф дерева, порожденный вершиной i и всеми ее потомками, называется поддеревом с корнем i.

Пусть X - непустое конечное множество. Обозначим через <X,X> множество упорядоченных пар элементов из X, т.е. декартово произведение XX

<X,X> = {(i,j) | i,j X}.

Ориентированным графом (орграфом) G называется пара множеств (X,U), где U <X,X>. Элементы множества X называются вершинами, элементы множества U - дугами. Пусть число вершин равно n, а число дуг равно m. Если занумеровать вершины графа числами от 1 до n, то получаем помеченный орграф с множеством X={1,2,…,n}. Нумерация дуг позволяет рассматривать множество U={u ₁,…,u _m} . При изображении орграфа на рисунке вершины отражаются кружками или точками, а дуги - линиями со стрелками.

Смежность вершин и инцидентность дуги и вершины в орграфе определяются аналогично, как и в графе. Если дуга u=(i,j), то i называют началом, а j - концом дуги u.

Полустепенью исхода d⁺ _i вершины i называется число дуг, имеющих i в качестве начала. Полустепенью захода d _i вершины i называется число дуг, имеющих i в качестве конца. Исходящим списком смежности Г⁺ i вершины i называется множество всех вершин, являющихся концом дуг, имеющих i в качестве начала. Ясно, что число элементов этого множества, т.е. мощность, равна d⁺ _i (| Г⁺ i |= d⁺ _i) . Заходящим списком смежности вершины i называется множество всех вершин, являющихся началом дуг, имеющих i в качестве конца. Ясно, что | |= d _i .

Лемма 3. Пусть G=(X,U) - произвольный орграф с n вершинами и m дугами. Тогда

.

Для орграфа также используют перечисленные выше способы представления в ЭВМ массив ребер.

Представление орграфа массивом дуг аналогично представлению графа.

Для матричного представления используется одна из двух матриц: матрица смежности A или матрица инцидентности B. Матрицей смежности орграфа G называется бинарная nn матрица A=(a_ij), где a_ij =1, если (i,j) U, a_ij =0 в противном случае. Матрицей инцидентности орграфа G называется бинарная nm матрица B=(b_ij), где b_ij =1, если вершина i является началом дуги u_j, b_ij =-1, если вершина i является концом дуги u_j, b_ij =0 в противном случае.

Представление графа в виде списков смежности использует или исходящие списки смежности, или заходящие списки смежности. В случае представления орграфа списками смежности v(n,m)=O(n+m).

На рис.2 показаны различные представления графа G с 5 вершинами и 7 ребрами.

Ориентированным маршрутом (ормаршрутом) в орграфе G=(X,U) называется чередующаяся последовательность вершин и дуг , в которой

.

Ормаршрут полностью определяется последовательностью вершин , в которой любые две соседние вершины соединены дугой . При этом говорят, что ормаршрут имеет длину k и соединяет начальную вершину с конечной .Такой ормаршрут называют ()-ормаршрутом. Если , то ормаршрут называется замкнутым. Ормаршрут, в котором все дуги различны, называется орцепью или путем. Простая орцепь - это орцепь, в которой нет повторяющихся вершин. Орциклом или контуром называется замкнутая орцепь. Длина кратчайшего (i,j)-пути определяет расстояние от вершины i до вершины j.

Лемма 4. Если в графе G существует ормаршрут, соединяющий вершины i и j, то существует простая (i,j)-орцепь.

Говорят, что вершина j достижима из i, если существует (i,j)-ормаршрут.

Компонентой сильной связности графа G называется максимальный по включению (максимальный по числу дуг и вершин) сильно связный подграф.

Замечание. Для орграфа сохраняется понятие маршрута как последовательности вершин и дуг, в которой игнорируется ориентация дуг.



Рис.2. Представления неориентированного графа. (а) Неориентированный граф G. (б) Представление массивом ребер. (в) Представление матрицей смежности. (г) Представление матрицей инцидентности. (д) Представление списками смежности.

Орграф называется сильно связным (орсвязным), если любая его вершина достижима из любой другой.

Связный ациклический орграф называется ордеревом с корне r, если каждая его вершина достижима из r. Ациклический орграф называется орлесом, если каждая его компонента связности есть ордерево с корнем. Пусть i,j произвольные вершины ордерева с корнем r. Тогда все вершины (i,j)-орцепи называют потомками вершины i или предками вершины j. Подграф ордерева, порожденный вершиной i и всеми ее потомками, называется поддеревом с корнем i.

2. Поиск в графе

Основой разработки быстрых алгоритмов на графах служат методы систематического обхода вершин и ребер (дуг) графа (орграфа). В этом разделе излагаются два стандартных и широко используемых метода перебора: поиск в ширину и поиск в глубину.

2.1 Поиск в ширину

Будем рассматривать неориентированный граф G=(X,U). Для описания поиска в ширину будем использовать очередь Q, элементами которой являются вершины графа G и два массива num и ftr . Поиск начинается с некоторой вершины r, которая помещается в очередь и объявляется корнем поиска, что фиксируется в массиве num (num[r]=0) и в массиве ftr (ftr[r]=0). Для остальных вершин ir полагаем num[i]=-1, тем самым подчеркивая, что вершина i еще не находилась в очереди. Пусть теперь очередь не пуста и в начале ее находится вершина i. Все смежные с ней вершины j из множества Гi, которые еще не побывали в очереди (num[j]=-1), помещаем в очередь Q, что и фиксируем в массиве num (num[j]=num[i]+1). А вершину i удаляем из очереди. При этом каждое из ребер (i,j) будем называть древесным, что отмечаем в массиве ftr, полагая ftr[j]=i. В тот момент, когда очередь окажется пустой, и все вершины побывали в очереди (т.е. среди элементов массива num нет отрицательных), поиск в ширину заканчивает свою работу. В противном случае, требуется выбрать новый корень поиска среди не побывавших в очереди вершин (num[i]=-1).

Поиск в ширину реализует описанный ниже алгоритм, в основе которого лежит процедура ПВШ, использующая ранее описанные массивы num и ftr. Кроме того, она вычисляет множество всех древесных ребер U_ПВШ. Это ребра вида . На вход алгоритма подается граф G, заданный списками смежности (для ориентированного графа - это исходящие списки смежности), а на выходе получаем массивы num и ftr .

Алгоритм 1. Поиск в ширину.

Вход: Граф G, представленный списками смежности Г.

Выход: массивы num, ftr.

1. Q:=nil

2. for iX do num[i]:=-1

3. for rX

4. do if num[r]=-1

5. then num[r]:=0

6. ftr[r]:= 0

7. Qr

8. ПВШ(r)

ПВШ(r)

1. while Qnil

2. do i Q

3. for j Г[i]

4. do if num[j]=-1

5. then Q j

6. ftr[j]:=i

7. num[j]:=num[i]+1

Оценим время работы описанного алгоритма. Каждая вершина помещается один раз в очередь и один раз извлекается из очереди. Каждая операция с очередью требует O(1) шагов, и всего на операции с очередью уходит времени O(n) . Список смежности каждой вершины просматривается один раз. Сумма длин всех этих списков равна 2m для неориентированного графа (m для орграфа), т.е. времени на обработку потребуется O(m). Инициализация требует O(n) шагов. Итого получаем O(n+m).

На рис.3 показан пример выполнения алгоритма для неориентированного графа.

Рис.3. Поиск в ширину: а - неориентированный граф; б - дерево ПВШ, массивы num, ftr.

В ходе работы алгоритма выделяется некоторый подграф - дерево поиска в ширину (дерево ПВШ), если исходный граф связный. Если граф G имеет p компонент связности, то алгоритм строит лес, состоящий из p деревьев поиска в ширину. Кроме того, поиск в ширину находит расстояние от корня поиска до каждой из достижимых вершин.

Теорема 4. Пусть G=(X,U) связный граф с n вершинами и m ребрами. Тогда

1) поиск в ширину просматривает каждую вершину в точности один раз;

2) поиск в ширину требует O(n+m) операций;

3) подграф (X,U_ПВШ) графа G является деревом с корнем 1, в котором для каждой вершины i имеется единственная простая (1,i)-цепь, являющаяся кратчайшей (1,i)-цепью длины num[i] в графе G.

Поиск в ширину разбивает вершины по ярусам. В k-ый ярус попадают все вершины i, для которых num[i]=k и (1,i)-цепь в дереве поиска в глубину является кратчайшей в графе G.

На рис.4 приведен пример выполнения алгоритма для орграфа.

Рис.4. Поиск в ширину. (а) Орграф. (б) Дерево ПВШ, массивы num, ftr.

Заметим также, что, применяя алгоритм ПВШ к связному графу из вершины r, можно заменить цикл в строках 2-4 однократным выполнением строк 3,4, подав на вход алгоритма вершину r.

2.2 Поиск в глубину

Будем рассматривать орграф G=(X,U). Поиск в глубину - это систематический обход вершин графа, в результате чего каждая вершина получает номер глубины. Стратегия поиска в глубину состоит в том, чтобы идти "вглубь", пока это возможно (т.е. есть непройденные выходящие дуги), возвращаться и искать другой путь. Так происходит до тех пор, пока не обнаружены все вершины, достижимые из исходной (корень поиска). Поиск в глубину начинается с некоторой вершины r, которая объявляется помеченной и называется корнем поиска, что фиксируется в массиве num и в массиве ftr (num[r]=1, ftr[r]=0). Для остальных вершин ir полагаем num[i]=0, тем самым подчеркивая, что вершина i еще не помечена. Пусть поиск находится в помеченной вершине i и на данный момент помечено k вершин. Тогда возможны следующие случаи:

1) среди вершин jГ⁺i есть непомеченные, т.е. num[j]=0. Тогда, выбрав вершину j, полагаем

num[j]=k+1, k=k+1, ftr[j]=i,

объявляем вершину j помеченной, дугу (i,j) - древесной дугой и просмотренной, поиск в глубину продолжаем из вершины j;

2) все вершины множества Г⁺i помечены. Вершина i объявляется обработанной, и дальнейший поиск зависит от метки ftr[i]. Если ftr[i]0, поиск в глубину продолжается из вершины ftr[i], иначе (ftr[i]=0) необходимо проанализировать наличие непомеченных вершин. Если непомеченных вершин нет, алгоритм окончен. Если непомеченные вершины есть, то выбираем среди них новый корень поиска.

Кроме того, поиск в глубину ставит на вершинах метки времени tn[i] и tk[i] (iX), т.е. момент, когда вершина помечена и когда обработана. Ниже описан алгоритм поиска в глубину для орграфа, заданного исходящими списками смежности. Однако исходный граф может быть и неориентированным, заданным списками смежности. В основе поиска в глубину лежит рекурсивная процедура ПВГ, использующая ранее описанные массивы num, ftr, tn, tk. Кроме того, она вычисляет множество всех древесных ребер U_ПВГ.

Алгоритм 2. Поиск в глубину.

Вход: Граф G, представленный списками смежности Г.

Выход: массивы num, ftr, tn, tk.

1. for iX

2. do num[i]:=0

3. ftr[i]:=0

4. time:=0; k:=1

5. for rX

6. do if num[r]=0

7. then ПВГ(r)

ПВГ(i)

1. time:=time+1; tn[i]:=time

2. num[i]:=k; k:=k+1

3. for j Г[i]

4. do if num[j]=0

5. then ftr[j]:=i

6. ПВГ(j)

7. time:=time+1; tk[i]:=time

Результат применения поиска в глубину к орграфу G показан на рис. 5. Около каждой вершины i указаны три метки: num[i] (tn[i]/tk[i]). Там же изображен граф T=(X,U_T) - дерево поиска в глубину (дерево ПВГ), порожденное древесными дугами

.

Теорема 5. Пусть G - неориентированный граф с n вершинами, m ребрами и p компонентами связности. Тогда

1) поиск в глубину помечает каждую вершину в точности один раз;

2) поиск в глубину требует О(n+m) операций;

3) дерево ПВГ является лесом с p компонентами связности.

Имеют место следующие утверждения.

Лемма 5. Вершина j является потомком вершины i в дереве ПВГ, тогда и только тогда, когда tn[i]<tn[j]<tk[j]<tk[i].

Лемма 6. . Вершина j является потомком вершины i в дереве ПВГ, тогда и только тогда, когда в момент tn[i] (в момент присвоения метки num[i]) существует путь из i в j, проходящий только по непомеченным вершинам.

Рис.5. Поиск в глубину: а - орграф G; б - дерево ПВГ.

В процессе поиска в глубину в орграфе дуги делятся на четыре категории, т.е. все дуги классифицируются и разбиваются на четыре подмножества. Пусть поиск находится в помеченной вершине i. Тогда возможны следующие случаи:

1) среди вершин jГ⁺i есть непомеченные, т.е. num[j]=0. Тогда, выбрав вершину j, полагаем num[j]=k+1, k=k+1, ftr[j]=i, объявляем вершину j помеченной, дугу (i,j) - древесной дугой и просмотренной, поиск в глубину продолжаем из вершины j;

2) все вершины множества Г⁺i помечены, но среди дуг множества (i, Г⁺i) есть непросмотренные. Пусть дуга (i,j) одна из не просмотренных. Анализируем метки num[i] и num[j]. Если num[i] < num[j], то дуга (i,j) классифицируется как прямая дуга (вершина j потомок вершины j). Если num[i] > num[j] и вершина j еще не обработана, то дуга (i,j) классифицируется как обратная дуга (вершина i потомок вершины j). Наконец, если num[i] > num[j] и вершина j обработана, то дуга (i,j) классифицируется как перекрестная дуга (вершины i, j не являются потомками друг друга).

Теорема 6. При поиске в глубину в неориентированном графе любое ребро классифицируется либо как древесное, либо как обратное.

Далее описан алгоритм поиска в глубину для орграфа, который строит множество UT древесных дуг, множество UB обратных дуг, множество UC перекрестных дуг, UF множество прямых дуг.

Алгоритм 3. Поиск в глубину с классификацией дуг (ребер).

Вход: Граф G, представленный списками смежности Г.

Выход: массивы num, ftr, множества UT,UB,UC,UF.

1. UB:=UC:=UF:= UT:=

2. for iX do num[i]:=0; ftr[i]:=0; tk[i]:=0

3. k:=1

4. for rX

5. do if num[r]=0 then ПВГК(r)

ПВГК(i)

1. num[i]:=k; k:=k+1

2. for j Г[i]

3. do if num[j]=0

4. then ftr[j]:=i

5. UT:=UT {(j,i)}

6. ПВГК(j)

7. else if num[j]>num[i]

8. then UF:=UF {(i,j)}

9. else if tk[j]=0

10. then UB:=UB {(i,j)}

11. else UC:=UC {(i,j)}

12. tk[i]:=k

На рисунках 6 и 7 показан результат применения поиска в глубину к графу и орграфу. При этом, древесные дуги изображены жирными линиями, обратные дуги-- пунктирными линиями, а прямые и перекрестные- тонкими линиями. На рисунке 6 множество ребер графа в результате поиска в глубину разбито на два подмножества: UT (древесные) и UB (обратные).

Рис.6. Поиск в глубину с классификацией ребер: а - граф; б - дерево ПВГ.

Рис.7.Поиск в глубину с классификацией дуг: а - орграф; б - дерево ПВГ.

Следующие утверждения можно использовать для анализа орграфа на бесконтурность и графа на ацикличность.

Лемма 7. Орграф не имеет контуров тогда и только тогда, когда поиск в глубину не находит обратных ребер.

Лемма 8. Неориентированный граф не имеет циклов тогда и только тогда, когда поиск в глубину не находит обратных ребер.

3. Алгоритмы нахождения некоторых подграфов графа и орграфа

3.1 Компоненты связности графа

Рассмотрим алгоритм нахождения числа компонент связности произвольного графа G и постоения этих компонент. В основе алгоритма лежит упрощенный поиск в глубину на графе G. Работа алгоритма направлена на формирование массива mrk меток вершин. Каждому элементу mrk[i] присваивается номер той компоненты связности, которой принадлежит вершина i. Сложность алгоритма составляет O(n+m). На вход алгоритма подается граф, заданный списками смежности. На выходе получаем массив mrk и число компонент cnt.

Алгоритм 4. Выделение связных компонент графа.

Вход: Граф G, представленный списками смежности Г.

Выход: число компонент cnt, массив mrk.

1. for iX do mrk[i]:=0

2. cnt:=0

3. for iX

4. do if mrk[i]=0

5. then cnt:=cnt+1

6. CMP(i,cnt)

CMP(i,c)

1. mrk[i]:=c

2. for jГ[i]

3. do if mrk[j]=0

4. then CMP(j,c)

Пример выделения компонент связности графа показан на рис.8.



Рис.8. Разбиение графа на компоненты связности. (а) Граф. (б) Две компоненты связности и массив mrk.

3.2 Точки раздела, мосты, блоки

Разложение графа на блоки имеет практическое значение и важно при изучении надежности коммуникационных и транспортных сетей. Для нахождения блоков применим поиск в глубину.

Пусть G=(X,U) - неориентированный граф. Вершина графа называется точкой раздела (сочленения),если удаление этой вершины из графа вместе с инцидентными ребрами увеличивает число компонент связности. Мостом в графе называется ребро, удаление которого увеличивает число компонент связности. Блоком называется связный граф без точек раздела. Блоком графа, имеющего точки раздела, называется максимальный по включению подграф без точек раздела.

На рис. 9 дан пример графа с точками раздела, мостом и блоками.



Рис. 9. Разложение графа на блоки. (а) Граф. (б) Блоки, точки раздела, мосты.

Теорема 7. Пусть G=(X,U) - связный граф и i X. Тогда следующие утверждения эквивалентны:

1) i - точка раздела;

2) существуют две различные вершины i_1, i₂, такие, что любая их соединяющая цепь содержит вершину i.

Теорема 8. Пусть G=(X,U) связный граф и u U. Тогда следующие утверждения эквивалентны:

1) u - мост;

2) u не принадлежит ни одному простому циклу;

3) существуют две различные вершины i₁, i₂, такие, что любая их соединяющая цепь содержит ребро u.

Теорема 9. Пусть G=(X,U) - связный граф, разбитый на блоки

.

Тогда имеют место следующие утверждения.

1. Ребра блоков образуют разбиение множества U,

.

2. Пересечение любых двух блоков состоит из единственной вершины - точки раздела графа G, т.е. и i - точка раздела.

3. Если для некоторого i, то ребро блока есть мост графа G.

Предположим, что в связном графе G=(X,U) из некоторой вершины r проведен поиск в глубину. Поиск в глубину строит дерево ПВГ T_ПВГ=(X, UТ) с корнем в r, множество обратных ребер UB и массив пит, состоящий из номеров, которые присваиваются вершинам. Получим сначала в терминах дерева ПВГ признак того, что данная вершина является точкой раздела. Подграф дерева ПВГ, порожденный множеством, состоящим из вершины i и всех ее потомков, будем обозначать через T_ПВГ(i) и называть поддеревом ПВГ с корнем i. Будем называть вершины, смежные с i в поддереве T_ПВГ(i), собственными потомками вершины i, а вершину i - собственным предком этих вершин.

Лемма 9. Если ребро (i,j) UB (обратное) и num[i]<num[j]), то j является потомком вершины i и принадлежит T_ПВГ(i), а i является предком вершины j.

Лемма 10. Вершина i r является точкой раздела тогда и только тогда, когда для некоторого собственного потомка j вершины i не существует обратного ребра () такого, что T_ПВГ(j), - предок вершины i (i ).

Лемма 11. Вершина r является точкой раздела тогда и только тогда, когда она имеет не менее двух собственных потомков.

На рис. 10,б показано дерево ПВГ с корнем в вершине 1 графа G (рис 10(а)). Поддерево ПВГ T_ПВГ(3) образовано множеством вершин {3,4,5,6, 7,8}; вершины 4 и 7 - собственные потомки вершины 3, но только для собственного потомка 4 выполнены условия леммы 2. Следовательно, вершина 3 - точка раздела.

Рис.10. Выделение точки раздела; а - граф; б - дерево ПВГ; в - поддерево T_ПВГ(3) .

Итак, в процессе поиска в глубину необходимо уметь выявлять точки раздела. Сформулированные утверждения дают соответствующие критерия, и их необходимо алгоритмизировать. С этой целью введем метку L[i], iX, определив ее как наименьший номер глубины среди вершин, где заканчиваются обратные ребра, обнаруженные в вершинах поддерева T_ПВГ(i), т.е.

.

Например, в графе на рис.10 L[4]=3, L[5]=3, L[6]=3, L[9]=1 и т.д.

Функция L обладает двумя важными свойствами:

1) с ее помощью легко распознавать точки раздела (см. теорему 9);

2) значения этой функции весьма просто и естественно вычисляются при помощи поиска в глубину.

Для вычисления L используем следующие правила:

1) в момент присвоения вершине i номера num[i] определить метку L[i], равную num[i];

2) если в вершине i обнаружено обратное ребро (i,j), то

L[i]:=min(L[i],num[j];

3) если вершина i обработана и ftr[i]0, то

L[ftr[i]]:=min(L[ftr[i]],L[i]).

Имеет место следующее утверждение.

Теорема 10. Вершина i r является точкой раздела тогда и только тогда, когда для некоторого собственного потомка j вершины i L[j]num[i].

Для выделения ребер одного блока используется стек SU, элементами которого являются ребра графа G. В стек последовательно попадают ребра по мере их классификации. Для обнаружения точки раздела достаточно после каждого возвращения в вершину i из собственного предка j сравнить величины L[j] и num[i]. Если окажется, что L[j] num[i], то все ребра стека, начиная с последнего и кончая (i,j), удаляются из стека. Удаляемые ребра и составят блок графа, которые будем помещать в массив ребер с отметкой numBL[k], указывающей номер блока.

Дадим формальное описание алгоритма нахождения блоков и точек раздела и мостов.

Алгоритм 5. Выделение блоков, мостов, точек раздела.

Вход: Граф G, представленный списками смежности Г.

Выход: число блоков cntBL, список ребер U, массив numBL.

1. for iX do num[i]:=0; ftr[i]:=0

2. for i=1 to m do numBL[i]:=0

3. k:=1; kU:=0; SU:=nil; cntBL:=0; U:=nil;

4. for rX

5. do if num[r]=0

6. then BLOCK(r)

BLOCK(i)

1. num[i]:=k; L[i]:=k k:=k+1

2. for jГ[i]

3. do if num[j]=0

4. then SU (i,j)

5. ftr[j]:=i

6. BLOCK(j)

7. L[i]:=min(L[i],L[j])

8. if L[j] num[i]

9. then cntBL:=cntBL+1

10. while Top(SU) (i,j)

11. do u SU ; U u

12. kU:=kU+1

13. numBL[kU]:=cntBL

14. else if j ftr[i]

15. then SU (i,j)

16. L[i]:=min(L[i],num[j])

На рис. 11 иллюстрируется работа описанного алгоритма. Около каждой вершины i указаны две метки num[i]/L[i] .



Рис.11. Выделение блоков графа. (а) Исходный граф. (б) Дерево ПВГ. (в) Состояние стека SU в момент обнаружения точки раздела и блока.

Процедура BLOCK(i) является модификацией процедуры ПВГ(i) из алгоритма 2 В момент завершения работы процедуры BLOCK(i) значение L[i] уже вычислено. Вычисление L[i] производится по правилам 1-3, перечисленным выше. В самом деле, в строке 1 выполняется присваивание L[i] := num[i]. Далее в строке 6 учитываются значения функции L для каждого из собственных потомков вершины i. Наконец, в строке 12 находится минимальное из двух чисел: текущего значения L[i] и num[j], где (i,j) - обратное ребро. Необходимое и достаточное условие для вершины быть точкой раздела, сформулированное в теореме 8, проверяется в строке 7. Разумеется, это условие нельзя применять к корневой вершине. Чтобы узнать, является ли корневая вершина точкой раздела, нужно подсчитать количество собственных потомков этой вершины в дереве ПВГ, что легко сделать с помощью массива numBL и списка ребер U.

Алгоритм выделения блоков выполняется за время O(n+m).

3.3 Сильно связные компоненты орграфа

Многие алгоритмы для орграфов, используют разложение орграфа на сильно связные компоненты и связь между компонентами. Если орграф G=(X,U) состоит из r компонент с вершинами , то можно построить орграф компонент (конденсаций) G* с r вершинами, сопоставив каждой вершине i орграфа G* множество , а множество дуг определить следующим образом: (i,j) - дуга орграфа G*, если существуют вершины , что . Пример орграфа, его сильно связных компонент и его графа компонент дан на рис. 12.

Лемма 12. Орграф конденсаций G* произвольного орграфа G не содержит контуров.

Алгоритм выделения сильно связных компонент орграфа G=(X,U) представляет собой поиск в глубину, который применяется в самом графе G в транспонированном графе G^Т.

Транспонированный орграф получается из G путем изменения направления дуг на противоположное. На рисунке 13 показан результат транспонирования графа G (см. рис.12,а).



Рис.12. Разложение орграфа на сильно связные компоненты. (а) Орграф G. (б) Сильно связные компоненты. (в) Орграф компонент G*.

Рис.13. Транспонированный граф G^Т.

Лемма 13. Если две вершины принадлежат одной сильно связной компоненте орграфа, то любой их соединяющий путь проходит только по вершинам этой компоненты.

Лемма 14 . Пусть G=(X,U) - орграф,



- сильно связные компоненты. Тогда множества вершин образуют разбиение множества X :

.

Пусть - компонента сильной связности opграфа G. Обозначим через r_i такую вершину компоненты , что

.

Пусть - преобразование множества вершин орграфа G, определенное правилом: (j)=tk[r_i ] для любой вершины j X_i . Ясно, что вершины j и l лежат в одной компоненте сильной связности тогда и только тогда, когда (j)= (l). Кроме того, все вершины из X_i принадлежат поддереву ПВШ с корнем в вершине r_{i -} T_ПВГ(r_i) и являются потомками вершины r_i. Функция , рассмотренная на множестве вершин орграфа компонент G^*, обладает следующим свойством.

Лемма 15. Пусть G^* орграф компонент орграфа G. Если в G^* вершина j достижима из вершины i, то (i) >(j).

В орграфе компонент G^* имеется хотя бы одна вершина, степень захода которой равна 0. Такую вершины назовем источником (входом) . Стоком (выходом) назовем вершину, степень исхода которой равна 0.Такая вершина также есть в G^*, т.к. он бесконтурный. Входом (выходом) орграфа G^* =(X^*, U^*) является та вершина, для которой значение максимально (минимально).

На рисунке 14 дан пример дерева ПВГ орграфа G рис.12, функции и орграфа G^* со значениями этой функции на вершинах. Если рассмотреть орграф компонент (G^T)^* транспонированного орграфа G^T, который получается изменением ориентации дуг орграфа G^*, то выходом его является вход орграфа G^*.

Лемма 16. Если i - выход орграфа G^*, то дерево ПВШ с корнем в вершине r_i содержит только вершины сильно связной компоненты .

Используя лемму, можно предложить следующую схему нахождения

сильно связных компонент орграфа.

1. Применить поиск в глубину к орграфу G, построить массив tk.

2. Построить транспонированный орграф G^T, упорядочив его вершины по убыванию tk, т.е. tk[1]>…>tk[n].

3. Применить поиск в глубину к орграфу G^*, построить массив ftr.

4. Число сильно связных компонент равно числу нулевых элементов массива ftr. Сильно связные компоненты определяются деревьями ПВГ, построенными на шаге 3.

Рис.14. Дерево ПВШ орграфа и граф компонент. (а) Дерево ПВШ. (б) Функция и орграф G^*.

Применение поиск в глубину в транспонированном графе позволяет последовательно построить все компоненты сильной связности. Полная иллюстрация описанной схемы для выделения всех сильно связных компонент орграфа G рис.12(а) приведена на рисунках 12-15. На рисунке 14 (а) изображено дерево

Рис.15.Иллюстрация алгоритма. (а) Транспонированный орграф G^T. (б) Дерево ПВШ .

ПВШ орграфа G с указанием массивов (tn/ tk) : tk={16,15,8,7,6,14,13,12}. На рисунке 13 можно увидеть транспонированный орграф G^T,а на рисунке 15(а) - этот же орграф с с упорядоченными вершинами (в каждом кружке указаны через дробь новый и старый номера). Там же (рис.15(б)) изображено его дерево ПВГ, состоящее из трех компонент, вершины которых перечислены рядом с рисунком, каждая из которых и определяет сильно связную компоненту орграфа G (рис.12(в)).

Теперь мы можем привести формальное описание алгоритма для отыскания компонент сильной связности орграфа G. Определим стек S и будем помещать в него вершины орграфа G в том порядке, в каком их просматривает поиск в глубину при обходе G^T, начиная с очередного корня поиска r_i . Если сразу после того, как вершина r_i - обработана, вытолкнуть из стека S все вершины до r_i включительно, мы получим компоненту . При этом вершины j этой компоненты получают метку numSSK[j]=i (номер компоненты).

Алгоритм 6. Выделение сильно связных компонент орграфа.

Вход: Орграф G, представленный исходящими списками смежности List.

Выход: число ССК cntSSK, массив numSSK.

1. for iX

2. do num[i]:=0; ftr[i]:=0

3. Г[i]:=List[i]; tk[i]:=0

4. k:=1; time:=0

5. for rX

6. do if num[r]=0

7. then ПВГ(r)

8. Создать массив New номеров вершин, упорядоченных по убыванию меток tk.

9. Сформировать исходящие списки смежности Г транспонированного орграфа G^T.

10. S:=nil; cnSSK:=0

11. for iX

12. do num[i]:=0

13. numSSK[i]:=0

14. k:=1

15. for rX

16. do if num[r]=0

17. then SSK(r)

18. cntSSK:=cntSSK+1

19. while Snil

20. do jS

21. numSSK[j]:=cntSSK

SSK(i)

1. num[i]:=k; k:=k+1

2. for jГ[i]

3. do if num[j]=0

4. then S j

5. SSK(j)

Заметим, что списки смежности орграфа G^T можно построить за времи O(n+m). Время работы всего алгоритма есть O(n+m).

4. Алгоритмы построения остова графа минимальной стоимости

Пусть дан неориентированный граф G=(X,U) с p компонентами связности, на ребрах которого задана весовая неотрицательная функция c: UR⁺. Остовом графа называется ациклический подграф T=(X,U_T),число компонентами связности которого равно p. Если граф G связный, то остов - это дерево, иначе остовом является лес. Остов графа легко найти поиском в глубину или поиском в ширину. Поскольку оба поиска имеют сложность O(m + n) и в связном графе m ? n - 1, остов связного графа можно найти за время O(m). Число остовов можно определить, воспользовавшись следующей теоремой.

Теорема Кирхгофа. Число остовов в связном графе G равно алгебраическому дополнению любого элемента матрицы Кирхгофа H(G)=D-A, где A - матрица смежности графа, D - квадратная диагональная матрица порядка n, на диагонали которой стоят степени вершин.

Следствие. Число остовов полного графа равно n^n-2.

Определим вес остова T как сумму весов ребер остова, т.е.

.

Задача о минимальном остове состоит в нахождении остова графа G минимального веса, который будем называть минимальным остовом.

Рассмотрим два способа решения задачи: алгоритм Краскала и алгоритм Прима. Было бы нерационально решать задачу, опираясь на перебор всех остовов, т.к. число остовов в полном графе экспоненциально зависит от n.

4.1 Алгоритм Краскала

Пусть G=(X,U) исходный граф с n вершинами, m ребрами, p компонентами связности и T₀=(X,U₀) пустой остовный подграф графа G. Алгоритм Краскала строит последовательность остовных ациклических подграфов

T₀=(X, U₀), T₁=(X,U₁),T₂=(X,U₂),…, T_n-p=(X,U_n-p).

При этом подграф T_i получается из T_i-1 путем добавления ребра, которое не нарушает ацикличность. Добавление ребра приводит к изменению числа компонент связности, т.е. две компоненты подграфа T_i-1 объединяются в одну компоненту подграфа T_i . Результат такого последовательного добавления ребер зависит от порядка рассмотрения ребер.

Теорема 11. Если ребра графа упорядочены по возрастанию их весов, то подграф T_n-p=(X,U_n-p) является минимальным остовом графа G.

Одной из основных операций в алгоритме Краскала является операция слияния деревьев (компонент связности остовных подграфов). Для эффективной организации этого процесса будем использовать структурные деревья с корнем на множестве вершин одной компоненты связности и массив ftr. Будем говорить, что на множестве X₁ связного графа G задано структурное дерево с корнем ST(r), если одна из вершин r X₁ объявлена корнем (ftr[r]=r), а остальные разбиты по ярусам. Вершинам i первого яруса приписаны метки ftr[i]=r, каждая вершина i второго яруса имеет метку ftr[i]= j, где j какая-либо вершина первого яруса, и т.п. Заметим, что если в структурном дереве только один ярус, то метки всех вершин совпадают. Опишем операцию слияния двух структурных деревьев ST₁(r₁) и ST₂(r₂), представляющих связные подграфы G₁=(X₁,U₁) и G₂=(X₂,U₂) графа G (X₁?X₂= ). Пусть (i,j) ребро графа G такое, что iX₁ j X₂ . Тогда связный подграф G₃= G₁G₂+(i,j) будет представлен ST₃(r₁), полученным переподчинением корня r₂ корню r₁ (ftr[r₂]=r₁). Важной характеристикой структурного дерева является число его ярусов. Определим для каждой вершины i ранг как число ярусов в поддереве ПВГ с корнем i. Отметим ряд свойств ранга.

Рис.16. Слияние структурных деревьев. (а) Подграфы G₁ и G₂. (б) Структурные деревья ST₁(3) и ST₂(6). (в) Результат слияния.

Лемма 17. В структурном дереве с n вершинами ранг любой вершины не превосходит log n. Число вершин ранга s не превосходит . Ранг любой вершины ir меньше ранга вершины ftr[i].

Информацию о ранге вершины i будем отражать в метке rnk[i]. Если вершина i единственная в структурном дереве, то rnk[i]=0. При слиянии может измениться только ранг корня. Заметим, что в процессе слияния значение этой метки может оказаться равным верхней оценке числа ярусов. При слиянии будем давать предпочтение корню с большим значением этой метки. На рисунке 16 дана иллюстрация операции слияния двух структурных деревьев ST₁(3) и ST₂(6) подграфов G₁=(X₁,U₁) и G₂=(X₁,U₁) при добавлении ребра (4,6). Около каждой вершины i деревьев указаны ftr[i]/rnk[i].

Дадим формальное описание алгоритма. Рекурсивная процедура Find(i) возвращает корень структурного дерева, которому принадлежит вершина i, кроме того, она перестраивает дерево, изменив ftr[j] на номер корня, для тех вер шин, которые были обнаружены в процессе поиска корня. Процедура Union(r₁,r₂) объединяет структурные деревья с корнями r₁,r₂ .

Алгоритм 7. Построение минимального остова. Алгоритм Краскала.

Вход: Граф G, заданный списком ребер U и их весов.

Выход: Список ребер UT минимального остова.

1. UT:=nil

2. for iX do do ftr[i]:=i; rnk[i]:=0

3. упорядочить ребра по весам

4. for (i,j)U

5. do if Find(i)Find(j)

6. then UT (i,j)

7. Union(Find(i),Find(j))

Find(i)

1. if iftr[i]

2. then ftr[i]:=Find(ftr[i])

3. RETURN ftr[i]

Union(r,s)

1. if rnk[r] rnk[s]

2. then ftr[s]:=r

3. if rnk[r]=rnk[s] then rnk[r]:=rnk[r]+1

4. else ftr[r]:=s

Теорема 12. Для связного графа G с n вершинами и m ребрами вычислительная сложность алгоритма 5 равна O(m log n).

На рисунке 17 показан граф G с весами ребер (числа рядом с ребрами) и его минимальный остов. После упорядочения ребра рассматриваются в следующем порядке: U={(1,2),(1,4),(2,4),(3,5),(3,6),(5,6),(2,3),(2,5),(4,5)}. В таблице указан порядок, в котором строился остов.

Рис.17. Построение минимального остова. Алгоритм Краскала.(а) Граф G с весами ребер. (б) Минимальный остов графа G.

Иллюстрация работы алгоритма Краскала

Итерация	(i,j)		UT
0		1/0, 2/0, 3/0, 4/0, 5/0, 6/0, 7/0
1	(1,2)	1/1, 1/0, 3/0, 4/0, 5/0, 6/0, 7/0	(1,2)
2	(1,4)	1/1, 1/0, 3/0, 1/0, 5/0, 6/0, 7/0	(1,2) (1,4)
4	(3,5)	1/1, 1/0, 3/1, 1/0, 3/0, 6/0, 7/0	(1,2) (1,4) (3,5)
5	(3,6)	1/1, 1/0, 3/2, 1/0, 3/0, 3/0, 7/0	(1,2) (1,4) (3,5) (3,6)
7	(2,3)	3/1, 1/0, 3/2, 1/0, 3/0, 3/0, 7/0	(1,2) (1,4) (3,5) (3,6) (2,3)
10	(4,7)	3/1, 1/0, 3/2, 3/0, 3/0, 3/0, 3/0	(1,2) (1,4) (3,5) (3,6) (2,3) (4,7)

4.2 Алгоритм Прима

Перейдем к рассмотрению алгоритма Прима, основанного на применении следующей стратегии. Пусть исходный граф G связный. Тогда строится последовательность связных ациклических подграфов

T₀=(X₀, U₀), T₁=(X₁,U₁),T₂=(X₂,U₂),…, T_n-1=(X_n-1,U_n-1).

При этом подграф T_i получается из T_i-1 путем добавления некоторой вершины k X_i-1 и ребра (j,k)U, где jX_i-1 . Ясно, что X_n-1=X . Результат такой стратегии зависит от порядка рассмотрения ребер.

Теорема 13. Если для каждого i0 добавляемое ребро удовлетворяет условию

,

то подграф T_n-1=(X,U_n-1) является минимальным остовом графа G.

Если исходный граф несвязный, то стратегия применяется к каждой его компоненте связности. Для организации эффективного выбора вершины k и ребра (j,k) используются два массива: ftr[i] и key[i]. Пусть TP=(XP,UP) - произвольное дерево из последовательности