3.1. Способы задания графов

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

Форма дуг несущественна, важен только сам факт соединения вершин. Дуги могут пересекаться, но точки пересечения не являются вершинами графа.

Если дуги имеют направление (ориентацию), отмеченное стрелкой, то такие графы называются ориентированными или орграфами. Дуги графа часто называют ребрами.

Вершины графа будем обозначать v , а дуги x . На рис.3.1 изображен граф, а на рис.3.2 – орграф.

Рис3.1 Рис.3.2

Дуга в орграфе, имеющая направление от вершины v к вершине v_ј , назы-вается выходящей из вершины v_i и заходящей в вершину v_j. При этом вершина v_i называется началом дуги, а v_j – ее концом.

Дуги, соединяющие две одинаковые вершины не ориентированного графа, называются кратными. На рис.3.1 это дуги x₁ и x₂.

Дуга, выходящая из вершины и входящая в нее, называется петлей. На рис.3.2 это дуга x₄.

Дуги орграфа называются параллельными, если они соединяют две одинаковые вершины графа и имеют одно направление. На рис.3.2 это дуги x и x .

Дуги орграфа называются противоположными, если они соединяют две одинаковые вершины графа и противоположно направленны. На рис.3.2 это дуги x₁

и x₂.

Две вершины графа называются смежными, если они соединены дугой, иначе они называются несмежными.

Вершина графа (орграфа) называется изолированной, если она не соединяется дугой с другими вершинами графа. На рис.3.1 это вершина v .

Граф с кратными дугами и петлями называется псевдографом. Ориентированный псевдограф соответственно имеет параллельные дуги и петли. Орграф на рис.3.2 является ориентированным псевдографом.

Граф с кратными дугами и без петель называется мультиграфом. Граф на рис.3.1 является мультиграфом. Ориентированный мультиграф соответственно имеет параллельные дуги, но не имеет петель.

Любой граф или орграф можно задать матрицей смежности.

Определение. Матрицей смежности графа, имеющего n вершин, называется квадратная матрица A у которой элемент a_ij = k, если вершина i и j соединены k дугами, иначе a_ij = 0.

В табл.3.1 и 3.2 приведены матрицы смежности графа рис.3.1 и орграфа рис.3.2 соответственно.

Таблица 3.1

Таблица 3.2

Можно заметить, что для неорграфа (неориентированного графа) матрица смежности симметрична. Если в графе (орграфе) нет петель, то в матрице смежности по главной диагонали стоят нулевые элементы.

Граф (орграф) можно задать матрицей инцидентности.

Определение. Матрицей инцидентности графа, имеющего n вершин и m дуг, называется матрица B у которой элемент b_ij = 1, если вершина v_i инцидентна дуге x_j, т.е. соединена дугой x_j с другой вершиной графа. Иначе b_ij = 0.

Для орграфа элемент матрицы инцидентности b_ij = - 1, если из вершины v_i выходит дуга x_j, и b_ij = 1, если в вершину v_i заходит дуга x_j. Элемент b_ij = 0, если вершина v_i не инцидентна дуге x_j. Элемент b_ij = α, где α- число петель в вершине vj.

В табл.3.3 и 3.4 приведены матрицы инцидентности для графов рис.3.1 и 3.2.

Таблица 3.3

Таблица 3.4

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

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

Таблица 3.5

Из способов задания графов видно, что граф однозначно определяется через множество своих вершин и множество дуг. Поэтому граф часто обозначают так: G(X,V) , где X- множество дуг графа, а V – множество его вершин.

Граф называется конечным, если X и V- конечные множества.

Степенью или валентностью вершины v графа (орграфа) называется число дуг, инцидентных ей при этом каждая петля вносит вклад равный 2.

Степень вершины v обозначается как deg v. Степень изолированной верши-ны равна 0. Вершина, степень которой равна 1, называется висящей или концевой.

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

Полустепенью исхода из вершины v орграфа называется число выходящих из v дуг и обозначается deg v.

Для вершины v₁ графа рис.3.2 deg v₁ = 3, deg v₁ = 1, deg v₁ = 4.

Утверждение 1 Для любого конечного графа (орграфа) сумма степеней всех вершин графа равна удвоенному числу его дуг, т.е.

, (3.1)

где m- число дуг графа, n- число его вершин.

Равенство (3.1) является очевидным следствием того, что вклад каждой дуги графа в сумму из левой части (3.1) равен 2.

Утверждение 2. Сумма элементов i - ой строки или i -ого столбца матрицы смежности графа равна степени i -ой вершины

deg v = = (3.2)

В этом можно убедиться на примере табл.3.1.

Утверждение 3. Сумма элементов i - ой строки матрицы инцидентности графа равна степени i - ой вершины

deg v = (3.3)

В этом можно убедиться на примере табл.3.3.

Утверждение 4. Для любого орграфа выполняется следующее равенство:

(3.4)

Доказательство (3.4) очевидно

Утверждение 5. Сумма элементов i - ой строки матрицы смежности ориенти-рованного мультиграфа равна полустепени исхода вершины v , а сумма элементов

i – го столбца – полустепени захода вершины v

deg v = , deg v = . (3.5)

Утверждение 6. (Теорема Эйлера о рукопожатиях). В любом конечном графе число вершин нечетной степени четно или равно нулю ( см. рис.3.1 ).

Рассмотрим одну из задач, положивших начало теории графов - задачу о Кенигсбергских мостах, которая заключается в следующем:

Семь мостов города Кенигсберга расположены на реке Прегель так, как изображено на рис.3.3, соединяя его части A,B,C,D. Нужно найти такую точку города, выйдя из которой можно пройти по всем мостам города по одному разу и вернуться в нее обратно.

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

Рис.3.3 Рис.3.4