Алейников С. М., Горяйнов В. В.
Представлены основные определения, понятия и термины теории графов. Рассматривается построение матриц смежности и инцидентности для неорграфов и орграфов. Описаны такие операции над графами, как их пересечение, объединение, симметрическая разность, удаление ребер и вершин. Дано понятие маршрута в графе, рассматриваются такие разновидности маршрутов, как цепь и путь, составная цепь и составной путь, простая цепь и простой путь, цикл и контур, простой цикл и простой контур. Показано, как выявить в графе маршрут заданной длины и найти кратчайший путь в орграфе. Описано построение матриц достижимости и контрдостижимости. Предложено 30 вариантов индивидуальных заданий для самостоятельной работы. Для студентов всех специальностей и направлений подготовки по дисциплине «Дискретная математика», содержащей раздел «Теория графов». Будет полезно студентам и аспирантам строительных специальностей при изучении сетевого планирования.
Введение 5
1. Основные определения теории графов 7
2. Геометрические графы 12
3. Степени вершин графа 14
4. Изоморфизм графов 17
5. Матричное представление графов 18
5.1. Матрица инцидентности 18
5.2. Матрица смежности 20
6. Части графов. Операции над графами 23
7. Типы конечных графов 31
7.1. Полный граф 31
7.2. Взвешенный граф 31
7.3. Однородные графы 34
7.4. Двудольный граф 36
7.5. Плоские и планарные графы 36
8. Маршруты в графе 39
8.1. Цепи и циклы. Пути и контуры 39
8.2. Выявление маршрутов в графе заданной длины 41
8.3. Кратчайший путь в орграфе 44
9. Связность графов 55
9.1. Связность неориентированных графов 55
9.2. Связность ориентированных графов 55
9.3. Матрицы достижимости и контрдостижимости 57
9.4. Вершинная и реберная связность 61
10. Расстояния в графе 63
11. Реберные и вершинные обходы графов 68
11.1. Эйлеровы графы 68
11.2. Гамильтоновы графы 70
12. Деревья 73
12.1. Основные определения 73
12.2. Свойства деревьев 74
12.3. Типы вершин дерева и его центры 75
12.4. Корневые деревья 75
12.5. Покрывающие деревья 77
13. Экстремальные задачи на графах 85
13.1. Задача об остове наименьшего веса 85
13.2. Задача о коммивояжере 90
14. Элементы сетевого планирования 93
15. Индивидуальные задания для самостоятельной работы 106
Характеристика заданий 106
Задание 1. Неориентированный граф 109
Задание 2. Ориентированный граф 114
Задание 3. Операции над графами 122
Задание 4. Кратчайший путь в орграфе 128
Задание 5. Взвешенный граф 133
Задание 6. Сетевой график 138
Заключение 149
Список рекомендуемой литературы 150
Приложение 1. Пакет символьной математики Maple для работы с графами 151
Приложение 2. Биографические сведения об ученых, работавших в области теории графов 155
Предметный указатель 169
