Федоров В.Н. - Введение в теорию графов, страница 8

где – множество вершин графа, достижимых из x_i за один шаг,

– множество вершин графа, достижимых из x_i за два шага и т. д.

– это не что иное, как объединение вершины x_i со множеством ее потомков.

Определим обратное транзитивное замыкание в графе для вершины x_i

,

где – множество вершин графа, из которых x_i достижима за один шаг,

– множество вершин графа, из которых x_i достижима за два шага и т.д.

– это не что иное, как объединение вершины x_i со множеством ее предков.

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

Поэтому для компонент сильной связности справедливо

,

где Cx_i – класс эквивалентности.

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

Формальными признаками наличия таких вершин являются:

• для источников – отсутствие 1 в столбце матрицы смежности,

• для тупиковых вершин – отсутствие 1 в строке матрицы смежности,

• для изолированных вершин – отсутствие 1 как в строке, так и в столбце матрицы смежности.

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

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

Алгоритм определения компонент сильной связности орграфа

1. Удалить из графа вершины источники, тупиковые и изолированные вершины, зафиксировав их как отдельные сильные компоненты.

2. Выбрать некоторую вершину x_i.

3. Определить для x_i .

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

5. Удалить из графа вершины, принадлежащие и инцидентные им дуги. Если получен подграф G’, то перейти к п. 2. Если граф пуст, то перейти к п. 6.

6. Сформировать множество классов C.

Для определения получим степени строки x_i матрицы смежности A, а для определения степени столбца x_i . Максимальный показатель степени n–1, так как учитываются только кратчайшие маршруты. Затем объединим полученные строки (степени строки x_i) со строкой, имеющей единственную 1 в позиции вершины x_i, а полученные столбцы (степени столбца x_i) объединим со столбцом, имеющим единственную 1 в позиции вершины x_i.

определяется как множество вершин, имеющих 1 в полученной матрице строке. определяется как множество вершин, имеющих 1 в полученной матрице столбце.

Пример. Дан граф рис. 9.1.

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

Анализируя граф, находим, что вершина 5 тупиковая. Удалив ее, обнаруживаем, что появилась новая тупиковая вершина 4.

После удаления вершины 4 получаем граф на трех вершинах, для которого матрица смежности равна

A
= .

Выберем вершину 1.

Для этой вершины Г₁ = – первая строка матрицы смежности.

Для получения возводим строку вершины 1 матрицы A во вторую степень, т.е. умножаем строку вершины 1 на матрицу A

= * = .

Поскольку после удаления вершин 4 и 5 в графе осталось только три вершины, то вторая степень – это предел.

Объединим Г₁, со строкой , представляющей вершину 1.

Получаем

= {1} Г₁ = = .

В другом представлении = {1, 2, 3}.

Теперь определим .

= . = * = . {1} = .

= {1} = = .

В другом представлении = {1, 2, 3}.

Таким образом

= {1, 2, 3} и = {1, 2, 3}.

Следовательно,

= {1, 2, 3} {1, 2, 3} = {1, 2, 3}.

Так как ранее были исключены тупиковые вершины 5 и 4, каждая из которых образует свой класс сильной связности, то все классы сильной связности будут такими {1, 2, 3}, {4}, {5}.

9.2. Определение компонент связности

Если для любой вершины x_i выполняется условие

,

то граф сильно связен.

Поскольку связный неорграф всегда сильно связен, то полученный алгоритм определения компонент сильной связности пригоден и для определения компонент связности неорграфов: Каждая компонента неорграфа сильно связана, а между компонентами связи нет.

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

Пример. Дан граф рис. 9.2, для которого имеем

A = .

В
графе изолированных вершин нет, поэтому исключать ничего не надо.

Выберем вершину 1.

В графе 6 вершин, поэтому для определения и нужно возводить первую строку и первый столбец матрицы смежности в степени с первой по пятую.

Возводим в степень первую строку матрицы A (сложение и умножение элементов булевские)

Первая строка матрицы смежности

= .

Вторая степень первой строки матрицы смежности

= * = .

Третья степень первой строки матрицы смежности

= * = .

