Тема 5. Основные понятия теории графов.

1. Основные понятия теории графов.

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

Первой работой, в которой использовалось название «граф» и давалось его точное определение, была работа Л. Эйлера, которая появилась в 1736 году в трудах Петербургской академии наук. В ней Эйлер предлагает читателю головоломку «Задача о кёнигсбергских мостах». Город Кёнигсберг (ныне Калининград) расположен на двух берегах реки Прегель и двух островах. Районы города соединены мостами (рис. 12, а). Вопрос состоит в том, можно ли, выйдя из одного района города, по одному разу пройти по каждому из мостов и вернуться в исходный район?

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

Попытки найти такой маршрут к успеху не привели, и тогда Л. Эйлер сформулировал и доказал свою теорему: для того чтобы существовал циклический маршрут в графе G, необходимо и достаточно, чтобы граф был связным и степени всех его вершин были четными.

Рисунок 8. Граф переходов по мостам г. Калининграда

Приведем примеры неориентированных графов.

Таблица 4

Примеры неориентированных графов

Граф	Вершины	Ребра
Семья	Люди	Родственные связи
Город	Перекрестки	Улицы
Сеть	Компьютеры	Кабели
Домино	Костяшки	Возможность
Дом	Квартиры	Соседство
Лабиринт	Развилки и тупики	Переходы
Метро	Станции	Пересадки
Листок в клеточку	Клеточки	Наличие общей границы

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

Перейдем к формальным определениям основных понятий теории графов.

Графом G = (X, А) называется упорядоченная пара множеств X = {x₁, x₂, …, x_n} и А = {a₁, a₂, …, a_m}, где X – множество вершин, а A – множество ребер графа. Если ребра из множества A ориентированы, то они называются дугами, а граф называют ориентированным. Если ребра не имеют ориентации, то граф называют неориентированным. В противном случае граф является смешанным. На рис. 9 приведены неориентированный и ориентированный графы соответственно.

a)	X = {x1, x2, x3, x4}, A = {a1, a2, a3, a4}.
b)	X = {x1, x2, x3, x4}, A = {a1 = (x1 , x2 ), a2 = (x1 , x3 ), a3 = (x3 , x4 ), a4 = (x3 , x2 )}.

Рисунок 9

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

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

Например, кратность ребра {v₁, v₂} в графе, изображенном на рис. 10, равна двум, кратность ребра {v₃, v₄} − трем.

Рисунок 10

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

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

Множество ребер графа может быть пустым. Множество вершин графа не может быть пустым.

Пример 1.

На рис. 11 изображен ориентированный граф G = (X, A). X = {x₁ , x₂ , x₃ , x₄ },A = .

Рисунок 11

Как в случае ориентированного, так и в случае неориентированного ребра говорят, что вершины x и y инцидентны ребру a, если эти вершины соединены a.

Две вершины называются смежными, если они инцидентны одному и тому же ребру. Два ребра называются смежными, если они имеют общую вершину.

Степенью  вершины графа называется число ребер, инцидентных этой вершине. На рис. 13 (v₃)=5, (v₂)=4. Вершина, имеющая степень 0, называется изолированной, а степень 1 – висячей.

Для ориентированного графа множество вершин, в которые ведут дуги, исходящие из вершины х, обозначают G(х), то есть G(х) = { y: ( x y ) G}. Множество G(x) называют образом вершины x. Соответственно G^-1(у) – множество вершин, из которых исходят дуги, ведущие в вершину у, G^-1(y) = {x: ( x , y ) G}. Множество G^-1(у) называют прообразом вершины y.

Полустепенью исхода (захода) вершины x ориентированного графа G называется число ⁺(x) (^(x)) дуг ориентированного графа G, исходящих из x (заходящих в x).

Следует заметить, что в случае ориентированного псевдографа вклад каждой петли инцидентной вершине x равен 1 как в ⁺(x), так и в ^(x).

Пример 2.

В графе, изображенном на рис. 13 (первый), концами ребра a₁ являются вершины x₁, x₂; вершина x₂ инцидентна ребрам a₁, a₂; степень вершины x₃ равна 3; вершины x₁ и x₃ смежные; ребра a₁ и a₂ смежные; вершина x₄ висячая. В ориентированном графе, изображенном на рис.13 (второй), началом дуги a₁ является вершина x₁, а ее концом - вершина x₂; вершина x₁ инцидентна дугам a₁ и a₂; G(x₁) = {x₂, x₃}, G(x₂) =Æ, G^-1(x₃) = {x₁}, G^-1(x₁) = Æ.

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

Граф G = (X, A) - полный, если для любой пары вершин x_i и x_j существует ребро (x_i, x_j).

Граф G = (X, A) - симметрический, если для любой дуги (x_i, x_j) существует противоположно ориентированная дуга (x_j, x_i).

Граф G = (X, A) - планарный, если он может быть изображен на плоскости так, что не будет пересекающихся дуг.

Неориентированный граф G = (X, A) – двудольный, если множество его вершин X можно разбить на два такие подмножества X₁ и X₂, что каждое ребро имеет один конец в X₁, а другой в X₂.

Основные виды графов показаны на рис. 12.

Рисунок 12. Основные виды графов:

а – обычный граф;

b – граф с кратными ребрами;

c – граф с петлями и вложенными петлями;

d – «нуль-граф» – граф, не имеющий ребер, но имеющий вершины);

e – «полный граф» – граф, у которого все вершины связаны со всеми остальными;

f – граф типа «дерево», т. е. граф, у которого нет внутренних циклов;

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

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