Достижимость и связность в графах

Баранов Виктор Павлович. Дискретная математика. Раздел 3. Графы, сети, коды.

Лекция 8. Достижимость и связность в графах

Лекция 8. ДОСТИЖИМОСТЬ И СВЯЗНОСТЬ В ГРАФАХ

План лекции:

Маршруты, цепи и циклы.
Связность графа и компоненты связности.
Диаметр, радиус и центр графа.
Матрицы достижимости и контрадостижимости.

Маршруты, цепи и циклы

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

, (1)

, (2)

(3)

являются путями.

Рис. 1.

Ориентированной цепью (или орцепью) называется путь, в котором каждая дуга используется не больше одного раза. Так, например, пути (2) и (3) являются орцепями, а путь (1) не является таким, поскольку дуга в нем используется дважды.

Простой называется орцепь, в которой каждая вершина используется не более одного раза. Например, орцепь (3) является простой, а орцепь (2) – нет.

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

Аналогично тому, как мы определили орцепи и простые цепи, можно определить цепи и простые цепи.

Путь или маршрут можно изображать также последовательностью вершин. Например, путь (1) можно записать в виде: .

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

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

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

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

° ° °

° ° ° ° ° °

а б в

Рис. 2.

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

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

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

Для орграфа определены три типа компонент связности: сильная компонента – максимально сильный подграф, односторонняя компонента – максимальный односторонний подграф и слабая компонента – максимально слабый подграф.

Понятие сильной компоненты иллюстрирует рис. 3.

° ° ° ° ° °

° ° ° °

° ° ° ° ° °

° ° °

° ° ° ° °

Рис. 3

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

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

Графы являются связными и в сумме дают граф . Эти графы называются компонентами связности графа . Число – еще одна числовая характеристика графа. Для связного графа , если граф несвязный, то .

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

Диаметр, радиус и центр графа

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

2) ;

3) .

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

которое называется эксцентриситетом. Очевидно, что эксцентриситет для всех вершин в полного графа равен единице, а для вершин простого цикла – .

Максимальный эксцентриситет носит название диаметра графа, а минимальный – радиуса графа . В полном графе имеем , а в простом цикле – .

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

Пример 1. Найти диаметр, радиус и центр графа, приведенного на рис. 4.

° °

° ° °

° °

Рис. 4.

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

Для каждой строки матрицы находим наибольший элемент и записываем его справа от черточки. Наибольшее из этих чисел равно диаметру графа , наименьшее – радиусу графа . Центр графа составляют центральные вершины и .

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

Матрицы достижимостей и контрадостижимостей

Матрица достижимостей определяется следующим образом:

Множество вершин графа , достижимых из заданной вершины , состоит из таких элементов , для которых -й элемент в матрице равен 1. Это множество можно представить в виде

Матрица контрадостижимостей (обратных достижимостей) определяется следующим образом:

Аналогично построению достижимого множества можно сформировать множество , используя следующее выражение:

Из определений следует, что -й столбец матрицы совпадает с -й строкой матрицы , т. е. , где – матрица, транспонированная к матрице .

Пример 2. Найти матрицы достижимостей и контрадостижимостей для графа, приведенного на рис. 5.

Рис. 5.

Определим множества достижимостей для вершин графа:

Следовательно, матрицы достижимостей и контрадостижимостей имеют вид:

, .

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

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

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

Достижимость и связность в графах