Теория графов. 
Элементы высшей математики

Граф — совокупность двух конечных множеств Г = ,.

где М — множество, исМ — бинарное отношение в этом множестве. Элементы множества М называются вершинами, а элементы бинарного отношения U — дугами (или ребрами).

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

Две вершины m₁ и m₂ называются смежными, если они соединены одной дугой (рис. 4.6.).

Рис. 4.6 Граф с дугами u1, u2,u3,u4, вершинами m1, m2,m3,m4,m5, петлей (m5,m5) и кратной дугой (m3,m4)

Иногда граф содержит петли, т. е. дуги вида (mi, mi). На рис. 4.7 представлена петля (m₅, m₅).

Одинаковые пары в U вида (m_i, mj) (i=1,… k, j=l,.k) называются дугой кратности к.

Два графа Г = и Г называются изоморфными, если существует такое взаимно однозначное соответствие между вершинами М и М'; что если вершины m_i и m_i+1 соединены дугой (m_i, m_i+1) в одном из графов, то соответствующие им вершины m'_i и m'_i+1 соединены дугой (m'_i, m'_i+1) в другом графе.

Например, графы на рис. 4.7. являются изоморфными.

Puc. 4.7 Изоморфные графы Г и Г'.

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

Цепью называется последовательность дуг (u₁, u₂,… u_n) вида (u_i = m_i, m_i+1) (рис. 4.8). Цепь образует незамкнутый маршрут, в котором все дуги попарно различны. Если в цепи все вершины попарно различны, то это простая цепь.

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

Рис. 4.8 Цепь и цикл

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

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

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

Рис. 4.9 Дерево и лес

Л. Эйлер в своей работе по теории графов рассмотрел следующую проблему: на каких графах можно найти цикл Р, содержащий все ребра графа, причем каждое ребро в точности по одному разу?

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

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

ПРИМЕР.

(«Задача о кенигсбергских мостах»).

Город Кенигсберг (ныне Калининград) расположен на берегах реки Преголи и двух островах. Различные части города (на рис. 4.11 обозначены А, В, С, Д) соединены семью мостами.

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

Рис. 4.10 Схема частей города А, В, С и Д и его мостов

Решение.

Л. Эйлер показал, что на графе, представленном на рис. 4.10, нельзя выделить эйлеровой линии. Иными словами, с какой бы вершины мы ни начали обход, мы не можем обойти весь граф и вернуться обратно, не проходя никакого ребра дважды.

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

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

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

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

ПРИМЕР («Задача коммивояжера «).

Коммивояжер выезжает из родного города. Он должен посетить несколько конкретных городов и вернуться домой. При этом в каждом городе он должен побывать только один раз, а длина пути должна быть выбрана минимальной.

Решение.

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

В общем виде эта задача не решена.

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

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

Графическое решение задачи коммивояжера.

ЗАДАНИЯ.

• 1). Для заданного графа построить матрицу смежности. Проверить, является ли граф эйлеровым, построить линию гамильтона.
• 2). Построить граф по заданной матрице смежности. Проверить, является ли граф эйлеровым.

3). Для заданного графа построить матрицу смежности.

Проверить, является ли граф эйлеровым, построить линию гамильтона.

4). Построить граф по заданной матрице смежности. Проверить, является ли граф эйлеровым.

• 5). Решить задачу коммивояжера для городов А (начало), В, С, Д, Е.
• 6). Достроить графы до эйлеровых графов (построить дополнительные ребра):
• 7). На заданных графах выделить эйлерову и гамильтонову линии:

Раздел 5. Теория вероятностей и математическая статистика.