- •2. Графы
- •2.1. Основные понятия
- •2.1.1. История теории графов
- •2.1.2. Определения
- •2.1.3. Смежность и инцидентность
- •2.1.4. Изоморфизм графов
- •2.2. Представление графов в эвм
- •2.2.1. Требования к представлению графов
- •2.2.2. Матрица смежности
- •2.2.3. Матрица инциденций
- •2.3. Геометрическая реализация графов
- •2.4. Маршруты, цепи, циклы
- •2.4.1. Определения
- •2.4.2. Эйлеровы графы
- •2.4.3. Гамильтоновы графы
- •2.5. Заключение
2. Графы
Среди дисциплин и методов дискретной математики теория графов и особенно алгоритмы на графах находят наиболее широкое применение в программировании. Дело в том, что теория графов предоставляет очень удобный язык для описания программных (да и многих других) моделей.
Этот тезис можно пояснить следующей аналогией. Понятие отношения также можно полностью выразить через понятие множества. Однако независимое определение понятия отношения удобнее - введение специальных терминов и обозначений упрощает изложение теории и делает ее более понятной.
То же относится и к теории графов. Стройная система специальных терминов и обозначений теории графов позволяют просто и доступно описывать сложные и тонкие вещи.
Особенно важно наличие наглядной графической интерпретации понятия графа. Само название «граф» подразумевает наличие графической интерпретации. Картинки позволяют сразу «усмотреть» суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовые доказательства и сложные формулы.
2.1. Основные понятия
2.1.1. История теории графов
Теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач.
1. Задача о Кенигсбергских мостах. Обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку (рис. 3.1). Эта задача была решена Эйлером в 1736 году.
Рис. 3.1. Иллюстрация к задаче о Кенигсбергских мостах
2. Задача о трех домах и трех колодцах. Имеется три дома и три колодца. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 3.2). Эта задача была решена Куратовским в 1930 году.
Рис. 3.2. Иллюстрация к задаче о трех домах и трех колодцах
Предметом первых задач теории графов были различные конфигурации, состоящие из точек и соединяющих их линий. При этом несущественно: являются ли эти линии прямыми или кривыми, длинными или короткими, тонкими или толстыми; важно только то, какие точки они соединяют. Т.о. граф – это абстрактное математическое понятие.
2.1.2. Определения
Графом G(V,E) называется совокупность двух множеств - непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элементов множества V (Е - множество ребер).
G(V,E): , EVxV.
Число вершин графа G обозначим р, а число ребер – q.
р(G) = |V| q(G) = |E|.
Часто рассматриваются следующие родственные графам объекты.
1. Если элементами множества Е являются упорядоченные пары, то граф называется ориентированным(или орграфом). В этом случае элементы множества V называются узлами, а элементы множества - дугами (G(V, )).
2. Если элементом множества Е может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом).
3. Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мультиграфом.
Далее выражение: граф G(V,E) означает неориентированный граф без петель и кратных ребер.
Обычно граф изображают диаграммой: вершины - точками (или кружками), ребра - линиями.
Примеры.
1. . .
|
|
|
Т.о. это неориентированный граф с петлей и кратными ребрами.
Рис. 3.3. Неориентированный граф с петлей и кратными ребрами.
2. . .
Т.о. это ориентированный граф с петлей и кратными ребрами.
|
|
|
Рис. 3.4. Ориентированный граф с петлей и кратными ребрами.
|
|
|
3. . , т.о.
Рис. 3.5. Неориентированный граф с петлей.