- •В. Н. Степанов дискретная математика: графы и алгоритмы на графах
- •Предисловие
- •1. Основные понятия теории графов
- •1.1. Граф и его разновидности
- •1.2. Морфизмы графов
- •1.3. Степени вершин
- •1.4. Маршруты, цепи, циклы, связность
- •1.5. Операции над графами
- •1.6. Примеры графов
- •1.7. Метрические характеристики графов
- •1.8. Представления графов
- •2. Алгоритмы и сложность
- •2.1. Понятие алгоритма
- •2.2. Сложность алгоритма
- •2.3. Запись алгоритма
- •3. Обходы графов
- •3.1. Поиск в глубину на графе
- •3.2. Поиск в ширину на графе
- •3.3. Алгоритм выделения компонент связности
- •4. Деревья
- •4.1. Деревья. Свойства деревьев
- •4.2. Остовы. Теорема Кирхгофа
- •4.3. Теорема Кэли
- •4.4. Фундаментальная система циклов. Цикломатическое число
- •4.5. Алгоритм отыскания фундаментального множества циклов на графе
- •5. Остов минимального веса. Алгоритм Краскала и Прима
- •5.1. Алгоритм д. Краскала
- •5.2. Алгоритм р. Прима
- •6. Кратчайшие пути между вершинами графа
- •6.1. Алгоритм Дейкстры
- •6.2. Алгоритм Флойда
- •7. Эйлеровы графы
- •7.1. Теорема Эйлера
- •7.2. Алгоритм Флёри
- •8. Гамильтоновы графы
- •8.1. Гамильтоновы маршруты. Задача коммивояжера
- •8.2. Существование гамильтоновых маршрутов
- •9. Алгоритмы отыскания гамильтоновых циклов
- •9.1. Алгоритм с возвратом (полного перебора)
Предисловие
В последние десятилетия теория графов стала важнейшим математическим инструментом в решении многочисленных прикладных задач. Начало теории графов как математической дисциплины было положено Л. Эйлером в его статье о кенигсбергских мостах: Euler L. Solutio problematis ad geometriam situs pertinentes. Commentarii Academiae Petropolitanae. 8. 1736. P. 128–140. Однако эта статья была единственной в течение почти ста лет. Интерес к теории графов возродился в середине XIX века и был связан с решением головоломок, исследованиями Г. Кирхгофа по электрическим цепям, описанием моделей кристаллов и структур молекул.
Оказалось, что при помощи графов вполне можно моделировать самые разнообразные задачи. Это потребовало обоснований, и теория графов стала одной из самых быстро развивающихся областей математики. Так возникли два естественных направления работы с графами:
изучение свойств абстрактных графов;
применение графов в других науках и прикладных задачах: поиск кратчайших маршрутов, сетевое планирование, теория игр, методы передачи и обработки информации, электрические цепи, схемы транспортных коммуникаций, задачи теории расписаний, проблемы биологии, психологии, социологии.
В пособии излагаются основы теории графов. Приводятся основные виды и способы задания графов, операции над графами, метрические характеристики графов. Рассматриваются задачи нахождения оптимальных маршрутов на графах. Дается критерий Понтрягина – Куратовского планарности графа. Приведены некоторые результаты по раскрашиванию графов.
Данное учебное пособие содержит не только основные понятия и теоретические результаты, но и многочисленные примеры, а также большое количество задач и упражнений для самостоятельной работы или практических занятий.
1. Основные понятия теории графов
1.1. Граф и его разновидности
Простым графом (кратко – графом) называется пара множеств: непустое конечное множество и множество неупорядоченных пар элементов из множества
(то есть симметричное отношение на ).
Множество называется множеством вершин, а множество – множеством ребер. Число вершин графа называется его порядком и обозначается . Обычно граф изображают диаграммой: вершины – точками, ребра – линиями.
Если вершины соединены ребром то говорят, что вершины смежные, а ребро инцидентно вершинам . Множество всех вершин графа смежных с некоторой вершиной , называется окружением вершины и обозначается через Два ребра называются смежными, если они имеют общую вершину. На рисунке 1.1.1 изображен граф с четырьмя вершинами и пятью ребрами. Вершины смежные; вершины не смежные, ребра смежные; не смежные.
|
Часто рассматриваются следующие разновидности графов.
1. Если множество упорядоченных пар элементов из , то граф называется ориентированным графом (орграфом). В этом случае элементы множества называются дугами. При этом дуга называется исходящей из вершины и заходящей в вершину . На диаграмме графа дуга изображается линией со стрелкой из вершины в вершину .
2. Если в графе (в орграфе) хотя бы одна пара вершин соединена более чем одной дугой (ребром), то такой граф (орграф) называется мультиграфом (рис. 1.1.2), а ребра (дуги) называются кратными.
3. Если, кроме того, элементами множества могут быть пары , то они называются петлями, а граф называется графом с петлями или псевдографом. Обычно петля считается неориентированной. На рис. 1.1.3 – петля.
|
|
4. Граф называется подграфом графа (обозначается ), если и
5. Если множество вершин подграфа есть , а множество его ребер совпадает с множеством всех ребер графа , оба конца которых принадлежат , то называется подграфом, порожденным множеством , и обозначается через .