Федоров В.Н. - Введение в теорию графов, страница 2

Р
исунок 1.7

Д
ве вершины называются смежными, если они соединяются некоторым ребром (дугой), и два различные ребра (дуги) смежны, если они имеют общую вершину. На рис. 1.8 у графа G(3,3) смежные вершины a и b; a и c; b и c, а также смежные дуги e₂ и e₃, смежные ребро e₁ и дуга e₂, смежные ребро e₁ и дуга e₃.

Рисунок 1.8

Вершина х инцидентна ребру (дуге) е, если она является началом или концом ребра (дуги). На рис. 1.8 вершины a и b инцидентны ребру e₁, вершины b и c инцидентны дуге e₂.

Дуга (ребро) е инцидентна вершине x, если она выходит из этой вершины или входит в нее. На рис. 1.8 дуга e₂ инцидентна вершинам b и c.

1.2. Подграфы и части графа

Пусть G (V, E) – исходный граф (рис. 1.9).

G’(V’, E’) – часть графа – это могут быть все вершины, но дуги не все.

V’ V, E’ E (V’ V’).

Если у части графа V’ = V, то ее называют суграфом.

G
”(V”, E”) – подграф – часть графа, в которой сохранены все ребра, связывающие вершины графа V” V, E” = Е (V” V”).

Рисунок 1.9

1.3. Гомоморфизм и изоморфизм графов

Пусть имеем граф G (V, E) (рис. 1.10).

Р
исунок 1.10

И пусть имеется отображение: : V  V, при котором

a,b, a, b  V   (a),  (b),  (a),  (b)  V.

Такое отображение называется гомоморфизмом.

Если отображение взаимно однозначно: : V  V, то это изоморфизм.

Изоморфные графы эквивалентны с точность до обозначений вершин.

Пример (рис. 1.10).

Для графа G ( V, E ) имеем

 (1) = a,  (2) = b,

 (3) = c,  (4) = b.

Это гомоморфное преобразование.

Для графа G = (V , E ) имеем

 (1) = a,  (3) = c,

 (2) = b,  (4) = d.

Это изоморфное преобразование.

G  G  c точностью до обозначения вершин.

1.4. Взвешенные графы

Иногда ребрам (дугам) графа и/или его вершинам сопоставляются числа, называемые весами ребер (дуг) и весами вершин. Тогда граф называют графом со взвешенными ребрами (дугами) и/или вершинами (или просто взвешенным графом).

П
римеры графов с взвешенными ребрами и вершинами показаны на рис. 1.11.

Рисунок 1.11

1.5. Степени вершин

В псевдографе число ребер и дуг (петли либо не учитывают, либо учитывают как два ребра или дуги), инцидентных некоторой вершине х_i, называют степенью вершины (обозначение deg x_i).

Например, у графа показанного на рис. 1.12

степень вершины: x₁: 6

(ребра е₁, е₂, е₅, е₇, е₈, дуга е₃);

степень вершины x₂: 5

(ребра е₁, е₂, дуги е₃, e₄, e₆);

степень вершины x₃: 2

(ребро e₅, дуга e₄,);

степень вершины x₄: 6

(ребра е₇, е₈, e₉, дуги e₆, e₁₀, e₁₁);

степень вершины x₅: 3

(ребро e₉, дуга e₁₀, дуга e₁₁).

Р
исунок 1.12

В неорграфе степень вершины равна числу инцидентных ей ребер, а сумма степеней вершин равна удвоенному числу его ребер

.

Пример, подтверждающий справедливость этой формулы, показан на рис. 1.13.

Если deg v_i = 0 , то эта вершина изолированная.

Если deg v_i = 1 , то эта вершина висячая.

Для орграфа вводятся понятия полустепени исхода (deg⁺) и полустепени захода (deg^–) вершины, что соответствует числу выходящих и входящих дуг соответственно.

Р
исунок 1.13

Для орграфа, показанного на рис. 1.14,

Р
исунок 1.14

полустепень исхода вершины a: 2 (две выходящие дуги: 1, 2),

полустепень захода вершины a: 1 (одна заходящая дуга 10),

полустепень исхода вершины b: 1,

полустепень захода вершины b: 2

полустепень исхода вершины c: 2,

полустепень захода вершины c: 0,

полустепень исхода вершины d: 0,

полустепень захода вершины d: 2,

полустепень исхода вершины e: 1,

полустепень захода вершины e: 3,

полустепень исхода вершины f: 3,

полустепень захода вершины f: 0,

полустепень исхода вершины g: 1,

полустепень захода вершины g: 2.

Для орграфа и .

