2.3. Достижимость

Вершина графа х_i называется достижимой из вершины x_j того же графа, если существует по крайней мере один путь из x_i в x_j.

Множество вершин R(x_i), достижимых из некоторой вершины , определяется следующим выражением:

2.9

Действительно, первым элементом множества R(x_i) является вершина x_i, которая достижима из себя самой с помощью пути длины нуль; Г(x_i) – множество вершин x_j, достижимых из x_i с использованием путей длины единица; Г²(x_i) – множество вершин, достижимых из x_i с использованием путей длины два; - множество вершин, достижимых из x_i с использованием путей длины p. Таким образом, множество R(x_i) получается путем последовательного выполнения слева направо операции объединения в выражении (2.9) до тех пор, пока мощность текущего множества не перестанет увеличиваться при очередной операции объединения. С этого момента последующие операции объединения не будут давать новых элементов множеству R(x_i). Число объединений, которые необходимо выполнить, зависит от графа G. Но если граф конечен, то p<n, где n – число вершин графа.

Матрицей достижимостей называется квадратная матрица порядка n, элемент которой

Пример. Построить матрицу достижимостей графа G, представленного на рис. 2.6.

Рис. 2.6

Решение. X={x₁, x₂, x₃, x₄}; Г(х₁)={x₂}; Г(х₂)={x₃}; Г(х₃)={x₄}; Г(х₄)={x₃}.

;

;

;

.

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

.

Очевидно, что элементы d_i,i=1, i=1, 2, …, n, так как каждая вершина достижима из себя самой.

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

где Q(x_i) – множество таких вершин x_iX, что из любой вершины этого множества можно достигнуть вершину x_i:

2.10

где - множество вершин, из которых достижима вершина x_i с использованием пути длины единица; ) – множество вершин, из которых достижима вершина x_i с использованием пути длины два и т.д. Операция объединения в выражении (2.10) выполняется слева направо до тех пор, пока очередное объединение не перестанет изменять “текущее множество”.

Пример. Построить матрицу контрдостижимостей Q для графа G рис. 2.6.

Решение.

Матрица контрдостижимостей будет иметь вид:

.

Из определения матриц D и Q следует, что Q=D^T. Так как D(x_i) является множеством вершин, достижимых из , а Q(x_j) – множество вершин, из которых достижима вершина x_j, то D(x_i) - множество таких вершин, каждая из которых принадлежит по крайней мере одному пути, идущему от x_i к x_j. Эти вершины называются существенными (неотъемлемыми) относительно двух концевых вершин x_i и x_j. Вершины называются несущественными (избыточными), так как их удаление не влияет на пути от x_i к x_j.

2.4. Неориентированные графы

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

Описать неориентированный граф G можно и путем задания пары множеств (X, U), где Х – множество вершин; U-множество ребер. Однако более удобным является описание неориентированного графа матрицей смежности или матрицей инциденций, которые строятся аналогично соответствующим матрицам для ориентированных графов с той разницей, что не делается различия между заходящей и исходящей из нее дугами. При этом вершины х и y называются смежными, если существует ребро их соединяющее, а само это ребро называется инцидентным вершинам х и у.

Пример. Построить матрицу смежности и матрицу инциденций для неориентированного графа, приведенного на рис. 2.7.

Рис. 2.7.

Вершины у графа рис. 2.7 обозначены цифрами, а ребра – латинскими буквами. Матрица смежности R и матрица инциденций S будут иметь вид:

; .

Степенью вершины х_i, обозначаемой deg(x_i) или , называют число ребер, инцидентных вершине x_i. Так, для графа рис. 2.7 имеем: . Если =1, то вершину называют тупиковой (вершина 4 рис.2.7). Если =0, то вершину называют изолированной (вершина 5 рис. 2.7).

Теорема. Пусть G – неориентированный граф с n вершинами и m ребрами и - степень j –ой вершины. Тогда

. 2.11

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

Следствие. В каждом графе число вершин нечетной степени четно.

Для неориентированного графа понятия «подграф», «частичный граф» аналогичны соответствующим понятиям для ориентированного графа.

С понятием неориентированного графа связана важная характерис-тика, называемая связностью графа. Граф связен, если любые две его вершины можно соединить цепью. Если граф G не связен, то его можно разбить на такие подграфы G_i, что все вершины в каждом подграфе связны, а вершины из различных подграфов не связны. Такие подграфы G_i называют компонентами связности графа G.

Итак, если в произвольном графе G вершина а связана с вершиной b, а вершина b связана с вершиной c, то очевидно, что а связана с с. Отношение связанности вершин является отношением эквивалентности. Следовательно, существует такое разложение множества вершин на попарно непересекающиеся подмножества, что все вершины в каждом связаны, а вершины из различных не связаны. В соответствии с этим и имеем прямое разложение графа на непересекающиеся связанные подграфы - компоненты связности графа G. Т.о. получили следующее утверждение (Теорема):

Каждый неориентированный граф распадается единственным образом в прямую сумму своих связанных компонент.

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

Для того, чтобы определить связность ориентированного графа, не нужно обращать внимание на ориентацию дуг. Граф, изображенный на рис. 2.1, несвязный, однако его подграф, состоящий из вершин b, c, d, e, является связным. Для ориентированного графа существует понятие сильной связности. Граф сильно связен, если для любых двух вершин (x и у, ху) существует путь, идущий из х в у.

Важный частный случай неориентированного графа – дерево. Деревом называется конечный связный неориентированный граф, не имеющий циклов (рис. 2.8).

Если дано множество вершин a, b, c…, то дерево можно построить следующим образом. Одну из вершин, например, а примем за начальную и назовем ее корнем дерева. Из этой вершины проводим ребра в близлежащие вершины b, h, s…, из них проводим ребра в соседние с ними вершины g, p … и т. д. Таким образом, дерево

Рис. 2.8.

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

Простейшее дерево состоит из двух вершин, соединенных ребром. Каждый раз, когда добавляется еще одно ребро, в конце его добавляется еще одна вершина. Следовательно, дерево с n вершинами имеет n-1 ребер.