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

Вершины периферийные – те, у которых e(x_i) = D(G).

Множество центральных вершин – центр, множество периферийных вершин – окраина.

Следовательно, вершина х₅ – центр графа, так как e(x₅) = r(G) = 1. Вершины x₁, x₂, x₃, x₄ – окраина.

Под средним диаметром графа понимают величину

D_ср= ,

где С – сумма кратчайших расстояний между всеми парами вершин графа, n – число вершин графа.

Для каждой пары вершин учитываем кратчайшие расстояния как d(a,b), так и d(b,a).

Найдем кратчайшие расстояния между всеми парами вершин графа G(6, 7) рис. 1.27:

d(a, b) = d(a, c) = d(b, a) = d(b, c) = d(c, a) =

= d(c, b) = d(c, d) = d(d, c) = d(d, e) = d(d, f) =

= d(e, d) = d(e, f) = d(f, d) = d(f, e) = 1,

d(a, d) = d(b, d) = d(c, e) = d(c, f) = d(d, a) = d(d, b) = d(e, c) = d(f, c)=

= d(a, e)= d(a, f) = d(b, e) = d(b, f) = d(e, a) = d(e, b) = d(f, a) = d(f, b) = 2.

Найдем сумму С всех этих расстояний: С = 1∙14 + 2∙8 + 3∙8 = 54.

Число вершин графа G(6, 7) n = 6.

Р
исунок 1.27

Найдем средний диаметр D_ср= = =1,8.

1.8. Обхват и окружение графа

Обхватом графа называют длину кратчайшего цикла (контура).

Для графа, показанного на рис. 1.28, кратчайший цикл:

a–e₇–e–e₈–d–e₃–a.

Длина этого цикла 3. Следовательно, обхват данного графа равен 3.

Окружением графа называют длину самого длинного простого цикла.

Для графа, показанного на рис. 1.28, окружение равно 5 – это длина цикла a, b, c, d, e, a.

Р
исунок 1.28

1.9. Граф – дерево

Дерево – это связный граф без циклов.

Число ребер у дерева m = n – 1 (минимальное число ребер у связного графа с n вершинами).

Следующие утверждения равносильны:

1. G – дерево.

2. G – связный граф без циклов.

3. G – связный граф с n – 1 ребром.

4. G – граф, в котором любые две вершины соединены простой цепью.

5. G – граф, у которого каждое ребро (дуга) является мостом.

У
далив, например, в графе рис. 1.29 ребро a получим граф, состоящий из двух компонент связности. Число компонент связности увеличилось до 2, следовательно, ребро a — мост. Аналогично, для других ребер.

Рисунок 1.29

Несколько деревьев образуют лес.

1.10. Обходы графа

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

• поиск в ширину,

• поиск в глубину.

Для пояснения различий этих поисков по исходному графу построим дерево рис. 1.30 с корнем в вершине – начале обхода (это этаж 1), от этой вершины проводим ребра, инцидентные ей, получаем этаж 2. Затем аналогично строим следующий этаж и т.д.

Р
исунок 1.30

Обход в ширину идет просмотром вершин этажа и далее по этажам. Это обслуживание очереди.

Обход в глубину – идем по ветви до конца, если нужная вершина не найдена, то возвращаемся до первого разветвления и далее по новой веточке вниз – обслуживание стека.

1.11. гамильтоновы и эйлеровы графы

Предположим, что имеем объект, функционирование которого описывается орграфом.

Предположим также, что неисправности объекта можно разделить на два типа:

• неисправность типа 1: приводит к потере вершины,

• неисправность типа 2: приводит к потере дуги.

При контроле работоспособности объекта с неисправностями типа 1 необходимо обойти все вершины.

При контроле работоспособности объекта с неисправностями типа 2 необходимо обойти все дуги (при этом будут пройдены и все вершины).

Очевидно, что время на проверку объекта в обоих случаях минимально, если вершины или дуги будут пройдены по одному разу.

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

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

Для неорграфа существует признак наличия гамильтонова цикла:

