Методические рекомендации по выполнению практических работ по междисциплинарному курсу «МДК.01.02. Математический аппарат для построения компьютерных сетей»
Методические рекомендации по выполнению практических работ по междисциплинарному курсу «МДК.01.02. Математический аппарат для построения компьютерных сетей» по разделу «Теория графов» для специальности «Компьютерные сети». Настоящие методические рекомендации определяют цели и задачи, порядок выполнения, содержат требования к выполнению практических работ и необходимы теоретический материал для их выполнения. Составлено преподавателем КГБ ПОУ ХМТ Богдановой Т.С.
Содержание
1
Практическая работа № 1. Графическое изображение графов ..
4
2
Практическая работа № 2. Решение задач по теории графов. Эйлеровы и Гамильтоновы графы
13
3
Практическая работа № 3. Решение задач по теории графов. Конечные графы. Бесконечные графы ..
19
4
Практическая работа № 4. Решение задач по теории графов
23
5
Практическая работа № 5. Решение задач по теории графов. Алгоритм «Краскаля» .
27
6
Практическая работа № 6. Решение задач по теории графов. Построение матриц смежностей и инциденций ...
33
7
Практическая работа № 7. Решение задач по теории графов. Выделение связных компонентов. Нахождение максимального потока и минимального разреза .
38
8
Практическая работа № 8. Решение задач по теории графов. Нахождение путей в графе .
48
9
Практическая работа № 9. Решение задач по теории графов. Нахождение кратчайшего пути ..
60
Практическая работа № 1
Тема: Графическое изображение графов.
Цель: изучить основы теоретико-множественного и графического представлений графов, простейших свойств графов, получить практический навык задания и визуализации графа на плоскости; закрепить навыки построения графов по образцу в графических средах (программы для графического представления графов).
Задачи:
1. Закрепить знания основных понятий теории графов.
2. Приобрести практические умения использования специального программного обеспечения для моделирования.
Материальное обеспечение:
Программы для графического представления графов: grin_rus, Grafoanalizator1.3.3 rus, windisc ru.
Теоретическая часть:
Графические представления в широком смысле – любые наглядные отображения исследуемой системы, процесса, явления на плоскости. К ним могут быть отнесены рисунки, чертежи, графики зависимостей характеристик, планы-карты местности, блок-схемы процессов, диаграммы и т. д. Такие изображения наглядно представляют различные взаимосвязи, взаимообусловленности: топологическое (пространственное) расположение объектов, хронологические (временные) зависимости процессов и явлений, логические, структурные, причинно-следственные и другие взаимосвязи.
Графические представления – удобный способ иллюстрации содержания различных понятий, относящихся к другим способам формализованных представлений (например, диаграммы Венна и другие графические иллюстрации основных теоретико-множественных и логических представлений).
Всё более распространенными становятся представления количественных характеристик, взаимосвязей между объектами в виде разного рода одно-, двух- и более мерных гистограмм, круговых диаграмм, других аналогичных способов представления в виде тех или иных геометрических фигур, по наглядным характеристикам которых (высоте, ширине, площади, радиусу и пр.) можно судить о количественных соотношениях сравниваемых объектов, значительно упрощая их анализ.
Мощным и наиболее исследованным классом объектов, относящихся к графическим представлениям, являются так называемые графы, изучаемые в теории графов.
Теория графов – это раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Как прикладная дисциплина теория графов позволяет описывать и исследовать многие технические, экономические, биологические и социальные системы.
Основные понятия теории графов
Граф – это система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий (геометрический способ задания графа – см. рисунок 1). Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – рёбрами.
Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным; граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным.
Теория графов может рассматриваться как раздел дискретной математики (точнее – теории множеств), и тогда определение графа таково:
Граф – это конечное множество Х, состоящее из n элементов 13EMBED Equation.31415 называемых вершинами графа, и подмножество V декартова произведения 13EMBED Equation.31415 называемое множеством дуг.
Ориентированным графом G (орграфом) называется совокупность (Х, V).
Неориентированным графом называется совокупность множеств Х и множества неупорядоченных пар элементов, каждый из которых принадлежит множеству Х.
Дугу между вершинами i и j, 13EMBED Equation.31415 будем обозначать (i, j). Число дуг графа будем обозначать 13EMBED Equation.31415
Подграфом называется часть графа, образованная подмножеством вершин вместе со всеми рёбрами (дугами), соединяющими вершины из этого множества. Если в графе удалить часть рёбер (дуг), то получим частичный граф.
Две вершины называются смежными, если они соединены ребром (дугой). Смежные вершины называются граничными вершинами соответствующего ребра (дуги), а это ребро (дуга) - инцидентным соответствующим вершинам.
Граф называется полным, если каждые две вершины его соединены одним и только одним ребром.
Граф, для которого из 13EMBED Equation.31415 следует 13EMBED Equation.31415 называется симметричным. Если из 13EMBED Equation.31415 следует 13EMBED Equation.31415, то соответствующий граф называется антисимметричным.
Язык графов оказывается удобным для описания многих физических, технических, экономических, биологических, социальных и других систем.
Вершины в графе могут отличаться друг от друга тем, скольким рёбрам они принадлежат.
Степень вершины называется число рёбер графа, которым принадлежит эта вершина. Степень графа ещё называют его валентностью и обозначают 13EMBED Equation.31415. Вершина графа, для которой 13EMBED Equation.31415 является изолированной, для которой 13EMBED Equation.31415висячей.
Вершина называется нечётной, если 13EMBED Equation.31415 нечётное число. Вершина называется чётной, если 13EMBED Equation.31415чётное число. Степень каждой вершины полного графа на единицу меньше числа его вершин.
В графе 13EMBED Equation.31415сумма степеней всех его вершин – число чётное, равное удвоенному числу рёбер графа. Число нечётных вершин любого графа чётно. Во всяком графе с n вершинами, где 13EMBED Equation.31415всегда найдутся, по меньшей мере, две вершины с одинаковыми степенями.
Если в графе с n вершинами 13EMBED Equation.31415 в точности две вершины имеют одинаковую степень, то в этом графе всегда найдётся либо в точности одна вершина степени 0, либо в точности одна вершина степени 13EMBED Equation.31415
Маршруты, цепи, циклы
Маршрутом в графе называется чередующаяся последовательность вершин и рёбер, в которой любые два соседних элемента инцидентны: 13EMBED Equation.31415
Если 13EMBED Equation.31415 то маршрут замкнут, в противном случае открыт.
Путём называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги.
Простой путь – путь, в котором ни одна дуга не встречается дважды.
Контур – путь, у которого конечная вершина совпадает с начальной вершиной.
Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы).
Цепью называется множество рёбер (в неориентированном графе), которые можно расположить так, что конец (в этом расположении) одного ребра является началом другого. Другое определение: цепь – последовательность смежных вершин. Замкнутая цепь называется циклом. Можно определить простые и элементарные цепи.
Элементарная цепь (цикл, путь, контур), проходящая через все вершины графа называется гамильтоновой цепью.
Простая цепь (цикл, путь, контур), содержащая все рёбра (дуги) графа называется эйлеровой цепью.
Если любые две вершины графа можно соединить цепью, то граф называется связным. Если граф не является связным, то его можно разбить на связные подграфы, называемые компонентами.
Связностью графа называется минимальное число рёбер, после удаления которых граф становится несвязным.
Ориентированные графы
Если элементы множества Е графа 13EMBED Equation.31415упорядоченные пары, то граф называется ориентированным или орграфом.
Ребро 13EMBED Equation.31415 графа G называется ориентированным, если одну вершину считают началом ребра, а другую – концом, на рисунке его изображают стрелкой между вершинами. Таким образом, граф, все рёбра которого ориентированы, называется ориентированным графом.
Одна и та же вершина ориентированного графа может служить началом для одних рёбер и концом для других, поэтому различают две степени вершины: степень выхода и степень входа.
Степенью выхода вершины орграфа называется число выходящих из вершины рёбер.
Степенью входа вершины орграфа называется число входящих в вершину рёбер.
В орграфах в зависимости от сочетаний степеней входа и выхода для данной вершины рассматривается три случая.
Изолированной вершиной называется вершина, у которой и степень входа и степень выхода равна 0.
Источником называется вершина, степень выхода которой положительна, а степень входа равна 0.
Стоком называется вершина, степень входа которой положительна, а степень выхода равна 0.
Путём в ориентированном графе называется последовательность ориентированных рёбер, т. е. для орграфов цепь называется путём.
Простым путём в ориентированном графе называется путь, в котором ни одна вершина не содержится более одного раза.
Замкнутый путь в ориентированном графе называется ориентированным циклом или контуром.
Длиной пути называется число рёбер в этом пути.
Полным ориентированным графом называется граф, каждая пара вершин которого соединена в точности одним ориентированным ребром.
Всякий полный ориентированный граф с n вершинами имеет простой ориентированный путь, проходящий через все вершины графа.
Петлёй называется ребро, у которого начальная и конечная вершины совпадают. Петля обычно считается неориентированной.
Мультиграфом называется граф, в котором пара вершин соединяется несколькими различными рёбрами. Для ориентированного мультиграфа вершины 13EMBED Equation.31415 и 13EMBED Equation.31415 могут соединяться несколькими рёбрами в каждом из направлений.
Изоморфизм графов
Два графа 13EMBED Equation.31415 и 13EMBED Equation.31415 называются изоморфными, если между множествами их вершин существует биективное (взаимнооднозначное) соответствие, такое, что вершины соединены рёбрами в одном из графов в том и только в том случае, когда соответствующие им вершины соединены в другом графе. Если рёбра ориентированы, то их направление в изоморфных графах должно совпадать. Изоморфизм графов есть отношение эквивалентности, так как обладает свойствами рефлексивности, симметричности, транзитивности. Для того чтобы граф 13EMBED Equation.31415 был изоморфен графу 13EMBED Equation.31415 необходимо и достаточно существования такой подстановки, которая бы установила взаимнооднозначное соответствие между вершинами графа, а также между их рёбрами.
При замене графа любым ему изоморфным все свойства графа сохраняются. Строго говоря, графы отличающиеся только нумерацией вершин, являются изоморфными.
Алгоритм распознания изоморфизма двух графов 13EMBED Equation.31415 и 13EMBED Equation.31415
1. Подсчитаем число вершин каждого графа (число вершин должно совпадать, в противном случае графы неизоморфные).
2. Выписываем все элементы обоих графов в естественной упорядоченности и определяем пары 13EMBED Equation.31415 и 13EMBED Equation.31415 для каждого элемента, где 13EMBED Equation.31415 число исходов для каждой вершины графов 13EMBED Equation.31415 и 13EMBED Equation.31415, а 13EMBED Equation.31415 число заходов для соответствующих графов.
3. Для каждого элемента х графа 13EMBED Equation.31415 ищем такой элемент у графа 13EMBED Equation.31415 что выполняется условие: число исходов х совпадает с числом исходов у, и число заходов х совпадает с числом заходов у. Найденные элементы х и у соединяем ребром, т. е. строим граф соответствия (если соответствия нет, то графы не изоморфны).
4. Выписываем подстановку, которая переводит граф 13EMBED Equation.31415 в граф 13EMBED Equation.31415.
Плоские графы
Граф 13EMBED Equation.31415 называется плоским, если на плоскости его можно изобразить так, что все пересечения его рёбер являются вершинами графа 13EMBED Equation.31415.
В качестве характеристики плоского представления графа вводится понятие грани.
Гранью в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов.
Операции над графами
Рассмотрим графы 13EMBED Equation.31415 и 13EMBED Equation.31415
а) Дополнением графа 13EMBED Equation.31415 называется граф 13EMBED Equation.31415 множеством вершин которого является множество 13EMBED Equation.31415 а множеством его рёбер является множество 13EMBED Equation.31415
б) Объединением графов 13EMBED Equation.31415 и 13EMBED Equation.31415 при условии, что 13EMBED Equation.31415 13EMBED Equation.31415 называется граф 13EMBED Equation.31415 множеством вершин которого является множество 13EMBED Equation.31415 а множеством его рёбер является множество 13EMBED Equation.31415
в) Пересечением графов 13EMBED Equation.31415 и 13EMBED Equation.31415 называется граф 13EMBED Equation.31415 множеством вершин которого является множество 13EMBED Equation.31415 а множеством его рёбер является множество 13EMBED Equation.31415
г) Суммой по модулю два графов 13EMBED Equation.31415 и 13EMBED Equation.31415 при условии, что 13EMBED Equation.31415 13EMBED Equation.31415называется граф 13EMBED Equation.31415 множеством вершин которого является множество 13EMBED Equation.31415 а множеством его рёбер – множество 13EMBED Equation.31415 Т. е. этот граф не имеет изолированных вершин и состоит только из рёбер, присутствующих либо в первом графе, либо во втором графе, но не в обоих графах одновременно.
Способы задания графов
Существуют три эквивалентных способа задания графов: аналитический, геометрический и матричный. Рассмотрим каждый из них.
Аналитический способ задания графов
Граф 13EMBED Equation.31415 задан, если задано множество элементов V и отображение E множеств V в V. Отображение Е может быть как однозначным, так и многозначным.
Пусть дано множество 13EMBED Equation.31415 которое имеет мощность 13EMBED Equation.31415
Для того чтобы задать отображение Е на V , необходимо каждому элементу 13EMBED Equation.31415 поставить в соответствие некоторое подмножество множества V, которому соответствует отображение Е. Это подмножество обозначают через 13EMBED Equation.31415 Поэтому 13EMBED Equation.31415 Совокупность двух объектов: множества V и отображение Е на V задаёт некоторый граф.
Другой формой аналитического способа задания является задание графа как совокупности множества элементов V и подмножества множества упорядоченных пар 13EMBED Equation.31415
Геометрический способ задания графов
Множество элементов V графа G изображают кружками, это множество вершин. Каждую вершину 13EMBED Equation.31415 соединяют линиями с теми вершинами 13EMBED Equation.31415, для которых выполняется условие 13EMBED Equation.31415 Множество линий, которое соответствует множеству упорядоченных пар 13EMBED Equation.31415 есть множество рёбер.
Матричный способ задания графов
Квадратная матрица 13EMBED Equation.31415 элементами которой являются нули и единицы, а также некоторое число m, называется матрицей смежности графа 13EMBED Equation.31415 тогда и только тогда, когда её элементы образуются по следующему правилу: элемент 13EMBED Equation.31415 стоящий на пересечении 13EMBED Equation.31415 й строки и 13EMBED Equation.31415го столбца, равен единице, если имеется ребро, идущее из вершины 13EMBED Equation.31415 в вершину 13EMBED Equation.31415 и 13EMBED Equation.31415 равен нулю в противном случае. Элемент 13EMBED Equation.31415 равен единице, если при вершине 13EMBED Equation.31415 имеется петля, и равен нулю в противном случае. Элемент 13EMBED Equation.31415 равен некоторому числу m, где m – число рёбер графа, идущее из вершины 13EMBED Equation.31415 в вершину 13EMBED Equation.31415
Таким образом, если граф 13EMBED Equation.31415 задан одним из указанных способов: аналитическим, геометрическим или матричным, всегда можно перейти к любому другому способу задания. Наиболее часто для задания графа используется аналитический и матричный способы, а геометрический способ служит для иллюстрации полученных результатов.
Инструкция к практической работе
Задание 1. Изобразите графически:
Неориентированное и ориентированное ребро;
Неориентированный граф G(V,E), заданный множеством V={v0, v1, v2, v3, v4, v5} E(v0)={v1,v2}={v0,v2,v4}; E(v1)={v0,v2,v4}; E(v2)={v0,v1,v5}; E(v3)={v4}; E(v5)={v2};
Плоский граф;
Полный неориентированный граф на трех, четырех и пяти вершинах;
Неполный ориентированный граф на пяти вершинах;
Петлю графа;
Неориентированный и ориентированный мультиграф.
Решение:
1) Неориентированное ребро ориентированное ребро
Задание 2. Изобразить графы в программах:
grin_rus, Grafoanalizator1.3.3 rus, windisc ru.
Задание:
Вариант № 1
Задание 1. Выполните задание по образцу.
Изобразите графически:
G(V,E) - орграф.
V={1,2,3,4}, E={(1, 2), (4, 3), (3, 4), (3, 1), (4, 1)}.
Задание 2. Изобразите графы в соответствующих программах. Полученные графы сохранить в свои папки.
Граф
Программа
Grafoanalizator1.3.3 rus
grin_rus
windisc ru
Вариант № 2
Задание 1. Выполните задание по образцу.
Изобразите графически:
G(V,E) - орграф.
V={1,2,3,4,5}, E={(1, 2), (4, 3), (3, 5), (5, 1), (4, 1)}.
Задание 2. Изобразите графы в соответствующих программах. Полученные графы сохранить в свои папки.
Граф
Программа
Grafoanalizator1.3.3 rus
grin_rus
windisc ru
Вариант № 3
Задание 1. Выполните задание по образцу.
Изобразите графически:
G(V,E) - орграф.
V={1,2,3,4,5}, E={(1, 3), (2, 3), (1, 5), (2, 4), (1, 2)}.
Задание 2. Изобразите графы в соответствующих программах. Полученные графы сохранить в свои папки.
Граф
Программа
Grafoanalizator1.3.3 rus
grin_rus
windisc ru
Вариант № 4
Задание 1. Выполните задание по образцу.
Изобразите графически:
G(V,E) - орграф.
V={1,2,3,4,5,6}, E={(1, 6), (4, 5), (1, 2), (2, 3), (3, 6)}.
Задание 2. Изобразите графы в соответствующих программах. Полученные графы сохранить в свои папки.
Граф
Программа
Grafoanalizator1.3.3 rus
grin_rus
windisc ru
Порядок выполнения работы:
1. Изучить инструкцию к практической работе.
2. Выполнить задание.
3. Оформить отчет.
Содержание отчета:
1. Тема.
2. Цель.
3. Задачи.
4. Материальное обеспечение.
5. Практическое задание.
Вопросы для самоконтроля:
Что называется графом? Ориентированным графом? Приведите примеры.
Что такое степень вершины?
Перечислите основные понятия, связанные с неориентированными графами.
Перечислите основные понятия, связанные с орграфами.
В чем состоит аналитический способ задания графа?
В чем состоит геометрический способ задания графа?
В чем состоит матричный способ задания графа?
Что называется маршрутом, циклом и цепью графа?
Сформулируйте понятие связности графа. Какой граф называют связным?
Какие два графа называются изоморфными?
Сформулируйте алгоритм изоморфизма двух графов.
Перечислите операции над графами.
Практическая работа № 2
Тема: Решение задач по теории графов. Эйлеровы и Гамильтоновы графы.
Цель: изучить алгоритм поиска эйлерова, гамильтонова цикла (пути) в графе, рассмотреть на конкретных примерах ориентированные и неориентированные графы.
Задачи:
1. Закрепить знания основных понятий теории графов.
2. Приобрести практические умения использования специального программного обеспечения для моделирования.
3. Использовать математический аппарат теории графов
Материальное обеспечение:
Программа анализатор графов: Grafoanalizator1.3.3 rus, практическое задание.
Теоретическая часть:
Эйлеровы графы
К задачам на Эйлеровы графы относятся головоломки, в которых требуется вычертить на плоскости одним росчерком замкнутые кривые, обводя каждый участок в точности один раз. Введём следующие понятия.
Эйлеровым путём в графе называется путь, содержащий все рёбра графа.
Эйлеровым циклом или эйлеровой цепью называется цикл, содержащий все рёбра графа и притом по одному разу.
Граф, обладающий эйлеровым циклом, называется эйлеровым графом.
Замкнутую линию, если её можно начертить, не отрывая карандаша от бумаги, проходя при этом каждый участок в точности один раз, принято называть уникурсальной.
Рисунок графа, обладающий эйлеровым путём или эйлеровым циклом, является уникурсальной линией.
Докажем следующие две теоремы
Теорема 1. Если граф 13EMBED Equation.31415 обладает эйлеровым циклом, то он связный и все его вершины четные.
Доказательство. Связность графа следует из определения эйлерова цикла. Эйлеров цикл содержит каждое ребро и притом только один раз, поэтому, сколько раз эйлеров путь приведет конец карандаша в вершину, столько и выведет, причём уже по одному ребру. Следовательно, степень каждой вершины графа должна состоять из двух одинаковых слагаемых: одно – результат подсчета входов в вершину, другое – выходов.
Теорема 2. Если граф 13EMBED Equation.31415 связный и все его вершины четные, то он обладает эйлеровым циклом.
Доказательство. Если начать путь из произвольной вершины графа 13EMBED Equation.31415, то найдётся цикл, содержащий все рёбра графа. Пусть 13EMBED Equation.31415- произвольная вершина. Из 13EMBED Equation.31415 начнём путь по l по одному из рёбер и продолжим его, проходя каждый раз по новому ребру. Все вершины графа имеют чётные степени, поэтому если l есть «выход» из 13EMBED Equation.31415, то должен быть и «вход» в 13EMBED Equation.31415, также как и для любой вершины другой вершины. И если есть «вход» в вершину, то должен быть и «выход». Так как число ребер конечно, то это путь должен окончиться, причём в вершине 13EMBED Equation.31415. Если путь, замкнувшийся в 13EMBED Equation.31415, проходит через все рёбра графа, то мы получим искомый эйлеров цикл.
Для построения эйлерова цикла в связном графе со всеми вершинами чётной степени применяется следующий алгоритм:
1. Выйти из произвольной вершины 13EMBED Equation.31415. Каждое пройденное ребро зачеркнуть. Если путь 13EMBED Equation.31415 замыкается в 13EMBED Equation.31415 и проходит через все рёбра графа, то получим искомый эйлеров цикл.
2. Если остались непройденные рёбра, то должна существовать вершина 13EMBED Equation.31415 принадлежащая 13EMBED Equation.31415 и ребру, не вошедшему в 13EMBED Equation.31415
3. Так как 13EMBED Equation.31415чётная, то число рёбер, которым принадлежит 13EMBED Equation.31415и которые не вошли в путь 13EMBED Equation.31415 тоже чётно. Начнём новый путь 13EMBED Equation.31415 из 13EMBED Equation.31415 и используем только рёбра, не принадлежащие 13EMBED Equation.31415 Этот путь кончится в 13EMBED Equation.31415
4. Объединим теперь оба цикла: из 13EMBED Equation.31415 пройдём по пути 13EMBED Equation.31415к 13EMBED Equation.31415 затем по 13EMBED Equation.31415 и, вернувшись в 13EMBED Equation.31415 пройдём по оставшейся части 13EMBED Equation.31415 обратно в 13EMBED Equation.31415.
5. Если снова найдутся рёбра, которые не вошли в путь, то найдём новые циклы. Так как число рёбер и вершин конечно, то процесс закончится.
Таким образом, замкнутую фигуру, в которой все вершины чётные, можно начертить одним росчерком без повторений и начиная с любой точки.
На практике эйлеровым графом может быть план выставки; это позволяет расставить указатели маршрута, чтобы посетитель смог пройти по каждому залу в точности по одному разу.
Гамильтоновы графы
Граф, обладающий гамильтоновым циклом, называется гамильтоновым графом.
Гамильтоновым циклом, или путём в графе, называется цикл, или путь, проходящий через каждую вершину графа в точности по одному разу.
Эйлеровы и гамильтоновы пути сходны по способу задания. Первые содержат все рёбра, и притом по одному разу, вторые – все вершины по одному разу. Но, несмотря на внешнее сходство, задачи их отыскания резко отличаются по степени трудности. Для решения вопроса о существовании эйлерова цикла в графе достаточно выяснить, все ли его вершины чётные.
Критерий же существования гамильтонова цикла на произвольном графе ещё не найден.
Однако есть несколько достаточных условий существования гамильтоновых циклов в графе:
1. Всякий полный граф является гамильтоновым, так как он содержит простой цикл, которому принадлежат все вершины данного графа.
2. Если граф, помимо простого цикла, проходящего через все его вершины, содержит и другие рёбра, то он также является гамильтоновым.
3. Если граф имеет один гамильтонов цикл, то он может иметь и другие гамильтоновы циклы.
Алгоритма проверки существования эйлерова пути
Представим динамику выполнения алгоритма проверки существования эйлерова пути (цикла) из вершины 0 для представленного на рисунке 1 графа. Цикл существует. Рисунок 1
Например, один из возможных путей прохождения всех ребер графа из вершины 0 может быть следующим: 0 – 1 – 2 – 0 – 6 – 4 – 2 – 3 – 4 – 5 – 0 В приведенном списке вершин, следующих за 0, каждая вершина является одновременно концом предыдущего ребра и началом следующего. В соответствии с алгоритмом: 0 – степень 4; 1 – 2; 2 – 4; 3 – 2; 4 – 4; 5 – 2; 6 – 2; Степени всех вершин четные, следовательно, эйлеров цикл в данном графе существует.
Рисунок 2
Граф, изображенный на рисунке 2 отличается от рисунка 1 только добавлением ребра (3 – 5). При этом степени вершин 3 и 5 стали нечетными. Согласно алгоритму проверки существования эйлерова цикла, основывающемуся на проверке четности степени каждой вершины, в данном графе цикла быть не может. Однако, если учесть следствие, по которому в точности две вершины имеют нечетную степень, то и в графе, изображенном на рисунке 1 должен существовать эйлеров путь. Пример такого пути: 3 – 2 – 4- 3 – 5 – 4 – 6 – 0 – 2 – 1 – 0 – 5. При этом две вершины, имеющие нечетную степень, находятся на концах такого пути.
Алгоритма поиска гамильтонова пути
Представим динамику выполнения рекурсивного алгоритма поиска гамильтонова пути (цикла) из вершины 0 для графа, представленного на рисунке 3.
Рисунке 3. Цикла не существует. 0-1 1-2 2-3 3-4 4-5 4-6 2-4 4-3 4-5 4-6 0-2 2-1 2-3 3-4 4-5 4-6 2-4 4-3 4-5 4-6 0-5 5-4 4-2 2-1 2-3 4-3 3-2 2-1 4-6 0-6 6-4 4-2 2-1 4-3 3-2 2-1 4-5 Представим динамику выполнения рекурсивного алгоритма поиска гамильтонова пути для представленного на рисунке 4 графа.
Цикл существует, например: 0 – 6 – 4 – 2 – 1 – 3 – 5 – 0. Рисунке 4. Продемонстрируем поиск цикла от вершины 1. 1-0 0-5 5-3 3-2 2-4 4-6 3-4 4-2 4-6 5-4 4-2 2-3 4-6 0-6 6-4 4-2 2-3 3-5 4-3 3-2 3-5 4-5 5-3 3-2 2-1
Искомый путь 1 – 0 – 6 – 4 – 5- 3 – 2 – 1 .
Инструкция к практической работе
1. Существует ли эйлеров цикл в графе G. Если существует, найдите его.
Решение:
А) Так как каждая вершина имеет чётную степень, то по критерию в этом графе существует эйлеров цикл: 1,4,6,9,10,8,5,3,2,4,7,10,11,8,6,5,2,1
Б) В этом графе также каждая вершина имеет чётную степень, значит, существует и эйлеров цикл: 1,2,3,4,5,3,1,4,5,2,1
В) Здесь каждая вершина имеет степень 5, то есть нечётную, следовательно, в этом графе (по критерию) нет эйлерова цикла.
2. Какие из следующих ориентированных графов имеют эйлеровы циклы?
Решение:
а) Граф связный, найдём степени входа и выхода вершин (по теореме 5 степени входа и выхода каждой вершины должны совпадать):
indeg(a)=2, outdeg(a)=1, то есть нашлась вершина, у которой не совпадают степени входа и выхода, значит, граф не имеет эйлерова цикла.
б) Граф связный, найдём степени вершин:
indeg(a)=2 outdeg(a)=2
indeg(b)=2 outdeg(b)=2
indeg(c)=2 outdeg(c)=2
indeg(d)=2 outdeg(d)=2
indeg(e)=2 outdeg(e)=2
Следовательно, по теореме 5, граф имеет эйлеров цикл.
в) Граф связный, найдём степени вершин:
indeg(a)=2 outdeg(a)=2
indeg(b)=1 outdeg(b)=1
indeg(c)=3 outdeg(c)=1
Условия теоремы 5 не выполняются, значит, граф не имеет эйлерова цикла.
г) Граф связный, найдём степени вершин:
indeg(a)=2 outdeg(a)=1
Следовательно, т.к. условия теоремы 5 не выполняются то, граф не имеет эйлерова цикла.
2. Задача. Найдите эйлеров цикл в эйлеровом графе
Решение. После выбора вершины а и прохождении рёбер 1 и 2 имеются три возможности выбора: рёбра 3, 6 или 7. Выбираем ребро 3 или 6. Например, ребро 3. Далее обходим оставшиеся рёбра и получаем эйлеров цикл 1, 2, 3, 4, 5, 6, 7, 8.
3.Задача. Найдите цикл, содержащий все вершины додекаэдра, причём в точности по одному разу каждую.
Решение.
Этот цикл: 1, 2, 3, 4, 5, 6, 19, 18, 14, 15, 16, 17, 7, 8, 9, 10, 11, 12, 13, 20.
Этот цикл называется гамильтоновым циклом.
Задание:
1. Проработать алгоритм выполнения поиска эйлерова и гамильтонова пути (изобразите графы, содержащие эти пути)
2. Среди приведённых ниже графов найдите те, которые имеют эйлеров и гамильтонов цикл. Результат проверить при помощи программы Grafoanalizator1.3.3.
2. Какие из следующих ориентированных графов имеют эйлеровы и гамильтоновы циклы? Результат проверить при помощи программы Grafoanalizator1.3.3.
Порядок выполнения работы:
1. Изучить инструкцию к практической работе.
2. Выполнить задание.
3. Оформить отчет.
Содержание отчета:
1. Тема.
2. Цель.
3. Задачи.
4. Материальное обеспечение.
5. Практическое задание.
Вопросы для самоконтроля:
Дайте определение эйлерова графа.
Сформулируйте алгоритм построения эйлерова цикла.
Какой граф называют гамильтоновым?
Существует ли эйлеров граф, обладающий висячей вершиной?
Чем отличается эйлеров путь от гамильтонова?
Практическая работа № 3
Тема: Решение задач по теории графов. Конечные графы. Бесконечные графы.
Цель: изучить теоретические основы конечных и бесконечных графов.
Задачи:
1.Закрепить знания основных понятий теории конечных и бесконечных графов.
2. Использовать математический аппарат теории графов
Материальное обеспечение:
практическое задание.
Теоретическая часть:
Конечный граф
Граф называется конечным, если число вершин и ребер в нем конечно, в противном случае – бесконечным.
Рассмотрим неориентированный граф G. Число ребер
·(v), инцидентных вершине v, назовем локальной степенью графа в вершине v.
Если все числа
·(v) для (v(V, то граф называется локально-конечным.
Обозначим
·(v,u) =
·(u,v) – это число ребер, соединяющих вершины v и u, т.е. это кратность ребра (v,u). Тогда
13EMBED Equation.31415
Обозначим m(G) – число ребер в графе G. Т.к. каждое ребро будет учитываться в двух локальных степенях v и u, то запишем:
(1)
Теорема. Число вершин нечетной локальной степени в графе четно.
Доказательство. Воспользуемся формулой (1), т.е. сумма всех локальных степеней четна. Тогда, удалив из суммы все четные слагаемые, получим четное число, представляющее собой сумму нечетных степеней. Теорема доказана.
Граф называется однородным в степени k, если локальные степени всех вершин равны k. Примерами однородных графов являются правильные треугольники, многоугольники, многогранники.
Для однородных графов можно записать:
13EMBED Equation.31415,
где n – число вершин графа G.
Для куба:
13EMBED Equation.31415
Пусть G – ориентированный граф. Тогда введем следующие обозначения:
od(v) – число дуг, выходящих из вершины;
id(v) – число дуг, заходящих в вершину.
Это локальные степени графа.
Петли, если они есть, считаются по одному разу и в od(v), и в id(v).
Аналогично считаются две кратности. Обозначим как
·o(v,u),
·i(v,u) число дуг, выходящих из v в u и из u в v соответственно.
13EMBED Equation.31415
13EMBED Equation.31415
13EMBED Equation.31415
13EMBED Equation.31415
Ориентированный граф называется однородным, если для (v(V выполняется следующее: od(v) = id(v) = k.
Бесконечный граф
Примеры бесконечных однородных графов.
Бесконечные однородные графы находят широкое применение в задачах трассировки печатных соединений, т.к. их использование позволяет разбивать коммутационное поле печатных плат на элементарные ячейки одинаковой формы.
Бесконечным графом называется пара , , где бесконечное множество элементов, называемое вершинами, а бесконечное семейство неупорядоченных пар элементов из , называемых ребрами.
Если оба множества и счетны, то называется счетным графом. Заметим, что наши определения исключают те случаи, когда бесконечно, а конечно. Такие объекты являются всего лишь конечными графами с бесконечным множеством изолированных вершин. Когда бесконечно, а конечно, такие объекты являются конечными графами с бесконечным числом петель или кратных ребер.
Некоторые определения таких понятий, как "смежный", "инцидентный", "изоморфный", "подграф", "объединение", "связный", "компонента" переносятся на бесконечные графы.
Степенью вершины бесконечного графа называется мощность множества ребер, инцидентных Степень вершины может быть конечной или бесконечной. Бесконечный граф, все вершины которого имеют конечные степени, называется локально конечным. Хорошо известным примером такого графа является бесконечная квадратная решетка, часть которой изображена на рисунке. Локально счетный бесконечный граф это граф, все вершины которого имеют счетную степень. Под счетным множеством здесь и в дальнейшем понимается бесконечное множество, допускающее взаимно однозначное отображение на множество натуральных чисел.
Теорема Каждый связный локально счетный бесконечный граф является счетным.
Доказательство
Пусть произвольная вершина такого бесконечного графа, и пусть множество вершин, смежных , множество всех вершин, смежных вершинам из , и т.д. По условию теоремы счетно и, следовательно, множества тоже счетны. Здесь используется тот факт, что объединение не более чем счетного множества счетных множеств счетно. Следовательно, последовательность множеств, объединение которых счетно. Кроме того, эта последовательность содержит каждую вершину бесконечного графа в силу его связности. Отсюда и следует нужный результат.
Следствие Каждый связный локально конечный бесконечный граф является счетным.
Помимо этого, на бесконечный граф можно перенести понятие маршрута, причем тремя различными способами:
Конечный маршрут в определяется так. Маршрутом в данном графе называется конечная последовательность ребер вида , . Маршрут можно обозначить и так: .
Бесконечным в одну сторону маршрутом в с начальной вершиной называется бесконечная последовательность ребер вида , .
Бесконечным в обе стороны маршрутом в графе называется бесконечная последовательность ребер вида ,
Бесконечные в одну сторону и в обе стороны цепи и простые цепи определяются очевидным образом, так же как и понятия длины цепи и расстояния между вершинами. Бесконечные простые цепи не так уж трудно обнаружить.
Теорема 6.1. (Кениг, 1936) Пусть связный локально конечный бесконечный граф, тогда для любой вершины существует бесконечная в одну сторону простая цепь с начальной вершиной .
Доказательство
Если произвольная вершина графа , отличная от , то существует нетривиальная простая цепь от до , отсюда следует, что в имеется бесконечно много простых цепей с начальной вершиной . Поскольку степень конечна, то бесконечное множество таких простых цепей должно начинаться с одного и того же ребра. Если таким ребром является , то, повторяя эту процедуру для вершины , получим новую вершину и соответствующее ей ребро . Продолжая таким образом, получим бесконечную в одну сторону простую цепь .
Важное значение леммы Кенига состоит в том, что она позволяет получить результаты о бесконечных графах из соответствующих результатов для конечных графов. Типичным примером является следующая теорема.
Теорема 6.2. Пусть счетный граф, каждый конечный подграф которого планарен, тогда и планарен.
Доказательство Так как счетный граф, его вершины можно занумеровать в последовательность . Исходя из нее, построим строго возрастающую последовательность подграфов графа , выбирая в качестве подграф с вершинами и ребрами графа , соединяющими только эти вершины между собой. Далее, примем на веру тот факт, что графы могут быть уложены на плоскости конечным числом, скажем , топологически различных способов, и построим еще один бесконечный граф . Его вершины , пусть соответствуют различным укладкам графов , а его ребра соединяют те из вершин и , для которых и плоская укладка, соответствующей . Мы видим, что граф связен и локально конечен, поэтому, как следует из леммы Кенига, он содержит бесконечную в одну сторону простую цепь. А так как граф является счетным, то эта бесконечная простая цепь и дает требуемую плоскую укладку графа .
Стоит подчеркнуть, что если принять дальнейшие аксиомы теории множеств, в частности, аксиому выбора для несчетных множеств, то многие результаты можно перенести и на такие бесконечные графы, которые необязательно являются счетными.
Задание
Изобразить конечные и бесконечные графы.
Определите, какие графы изображены
A
B
C
D
E
F
Проверьте правильность ответа: A, b – платоновы тела; c – неориентированный конечный однородный граф степени 2; d – неориентированный конечный однородный граф степени 1; е – неориентированный конечный однородный граф степени 4; f – ориентированный бесконечный однородный граф степени 2
Порядок выполнения работы:
1. Выполнить задание.
2. Оформить отчет.
Содержание отчета:
1. Тема.
2. Цель.
3. Задачи.
4. Материальное обеспечение.
5. Практическое задание.
Вопросы для самоконтроля:
1. Дайте определение конечного графа.
2. Дайте определение бесконечного графа.
3. Какой граф называется однородным?
4. Где применяются бесконечные графы?
Практическая работа № 4
Тема: Решение задач по теории графов
Цель: научиться применять математический аппарат теории графов в решении задач.
Задачи:
1.Закрепить знания основных понятий теории конечных и бесконечных графов.
2. Использовать математический аппарат теории графов
Материальное обеспечение: раздаточный материал.
Теоретическая часть:
Под графом мы будем понимать множество точек (вершин), некоторые из которых соединены отрезками (ребрами).
Степень вершины графа это количество выходящих из нее (или, что то же самое, входящих в нее) ребер (еще говорят: количество ребер, инцидентных данной вершине). Вершина графа называется четной, если ее степень четна, и нечетной в противном случае.
Некоторая часть вершин данного графа называется компонентой связности, если из любой ее вершины можно «дойти» до любой другой, двигаясь по ребрам.
В некоторых случаях на ребрах графа выбирается «направление движения» (например, когда на автомобильной дороге вводится одностороннее движение). При этом получается ориентированный граф. (Если направление движения по ребрам не определено, то граф называется неориентированным). В ориентированном графе различают положительную и отрицательную степень каждой вершины (то есть количество ребер, соответственно, входящих и выходящих из нее). Две вершины могут быть соединены и несколькими ребрами, направления движения по которым противоположны («дорога с двусторонним движением»). Изменяется понятие компоненты связности: теперь каждый «маршрут» от одной вершины до другой должен учитывать направление движения по ребрам.
Графовые задачи обладают рядом достоинств, позволяющих их использовать для развития воображения и улучшения логического мышления, применимы в решении многих геометрических задач.
На уроке геометрии было предложено построить граф классификации геометрических объектов. Это оказалось легко сделать с помощью понятия граф.
Задача о мостах
Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены.
Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды? Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.
Этот вопрос привлек внимание ученых разных стран. В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно).
Причем, он не только решил эту конкретную задачу, но придумал общий метод решения подобных задач. Эйлер поступил следующим образом: он «сжал» сушу в точки, а мосты « вытянул» в линии, как показано на рисунке 1 а, б.
Рисунок 1
На упрощённой схеме части города (графе) мостам соответствуют линии (рёбра графа), а частям города точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:
Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа всегда чётно. Невозможно начертить граф, который имел бы нечётное число нечётных вершин.
Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
Давайте четко сформулируем поставленную задачу. При каком условии можно обойти все ребра графа, пройдя каждое ровно один раз? Решение оказалось очень простым. Сосчитаем, сколько ребер выходит из каждой вершины. Одни из этих чисел будут четными, а другие - нечетными. Будем и сами вершины называть четными, если из них выходит четное число ребер, и нечетными в противном случае. Как мы уже знаем: количество ребер, выходящих из данной вершины, называется степенью вершины. Вершина графа, имеющая нечетную степень, называется нечетной, а четную степень – четной.
Граф кёнигсбергских мостов имел четыре нечётные вершины, следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
Решая задачу про кенигсбергские мосты, Эйлер установил, в частности, свойства графа:
Если все вершины графа четные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине.
Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение надо начинать от любой нечетной вершины, а закончить на другой нечетной вершине.
Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.
В задаче о кенигсбергских мостах все четыре вершины соответствующего графа нечетные, то есть нельзя пройти по всем мостам один раз и закончить путь там, где он был начат.
Задачи:
1. Между девятью планетами Cолнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля Меркурий, Плутон Венера, Земля Плутон, Плутон Меркурий, Меркурий Венера, Уран Нептун, Нептун Сатурн, Сатурн Юпитер, Юпитер Марс и Марс Уран. По каждому маршруту ракеты летают в обе стороны. Можно ли долететь на рейсовых ракетах от Земли до Марса?
2. В государстве 100 городов. Из каждого города выходит 4 дороги. Сколько всего дорог в государстве?
3. Экспозиция картинной галереи представляет собой систему коридоров, на обеих стенах которых развешаны картины:
Можно ли предложить такой маршрут осмотра экспозиции, при котором
посетитель проходит вдоль каждой стены ровно один раз?
4. В городе 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединён ровно с пятью другими?
5. В теннисном турнире каждый игрок команды «синих» встречается с каждым игроком команды «красных». Число игроков в командах одинаково и не больше восьми. «Синие» выиграли в четыре раза больше встреч, чем «красные». Сколько человек в каждой из команд?
6. Можно ли прогуляться по парку и его окрестностям так, чтобы при этом перелезть через каждый забор ровно один раз?
7. Можно ли нарисовать граф, изображённый на рисунках а,б
не отрывая карандаша от бумаги и проводя каждое ребро ровно один раз?
8. Дан кусок проволоки длиной 120 см.
Можно ли, не ломая проволоки, изготовить каркас куба с ребром 10 см? Какое наименьшее число раз придётся ломать проволоку, чтобы всё же изготовить требуемый каркас?
9. Можно ли так нарисовать 5 горизонтальных и 4 вертикальных отрезка, чтобы каждый горизонтальный отрезок пересекался ровно с тремя вертикальными, а каждый вертикальный ровно с тремя горизонтальными?
10. При встрече каждый из моих одноклассников пожал руку другому (каждый пожал каждому). Сколько рукопожатий было сделано, если друзей было: 1)трое; 2)четверо; 3)пятеро? (решите и изобразите граф решения)
Порядок выполнения работы:
1. Решить задачи.
2. Оформить отчет.
Содержание отчета:
1. Тема.
2. Цель.
3. Задачи.
4. Материальное обеспечение.
5. Практическое задание.
Вопросы для самоконтроля:
1. Как в задачах применяется ориентированный граф?
2. Какой граф можно начертить, не отрывая карандаша от бумаги, при этом можно начинать с любой вершины графа и завершить его в той же вершине?
3. Какое современное устройство решает задачу о кинесберских мостах?
4. Когда вершина графа называется четной, а когда нечетной?
Практическая работа № 5
Тема: Решение задач по теории графов. Алгоритм «Краскаля»
Цель: изучить и отработать навыки в применении алгоритма Краскала; закрепить навыки моделирования графов в графической среде Kraskal.
Задачи:
1. Закрепить знания основных понятий теории графов.
2. Приобрести практические умения использования специального программного обеспечения для моделирования.
3. Использовать математический аппарат теории графов
Материальное обеспечение:
Программы для вычисления алгоритма краскала: Kraskal
Теоретическая часть:
Остов графа (стягивающее дерево, spanning tree, ST) – дерево, полученное из графа, выбрасыванием части ребер.
Минимальный остов графа (стягивающее дерево минимального веса, Minimal Spanning Tree, MST) – остов, с минимальной суммой весов входящих в него ребер.
Алгоритм Краскала вычисляет для заданного взвешенного неориентированного графа остовное дерево с наименьшей суммой весов ребер остовное дерево наименьшего веса. В новой задаче множество вершин при поиске остовного дерева наименьшего веса не меняется.
Минимальный остов графа. Дан взвешенный граф.
Строим граф, присоединяя к пустому графу на множестве вершин заданного графа ребро наименьшего веса. К полученному графу последовательно присоединяем остальные ребра, выбирая на каждом шаге ребро наименьшего веса, не образующее цикл с имеющимися ребрами. В нашем случае начинаем с ребра весом 13 – наименьшего в графе. На рисунках дана последовательность действий. Ребро весом 19 не включается в остов, так как оно образует цикл с ребрами
весом 14 и 13.
Выполнение алгоритма Краскала:
1. Начальная фаза. Минимальный покрывающий лес пуст.
2. Перебираем ребра в порядке возрастания веса: первое ребро с весом 2. Добавляем его к А.
3. Следующее безопасное ребро с весом 6. Добавляем его.
4-8. Добавляем остальные безопасные ребра.
Пример выполнения алгоритма Краскаля. Заштрихованные ребра принадлежат растущему лесу.
Изучить инструкцию к практической работе.
Для запуска программы необходимо активировать exe – файл с названием «Краскал.exe» запустится программа. Рисунок главной формы изображен на ри сунке.
На главной форме программы изображены: текстовое поле необходимое для ввода количество узлов графа, для которого нужно будет найти остов мини мального веса, затем нужно нажать кнопку «ОК». Далее нужно занести веса в матрицу весов «Дано» вводить нужно только по горизонтали, а по вертикали программа заполнит поля автоматически. Далее нужно расставить узлы нашего графа, для этого одним щелчком по полю «Данный граф» создастся узел, он бу дет помечен синей точкой аналогично выполнить для остальных вершин графа. Также узлы можно расставить случайным образом, для этого нужно пометить флажок «Разместить узлы случайно» и нажать кнопку «Рисовать» при каждом нажатии на кнопку вершины будут размещаться случайно.
После того, когда граф на рисован необходимо найти «Остов минималь ного веса» с помощью алгоритма Краскала, для этого нажимать кнопку «Вычис лить». Остов минимального веса будет изображен в поле «Полученный мини мальный остов» и в поле «Результат» будет показан результат виде матрицы ве сов.
Задание:
Проработать две первые задачи. Третью и четвертую решить самостоятельно, используя программное обеспечение Kraskal .
Задача №1. Дан взвешенный связный неориентированный граф, состоя щий из пяти вершин. Необходимо найти остов минимального веса с помощью ал горитма Краскала.
Выбираем вершину начала построения остова минимального веса, напри мер, первую вершину.
Шаг 1. Найдено ребро минимального веса: 1-2=6. Полученный остов на рисунок.
Шаг 2. Найдено ребро минимального веса: 2-3=7. Полученный остов на рисунок.
Шаг 3. Найдено ребро минимального веса: 3-4=9. Полученный остов на рисунок.
Шаг 4. Найдено ребро минимального веса: 3-5=11.
Рассмотрены все вершины и инцидентные ребра этим вершинам, остав шиеся образуют цикл в полученном минимальном остове. А это не удовлетворяет условиям поставленной задачи.
На четвертом шаге получили окончательный остов минимального веса, ко торый представлен на рисунке.
При изменении вершины начала построения конфигурация остова мини мального веса не измениться, а измениться лишь последовательность построения ребер остова.
Например, если в качестве начальной вершины выбрать четвертую вер шину, то последовательность этапов построения остова минимального веса будет выглядеть следующим образом:
Шаг 1. 4-3=9;
Шаг 2. 3-2=7;
Шаг 3. 2-1=6;
Шаг 4. 3-5=11;
При этом конфигурация остова останется прежней. Решим данную задачу с помощью программной модели. Чтобы решить данную задачу необходимо по строить матрицу весов, матрица представлена на рисунке.
Матрица весов
Полученный минимальный остов с помощью программной модели изо бражен на рисунке.
Полученный минимальный остов
После проверки вычислений вручную и программной модели результат одинаковый, это означает, что программная модель работает и функционирует верно.
Задача №2. Дан взвешенный, связный, неориентированный граф, состоя щий из девяти вершин. Необходимо найти остов минимального веса с помощью ал горитма Краскала. Исходный граф на рисунке.
Выбираем вершину начала построения остова минимального веса, напри мер, первую вершину.
Шаг 1. Найдено ребро минимального веса: AC=1. Полученный остов на рисунок.
Шаг 2. Найдено ребро минимального веса: CF=3, AB=4, AC=4. Полученный остов на рисунок.
Шаг 3. Найдено ребро минимального веса: FD=4, EK=3, AE=4. Полученный остов на рисунок.
Шаг 4. Найдено ребро минимального веса: KH=5, KG=4. Рассмотрены все вершины и инцидентные ребра этим вершинам, остав шиеся ребра образуют цикл в полученном минимальном остове. А это не удовлетворяет условиям поставленной задачи.
На четвертом шаге получен окончательный остов минимального веса, ко торый представлен на рисунке.
Решим данную задачу с помощью программной модели. Чтобы решить данную задачу необходимо по строить матрицу весов.
Таблица 13 SEQ Таблица \* ARABIC 14115. Матрица весов
A
B
C
D
E
F
G
H
K
A
-
4
1
9
4
-
-
-
-
B
4
-
-
-
-
-
-
5
-
C
1
-
-
10
-
3
-
-
-
D
9
-
10
-
5
4
-
6
9
E
4
-
-
5
-
7
-
-
3
F
-
-
3
4
7
-
10
-
-
G
-
-
-
-
-
10
-
-
7
H
-
5
-
6
-
-
-
-
5
K
-
-
-
9
3
-
7
5
-
Полученный минимальный остов с помощью программной модели изо бражен на рисунке.
Остов минимального веса
После проверки вычислений вручную и программной модели полученные остовы минимального веса различаются, но они построены верно. Это связано с тем, что программа выбирает другую вершину начала. После решения двух контрольных задач стало ясно, что разработанная программная модель работает верно.
Задача №3. Найти остов минимального веса с помощью алгоритма Краскала., проверить программой Краскала.
Задача №4. Найти минимальное остовное дерево в неориентированном нагруженном графе. Результат проверить программным обеспечением.
13EMBED PBrush1415
13EMBED PBrush1415
13EMBED PBrush1415
а)
б)
в)
Порядок выполнения работы:
1. Изучить инструкцию к практической работе.
2. Выполнить задание.
3. Оформить отчет.
Содержание отчета:
1. Тема.
2. Цель.
3. Задачи.
4. Материальное обеспечение.
5. Практическое задание.
Вопросы для самоконтроля:
1. Дайте определение остов графа.
2. Дайте определение минимальный остов графа.
3. В чем смысл алгоритма Краскала?
Практическая работа № 6
Тема: Решение задач по теории графов.
Построение матриц смежностей и инциденций
Цель: изучение матричных способов представления графов; отработать на примерах основные понятия теории графов; научить строить графы по матрице смежности; по графу составлять матрицу смежности; закрепить навыки моделирования графов в графической среде Grafoanalizator1.3.3 rus.
Задачи:
1. Закрепить знания основных понятий теории графов.
2. Приобрести практические умения использования специального программного обеспечения для моделирования.
3. Использовать математический аппарат теории графов
Материальное обеспечение:
Программы для графического представления графов: Grafoanalizator1.3.3 rus, Просто граф, практическая работа.
Теоретическая часть:
Матрица смежности
Пусть дан граф G, его матрица смежности обозначается через A=[aij] и определяется следующим образом:
aij=1, если в G существует дуга (xi,xj),
aij=0, если в G нет дуги (xi,xj).
Таким образом, матрица смежности графа, изображенного на рисунке 1, имеет вид
Матрица смежности полностью определяет структуру графа. Например, сумма всех элементов строки xi матрицы дает полустепень исхода вершины xi, а сумма элементов столбца xi - полустепень захода вершины xi. Множество столбцов, имеющих 1 в строке xi есть множество Г(xi), а множество строк, которые имеют 1 в столбце xi совпадает с множеством Г-1(xi).
Петли на графе представляют собой элементы, имеющие 1 на главной диагонали матрицы, например a22, a66 для графа, изображенного на рисунке 1.
В случае неориентированного графа матрица смежности является симметричной относительно главной диагонали (рисунок 2).
Матрица инцидентности
Пусть дан граф G с n вершинами и m дугами. Матрица инцидентности графа G обозначается через B=[bij] и является матрицей размерности n x m, определяемой следующим образом:
bij=1, если xi является начальной вершиной дуги aj;
bij=-1, если xi является конечной вершиной дуги aj;
bij=0, если xi не является концевой вершиной дуги aj.
Для графа, приведенного на рисунке 1, матрица инцидентности имеет вид:
Поскольку каждая дуга инцидентна двум различным вершинам (за исключением случая, когда дуга образует петлю), то каждый столбец содержит один элемент, равный 1, и один - равный -1. Петля в матрице инцидентности не имеет адекватного математического представления (в программной реализации допустимо задание одного элемента bij=1).
Если G является неориентированным графом (рисунок 2), то его матрица инцидентности определяется следующим образом:
bij=1, если xi является концевой вершиной дуги aj;
bij=0, если xi не является концевой вершиной дуги aj.
Матрица инцидентности, как способ задания графов, успешно применяется при описании мультиграфов (графов, в которых смежные вершины могут соединяться несколькими параллельными дугами).
Инструкция к практической работе
Задача. Для неориентированного графа, изображённого на рисунке, постройте матрицу смежности и матрицу инцидентности.
Решение:
Матрица смежности
13EMBED Equation.31415
Матрица инцидентности
13EMBED Equation.31415
Задача. Дана матрица 13EMBED Equation.31415
Постройте орграф, для которого данная матрица является матрицей смежности. Найдите матрицу инцидентности орграфа.
Решение: Для построения орграфа его вершине однозначно сопоставим точку на плоскости. Данная матрица смежности имеет четыре строки и четыре столбца, следовательно, в орграфе четыре вершины 1, 2, 3, 4.
Проанализируем элементы матрицы:
13EMBED Equation.31415 при вершине 1 нет петель;
13EMBED Equation.31415 из вершины 1 выходят две стрелки к вершине 2;
13EMBED Equation.31415 из вершины 1 не выходит ни одной стрелки к вершине 3;
13EMBED Equation.31415 из вершины 1 не выходит ни одной стрелки к вершине 4;
13EMBED Equation.31415 из вершины 2 не выходит ни одной стрелки к вершине 1;
13EMBED Equation.31415 при вершине 2 нет петель;
13EMBED Equation.31415 из вершины 2 выходит одна стрелка к вершине 3;
13EMBED Equation.31415 из вершины 2 не выходит ни одной стрелки к вершине 4;
13EMBED Equation.31415 из вершины 3 выходит одна стрелка к вершине 1;
13EMBED Equation.31415 из вершины 3 не выходит ни одной стрелки к вершине 2;
13EMBED Equation.31415 при вершине 3 нет петель;
13EMBED Equation.31415 из вершины 3 выходит одна стрелка к вершине 4;
13EMBED Equation.31415 из вершины 4 выходит 3 стрелки к вершине 1;
13EMBED Equation.31415 из вершины 4 выходит одна стрелка к вершине 2;
13EMBED Equation.31415 из вершины 4 не выходит ни одной стрелки к вершине 3;
13EMBED Equation.31415 при вершине 4 нет петель.
Строим орграф.
Для построения графа запишем матрицу инцидентности:
13EMBED Equation.31415
Здесь четыре строки по числу вершин и 9 столбцов по числу дуг.
Задание:
Для графа заданного матрицей смежности
найти матрицу инцидентности
построить граф
Используя программное обеспечение, изобразите граф и проверьте матрицу.
Вариант 1
1
2
3
4
5
6
1
2
3
4
5
6
1
2
3
4
5
6
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
2
1
1
2
1
1
1
3
1
1
1
1
1
3
1
1
3
1
1
4
1
1
1
4
1
4
1
5
1
1
5
1
5
1
6
1
1
1
1
1
6
6
Вариант 2.
1
2
3
4
5
6
1
2
3
4
5
6
1
2
3
4
5
6
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
2
1
1
2
1
1
1
1
3
1
1
3
1
1
1
3
1
1
1
1
4
1
4
1
1
4
1
1
1
5
1
5
1
5
1
1
1
1
1
6
6
6
1
1
1
Вариант 3
1
2
3
4
5
6
1
2
3
4
5
6
1
2
3
4
5
6
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
2
1
2
1
1
1
1
3
1
1
1
3
1
1
1
3
1
1
4
1
4
1
1
4
1
1
1
5
1
5
1
5
1
1
1
6
6
6
1
1
1
Вариант 4
1
2
3
4
5
6
1
2
3
4
5
6
1
2
3
4
5
6
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
2
1
1
2
1
1
3
1
1
3
1
1
3
1
1
1
1
1
4
1
4
1
1
4
1
1
1
1
5
1
5
5
1
1
1
6
6
6
1
1
1
1
Вариант 5
1
2
3
4
5
6
1
2
3
4
5
6
1
2
3
4
5
6
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
2
1
1
1
2
1
1
1
1
3
1
1
3
1
1
1
3
1
1
1
1
4
1
4
1
1
4
1
1
1
1
5
1
5
1
5
1
1
1
1
6
6
6
1
1
Порядок выполнения работы:
1. Изучить инструкцию к практической работе.
2. Выполнить задание.
3. Оформить отчет.
Содержание отчета:
1. Тема.
2. Цель.
3. Задачи.
4. Материальное обеспечение.
5. Практическое задание.
Вопросы для самоконтроля:
1. Перечислите основные способы представления графов.
2. В чем отличия матричного представления ориентированных и неориентированных графов?
3. В чем особенности представления графа матрицей смежности?
4. В чем особенности представления графа матрицей инцидентности?
Практическая работа № 7
Тема: Решение задач по теории графов. Выделение связных компонентов. Нахождение максимального потока и минимального разреза.
Цель: научиться определять компоненты связности и находить максимальный поток и строить минимальный разрез в сети с использованием алгоритма Форда- Фалкерсона; закрепить навыки моделирования графов в графической среде Grafoanalizator1.3.3 rus.Простой граф.
Задачи:
1. Закрепить знания основных понятий теории графов.
2. Приобрести практические умения использования специального программного обеспечения для моделирования.
3. Использовать математический аппарат теории графов
Материальное обеспечение:
Программы для графического представления графов: Grafoanalizator1.3.3 rus, Прстой граф, практическая работа.
Теоретическая часть:
Компоненты связного и несвязного графа
В теории графов, понятие связности графа является ключевым при решении многих прикладных задач.
Определение связного и несвязного графа.
Граф G(V,E) называется связным, если для любой пары различных вершин этого графа существует цепь, соединяющая эти вершины. Если для графа G(V,E) можно указать пару различных вершин, которые не соединяются цепью, то граф называется несвязным.
Пример связного и несвязного графов.
Компонента связности графа некоторое множество вершин [ Cкачайте файл, чтобы посмотреть ссылку ] такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.
Для ориентированных графов определено понятие сильной компоненты связности
Пример компонент связности графа.
Рассмотрим пример двусвязного графа G(V, E). Всего имеется два множества связных между собой вершин V1 = {v1, v2, v5, v6} и V2 = {v3, v4, v7, v8}.
Свойства компонент связности.
1. Каждая вершина графа входит лишь в одну компоненту связности.
2. Любой конечный граф имеет конечное число компонент связности.
3. Граф, состоящий из единственной компоненты связности, является связным.
4. Каждая компонента связности графа является его подграфом.
Теорема. Если в конечном графе G ровно две вершины u и v имеют нечетную степень, то они связаны.
Задание 1. Компоненты сильной связности ориентированного графа.
С помощью матрицы смежности найти компоненты сильной связности ориентированного графа D.
Cоставляем матрицу смежности A(D) размерности 13EMBED Equation.31415 (n
· количество вершин) для данного ориентированного графа: она состоит из нулей и единиц, номера строк – индексы вершин , из которых исходят дуги, номера столбцов – индексы вершин, в которые дуги входят (если есть дуга, исходящая из вершины vi и входящая в vj, то элемент матрицы смежности, стоящий на пересечении i-той строки и j-того столбца равен 1, иначе – 0.).
Для того, чтобы выделить компоненты сильной связности, необходимо сначала найти матрицу достижимости T(D)
Матрица достижимости ориентированного графа D
· квадратная матрица T(D)=[tij] порядка n, элементы которой равны
13EMBED Equation.31415
ориентированного графа по (1) формуле (T(D)=sign[E+A+A2+A3+ An-1]), затем находим матрицу сильной связности S(D) ориентированного графа (она должна быть симметрической) по (2) формуле (S(D)=T(D)(TT(D) (TT-транспонированная матрица, (- поэлементное умножение)).
Алгоритм выделения компонент сильной связности
1. Присваиваем p=1 (p
· количество компонент связности), 13EMBED Equation.31415.
2. Включаем в множество вершин Vp компоненты сильной связности Dp вершины, соответствующие единицам первой строки матрицы Sp. В качестве матрицы A(Dp) возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из Vp.
3. Вычеркиваем из Sp строки и столбцы, соответствующие вершинам из Vp. Если не остается ни одной строки (и столбца), то p- количество компонент сильной связности. В противном случае обозначим оставшуюся после вычеркивания срок и столбцов матрицу как Sp+1, присваиваем p=p+1 и переходим к п. 2.
Пример выполнения задания 1
Выделим компоненты связности ориентированного графа, изображенного на рисунке 1. В данной задаче количество вершин n=5.
13EMBED PBrush1415
Рисунке 1.
Значит, для данного ориентированного графа матрица смежности будет иметь размерность 5Ч5 и будет выглядеть следующим образом
13EMBED Equation.31415.
Найдем матрицу достижимости для данного ориентированного графа по формуле (1)
13EMBED Equation.31415, 13EMBED Equation.31415,
13EMBED Equation.31415,
Следовательно,
13EMBED Equation.31415
13EMBED Equation.31415.
Таким образом, матрица сильной связности, полученная по формуле (2), будет следующей:
13EMBED Equation.31415.
Присваиваем p=1 13EMBED Equation.31415 и составляем множество вершин первой компоненты сильной связности D1: это те вершины, которым соответствуют единицы в первой строке матрицы S(D). Таким образом, первая компонента сильной связности состоит из одной вершины 13EMBED Equation.31415.
Вычеркиваем из матрицы S1(D) строку и столбец, соответствующие вершине v1, чтобы получить матрицу S2(D):
13EMBED Equation.31415.
Присваиваем p=2. Множество вершин второй компоненты связности составят те вершины, которым соответствуют единицы в первой строке матрицы S2(D), то есть 13EMBED Equation.31415. Составляем матрицу смежности для компоненты сильной связности 13EMBED Equation.31415 исходного графа D
· в ее качестве возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из V2:
13EMBED Equation.31415.
Вычеркиваем из матрицы S2(D) строки и столбцы, соответствующие вершинам из V2 ,чтобы получить матрицу S3(D), которая состоит из одного элемента:
13EMBED Equation.31415
и присваиваем p=3. Таким образом, третья компонента сильной связности исходного графа, как и первая, состоит из одной вершины 13EMBED Equation.31415.
Таким образом, выделены 3 компоненты сильной связности ориентированного графа D:
D1:
13EMBED PBrush1415
D2:
13EMBED PBrush1415
D3:
13EMBED PBrush1415
Максимальный поток и минимальный разрез
Теорема Форда-Фалкерсона 1 (о максимальном потоке и минимальном разрезе).
В любой сети существует максимальный поток. Величина максимального потока равна пропускной способности минимального разреза.
Теорема Форда-Фалкерсона 2.
Поток, вычисленный с помощью алгоритма Форда-Фалкерсона имеет максимальную величину, а разрез 13EMBED Equation.31415, где 13EMBED Equation.31415-множество вершин, помеченных при последнем помечивании, имеет минимальную пропускную способность.
Нахождение максимального потока и построение минимального разреза в сети с использованием алгоритма Форда-Фалкерсона
В данной задаче основным параметром на дугах сети является 13EMBED Equation.31415 – пропускная способность. Пропускная способность показывает, сколько единиц потока может быть передано по дугам сети. Таким образом, потоком в сети D = [N, M] называется неотрицательная вещественная функция, удовлетворяющая условиям:
1. ограниченности: поток по любой дуге сети не превосходит пропускной способности этой дуги 13EMBED Equation.31415;
2. сохранения: суммарный поток, заходящий в любую вершину сети (кроме истока и стока), равен суммарному потоку, выходящему из этой вершины.
Дуга сети называется насыщенной, если поток по этой дуге равен пропускной способности этой дуги, т. е. 13EMBED Equation.31415.
Разрезом сети называется множество дуг, удаление которых из сети приводит к тому, что исток и сток оказываются несвязанными.
Пропускной способностью разреза называется число, равное сумме пропускных способностей дуг этого разреза. Разрез называется минимальным, если имеет наименьшую пропускную способность.
Отыскание минимального разреза – одна из основных задач анализа транспортных сетей. В силу конечности графа минимальный разрез может быть найден перебором всех разрезов, но этот путь, конечно, неприемлем для достаточно больших графов.
Минимальный разрез можно отыскать при помощи теоремы Форда – Фалкерсона: в любой транспортной сети величина любого максимального потока равна пропускной способности любого минимального разреза.
Для нахождения максимального потока в сети разработан алгоритм Форда – Фалкерсона. Перед началом выполнения алгоритма все вершины сети нумеруются произвольным образом, кроме источника и стока (источник получает минимальный номер 1, сток – максимальный 13EMBED Equation.31415, где 13EMBED Equation.31415 – число узлов).
Алгоритм состоит из следующих основных шагов:
1. Определить начальный поток в сети, сложив потоки по дугам, выходящим из источника.
2. Вершинам сети присвоить целочисленные метки, а дугам – знаки «+» и «–» по следующим правилам:
а) вершине-истоку присвоить метку 13EMBED Equation.31415;
б) находим непомеченную вершину 13EMBED Equation.31415, смежную помеченной вершине 13EMBED Equation.31415. Если поток по соединяющей вершины 13EMBED Equation.31415 дуге меньше пропускной способности этой дуги, то происходит помечивание, иначе переходим к рассмотрению следующей вершины. Если вершина 13EMBED Equation.31415 является образом помеченной вершины 13EMBED Equation.31415, то происходит прямое помечивание (дуга в прямом направлении допустима): вершина 13EMBED Equation.31415 получает метку, равную номеру вершины 13EMBED Equation.31415, соединяющая вершины 13EMBED Equation.31415 дуга получает метку «+», переходим к рассмотрению следующей вершины. Если вершина 13EMBED Equation.31415 не имеет ни одного помеченного прообраза, поток по дуге в прямом направлении больше 0, то происходит обратное помечивание (дуга допустима в обратном направлении): вершина 13EMBED Equation.31415 получает метку, равную номеру вершины 13EMBED Equation.31415 (являющейся в данном случае ее образом), соединяющая вершины 13EMBED Equation.31415 дуга получает метку «–», происходит переход к рассмотрению следующей вершины. Процесс помечивания продолжается до тех пор, пока все удовлетворяющие этим условиям вершины не получат метку.
3. Если в результате процедуры помечивания вершина-сток метки не получила, то текущий поток – максимальный, переход к шагу 5. В противном случае перейти к пункту 4.
4. Рассмотреть последовательность вершин L, метка каждой из которых равна номеру следующей за ней вершины, и множество дуг МL, соединяющих соседние вершины из L.
Построение нового потока по схеме:
а) Если дуга принадлежит множеству МL (смотри выше) и имеет знак «+», то новый поток по этой дуге = старый поток по этой дуге +
· (схему нахождения смотри далее).
б) Если дуга принадлежит множеству МL и имеет знак «–», то новый поток по этой дуге = старый поток по этой дуге –
·.
в) Если дуга не принадлежит множеству МL, то поток по дуге оставляем без изменения.
Схема нахождения
·:
I. 13EMBED Equation.31415, где для нахождения 13EMBED Equation.31415 рассматриваются все дуги, принадлежащие множеству МL и имеющие знак «+», и для каждой такой дуги вычисляется разность между пропускной способностью дуги и потоком по этой дуге (13EMBED Equation.31415). Затем из этих значений разностей выбирается минимальное значение и присваивается 13EMBED Equation.31415.
II. Для нахождения 13EMBED Equation.31415 рассматриваются все дуги, принадлежащие множеству МL и имеющие знак «–». Затем из этих дуг выбирается дуга с минимальным потоком (13EMBED Equation.31415), и значение потока по этой дуге присваивается 13EMBED Equation.31415.
Перейти к шагу 2.
5. Определяем максимальный поток, складывая начальный поток и все полученные изменения потока.
В оптимальном решении, т. е. когда найден максимальный поток, минимальный разрез образуется насыщенными дугами.
Пример № 1 выполнения задания 2
На заданной сети найти максимальный поток из X4 в X1 и минимальный разрез. Решение Необходимо заполнить таблицу:
1
2
3
4
5
6
7
t X1
2, +Х2
1, +Х6
2, +Х8
1, +Х6
1, +Х6
1,+Х8
X2
2, +Х3
1, +Х3
1, +Х6
X3
2, +Х4
1, +Х5
2, +Х5
1, +Х5
s X4
·,+Х4
·,+Х4
·,+Х4
·,+Х4
·,+Х4
·,+Х4
·,+Х4
X5
1, +Х4
1, +Х4
2, +Х7
2, +Х7
2, +Х7
1, +Х7
X6
2, Х3
1, +Х5
2, +Х7
1, +Х7
2, +Х5
1, Х5
X7
5, +Х4
5, +Х4
5, +Х4
3, +Х4
2, +Х4
1, +Х4
X8
2, +Х7
1, +Х6
V
2
1
2
1
1
1
После первого шага увеличиваем потоки в дугах, которые сначала были везде = 0. Далее продолжаем наращивать поток по цепям: Х4, Х3, Х2, Х1, V1 = 2 Х4, Х5, Х6, Х1, V2 = 1 Х4, Х7, Х8, Х1, V3 = 2 Х4, Х7, Х6, Х1, V4 = 1 Х4, Х7, Х5, V5 = 1 Х4, Х7, Х5, Х6, Х8, V6 = 1 , т.е. максимальный поток = 8. На последнем, 7-ом шаге, на котором мы не достигли (не можем пометить) вершину t = Х1 находим все помеченные вершины: Xs = {X4} и непомеченные вершины Xt = {X1, X2, X3, X5, X6, X7, X8}. Минимальный разрез – ребра, один конец которых лежит в Xs, а другой в Xt. В нашем случае это: (Х4, Х3), V(Х4, Х3) = 2; (Х4, Х5), V(Х4, Х5) = 1; (Х4, Х7), V(Х4, Х7) = 5 Т.е. величина минимального разреза совпадает с максимальным потоком.
Пример № 2 выполнения задания № 2.
Постановка задачи поиска максимального потока: найти максимальный поток из 13EMBED Equation.31415 в 13EMBED Equation.31415 для транспортной сети (рисунок) с помощью алгоритма Форда – Фалкерсона:
Решение:
№
Алгоритм
Конкретные действия
1.
1-я итерация
1. 13EMBED Equation.31415.
2.1 (Второй шаг, первая итерация – подобное обозначение идет далее для всех шагов алгоритма). Производим помечивание вершин и дуг, результат показан на рисунке. Вершина 6 получила метку 13EMBED Equation.31415.
2.
2-я итерация
3.1. 13EMBED Equation.31415 .
4.1. 13EMBED Equation.31415;
13EMBED Equation.31415;
13EMBED Equation.31415.
2.2. Заново осуществляется помечивание. Вершина 6 снова получает метку 13EMBED Equation.31415 (смотри рисунок).
3.
3-я итерация
3.2. 13EMBED Equation.31415.
4.2. 13EMBED Equation.31415;
13EMBED Equation.31415;
13EMBED Equation.31415.
2.3. Осуществляется помечивание. При этом из вершины 3 прямых допустимых дуг не выходит, однако дуга 2–3 является допустимой в обратном направлении, и вершина 2 получает метку 13EMBED Equation.31415. Вершина 6 получает метку 13EMBED Equation.31415 (смотри рисунок).
4.
4-я итерация
3.3. 13EMBED Equation.31415.
4.3. 13EMBED Equation.31415;
13EMBED Equation.31415;
13EMBED Equation.31415;
13EMBED Equation.31415;
13EMBED Equation.31415.
2.4. Осуществляется помечивание. При этом из вершины 3 допустимые дуги не выходят. Вершина 6 не получает метку (смотри рисунок). Переходим к шагу 5.
5.
5. 13EMBED Equation.31415.
Минимальный разрез образуют насыщенные дуги 3–6 и 5–6. Пропускная способность минимального разреза 13EMBED Equation.31415. Условия теоремы Форда – Фалкерсона выполняются 13EMBED Equation.31415 13EMBED Equation.31415 задача решена правильно.
Алгоритм Форда – Фалкерсона используется при решении многих практических задач. Одна из них – задача об источниках и потребителях.
Задание:
1. С помощью матрицы смежности найти компоненты сильной связности ориентированного графа D. При решении использовать программу Grafoanalizator1.3.3 rus, Простой граф
13EMBED PBrush1415
13EMBED PBrush1415
13EMBED PBrush1415
Вариант1
Вариант 2
Вариант 3
2. Дана сеть:
Определить максимальный поток в сети при начальных значениях дуговых потоков: 13EMBED Equation.31415, 13EMBED Equation.31415, 13EMBED Equation.31415, 13EMBED Equation.31415, 13EMBED Equation.31415, 13EMBED Equation.31415, 13EMBED Equation.31415.
Варианты значений пропускных способностей дуг для задания:
Порядок выполнения работы:
1. Изучить примеры выполнения заданий 1 и 2 .
2. Выполнить задание.
3. Оформить отчет.
Содержание отчета:
1. Тема.
2. Цель.
3. Задачи.
4. Материальное обеспечение.
5. Практическое задание.
Вопросы для самоконтроля:
1. Перечислите основные компоненты связности графов.
2. В чем смысл матрицы достижимости?
3. Запишите теорему Форда-Фалкерсона 1 (о максимальном потоке и минимальном разрезе).
Практическая работа № 8
Тема: Решение задач по теории графов. Нахождение путей в графе
Цель: реализовать алгоритмы обработки графовых структур: поиск различных путей; получение навыком при решении задач нахождения пути в графе; закрепить навыки моделирования графов в графической среде Grafoanalizator1.3.3 rus, Простой граф, Grin.
Задачи:
1. Закрепить знания основных понятий теории графов.
2. Приобрести практические умения использования специального программного обеспечения для моделирования.
3. Использовать математический аппарат теории графов.
4. Применение алгоритмов поиска кратчайшего пути.
5. Планирование структуры сети с помощью графа с оптимальным расположением узлов.
Материальное обеспечение:
Программы для графического представления графов: Grafoanalizator1.3.3 rus? Простой граф, Grin.
практическая работа. Интернет ссылка: [ Cкачайте файл, чтобы посмотреть ссылку ]
Теоретическая часть:
В основе построения большинства алгоритмов на графах лежит систематический перебор вершин графа, при котором каждая вершина просматривается в точности один раз, а количество просмотров ребер графа ограничено заданной константой (лучше – не более одного раза).
Один из основных методов проектирования графовых алгоритмов – это поиск (или обход графа) в глубину (depth first search, DFS), при котором начиная с произвольной вершины v0, ищется ближайшая смежная вершина v, для которой в свою очередь осуществляется поиск в глубину (т.е. снова ищется ближайшая, смежная с ней вершина) до тех пор, пока не встретится ранее просмотренная вершина, или не закончится список смежности вершины v (то есть вершина полностью обработана). Если нет новых вершин, смежных с v, то вершина v считается использованной, идет возврат в вершину, из которой попали в вершину v, и процесс продолжается до тех пор, пока не получим v = v0. Иными словами, поиск в глубину из вершины v основан на поиске в глубину из всех новых вершин, смежных с вершиной v.
Путь, полученный методом поиска в глубину, в общем случае не является кратчайшим путем из вершины v в вершину u. Это общий недостаток поиска в глубину. На рисунке показан путь, полученный обходом графа в глубину.
Указанного недостатка лишен другой метод обхода графа – поиск в ширину (breadth first search, BFS). Обработка вершины v осуществляется путем просмотра сразу всех новых соседей этой вершины. При этом полученный путь является кратчайшим путем из одной вершины в другую.
показан путь, найденных методом поиска в ширину
При использовании алгоритмов DFS и BFS графы обходят разными способами, получая при этом некоторые подграфы, которые имеют специфические названия: каркасы, остовы или стягивающие деревья. Все вершины исходного графа входят в полученное стягивающее дерево, а все ветви дерева – это множество ребер из все множеств ребер графа.
Произвольный путь в графе, проходящий через каждое ребро графа точно один раз, называется эйлеровым путем. При этом, если по некоторым вершинам путь проходит неоднократно, то он является непростым. Если путь замкнут, то имеем эйлеров цикл. Для существования эйлерова пути в связном графе необходимо и достаточно, чтобы граф содержал не более двух вершин нечетной степени.
Путь в графе, проходящий в точности один раз через каждую вершину графа (а не каждое ребро) и соответствующий цикл называются гамильтоновыми и существуют не для каждого графа, как и эйлеров путь. В отличие от эйлеровых путей неизвестно ни одного простого необходимого и достаточного условия для существования гамильтоновых путей. Неизвестен даже алгоритм полиномиальной сложности, проверяющий существование гамильтонова пути в произвольном графе. Проблема существования гамильтонова пути принадлежит к классу так называемых NP-полных задач.
В теории алгоритмов классом NP (от [ Cкачайте файл, чтобы посмотреть ссылку ] non-deterministic polynomial) называют множество задач распознавания ([ Cкачайте файл, чтобы посмотреть ссылку ]), решение которых при наличии некоторых дополнительных сведений (так называемого сертификата решения) можно «быстро» (за время, не превосходящее полинома от размера данных) проверить на машине Тьюринга.
NP-полная задача задача из [ Cкачайте файл, чтобы посмотреть ссылку ], к которой можно свести любую другую задачу из класса NP за полиномиальное время. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро».
При решении некоторых практических задач возникает необходимость поиска максимального пути ( пути с наибольшей суммой длин дуг). Такая задача сводится к задаче нахождения минимального пути заменой знаков при длинах дуг ( в матрице весов C) на противоположные . При этом необходимым является требование отсутствия в ориентированном графе контуров положительной длины .
Поиск путей
знать:
если в город R можно приехать только из городов X, Y, и Z, то число различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть NR = NX + NY + NZ, где NQ обозначает число путей из вершины A в некоторую вершину Q
число путей конечно, если в графе нет циклов – замкнутых путей
Пример задания:
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Решение (1 вариант, подстановки):
1) начнем считать количество путей с конца маршрута – с города К
2) будем обозначать через NX количество различных путей из города А в город X
3) общее число путей обозначим через N
4) по схеме видно, что NБ = NГ = 1
5) очевидно, что если в город X можно приехать только из Y, Z, то NX = NY + N Z, то есть нужно сложить число путей, ведущих из A во все города, откуда можно приехать в город X
6) поскольку в K можно приехать из Е, Д, Ж или И, поэтому
N = N К = NД + NЕ + NЖ + NИ
7) в город И можно приехать только из Д, поэтому NИ = NД
8) в город Ж можно приехать только из Е и В, поэтому
N Ж = NЕ + NВ
9) подставляем результаты пп. 6 и 7 в формулу п. 5:
N = NВ + 2NЕ + 2NД
10) в город Д можно приехать только из Б и В, поэтому
N Д = NБ + NВ
так что
N = 2NБ + 3NВ + 2NЕ
11) в город Е можно приехать только из Г, поэтому N Е = NГ так что
N = 2NБ + 3NВ + 2NГ
12) по схеме видно, что NБ = NГ = 1, кроме того, NВ = 1 + N Б + NГ = 3
13) окончательно N = 2NБ + 3NВ + 2NГ = 2·1 + 3·3 + 2·1 = 13
14) Ответ: 13.
Решение (2 вариант, удобная форма записи):
1) начнем считать количество путей с конца маршрута – с города К
2) записываем для каждой вершины, из каких вершин можно в нее попасть
К ИДЖЕ
И Д
Ж ВЕ
Е Г
Д БВ
Г А
В АБГ
Б А
3) теперь для удобства «обратного хода» вершины можно отсортировать так[ Cкачайте файл, чтобы посмотреть ссылку ], чтобы сначала шли все вершины, в которые можно доехать только из начальной точки А:
Б А
Г А
затем на каждом шаге добавляем те вершины, в которые можно доехать из уже добавленных в список (и из исходной точки):
В АБГ
Е Г
далее добавляем все вершины, куда можно доехать из А, Б, Г, В и Е:
Д БВ
Ж ВЕ
на следующем шаге добавляем вершину И
И Д
и, наконец, конечную. вершину
К ИДЖЕ
именно в таком порядке мы и будем вычислять количество путей для каждой вершины
[ Cкачайте файл, чтобы посмотреть ссылку ] Такая процедура называется топологической сортировкой графа.
4) теперь идем по полученному списку вершин, полагая, что количество вариантов попасть в вершину равно суммарному количеству вариантов попасть в ее непосредственных предшественников.
NБ = 1, NГ = 1
NВ = 1+1+1 = 3, NЕ = 1
NД = 1+3 = 4, NЖ = 3 + 1 = 4
NИ = 4,
N = NК = 4 + 4 + 4 + 1 = 13
5) заметим, что вершины можно и не сортировать специально, а просто выбирать возможный порядок вычисления: проверять, какие значения известны и какие можно рассчитать с их помощью на следующем шаге
6) Ответ: 13.
Возможные ловушки и проблемы:
очень важна аккуратность и последовательность; сначала идем от конечной точки к начальной, выписывая все вершины, из которых можно приехать в данную; затем идем обратно, определяя числовые значения
построение полного дерева маршрутов – занятие трудоемкое и достаточно бесперспективное, даже грамотные учителя информатики здесь в большинстве случаев что-то забывают и ошибаются
Решение (3 вариант, перебор вершин по алфавиту):
1) Запишем вершины в алфавитном порядке и для каждой из них определим, из каких вершин можно в нее попасть
Б А
В АБГ
Г А
Д БВ
Е Г
Ж ВЕ
И Д
К ИДЖЕ
2) теперь определяем количество путей; сначала ставим 1 для тех вершин, в которые можно проехать только из начальной (А):
3) затем на каждом шаге добавляем те вершины, в которые можно доехать из уже добавленных в список (и из исходной точки):
4) следующий шаг
5) и последние 2 шага
6) Ответ: 13.
Решение (4 вариант, перебор всех путей с начала, А. Яфарова):
1) запишем все вершины, в которые есть прямой путь из вершины A: Б, В и Г; получается три начальных отрезка:
АБ, АВ, АГ
2) рассмотрим маршрут АБ: из Б можно ехать в В и Д, поэтому получаем два маршрута:
АБВ, АБД
3) рассматриваем конечные точки этих маршрутов: из В можно ехать в Д и Ж, а из Д – в И и К:
АБВД, АБВЖ, АБДИ, АБДК
4) снова смотрим на конечные точки: из Д едем в И и К, из Ж и И – только в К:
АБВДИ, АБВДК, АБВЖК, АБДИК, АБДК
5) из И едем только в К, таким образом, все возможные маршруты, содержащие участок АБ, доведены до конечной точки К, всего 5 таких маршрутов:
АБВДИК, АБВДК, АБВЖК, АБДИК, АБДК
6) затем аналогично рассматриваем маршруты, которые начинаются с АВ:
АВД, АВЖ
АВДИ, АВДК, АВЖК
АВДИК, АВДК, АВЖК
всего 3 маршрута
7) наконец, остается рассмотреть маршруты, которые начинаются с АГ:
АГВ, АГЕ
АГВД, АГВЖ, АГЕЖ, АГЕК
АГВДИ, АГВДК, АГВЖК, АГЕЖК, АГЕК
АГВДИК, АГВДК, АГВЖК, АГЕЖК, АГЕК
всего 5 маршрутов
8) складываем количество маршрутов для всех начальных участков: 5 + 3 + 5 = 13
9) Ответ: 13.
Возможные проблемы:
при большом количестве маршрутов легко запутаться и что-то пропустить
Решение (5 вариант, графический):
1) Главную идею решения: (число дорог в город N есть сумма дорог, приводящих в города, из которых есть прямой проезд в город N), отразим на самой схеме, показывая на ней ЧИСЛО ДОРОГ, приводящих в каждый город.
2) Последовательность очевидна: начинаем с Б и Г (городов, куда есть по 1-й дороге из А)
3) Посчитаем дороги в В: 1 (из A)+ 1(дороги города Б)+ 1(дороги города В)= 3
4) Аналогично посчитаем дороги в Д, И, Е, Ж:
5) Определяем число дорог в город К, как сумму дорог в города, с которыми он связан: Д, И, Ж, Е.
6) Ответ: 13.
Задания:
Выполнить задание и проверить с помощью программы Grin, Простой граф.
1. На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
2. На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
3. На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
4. На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
5. На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
6. На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
7. На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
8. На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
9. На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
10. На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
11. На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
12. На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З?
13. На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
14. На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
15. На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З?
16. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
17. На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H?
18. На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город M?
19. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
20. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город M?
21. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
22. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И?
23. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
24. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И?
25. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И?
26. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З?
27. На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Е?
28. На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город E?
29. На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З?
30. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Порядок выполнения работы:
1. Изучить примеры выполнения заданий.
2. Выполнить задание.
3. Оформить отчет.
Содержание отчета:
1. Тема.
2. Цель.
3. Задачи.
4. Материальное обеспечение.
5. Практическое задание.
Вопросы для самоконтроля:
1. В поиск в графе иначе называется?
2. Что означает DFS и BFS?
3. Дайте определение NP-полная задача?
Практическая работа № 9
Тема: Решение задач по теории графов. Нахождение кратчайшего пути
Цель: научиться находить кратчайшие пути в графе при помощи алгоритма Дейкстры; получение навыком при решении задач нахождения пути в графе; закрепить навыки моделирования графов в графической среде Grafoanalizator1.3.3 rus, Простой граф, Grin.
Задачи:
1. Закрепить знания основных понятий теории графов.
2. Приобрести практические умения использования специального программного обеспечения для моделирования.
3. Использовать математический аппарат теории графов.
4. Применение алгоритмов поиска кратчайшего пути.
5. Планирование структуры сети с помощью графа с оптимальным расположением узлов.
Материальное обеспечение:
Программы для графического представления графов: Grafoanalizator1.3.3 rus, Простой граф, Grin, практическая работа.
Теоретическая часть:
Нахождение кратчайшего пути на сегодняшний день является жизненно необходимой задачей и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в сетях и т.п.
Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом. Поиск кратчайшего пути ведется между двумя заданными вершинами в графе. Результатом является путь, то есть последовательность вершин и ребер, инцидентных двум соседним вершинам, и его длина.
Описываемый в данном разделе алгоритм позволяет находить в графе кратчайший путь между двумя выделенными вершинами 13EMBED Equation.31415 и 13EMBED Equation.31415 при положительных длинах дуг. Этот алгоритм предложенный в 1959 г. Дейкстрой, считается одним из наиболее эффективных алгоритмов решения задачи.
Главная идея, лежащая в основе алгоритма Дейкстры, предельно проста. Предположим, что нам известны 13EMBED Equation.31415 вершин, ближайших к вершине 13EMBED Equation.31415 (близость любой вершины x к вершине 13EMBED Equation.31415 определяется длиной кратчайшего пути, ведущего из 13EMBED Equation.31415 в 13EMBED Equation.31415). Пусть также известны сами кратчайшие пути, соединяющие вершину 13EMBED Equation.31415 с выделенными m вершинами). Покажем теперь, как может быть определена 13EMBED Equation.31415-я ближайшая к 13EMBED Equation.31415 вершина.
Окрасим вершину 13EMBED Equation.31415 и 13EMBED Equation.31415 ближайших к ней вершин. Построим для каждой неокрашенной вершины 13EMBED Equation.31415 пути, непосредственно соединяющие с помощью дуг 13EMBED Equation.31415 каждую окрашенную вершину 13EMBED Equation.31415 с 13EMBED Equation.31415. Выберем из этих путей кратчайший, и будем считать его условно кратчайшим путем из вершины 13EMBED Equation.31415 в вершину 13EMBED Equation.31415.
Какая же из неокрашенных вершин является 13EMBED Equation.31415-й ближайшей к 13EMBED Equation.31415 вершиной? Та, для которой условно кратчайший путь имеет наименьшую длину. Это обусловливается тем, что кратчайший путь из вершины 13EMBED Equation.31415 в 13EMBED Equation.31415-ю ближайшую вершину при положительном значении длин всех дуг должен содержать в качестве промежуточных лишь окрашенные вершины, т. е. вершины, входящие в число 13EMBED Equation.31415 вершин, ближайших к вершине 13EMBED Equation.31415.
Итак, если известны 13EMBED Equation.31415 ближайших к 13EMBED Equation.31415 вершин, то 13EMBED Equation.31415-я ближайшая к 13EMBED Equation.31415 вершина может быть найдена так, как это описано выше. Начиная с 13EMBED Equation.31415, описанная процедура может повторяться до тех пор, пока не будет получен кратчайший путь, ведущий из вершины 13EMBED Equation.31415 к вершине 13EMBED Equation.31415.
Алгоритм работает только для графов без рёбер отрицательного веса.
Любая задача,требующая нахождения оптимальных маршрутов может быть выполнена с помощью алгоритма Дейкстры. Это касается и сетей, и транспортных потоков, и обработка графов. Очень часто используется не сам алгоритм в чистом виде, а его модификация.
Примеры:
1. При эвакуации населения из очагов бедствия оптимальные маршруты до пунктов сбора транспорта для каждой группы людей(дом,улица,школа и т.д) в штабе МЧС рассчитывает программа на основе алгоритма Дейкстры.
2. Компьютерная игра. Указываете точку назначения для персонажа и он движется туда по кратчайшему маршруту. Это тоже алгоритм Дейкстры.
3. Дана сеть автомобильных дорог, соединяющих города Гомельской области. Некоторые дороги односторонние. Найти кратчайшие пути от города Гомеля до каждого города области (если двигаться можно только по дорогам).
4. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Милана до Минска.
Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.
OSPF разбивает процесс построения таблицы маршрутизации на 2 этапа.
Второй этап состоит в нахождении оптимальных маршрутов с помощью полученного графа. Задача нахождения оптимального пути на графе является достаточно сложной и ёмкой. В протоколе OSPF для её решения используется итеративный алгоритм Дейкстры. Каждый маршрутизатор считает себя центром сети и ищет оптимальный маршрут до каждой известной ему сети. В каждом найденном таким образом маршруте запоминается только один шаг - до следующего маршрутизатора, в соответствии с принципом одношаговой маршрутизации. Данные об этом шаге и попадают в таблицу маршрутизации. Если несколько маршрутов имеют одинаковую метрику до сети назначения, то в таблице маршрутизации запоминаются первые шаги всех этих маршрутов".
Алгоритм
1. Каждой вершине 13EMBED Equation.31415 в ходе алгоритма присваивается число 13EMBED Equation.31415, равное длине кратчайшего пути из вершины 13EMBED Equation.31415 в вершину 13EMBED Equation.31415 и включающем только окрашенные вершины. Положить 13EMBED Equation.31415 и 13EMBED Equation.31415 для всех остальных вершин графа. Окрашиваем вершину 13EMBED Equation.31415 и полагаем 13EMBED Equation.31415, где 13EMBED Equation.31415 – последняя окрашенная вершина.
2. Для каждой неокрашенной вершины 13EMBED Equation.31415 пересчитывается величина 13EMBED Equation.31415 по следующей формуле:
13EMBED Equation.31415 13EMBED Equation.31415
3. Если 13EMBED Equation.31415 для всех неокрашенных вершин, то алгоритм заканчивается т. к. отсутствуют пути из вершины 13EMBED Equation.31415 в неокрашенные вершины. Иначе окрашивается та вершина, для которой величина 13EMBED Equation.31415 является минимальной. Окрашивается и дуга, ведущая в эту вершину в соответствии с выражением 13EMBED Equation.31415 и полагаем 13EMBED Equation.31415.
4. Если 13EMBED Equation.31415, кратчайший путь из 13EMBED Equation.31415 в 13EMBED Equation.31415 найден. Иначе переходим к шагу 2.
Каждый раз окрашивается вершина и дуга, заходящая в эту вершину. Окрашенные дуги не могут образовывать цикл, а образуют в исходном графе дерево с корнем (началом) в вершине 13EMBED Equation.31415. Это дерево называют ориентированным деревом кратчайших путей. Путь из 13EMBED Equation.31415 в 13EMBED Equation.31415 принадлежит этому дереву. При поиске одного кратчайшего пути процедура наращивания завершается при достижении конечной вершины этого пути. Нам же необходимо получить все кратчайшие пути начинающиеся в вершине №1. Для этого процедуру наращивания ориентированного дерева продолжается до тех пор, пока все вершины не будут включены. Таким образом, мы получаем ориентированное дерево кратчайших путей, которое является покрывающим деревом графа.
Иногда в графе имеются несколько кратчайших путей. Кратчайший путь будет единственным, если в алгоритме ни разу не возникает неоднозначность при окрашивании дуги.
Отметим, что главным условием успешного применения алгоритма Дейкстры к задаче на графе является неотрицательность длин дуг этого графа
Для графа с отрицательными весами применяется более общий алгоритм Алгоритм Дейкстры с потенциалами.
Пример выполнения задания.
Требуется найти кратчайшие расстояния от 1-й вершины до всех остальных для графа, представленного на рисунке:
№
Алгоритм
Конкретные действия
1.
Инициализация.
Cтартовая вершина, от которой строится дерево кратчайших путей - вершина № 1.
Задаем стартовые условия: d(1)=0, d(x)=
·.
Окрашиваем вершину № 1, y=1.
Находим ближайшую вершину к окрашенной нами, используя формулу: 13EMBED Equation.31415.
Составим матрицу длин кратчайших дуг для данного графа.
№/№
1
2
3
4
5
6
1
13EMBED Equation.31415
7
9
13EMBED Equation.31415
13EMBED Equation.31415
14
2
7
13EMBED Equation.31415
10
15
13EMBED Equation.31415
13EMBED Equation.31415
3
9
10
13EMBED Equation.31415
11
13EMBED Equation.31415
2
4
13EMBED Equation.31415
15
11
13EMBED Equation.31415
6
13EMBED Equation.31415
5
13EMBED Equation.31415
13EMBED Equation.31415
13EMBED Equation.31415
6
13EMBED Equation.31415
9
6
14
13EMBED Equation.31415
2
13EMBED Equation.31415
9
13EMBED Equation.31415
или
13EMBED Equation.31415
2.
Первый шаг.
Рассмотрим шаг алгоритма Дейкстры.
d(2)=min{d(2) ; d(1)+a(1,2)}=min{
·; 0+7}=7
d(3)=min{d(3) ; d(1)+a(1,3)}=min{
·; 0+9}=9
d(4)=min{d(4) ; d(1)+a(1,4)}=min{
·; 0+
·}=
·
d(5)=min{d(5) ; d(1)+a(1,5)}=min{
·; 0+
·}=
·
d(6)=min{d(6) ; d(1)+a(1,6)}=min{
·; 0+14}=14
Минимальную длину имеет путь от вершины № 1 до вершины № 2 d(2)=7.
Включаем вершину № 2 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину.
Согласно выражению это дуга (1,2).
3.
Второй шаг.
d(3)=min{d(3) ; d(2)+a(2,3)}=min{9; 7+10}=9
d(4)=min{d(4) ; d(2)+a(2,4)}=min{
·; 7+15}=22
d(5)=min{d(5) ; d(2)+a(2,5)}=min{
·; 7+
·}=
·
d(6)=min{d(6) ; d(2)+a(2,6)}=min{14; 7+
·}=14
Минимальную длину имеет путь от вершины № 1 до вершины № 3 d(3)=9.
Включаем вершину № 3 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину.
Согласно выражению это дуга (1,3)
4.
Третий шаг.
d(4)=min{d(4) ; d(3)+a(3,4)}=min{22; 9+11}=20
d(5)=min{d(5) ; d(3)+a(3,5)}=min{
·; 9+
·}=
·
d(6)=min{d(6) ; d(3)+a(3,6)}=min{14; 9+2}=11
Минимальную длину имеет путь от вершины № 1 до вершины № 6 d(6)=11.
Включаем вершину № 6 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (1,6)=(1,3)+(3,6)
5.
Четвертый шаг.
d(4)=min{d(4) ; d(6)+a(6,4)}=min{20; 11+
·}=20
d(5)=min{d(5) ; d(6)+a(6,5)}=min{
·; 11+9}=20
Минимальную длину имеет путь от вершины № 1 до вершины № 4 и № 5 d(4)=d(6)=20.
Включаем вершину № 4 и № 5 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину.
Согласно выражению это дуга (1,4)=(1,3)+(3,4) и (1,5)=(1,3)+(3,6)+(6,5).
6.
Заключение.
Мы получили ориентированное дерево кратчайших путей начинающихся в вершине №1 для исходного графа.
d(1)=1 Длина маршрута L=0
d(2)=1-2 Длина маршрута L=7
d(3)=1-3 Длина маршрута L=9
d(4)=1-3-4 Длина маршрута L=20
d(5)=1-3-6-5 Длина маршрута L=20
d(6)=1-3-6 Длина маршрута L=11
Пример выполнения задание № 2
Требуется найти кратчайшие расстояния от 1-й вершины до всех остальных для графа, представленного на рисунке:
Решение:
№
Алгоритм
Конкретные действия
1.
Инициализация.
Cтартовая вершина, от которой строится дерево кратчайших путей - вершина № 1.
Задаем стартовые условия: d(1)=0, d(x)=
·.
Окрашиваем вершину № 1, y=1.
Находим ближайшую вершину к окрашенной нами, используя формулу: 13EMBED Equation.31415.
Составим матрицу длин кратчайших дуг для данного графа.
№/№
1
2
3
4
5
6
1
13EMBED Equation.31415
10
18
8
13EMBED Equation.31415
13EMBED Equation.31415
2
10
13EMBED Equation.31415
16
9
21
13EMBED Equation.31415
3
13EMBED Equation.31415
16
13EMBED Equation.31415
13EMBED Equation.31415
13EMBED Equation.31415
15
4
7
9
13EMBED Equation.31415
13EMBED Equation.31415
13EMBED Equation.31415
12
5
13EMBED Equation.31415
13EMBED Equation.31415
13EMBED Equation.31415
13EMBED Equation.31415
13EMBED Equation.31415
23
6
13EMBED Equation.31415
13EMBED Equation.31415
15
13EMBED Equation.31415
23
13EMBED Equation.31415
или13EMBED Equation.31415
2.
Первый шаг.
Рассмотрим шаг алгоритма Дейкстры.
d(2)=min{d(2) ; d(1)+a(1,2)}=min{
·; 0+10}=10
d(3)=min{d(3) ; d(1)+a(1,3)}=min{
·; 0+18}=18
d(4)=min{d(4) ; d(1)+a(1,4)}=min{
·; 0+8}=8
d(5)=min{d(5) ; d(1)+a(1,5)}=min{
·; 0+
·}=
·
d(6)=min{d(6) ; d(1)+a(1,6)}=min{
·; 0+
·}=
·
Минимальную длину имеет путь от вершины № 1 до вершины № 4 d(4)=8.
Включаем вершину № 4 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину.
Согласно выражению это дуга (1,4)
3.
Второй шаг.
d(2)=min{d(2) ; d(4)+a(4,2)}=min{10; 8+9}=10
d(3)=min{d(3) ; d(4)+a(4,3)}=min{18; 8+
·}=18
d(5)=min{d(5) ; d(4)+a(4,5)}=min{
·; 8+
·}=
·
d(6)=min{d(6) ; d(4)+a(4,6)}=min{
·; 8+12}=20
Минимальную длину имеет путь от вершины № 1 до вершины № 2 d(2)=10.
Включаем вершину № 2 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину.
Согласно выражению это дуга (1,2)
4.
Третий шаг.
d(3)=min{d(3) ; d(2)+a(2,3)}=min{18; 10+16}=18
d(5)=min{d(5) ; d(2)+a(2,5)}=min{
·; 10+21}=31
d(6)=min{d(6) ; d(2)+a(2,6)}=min{20; 10+
·}=20
Минимальную длину имеет путь от вершины № 1 до вершины № 3 d(3)=18.
Включаем вершину № 3 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину.
Согласно выражению это дуга (1,3)
5.
Четвертый шаг.
d(5)=min{d(5) ; d(3)+a(3,5)}=min{31; 18+
·}=31
d(6)=min{d(6) ; d(3)+a(3,6)}=min{20; 18+15}=20
Минимальную длину имеет путь от вершины № 1 до вершины № 6 d(6)=20.
Включаем вершину № 6 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину.
Согласно выражению это дуга (4,6)
6.
Пятый шаг.
d(5)=min{d(5) ; d(6)+a(6,5)}=min{31; 20+23}=31
Минимальную длину имеет путь от вершины № 1 до вершины № 5 d(5)=31.
Включаем вершину № 5 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину.
Согласно выражению это дуга (2,5)
7.
Заключение.
Мы получили ориентированное дерево кратчайших путей начинающихся в вершине №1 для исходного графа.
d(1)=1 Длина маршрута L=0
d(2)=1-2 Длина маршрута L=10
d(3)=1-3 Длина маршрута L=18
d(4)=1-4 Длина маршрута L=8
d(5)=1-2-5 Длина маршрута L=31
d(6)=1-4-6 Длина маршрута L=20
Ориентированное дерево с корнем в вершине №1:
Задание.
1. Найти кратчайшие расстояния от 1-й вершины до всех остальных для графа, представленного на рисунке. Используя программное обеспечение, проверьте другие алгоритмы вычисления кратчайшего пути.
Порядок выполнения работы:
1. Изучить примеры выполнения заданий
2. Выполнить задание.
3. Оформить отчет.
Содержание отчета:
1. Тема.
2. Цель.
3. Задачи.
4. Материальное обеспечение.
5. Практическое задание.
Вопросы для самоконтроля:
1.Чем отличается путь от маршрута?
2. Дайте определение понятию поиск кратчайшего пути?
3. Перечислите, какие алгоритмы по поиску кратчайшего пути вы знаете?
4. Какое программное обеспечение лучше подходит для вычисления пути?
13PAGE 15
13PAGE 146815
Министерство образования и науки Хабаровского края
Краевое государственное бюджетное
профессиональное образовательное учреждение
«Хабаровский машиностроительный техникум»
Методические рекомендации по выполнению практических работ по междисциплинарному курсу «МДК.01.02. Математический аппарат для построения компьютерных сетей»
2016
13EMBED Equation.31415
А)
Б)
В)
x1
x2
x3
x4
x5
x6
x1
0
1
1
0
0
0
x2
0
1
0
0
1
0
A=
x3
0
0
0
0
0
0
x4
0
0
1
0
0
0
x5
1
0
0
1
0
0
x6
1
0
0
0
1
1
Рисунок 1.
x1
x2
x3
x4
x5
x6
x1
0
1
1
0
0
1
x2
1
0
1
0
0
0
A=
x3
1
1
0
1
0
0
x4
0
0
1
0
1
1
x5
0
0
0
1
0
1
x6
1
0
0
1
1
0
Рисунок 2.
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
x1
1
1
0
0
0
0
0
-1
-1
0
x2
-1
0
(1
1
0
0
0
0
0
0
B=
x3
0
-1
0
0
0
0
0
0
0
0
x4
0
0
0
0
-1
-1
0
0
0
0
x5
0
0
0
-1
1
1
-1
1
0
0
x6
0
0
0
0
0
0
1
0
1
(1
a1
a2
a3
a4
a5
a6
a7
a8
x1
1
1
0
0
0
0
0
1
x2
1
0
1
0
0
0
0
0
B=
x3
0
1
1
1
0
0
0
0
x4
0
0
0
1
1
1
0
0
x5
0
0
0
0
0
1
1
0
x6
0
0
0
0
1
0
1
1