Тема 14.1. Граф достижимости

Один из первых вопросов, возникающих при изучении графов, это вопрос о существовании путей между заданными или всеми парами вершин. Ответом на этот вопрос – введённое выше отношение достижимости на вершинах графа вершина достижима из вершины , если или в есть путь из в . Иначе говоря, отношение достижимости является рефлексивным и транзитивным замыканием отношения . Для неориентированных графов это отношение также симметрично и, следовательно, является отношением эквивалентности на множестве вершин . В неориентированном графе классы эквивалентности по отношению достижимости называются связными компонентами. Для ориентированных графов достижимость, вообще говоря, не должна быть симметричным отношением. Симметричной является взаимная достижимость.

Определение: Вершины и ориентированного графа называются взаимно достижимыми, если в есть путь из в и путь из в .

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

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

Определение: Пусть – ориентированный граф. Граф достижимости для имеет тоже множество вершин и следующее множество рёбер в графе вершина достижима из вершины .

Пример 14.1: Рассмотрим граф.

Тогда можно проверить, что граф достижимости для выглядит так (новые рёбра – петли для каждой из вершин не показаны):

Каким образом по графу можно построить граф ? Один способ заключается в том, чтобы для каждой вершины графа определить множество достижимых из неё вершин, последовательно добавляя в него вершины, достижимые из неё путями длины 0, 1, 2 и т.д.

Мы рассмотрим другой способ, основанный на использовании матрицы смежности графа и булевых операций.

Ниже для сохранения сходства с обычными операциями над матрицами мы будем использовать «арифметические» обозначения для булевых операций: через «+» будем обозначать дизъюнкцию , а через «*» конъюнкцию .

Обозначим через единичную матрицу размера , а - матрицу смежности заданного графа. Положим . Пусть , ,…, . Наша процедура построения основана на следующем утверждении.

Лемма. Пусть Тогда

Доказательство проведём индукцией по .

Базис. При и утверждение справедливо по определению.

Индукционный шаг. Пусть лемма справедлива для . Покажем, что она остаётся справедливой и для . По определению имеем:

Предположим, что в графе из в имеется путь длины . Рассмотрим кратчайший из таких путей. Если его длина , то по предположению индукции . Кроме того, . Поэтому и . Если длина кратчайшего пути из в равна , то пусть - его предпоследняя вершина. Тогда из в имеется путь длины и по предположению индукции . Так как , то . Поэтому и .

Обратно, если , то хотя бы для одного слагаемое в сумме равно 1. Если это , то и по индуктивному предположению в имеется путь из в длины . Если же , то и . Это означает, что в имеется путь из в длины и ребро . Объединив их, получаем путь из в длины .

Из леммы непосредственно получаем

Следствие 1. Пусть – ориентированный граф с вершинами, а – его граф достижимости. Тогда .

Доказательство: Из леммы следует, что, если в имеется путь из в , то в нём имеется и простой путь из в длины . А по лемме все такие пути представлены в матрице .

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

· Для возведения матрицы в произвольную степень достаточно выполнить возведений в квадрат:

где – это наименьшее число такое, что .

· Так как на диагонали в матрице стоят единицы, то для любых все единицы матрицы сохраняются в матрице , в частности, и в матрице .

· Если при вычислении элемента матрицы по стандартной формуле

обнаруживается такое , что и , то и вся сумма . Поэтому остальные слагаемые можно не рассматривать.

Пример 14.2: Рассмотрим в качестве примера вычисление матрицы графа достижимости для графа примера 14.1. В этом случае

Так как у имеется 6 вершин, то . Вычислим эту матрицу:

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

Как видим, эта матрица действительно задаёт граф , представленный в примере 14.1.

Дата добавления: 2015-10-28