книги / Теория графов и её приложения.-1
.pdfМинистерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего образования «Пермский национальный исследовательский политехнический университет»
С.Ф. Тюрин
ТЕОРИЯ ГРАФОВ И ЕЁ ПРИЛОЖЕНИЯ
Практикум
Утверждено Редакционно-издательским советом университета
Издательство Пермского национального исследовательского
политехнического университета
2017
УДК 621.399 Т89
Рецензенты:
доктор технических наук, профессор В.А. Твердохлебов (Институтточноймеханики ипроблемуправленияРАНг. Саратов); кандидат технических наук, доцент А.И. Дерябин (Национальный исследовательский университет
«Высшая школа экономики» (Пермский филиал))
Тюрин, С.Ф.
Т89 Теория графов и её приложения : практикум / C.Ф. Тюрин. – Пермь : Изд-во Перм. нац. исслед. политехн.
ун-та, 2017. – 207 с.
ISBN 978-5-398-01745-8
Изложен материал практикума по основным задачам, решаемым на графах, с использованием систем компьютерной математики и моделирования.
Предназначено для студентов специалитета, изучающих дисциплину «Теория графов и её приложения». Приведены варианты заданий для самостоятельной работы и НИРС. Может быть полезно для магистров, изучающих дисциплины «Исследование операций», «Теория игр и исследование операций».
УДК 621.399
ISBN 978-5-398-01745-8 |
© ПНИПУ, 2017 |
ОГЛАВЛЕНИЕ |
|
Введение ................................................................................................... |
5 |
Практическое занятие № 1. Задание графов и определение |
|
их свойств. ............................................................................................... |
14 |
Практическое занятие № 2. Определение простых |
|
метрик графа ........................................................................................... |
24 |
Практическое занятие № 3. Определение множеств |
|
внутренней и внешней устойчивости ориентированного графа........ |
35 |
Практическое занятие № 4. Анализ теорем Холла и Рамсея............ |
45 |
Практическое занятие № 5. Решение экстремальных |
|
задач на графах 1. Нахождение кратчайших путей в графе |
|
с рёбрами единичной длины. Задача о Ханойской башне.................. |
48 |
Практическое занятие № 6. Решение экстремальных |
|
задач на графах. Нахождение кратчайших путей в графе |
|
с рёбрами не единичной длины. Нахождение минимального |
|
стягивающего дерева. ............................................................................. |
55 |
Практическое занятие № 7. Решение экстремальных задач |
|
на графах. Нахождение максимального потока в транспортной |
|
сети (flow network). Алгоритм Форда–Фалкерсона............................. |
60 |
Практическое занятие № 8. Анализ графа марковской цепи |
|
в СКМ «Маткад» и в системе Windchill Quality Solutions 10.0.......... |
68 |
Практическое занятие № 9. Нахождение критического пути |
|
в сетевом графике. .................................................................................. |
79 |
Практическое занятие № 10. Перечисление деревьев. |
|
Кодирование Прюфера .......................................................................... |
85 |
Практическое занятие № 11. Анализ автоморфизмов графов.......... |
95 |
Практическое занятие № 12. Решение задач реализации |
|
графа – схемы алгоритма (СА) конечным автоматом......................... |
97 |
Практическое занятие № 13. Моделирование сети Петри.............. |
132 |
Практическое занятие № 14. Анализ графа Small World................ |
141 |
Список литературы............................................................................... |
145 |
3
Приложение 1. Варианты неориентированных графов |
|
без петель ..................................................................................... |
147 |
Приложение 2. Варианты ориентированных графов без петель ..... |
152 |
Приложение 3. Варианты задач определения кратчайших |
|
путей в графах с рёбрами не единичной длины использованием |
|
программы GRIN .................................................................................. |
157 |
Приложение 4. Варианты задач поиска минимального |
|
стягивающегодеревасиспользованиемпрограммыGRIN (Maple) .... |
166 |
Приложение 5. Варианты задач нахождения максимальных |
|
потоков в транспортных сетях............................................................. |
175 |
Приложение 6. Варианты транспортных задач. ................................ |
182 |
Приложение 7. Варианты схем алгоритмов....................................... |
187 |
Приложение 8. Варианты для сетевого графика |
|
и определения критического пути ..................................................... |
195 |
Приложение 9. Варианты определения кратчайшего пути ............. |
197 |
4
ВВЕДЕНИЕ
Считается, что всё началось с Эйлера, со знаменитой задачи о кёнигсбергских мостах (1736 г.) [1] (рис. 1).
Рис. В1. Марка СССР, посвящённая юбилею Эйлера
Но упоминаний о пребывании Эйлера в Кёнигсберге найдено не было. В 1752 г. Эйлер опубликовал формулу, связывающую между собой количество граней трёхмерного многогранника:
В + Г = Р + 2,
где В – количество вершин, Г – количество граней, Р – количество рёбер.
Однако ещё в 1620 г. Рене Декарт показал, что сумма углов всех граней многогранника равна одновременно 360° (Р – Г)
и 360° (В – 2).
Более строгое доказательство формулы Эйлера дал Коши в 1811 г.
Оказывается, соотношение Эйлера справедливо не для любых многогранников. Симон Люилье в 1812 г. (фр. Simon Antoine
5
РенеДекарт |
ОгюстЛуиКоши |
(1596–1650) |
(фр. Augustin Louis Cauchy; |
|
1789–1857) |
Jean L'Huilier, иногда L’Huillier, 1750–1840), швейцарский мате-
матик французского происхождения, при рассмотрении коллекции минералов обратил внимание на прозрачный кристалл полевого шпата, внутри которого был чёрный кубический кристалл сернистого свинца (рис. В2–В4).
Рис. В2. Полевойшпат |
Рис. В3. Галени́т(отлат. Galena – |
|
свинцоваяруда, окалина) |
6
Рис. В4. Кристаллическая структура галенита (Pb + S)
Люилье догадался, что куб с кубической полостью внутри не подчиняется формуле Эйлера. Позже были обнаружены и другие объекты, в которых формула Эйлера не выполнялась, например, два тетраэдра, склеенные по ребру или имеющие общую вершину. Теорема Эйлера была уточнена: она верна для многогранников, топологически эквивалентных сфере.
Рассмотрим куб как бы со стеклянными внешними и внутренними гранями (рис. В5).
Рис. В5. Куб в кубе
7
Тогда имеем 12 рёбер внешнего куба, 6 граней внешнего куба и 8 внешних вершин. Те же цифры для внутреннего куба. Всё верно: 16 + 12 не равно 24 + 2. Но вот другой куб – 4-мерный (шесть «громкоговорителей» – «рупоров») (рис. В6).
Рис. В6. Куб с 18 гранями
По низу – 4 грани (они, грани, двухсторонние, но считаем одну), по верху 4, итого 8, «боковушки» – 4 штуки + 6 внутренний кубик, итого 18. Вершин: 8 внешнего куба, 8 – внутреннего, рёбер 12 внешних и 12 внутренних:
В + Г = Р + 2 16 + 18 = 32 + 2.
Всё сходится!
В 1899 г. Пуанкаре обобщил формулу Эйлера на случай N-мерного многогранника.
Здесь мы уже вторгаемся в топологию… Но кто его знает, может топологические нюансы когда-то и будут использоваться в своих корыстных целях нарушителями не только информационной, но и, может быть, пространственно-временной безопасно-
8
сти. Злоумышленники, они есть всегда. Не хочется в это верить, но кто мог подумать в начале эры ЭВМ-компьютеров о каких-то компьютерных вирусах, хакерах и о прочей напасти… А они таки появились.
Жюль Анри́Пуанкаре́
(фр. Jules Henri Poincaré; 1854–1912) –
французский математик, механик, физик, астроном и философ
Теория графов, помимо чисто математических приложений, например, в такой специфической области, как теория групп, применяемая в кодировании как помехоустойчивом, так и с целью шифрования, стала бурно развиваться в ХХ в. на фоне создания и совершенствования первых ЭВМ, на фоне зарождения информатики, информационных технологий и систем.
Автоморфизм алгебраической системы – изоморфизм (от др.-греч. ἴσος – «равный, одинаковый, подобный» и μορφή – «форма»), отображающий алгебраическую систему на себя. Совокупность всех автоморфизмов некоторой алгебраической системы с операцией композиции и тождественным отображением в качестве нейтрального элемента образует группу (рис. В7).
9
Рис. В7. Группа автоморфизмов
10