Начальные понятия Даже в период становления теории графов в ней возникало немало таких задач, решение которых предполагало построение некоторых алгоритмов. <...> На его основе позже был разработан алгоритм обхода связного графа. <...> Внедрение вычислительной техники поставило и перед всей математикой, и перед теорией графов проблему нахождения не произвольных алгоритмов, позволяющих решать те или иные классы задач, а таких алгоритмов, которые допускали бы практическую реализацию на компьютере. <...> Число вершин графа G будем обозначать через n(G), число ребер – через m(G). <...> Очевидно, что максимальное число ребер в графе на n вершинах равно n(n-1)/2. <...> Исключительную роль во многих прикладных задачах играет остовный подграф графа. <...> Остовный подграф – это подграф графа G, содержащий все его вершины. <...> Подграф G0 на подмножестве вершин V0 V называется порожденным, если множество его ребер совпадает с множеством всех ребер графа G, оба конца которых принадлежат V0. <...> Полный граф на n вершинах обозначается Kn. <...> Полный двудольный граф, доли которого состоят из p и из q вершин, обозначается символом K p,q. <...> Представление графа в памяти компьютера Выбор соответствующей структуры данных для представления графа имеет принципиальное значение при разработке эффективных алгоритмов. <...> При решении задач используются следующие два стандартных способа представления графа G = (V, E): как набора списков смежных вершин или как матрицы смежности. <...> Оба способа представления применимы как для ориентированных, так и для неориентированных графов. <...> Обычно более предпочтительно представление с помощью списков смежности, поскольку оно обеспечивает компактное представление разре9 женных графов, т. е. таких, для которых число ребер гораздо меньше квадрата числа вершин. <...> Представление при помощи матрицы смежности предпочтительнее в случае плотных графов, т. е. когда число ребер близко к n(G)2 или когда нам надо иметь возможность быстро определить, имеется ли ребро <...>
Основные_алгоритмы_на_графах__Текст_лекций.pdf
Министерство образования и науки Российской Федерации
Ярославский государственный университет им. П. Г. Демидова
В. Л. Дольников
О. П. Якимова
Основные алгоритмы
на графах
Текст лекций
Рекомендовано
Научно-методическим советом университета для студентов,
обучающихся по специальности Компьютерная безопасность
Ярославль 2011
Стр.1
УДК 519.254
ББК В 174.2я73
Д 65
Рекомендовано
Редакционно-издательским советом университета
в качестве учебного издания. План 2011 года
Рецензенты:
Р. Н. Карасев, доктор физико-математических наук;
кафедра теории и методики преподавания информатики ЯГПУ
им. К. Д. Ушинского
Дольников, В. Л. Основные алгоритмы на графах :
Д 65
текст лекций / В. Л. Дольников, О. П. Якимова; Яросл. гос.
ун-т им. П. Г. Демидова. – Ярославль : ЯрГУ, 2011. – 80 с.
ISBN 978-5-8397-0855-6
Текст лекций предназначен для студентов, обучающихся
по специальности 090102.65 Компьютерная безопасность
(дисциплина «Алгоритмы на графах», блок ОПД), очной
формы обучения.
УДК 519.254
ББК В 174.2я73
ISBN 978-5-8397-0855-6
© Ярославский государственный
университет им. П. Г. Демидова,
2011
2
Стр.2
Введение
Теория графов – важнейший математический инструмент,
широко используемый в информатике, химии, генетике, исследовании
операций, лингвистике, проектировании, так как посредством
графов можно описывать разнообразные реальные
явления: организацию транспортных систем, сети передачи
данных, человеческих взаимоотношений, структуру гена или
молекулы. Возможность формального моделирования такого
множества разных реальных структур позволяет программисту
решать широкий круг прикладных задач.
Разработка хорошего алгоритма «с нуля» – очень трудная
задача. Часто достаточно правильно построить модель задачи и
применить уже известный алгоритм, решающий задачу быстро и
верно.
В рамках этого пособия разбираются основные алгоритмы на
графах, решающие практические задачи. Для записи алгоритма
используется как естественный язык, так и язык
программирования C#.
3
Стр.3
Оглавление
Введение ............................................................................................................... 3
1. Начальные понятия ......................................................................................... 4
1.1. Основные определения ........................................................................ 5
1.2. Представление графа в памяти компьютера ..................................... 9
1.3 Анализ алгоритмов .............................................................................. 14
Упражнения ............................................................................................... 16
2. Алгоритмы обхода графа .............................................................................. 17
2.1. Поиск в ширину .................................................................................. 18
2.2. Применение поиска в ширину .......................................................... 20
2.3. Поиск в глубину ................................................................................. 22
2.4. Применение обхода в глубину .......................................................... 25
Упражнения ............................................................................................... 29
3. Кратчайшие пути ........................................................................................... 30
3.1. Алгоритм Дейкстpы ........................................................................... 31
3.2. Кратчайшие пути между всеми парами вершин ............................. 35
Упражнения ............................................................................................... 40
4. Остов минимального веса ............................................................................ 41
4.1. Алгоритм Краскала ............................................................................ 41
4.2. Алгоритм Прима................................................................................. 46
4.3. Разновидности остовных деревьев ................................................... 49
Упражнения ............................................................................................... 50
77
Стр.77
5. Циклы в графах .............................................................................................. 51
5.1. Эйлеров цикл ...................................................................................... 51
5.2. Задача китайского почтальона .......................................................... 54
5.3. Гамильтонов цикл и задача коммивояжера .................................... 55
5.4. Классы сложности P и NP ................................................................. 56
5.5. Решение NP-полных задач ................................................................ 59
Упражнения ............................................................................................... 60
6. Независимые множества и покрытия .......................................................... 60
6.1. Независимые множества ................................................................... 60
6.2. Алгоритм аппроксимации максимального независимого
множества методом исключения подграфов ............................ 63
6.3. Вершинное покрытие ......................................................................... 70
6.4. Паросочетания .................................................................................... 72
Упражнения ............................................................................................... 75
Список литературы ........................................................................................... 76
78
Стр.78