Если сумма степеней двух любых вершин графа больше или равна n , т.е. deg a + deg b  n , то в графе можно построить гамильтонов цикл.

Следствие: Если у любой вершины графа deg v_i  n/2, то в таком графе можно построить гамильтонов цикл.

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

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

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

Граф, который удовлетворяет условиям Эйлера, называется эйлеровым графом. Пример такого графа показан на рис. 1.31. У этого графа каждая вершина имеет четную степень, равную 2.

Цикл в этом графе a–e₁–b–e₃–c–e₂–a называется эйлеровым, так как он проходит через все ребра по одному разу.

Р
исунок 1.31

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

1.12. Контрольные вопросы

1. Что называется графом? Какие графы вы знаете? Приведите примеры.

2. Что такое смежность вершин и смежность ребер (дуг)?

3. Какие вершина и ребро (дуга) инцидентны?

4. Что такое маршрут, цепь, путь, цикл, контур?

5. Что такое подграф и часть графа? Чем они отличаются?

6. Поясните понятия гомоморфизм и изоморфизм графов.

7. Что называется степенью вершины неорграфа? Орграфа? Чему равна сумма степеней вершин неорграфа? Орграфа?

8. Поясните понятия связность и достижимость. Что такое сильная связность, слабая связность, просто связность, вершинная связность, реберная связность?

9. Чем отличается компонента связности от компоненты сильной связности?

10. Какая вершина называется точкой сочленения?

11. Какое ребро (дуга) называется мостом (перешейком)?

12. Поясните понятия теории графов: расстояние, эксцентриситет, радиус, диаметр, средний диаметр.

13. Что такое центр и окраина графа? Приведите примеры графов с двумя и тремя центральными вершинами.

14. Что такое обхват графа? Что такое окружение графа?

15. Как организуется поиск в графах?

16. Какой граф называется гамильтоновым? Какому условию отвечает гамильтонов граф?

17. Какой граф называется эйлеровым? Каким условиям отвечает эйлеров граф?

2. Представление графов в ЭВМ

2.1. Матричная форма представления графов

2.1.1. Матрица смежности

Матрица смежности – это квадратная матрица А = , число строк и столбцов в которой равно числу вершин графа n, а элементы определяются по правилу

а_ij =

где e_ij – ребро (дуга), соединяющее вершины i и j.

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

Два графа эквивалентны, если равны их матрицы смежности.

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

Вот пример матрицы смежности

A_{6 6} = .

Задание. Нарисуйте граф.

Для неорграфа матрица смежности симметрична относительно главной диагонали. Для орграфа матрица смежности не симметрична.

Для мультиграфа и псевдографа:

a_ij=

m(x_i, x_j) –число ребер между вершинами х_i и х_j.

Если на вершинах графа заданы веса, то вводится дополнительный массив W длины n, в котором элемент w(i) задает значение веса вершины графа.

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

Для мультиграфа, псевдографа с весами на ребрах и дугах используется трехмерная матрица, где третья размерность используется для записи веса ребра, дуги, петли.

2.1.2. Матрица инцидентности

Матрица инцидентности S = , имеет n строк и m столбцов, где n – число вершин в графе, m – число ребер (дуг) в графе. Элементы этой матрицы определяются по следующим правилам.

Для неорграфа

s_ij =

Вот пример матрицы инцидентности неорграфа.

S_{6 7} = .

Задание. Нарисуйте граф.

Для орграфа учитывается ориентация:

s_ij =

Здесь каждый столбец содержит один элемент, равный +1, и один элемент, равный –1, либо константу.

Два графа эквивалентны, если равны их матрицы инцидентности.

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

S_{6 9} = .

Матрица S задает граф с точностью до изоморфизма.

основное преимущество матрицы А перед матрицей S в том, что за один шаг алгоритма можно получить ответ на вопрос: есть ли ребро из вершины х_i в х_j?

Основной недостаток матрицы А – большой объем памяти независимо от числа ребер: n².

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