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

Иногда граф рассматривают без учета ориентации дуг. Тогда его называют неориентированным графом. Для неориентированного графа понятия «дуга».«путь», «контур» заменяются понятиями «ребро», «цепь», «цикл» соответственно.

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

Рисунок 4.2

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

Ребро – это отрезок, соединяющий две вершины; цепь - последовательность ребер; цикл – цепь, у которой начальная и конечная вершины совпадают.

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

Степенью вершины х, обозначаемой deg(x) или d_x, называют число ребер инцидентных вершине х. Так, для графа, изображенного на рисунке 3 имеем:

Если то вершину называют тупиковой, если то изолированной.

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

(4.3)

.

Рисунок 4.3

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

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

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

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