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

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

Описать неориентированный граф 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).

 

 

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

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