§ 27. Сильно связный граф. Разложение на максимальные сильно связные подграфы. Транзитивное замыкание и пересчет путей

Транзитивное замыкание. Пусть задан граф

Определим многозначные отображения по формулам

а обратные многозначные отображения — по формулам

Например, для графа на рис. 92 имеем

Читателю предлагается продолжить дальше и выписать обратные преобразования.

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

Рис. 92

Транзитивным замыканием называется многозначное отображение, определяемое формулой

Другими словами является множеством вершин, в которые можно прийти из по некоторому пути.

Аналогично определяется обратное транзитивное замыкание:

т. е. множество вершин, из которых попадают в некоторому пути.

Например (рис. 92),

Предоставим читателю в качестве упражнения найти соответствующие

Сильно связный граф. Граф называют сильно связным, если

т. е. для любых двух вершин такого графа существует путь, идущий из Граф на рис. 93 сильно связный, а граф на рис. 92 не является таковым.

Легко показать, что (27.10) эквивалентно условию

Рис. 93.

Бинарное отношение «существует путь из является отношением частичного порядка на множестве вершин так как оно транзитивно и рефлексивно. Бинарное отношение «существует путь из и путь из отношение эквивалентности так как оно, кроме того, симметрично.

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

Пример. Максимальные сильно связные подграфы графа на рис. 95 обведены пунктиром.

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

Пример. Рассмотрим граф на рис. 94. Из его представления на рис. 95 видно, что состоит из шести классов.

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

то следовало бы объединить в один класс, что противоречит их максимальности.

Пример. Рис. 96 показывает, как можно упорядочить из рис. 95. Этот порядок, очевидно, частичный.

Рис. 94.

Рис. 95.

Метод разложения графа на максимальные сильно связные подграфы. Если класс, содержащий то

Метод состоит в следующем. Берем произвольную вершину и находим и Затем берем вершину и действуем аналогично. Продолжаем процесс до тех пор, пока это возможно.

Рис. 96.

Пример. Рассмотрим представление графа на рис. 94 в виде булевой матрицы (см. рис. 97, нули опущены). Справа от матрицы поместим столбец, а внизу — строку, которые будем заполнять следующим образом. В клетку столбца напротив строки А ставим нуль. В клетку столбца напротив строки ставим 1, так как строка А содержит 1 на месте Строка матрицы содержит 1 на месте К, поэтому напротив К помещаем 2 (это показывает, что кратчайший путь из длины 2). Строка К матрицы содержит 1 на местах Ставим 3 напротив (клетки напротив уже заполнены). В строке

Е на месте стоит 1 и напротив ставим 4. В строке стоит на местах Клетка напротив уже заполнена, и мы ставим 4 напротив Я. Рассмотрение строк приводит к уже заполненным клеткам. В оставшиеся клетки столбца ставим «X». Числа в клетках этого столбца — длины кратчайших путей из А в соответствующие вершины; «X» означает, что пути не существует. Таким образом,

Аналогично действуем для получения но при этом меняем ролями строки и столбцы матрицы.

Рис. 97.

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

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

Удаляя из графа на рис. 98 вершины получаем граф, представленный на рис. 99.

Рис. 98.

Рис. 99.

Рис. 100.

Для произвольной его вершины, например С, получаем

Продолжая, легко находим (рис. 100)

Таким образом, приходим к шести классам, показанным на рис. 95.

Существование и пересчет путей. Путь положительной длины из существует, если

Если рассматривать пути длины нуль, то (27.23) можно записать так:

Булева матрица графа показывает, какие существуют пути длины 1. Пусть

тогда

где + означает булево сложение.

Рис. 101.

Если

то матрица показывает, какие вершины в графе связаны путями.

Пример (рис. 101). Рассмотрим матрицу изображенную на рис. 102.

Рис. 102.

Рис. 103.

Матрица (рис. 103) показывает, какие существуют пути длины 2. Замечаем, что (см. рис. 104, 105). Следовательно, показывает, какие вершины в графе связаны путями,

Чтобы пересчитать различные пути длины рассмотрим степени булевой матрицы

Рис. 104.

Рис. 105.

Рис. 106.

Рис. 107.

Пример (рис. 101). Матрицы на рис. 106—109 дают число путей длин соответственно 1, 2, 3, 4 в графе. Видим, что имеется

пять путей длины 3 от В к девять путей длины 4 от В к

Рис. 108.

Рис. 109.

УПРАЖНЕНИЯ

(см. скан)

(см. скан)