§5. Графы

Первой научной работой посвященной графам считается статья Л. Эйлера, посвященная задаче о кенигсбергских мостах и опубликованная в 1736 году. Суть задачи следующая. Четыре части города Кенигсберга (a, b, c, d на рис.

Рис. 1

Дадим строгое определение графа. Пусть задано некоторое непустое множество V и множество Е пар различных элементов из V. Элементы множества V называются вершинами графа, элементы множества Е называются ребрами графа, а пара (V, Е), т.е. множество вершин и множество ребер, называется графом.

Граф, как правило, обозначают прописными латинскими буквами, например, G, H.

Несложные графы удобно изображать в виде графических схем, где вершины –– точки, а ребра –– соединяющие их линии. В этих схемах длина линий, их толщина и форма, а также взаиморасположение вершин не имеют никакого значения. Например, на рис. 2 изображен один и тот же граф G = (V, Е), заданный множеством вершин V = {х1, х2, х3, х4} и множеством ребер Е = {(х1, х1), (х1, х2), (х1, х3), (х2, х3), (х3, х4)}.

Рис. 2

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

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

Число ребер, инцидентных данной вершине называется степенью (кратностью) данной вершины.

Граф без петель и кратных ребер называется простым или обыкновенным.

На рис. 3 изображены три графа.

Рис. 3

Соответствующие этим трем случаям матрицы смежности представлены ниже:

а) б) в) .

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

Граф называется планарным (плоским), если он может быть изображен на плоскости так, что все пересечения ребер есть его вершины. Так, граф, представленный на рис. 4 не является плоским, а на рис. 5 –– плоский.

Рис. 4

Рис. 5

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

Ориентированный граф G или орграф состоит из конечного непустого множества V и множества Е упорядоченных пар элементов из V. Элементы множества V называются вершинами орграфа, элементы множества Е –– дугами орграфа. Если (xi, xj) –– дуга, то первая вершина xi называется началом дуги, а вторая xj –– концом дуги. На рисунках дуги изображаются стрелками.

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

Граф Gb = (Vb, Еb) называется частичным графом (суграфом) граф G = (V, Е), если он содержит все вершины исходного графа и лишь часть ребер исходного графа, т.е.

Еb Ì Е.

Подграфом Gа = (Vа, Еа) графа G = (V, Е) называется граф, в который входит подмножество вершин исходного графа (Vа Ì V) и все ребра, соединяющие вершины Vа этого графа (Еа Ì Е).

На рис. 6 представлены частичный граф и подграф для данного исходного графа

G = (V, Е).

Рис. 6

Пусть G = (V, Е) –– неориентированный граф. Маршрутом длины m называется некоторая последовательность m ребер графа G, такая, что вершины двух соседних ребер последовательности совпадают.

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

Примерами маршрутов на графе, изображенном на рис. 71, могут служить следующие последовательности ребер (a1, a6, a5, a1, a3) и (a2, a1, a4, a6). Первый из них проходит последовательно через вершины х1, х2, х3, х2, х1, х3, соединяя х1 с х3. Второй, проходя через вершины х2, х1, х2, х3, х2, образует замкнутый маршрут, т.к. приводит в ту же вершину, из которой и начался.

Рис. 7

Нуль–маршрутом называется маршрут, не содержащий ребер.

Вершина xj называется достижимой из вершины xi, если существует маршрут из хi в хj.

Граф называется связным, если все его вершины попарно достижимы.

Маршрут, все ребра которого различны, называется цепью. Цепь, проходящая через различные вершины, называется простой (элементарной) цепью. Цепь называется циклом, если начальная и конечная вершины цепи равны. Цикл называется простым, если все его вершины различны. Так в графе, изображенном на рис. 71, маршрут (a1, a5, a8) является простой цепью, маршрут (a2, a5, a6, a1) –– циклом.

На ориентированном графе аналогично понятию цепи вводится понятие пути, а аналогично понятию цикла –– понятие контура. Путь –– это ориентированная цепь. Контур –– это замкнутый путь.

Для практики большое значение имеют задачи о нахождении различного рода маршрутов. Наиболее известные из них два: эйлеров цикл и гамильтонов цикл.

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

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

Вопрос о существовании эйлерова графа разрешается следующей теоремой.

Теорема. Конечный граф G является эйлеровым графом тогда и только тогда, когда он связан и все степени его вершин четны.

Простой цикл, который проходит через все вершины графа, называется гамильтоновым (У.Р. Гамильтон, 1805–1865).

Укажем некоторые задачи, интерпретация которых состоит в необходимости построения гамильтоновых циклов.

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

Задача о званом обеде. Обед накрыт на круглом столе. Среди приглашенных некоторые являются друзьями. При каких условиях можно рассадить всех так, чтобы по обе стороны каждого из присутствующих сидели его друзья?

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

В настоящее время условий, гарантирующих существование в графе гамильтонова цикла, не установлено.

Связный граф называется деревом, если он не имеет циклов, а ребра дерева называются ветвями.

Дерево с п вершинами содержит п–1 ветку (ребро) (рис.8 а).

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

Рис. 8

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

Рис. 9

Пусть задан неориентированный граф G = (V, Е). Дерево D = (Y, I) называется покрывающим деревом графа G, если V = Y и I Ì Е. Таким образом, покрывающее дерево связывает все вершины данного графа, но не обязательно при этом включает все его ребра. На рисунке 10 а показан граф, для которого на рис. 74 б построено покрывающее дерево. Любой связанный граф содержит хотя бы одно покрывающее дерево.

Рис. 10