При возведении в третью степень получено повторение строки, возводимой в степень, поэтому операцию возведения в степень прекращаем.

Если продолжить возведение в степень, то результат будет повторяться.

Найдем .

= {1} =

= = .

В других обозначениях

= {1, 3, 5}.

Определим .

= . = * = .

= * = .

Результат совпадает с начальным значением, следовательно, возведение в степень надо прекратить.

Найдем

= {1} = = .

В других обозначениях

= {1, 3, 5}.

= {1, 3, 5} {1, 3, 5} = {1, 3, 5}.

Вершины 1, 3, 5 принадлежат отдельной компоненте связности, поэтому на дальнейший процесс поиска других компонент связности влиять не будут. для уменьшения объема вычислений эти вершины, вместе с инцидентными им ребрами, можно исключить. Рассматриваемый пример достаточно простой, поэтому исключать ничего не будем.

Возьмем вершину, не принадлежащую , например, 4.

Действуя аналогично, находим

= .

= * = .

= * = .

Получено повторение строки, возводимой в степень, поэтому операцию возведения прекращаем.

Найдем .

= {4} =

= = .

В других обозначениях

= {2, 4, 6}.

Определим .

= . = * = .

= * = .

Результат совпадает с начальным значением, следовательно, возведение в степень надо прекратить.

Найдем

= {4} = = .

В других обозначениях

= {2, 4, 6}.

= {2, 4, 6} {2, 4, 6} = {2, 4, 6}.

Таким образом, все вершины графа вошли в два класса – в две компоненты связности C₁ = {1, 3, 5} и C₄ = {2, 4, 6}.

9.3. Контрольные вопросы

1. Поясните понятия сильная связность, слабая связность, просто связность? (Для подготовки ответа см. также раздел 1.)

2. Чем отличается компонента связности от компоненты сильной связности?

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

4. Почему при определении компонент сильной связности орграфа еще на этапе анализа можно исключить изолированные, тупиковые вершины и вершины источники?

5. Почему алгоритм определения компонент сильной связности орграфа можно применить для нахождения компонент связности неорграфа?

6. Как можно определить компоненты связности орграфа?

10. Фундаментальные циклы и разрезы графа

10.1. Остов графа

Остов – минимальное множество ребер, которые связывают все вершины связного графа.

Остов это дерево.

Часть G' графа G называется остовом (каркасом, скелетом), если V’ = V и все они связаны без циклов. Остов обычно обозначают буквой T.

Для орграфов остов – часть G, которая является остовом в неорграфе, полученном из G удалением ориентации дуг.

Остов получается из графа разрушением циклов. Число удаляемых при этом ребер: (G) = m – n + 1 – называется цикломатическим числом или цикломатическим рангом графа (или просто рангом графа).

Если граф состоит из нескольких компонент, то его остов лес, а число удаляемых при определении остова ребер будет равно

(G) = m – n + ρ,

где ρ – количество компонент связности графа.

Количеств ребер в остове графа

*(G) = n – ρ

называется коциклическим рангом.

(У связного графа *(G) = n – 1.)

Для дерева цикломатическое число равно 0.

10.2. Нахождение остова минимальной длины

Имеется связный граф G(V, E).

1. Строим начальный остов T_i , который состоит из всех вершин и одного ребра с минимальным весом.

2. Имеем T_i, среди всех ребер находим ребро с минимальным весом такое, которое смежно с одним из ребер из T_i и которое не образует циклов. Добавляем его к T_i .

3. Повторяем п. 2, пока находятся нужные ребра.

10.3. Фундаментальные циклы

Фундаментальным циклом графа G(V,E) с остовным деревом T(V,E') называется простой цикл, получаемый в результате добавления к T одного из ребер G, не принадлежащего E'. Количество фундаментальных циклов графа G = (V,E) при любом остовном дереве T равно цикломатическому числу (G).

Пусть G(V, E) связный неорграф с n вершинами и m ребрами, T – остов графа, имеющий n – 1 ребро, которые называются ветвями T (ведь остов – это дерево) и обозначаются b_j.

Не входящие в остов (G) = m – n + 1 ребер называются хордами и обозначаются h_i.