Если deg^– v_i = 0 , то эта вершина – источник.

Если deg⁺ v_i = 0, то эта вершина тупиковая – сток.

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

Вершины графа G(3,6) x₁, x₂, x₃ (рис. 1.15) имеют одинаковую степень, равную 4, следовательно, G – регулярный граф.

Р
исунок 1.15

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

У графа, показанного на рис. 1.16, имеем

Смежные вершины Несмежные вершины

x₁ и x₂ : 2 общих соседа: x₄ и x₃ х₁ и х₃: 2 общих соседа: x₂ и x₄

x₁ и x₄ : 2 общих соседа: x₂ и x₃ х₂ и х₄: 2 общих соседа: x₁ и x₃

x₄ и x₃ : 2 общих соседа: x₁ и x₂ x₂ и x₃ : 2 общих соседа: x₄ и x₁

Одинаковое число общих Одинаковое число общих

соседей: 2. соседей: 2.

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

Р
исунок 1.16

1.6. Связность и достижимость

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

Маршрут можно указать также перечислением вершин или ребер (дуг). Каждая пара соседних вершин или ребер (дуг) в таком представлении должны быть смежными.

В графе рис. 1.17 маршрут из точки “a” в точку “b” (а – начальная вершина, b – конечная вершина): последовательность вершина a, дуга e₇, вершина d, дуга e₆, вершина e, дуга e₅, вершина c, ребро e₃, вершина b.

Число ребер (дуг) в маршруте называется его длиной.

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

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

Рисунок 1.17

Замкнутую цепь называют циклом, если ее длина >2. Цикл называется простым, если все его вершины различны.

Замкнутый путь называют контуром, если его длина >2. Контур называется простым, если все его вершины различны.

В графе на рис. 1.18 маршрут b–e₁–c–e₂–d–e₅–b является замкнутым и его вершины (b, c, d) и ребра (e₁, e₂, e₅) различны, а длина маршрута равна 3, следовательно, данный маршрут можно назвать простым циклом.

Р
исунок 1.18

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

Граф G₁(4,5) на рис. 1. 19 связный. Он имеет одну компоненту связности. Несвязный граф G₂(6,4) на рис. 1.19 состоит из двух компонент связности.

Р
исунок 1.19

Орграф связен, если связен неорграф, полученный из него заменой дуг на ребра.

Орграф называется сильно связным, если любые его вершины взаимно достижимы. Вершина y достижима из вершины x, если имеется путь от x до y.

Заметим, связный неорграф всегда сильно связен.

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

Р
исунок 1.20

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

Вершинная связность графа G(7,7) рис. 1.21 для получения нуль графа равна 2 (результат удаления вершин c и e показан на рис. 1.22, а).

В
ершинная связность графа G(7,7) для получения несвязного графа равна 1 (результат удаления вершины c показан на рис. 1.22, б).

Реберная (дуговая) связность определяется как наименьшее число ребер (дуг), удаление которых приводит к несвязному или нуль графу. Реберная связность графа G(4,6) показана на рис. 1.23 и на рис. 1.24.

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

На рис. 1.25 показан граф, имеющий мост и три точки сочленения:

вершины x₃, x₄, x₆ – точки сочленения, ребро x₃, x₄ – мост.

1.7. Метрические характеристики графа

Обозначим через d(a, b) длину (число ребер или дуг) кратчайшего маршрута между вершинами a и b.

Для d(a, b) справедливы следующие утверждения

1) d(a, a) = 0,

2) d(a, b)  0,

3) d(a, b) = 0  a = b,

4) d(a, b) d(a, c) + d(c, b),

5) d(a, b) = d(b, a) – только для неорграфа расстояния симметричны.

Р
исунок 1.25

Пример. В графе, показанном на рис. 1.26, для вершины х₁ имеем

d(x₁, x₂) = d(x₁, x₄) = d(x₁, x₅) = 1,

d(x₁, x₃) = 2,

d(x₁, x_i) = d(x₁, x₃) = 2.

Р
исунок 1.26

Результаты расчетов для других вершин представлены в матрице расстояний D, а максимальные кратчайшие расстояния – в столбце e(x_i):

e(x_i)

D = .

Для каждой вершины x_i существует максимальный кратчайший маршрут до некоторой вершины x_j, он называется эксцентриситетом вершины и обозначается e(x_i). (См. столбец справа от матрицы D).

Максимальный из всех эксцентриситетов графа – это диаметр графа

D(G) = max e(x_i).

для графа примера D(G) = 2.

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

r(G) = min e(x_i).

для графа примера r(G) = 1.

Вершины, у которых e(x_i) = r(G) называются центральными.