Инфоурок Информатика Другие методич. материалыМетодические рекомендации по выполнению практических работ по междисциплинарному курсу «МДК.01.02. Математический аппарат для построения компьютерных сетей»

Методические рекомендации по выполнению практических работ по междисциплинарному курсу «МДК.01.02. Математический аппарат для построения компьютерных сетей»

Скачать материал

 

Надпись: Министерство образования и науки Хабаровского края
 Краевое государственное бюджетное 
профессиональное образовательное учреждение 
«Хабаровский машиностроительный техникум»




 







Методические рекомендации по выполнению практических работ по междисциплинарному курсу  «МДК.01.02. Математический аппарат для построения компьютерных сетей»















2016

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Методические рекомендации по выполнению практических работ по междисциплинарному курсу  «МДК.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 элементов  называемых вершинами графа, и подмножество V декартова произведения  называемое множеством дуг.

Ориентированным графом G (орграфом) называется совокупность (Х, V).

Неориентированным графом называется совокупность множеств Х и множества неупорядоченных пар элементов, каждый из которых принадлежит множеству  Х.

Дугу между вершинами i и j,  будем обозначать (i, j). Число дуг графа будем обозначать

Подграфом называется часть графа, образованная подмножеством вершин вместе со всеми рёбрами (дугами), соединяющими вершины из этого множества. Если в графе удалить часть рёбер (дуг), то получим частичный граф.

Две вершины называются смежными, если они соединены ребром (дугой). Смежные вершины называются граничными вершинами соответствующего ребра (дуги), а это ребро (дуга) - инцидентным соответствующим вершинам.

Граф называется полным, если каждые две вершины его соединены одним и только одним ребром.

Граф, для которого из  следует  называется симметричным. Если из  следует , то соответствующий граф называется антисимметричным.

Язык графов оказывается удобным для описания многих физических, технических, экономических, биологических, социальных и других систем.

Вершины в графе могут отличаться друг от друга тем, скольким рёбрам они принадлежат.

Степень вершины называется число рёбер графа, которым принадлежит эта вершина. Степень графа ещё называют его валентностью и обозначают . Вершина графа, для которой  является изолированной, для которой висячей.

Вершина называется нечётной, если  нечётное число. Вершина называется чётной, если чётное число. Степень каждой вершины полного графа на единицу меньше числа его вершин.

В графе сумма степеней всех его вершин – число чётное, равное удвоенному числу рёбер графа. Число нечётных вершин любого графа чётно. Во всяком графе с n вершинами, где всегда найдутся, по меньшей мере, две вершины с одинаковыми степенями.

Если в графе с n вершинами  в точности две вершины имеют одинаковую степень, то в этом графе всегда найдётся либо в точности одна вершина степени 0, либо в точности одна вершина степени

1.Маршруты, цепи, циклы

Маршрутом в графе называется чередующаяся последовательность вершин и рёбер, в которой любые два соседних элемента инцидентны:

Если  то маршрут замкнут, в противном случае открыт.

Путём называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги.

Простой путь – путь, в котором ни одна дуга не встречается дважды.

Контур – путь, у которого конечная вершина совпадает с начальной вершиной.

Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы).

Цепью называется множество рёбер (в неориентированном графе), которые можно расположить так, что конец (в этом расположении) одного ребра является началом другого. Другое определение: цепь – последовательность смежных вершин. Замкнутая цепь называется циклом. Можно определить простые и элементарные цепи.

Элементарная цепь (цикл, путь, контур), проходящая через все вершины графа называется гамильтоновой цепью.

Простая цепь (цикл, путь, контур), содержащая все рёбра (дуги) графа называется эйлеровой цепью.

Если любые две вершины графа можно соединить цепью, то граф называется связным. Если граф не является связным, то его можно разбить на связные подграфы, называемые компонентами.

Связностью графа называется минимальное число рёбер, после удаления которых граф становится несвязным.

2.Ориентированные графы

Если элементы множества Е графа упорядоченные пары, то граф называется ориентированным или орграфом.

Ребро  графа G называется ориентированным, если одну вершину считают началом ребра, а другую – концом, на рисунке его изображают стрелкой между вершинами. Таким образом, граф, все рёбра которого ориентированы, называется ориентированным графом.

Одна и та же вершина ориентированного графа может служить началом для одних рёбер и концом для других, поэтому различают две степени вершины: степень выхода и степень входа.

Степенью выхода вершины орграфа называется число выходящих из вершины рёбер.

Степенью входа вершины орграфа называется число входящих в вершину рёбер.

В орграфах в зависимости от сочетаний степеней входа и выхода для данной вершины рассматривается три случая.

Изолированной вершиной называется вершина, у которой и степень входа и степень выхода равна 0.

Источником называется вершина, степень выхода которой положительна, а степень входа равна 0.

Стоком называется вершина, степень входа которой положительна, а степень выхода равна 0.

Путём в ориентированном графе называется последовательность ориентированных рёбер, т. е. для  орграфов цепь называется путём.

Простым путём в ориентированном графе называется путь, в котором ни одна вершина не содержится более одного раза.

Замкнутый путь в ориентированном графе называется ориентированным циклом или контуром.

Длиной пути называется число рёбер в этом пути.

Полным ориентированным графом называется граф, каждая пара вершин которого соединена в точности одним ориентированным ребром.

Всякий полный ориентированный граф с n вершинами имеет простой ориентированный путь, проходящий через все вершины графа.

Петлёй называется ребро, у которого начальная и конечная вершины совпадают. Петля обычно считается неориентированной.

Мультиграфом называется граф, в котором пара вершин соединяется несколькими различными рёбрами. Для ориентированного мультиграфа вершины   и  могут соединяться несколькими рёбрами в каждом из направлений.

3.Изоморфизм графов

Два графа  и  называются изоморфными, если между множествами их вершин существует биективное (взаимнооднозначное) соответствие, такое, что вершины соединены рёбрами в одном из графов  в том и только в том случае, когда соответствующие им вершины соединены в другом графе. Если рёбра ориентированы, то их направление в изоморфных графах должно совпадать. Изоморфизм графов есть отношение эквивалентности, так как обладает свойствами рефлексивности, симметричности, транзитивности. Для того чтобы граф  был изоморфен графу  необходимо и достаточно существования такой подстановки, которая бы установила взаимнооднозначное соответствие между вершинами графа, а также между их рёбрами.

При замене графа любым ему изоморфным все свойства графа сохраняются. Строго говоря, графы отличающиеся только нумерацией вершин, являются изоморфными.

Алгоритм распознания изоморфизма двух графов   и

1. Подсчитаем число вершин каждого графа (число вершин должно совпадать, в противном случае графы неизоморфные).

2. Выписываем все элементы обоих графов в естественной упорядоченности и определяем пары  и  для каждого элемента, где  число исходов для каждой вершины графов  и , а  число заходов для соответствующих графов.

3. Для каждого элемента х графа  ищем такой элемент у графа  что выполняется условие: число исходов х совпадает с числом исходов у, и число заходов х совпадает с числом заходов у. Найденные элементы х и у соединяем ребром, т. е. строим граф соответствия (если соответствия нет, то графы не изоморфны).

4. Выписываем подстановку, которая переводит граф  в граф .

4.Плоские графы

Граф  называется плоским, если на плоскости его можно изобразить так, что все пересечения его рёбер являются вершинами графа .

В качестве характеристики плоского представления графа вводится понятие грани.

Гранью в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов.

5.Операции над графами

Рассмотрим графы  и

а) Дополнением графа  называется граф  множеством вершин которого является множество  а множеством его рёбер является множество

б) Объединением графов  и  при условии, что   называется граф  множеством вершин которого является множество  а множеством его рёбер является множество

в) Пересечением графов  и  называется граф  множеством вершин которого является множество  а множеством его рёбер является множество

г) Суммой по модулю два графов  и  при условии, что  называется граф  множеством вершин которого является множество  а множеством его рёбер – множество  Т. е. этот граф не имеет изолированных вершин и состоит только из рёбер, присутствующих либо в первом графе, либо во втором графе, но не в обоих графах одновременно.

 

 

6.Способы задания графов

Существуют три эквивалентных способа задания графов: аналитический, геометрический и матричный. Рассмотрим каждый из них.

Аналитический способ задания графов

Граф  задан, если задано множество элементов V и отображение E множеств V в V. Отображение Е может быть как однозначным, так и многозначным.

Пусть дано множество  которое имеет мощность

Для того чтобы задать отображение Е на V , необходимо каждому элементу  поставить в соответствие некоторое подмножество множества V, которому соответствует отображение Е. Это подмножество обозначают через  Поэтому  Совокупность двух объектов: множества V и отображение Е на V задаёт некоторый граф.

Другой формой аналитического способа задания является задание графа как совокупности множества элементов V и подмножества множества упорядоченных пар

         Геометрический способ задания графов

Множество элементов V графа G изображают кружками, это множество вершин. Каждую вершину  соединяют линиями с теми вершинами , для которых выполняется условие  Множество линий, которое соответствует множеству упорядоченных пар  есть множество рёбер.

Матричный способ задания графов

Квадратная матрица  элементами которой являются нули и единицы, а также некоторое число m, называется матрицей смежности графа  тогда и только тогда, когда её элементы образуются по следующему правилу: элемент  стоящий на пересечении  й строки и го столбца, равен единице, если имеется ребро, идущее из вершины  в вершину  и  равен нулю в противном случае. Элемент  равен единице, если при вершине  имеется петля, и равен нулю в противном случае. Элемент  равен некоторому числу m, где m – число рёбер графа, идущее из вершины  в вершину

Таким образом, если граф  задан одним из указанных способов: аналитическим, геометрическим или матричным, всегда можно перейти к любому другому способу задания.  Наиболее часто для задания графа используется аналитический  и матричный способы, а геометрический способ служит для иллюстрации полученных результатов.

 

Инструкция к практической работе

Задание 1. Изобразите графически:

1.      Неориентированное и ориентированное ребро;

2.      Неориентированный граф 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};

3.      Плоский граф;

4.      Полный неориентированный граф на трех, четырех и пяти вершинах;

5.      Неполный ориентированный граф на пяти вершинах;

6.      Петлю графа;

7.      Неориентированный и ориентированный мультиграф.

Решение:

 

 

         1) Неориентированное ребро                    ориентированное ребро

Задание 2. Изобразить графы в программах: 

                   grin_rus, Grafoanalizator1.3.3 rus, windisc ru.

http://rudocs.exdat.com/pars_docs/tw_refs/58/57413/57413_html_6bf4636c.png  

Задание:

Вариант № 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

http://neerc.ifmo.ru/wiki/images/thumb/f/f2/Hamiltonial.png/300px-Hamiltonial.png

grin_rus

http://pics.livejournal.com/nastymaster_one/pic/0000ac6c

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. Изобразите графы в соответствующих программах. Полученные графы сохранить в свои папки.

 

Граф

Программа

http://referat.ru/cache/referats/19821/image077.gif

Grafoanalizator1.3.3 rus

https://encrypted-tbn1.gstatic.com/images?q=tbn:ANd9GcRRJhqW_4fZmd4jxU52T9Y2l6SElI8gBpFK1uEa3KHmO0ImDE2kUQ

grin_rus

https://encrypted-tbn1.gstatic.com/images?q=tbn:ANd9GcSqRZwAcl4vlNd-sHp81EdimXU3bXJqPCOjGo5LPFdrdTyElZa5Ig

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

https://encrypted-tbn2.gstatic.com/images?q=tbn:ANd9GcTN7EsYNR6R8AnDigg66xsRiQTTKjRDygd6csP_LZ-UPQNl7Rqp

grin_rus

https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcQ1iQ8Wkv4z9inMfC4qrKGU88NJVLdC62cGajgBqiY0oA6meASRtA

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. Изобразите графы в соответствующих программах. Полученные графы сохранить в свои папки.

 

 

 

Граф

Программа

http://upload.wikimedia.org/wikipedia/commons/d/de/Dijkstra_graph0.PNG

Grafoanalizator1.3.3 rus

https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcQFcyTzK4k6olk-3P1RYkPPmyCdNqIFJc_MPA_Tc73N0SIVNRz6

grin_rus

http://rudocs.exdat.com/pars_docs/tw_refs/345/344596/344596_html_797c4688.jpg

windisc ru

 

 

Порядок выполнения работы:

 

1. Изучить инструкцию к практической работе.

2. Выполнить задание.

3. Оформить отчет.

 

Содержание отчета:

 

1. Тема.

2. Цель.

3. Задачи.

4. Материальное обеспечение.

5. Практическое задание.

 

Вопросы для самоконтроля:

 

1. Что называется графом? Ориентированным графом? Приведите примеры.

2. Что такое степень вершины?

3. Перечислите основные понятия, связанные с неориентированными графами.

4. Перечислите основные понятия, связанные с орграфами.

5. В чем состоит аналитический способ задания графа?

6. В чем состоит геометрический способ задания графа?

7. В чем состоит матричный способ задания графа?

8. Что называется маршрутом, циклом и цепью графа?

9. Сформулируйте понятие связности графа. Какой граф называют связным?

10.Какие два графа называются изоморфными?

11.Сформулируйте алгоритм изоморфизма двух графов.

12.Перечислите операции над графами.

Практическая работа  № 2

Тема: Решение задач по теории графов. Эйлеровы и  Гамильтоновы графы.

Цель: изучить алгоритм поиска эйлерова, гамильтонова цикла (пути) в графе, рассмотреть на конкретных примерах ориентированные и неориентированные графы.

Задачи:

1. Закрепить знания основных понятий теории графов.

2. Приобрести практические умения использования специального программного обеспечения для моделирования.

3. Использовать математический аппарат теории графов

Материальное обеспечение:

Программа анализатор графов: Grafoanalizator1.3.3 rus, практическое задание.

 

Теоретическая часть:

Эйлеровы графы

К задачам на Эйлеровы графы относятся головоломки, в которых требуется вычертить на плоскости одним росчерком замкнутые кривые, обводя каждый участок в точности один раз. Введём следующие понятия.

Эйлеровым путём в графе называется путь, содержащий все рёбра графа.

Эйлеровым циклом или эйлеровой цепью называется цикл, содержащий все рёбра графа и притом по одному разу.

Граф, обладающий эйлеровым циклом, называется эйлеровым графом.

Замкнутую линию, если её можно начертить, не отрывая карандаша от бумаги, проходя при этом каждый участок в точности один раз, принято называть уникурсальной.

Рисунок графа, обладающий эйлеровым путём или эйлеровым циклом, является уникурсальной линией.

Докажем следующие две теоремы

Теорема 1.  Если граф  обладает эйлеровым циклом, то он связный и все его вершины четные.

Доказательство. Связность графа следует из определения эйлерова цикла. Эйлеров цикл содержит каждое ребро и притом только один раз, поэтому, сколько раз эйлеров путь приведет конец карандаша в вершину, столько и выведет, причём уже по одному ребру. Следовательно, степень каждой вершины графа должна состоять из двух одинаковых слагаемых: одно – результат подсчета входов в вершину, другое – выходов.

Теорема 2.  Если граф  связный и все его вершины четные, то он обладает эйлеровым циклом.

Доказательство. Если начать путь из произвольной вершины графа , то найдётся цикл, содержащий все рёбра графа. Пусть - произвольная вершина. Из  начнём путь по l по одному из рёбер и продолжим его, проходя каждый раз по новому ребру. Все вершины графа имеют чётные степени, поэтому если l есть «выход» из , то должен быть и «вход» в , также как и для любой вершины другой вершины. И если есть «вход» в вершину, то должен быть и «выход». Так как число ребер конечно, то это путь должен окончиться, причём в вершине . Если путь, замкнувшийся в , проходит через все рёбра графа, то мы получим искомый эйлеров цикл.

Для построения эйлерова цикла в связном графе со всеми вершинами чётной степени применяется следующий алгоритм:

1. Выйти из произвольной вершины . Каждое пройденное ребро зачеркнуть. Если путь  замыкается в  и проходит через все рёбра графа, то получим искомый эйлеров цикл.

2. Если остались непройденные рёбра, то должна существовать вершина   принадлежащая  и ребру, не вошедшему в

3. Так как чётная, то число рёбер, которым принадлежит и которые не вошли в путь  тоже чётно. Начнём новый путь  из  и используем только рёбра, не принадлежащие  Этот путь кончится в

4. Объединим теперь оба цикла: из  пройдём по пути к  затем по  и, вернувшись в  пройдём по оставшейся части  обратно в .

5. Если снова найдутся рёбра, которые не вошли в путь, то найдём новые циклы. Так как число рёбер и вершин конечно, то процесс закончится.

Таким образом, замкнутую фигуру, в которой все вершины чётные, можно начертить одним росчерком без повторений и начиная с любой точки.

На практике эйлеровым графом может быть план выставки; это позволяет расставить указатели маршрута, чтобы посетитель смог пройти по каждому залу в точности по одному разу.

Гамильтоновы графы

Граф, обладающий гамильтоновым циклом, называется гамильтоновым графом.

Гамильтоновым циклом, или путём в графе, называется цикл, или путь, проходящий через каждую вершину графа в точности по одному разу.

Эйлеровы и гамильтоновы пути сходны по способу задания. Первые содержат все рёбра, и притом по одному разу, вторые – все вершины по одному разу. Но, несмотря на внешнее сходство, задачи их отыскания резко отличаются по степени трудности. Для решения вопроса о существовании эйлерова цикла в графе достаточно выяснить, все ли его вершины чётные.

Критерий же существования гамильтонова цикла на произвольном графе ещё не найден.

Однако есть несколько достаточных условий существования гамильтоновых циклов в графе:

1. Всякий полный граф является гамильтоновым, так как он содержит простой цикл, которому принадлежат все вершины данного графа.

2. Если граф, помимо простого цикла, проходящего через все его вершины, содержит и другие рёбра, то он также является гамильтоновым.

3. Если граф имеет один гамильтонов цикл, то он может иметь и другие гамильтоновы циклы.

Алгоритма проверки существования эйлерова пути

Представим динамику выполнения алгоритма проверки существования эйлерова пути (цикла) из вершины 0 для представленного на рисунке 1 графа.
Цикл существует. 
http://sampo.ru/~infmod/nore_gr_eiler.jpgРисунок 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;
Степени всех вершин четные, следовательно, эйлеров цикл в данном графе существует.

http://sampo.ru/~infmod/nore_gr_eiler.jpgРисунок 2

Граф, изображенный на рисунке 2 отличается от рисунка 1 только добавлением ребра (3 – 5).
При этом степени вершин 3 и 5 стали нечетными.
Согласно алгоритму проверки существования эйлерова цикла, основывающемуся на проверке четности степени каждой вершины, в данном графе цикла быть не может.
Однако, если учесть следствие, по которому в точности две вершины имеют нечетную степень, то и в графе, изображенном на рисунке 1 должен существовать эйлеров путь.
Пример такого пути: 3 – 2 – 4- 3 – 5 – 4 – 6 – 0 – 2 – 1 – 0 – 5. 
При этом две вершины, имеющие нечетную степень, находятся на концах такого пути.

 Алгоритма поиска гамильтонова пути

Представим динамику выполнения рекурсивного алгоритма поиска гамильтонова пути (цикла) из вершины 0 для графа, представленного на рисунке 3.

http://sampo.ru/~infmod/noer_gr_4et.jpg Рисунке 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.
http://sampo.ru/~infmod/neor_gr_4et2.jpgРисунке 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. Практическое задание.

 

Вопросы для самоконтроля:

 

1.  Дайте определение эйлерова графа.

2.  Сформулируйте алгоритм построения эйлерова цикла.

3.  Какой граф называют гамильтоновым?

4.  Существует ли эйлеров граф, обладающий висячей вершиной?

5.  Чем отличается эйлеров путь от гамильтонова?

 


 

Практическая работа  № 3

 

Тема: Решение задач по теории графов. Конечные графы. Бесконечные графы.

 

Цель: изучить теоретические основы конечных и бесконечных графов.

Задачи:

1.Закрепить знания основных понятий теории конечных и бесконечных графов.

2. Использовать математический аппарат теории графов

Материальное обеспечение:

практическое задание.

Теоретическая часть:

Конечный граф

Граф называется конечным, если число вершин и ребер в нем конечно, в противном случае – бесконечным.

Рассмотрим неориентированный граф G. Число ребер ρ(v), инцидентных вершине v, назовем локальной степенью графа в вершине v.

Если все числа ρ(v) для "vÎV, то граф называется локально-конечным.

Обозначим ρ(v,u) = ρ(u,v) – это число ребер, соединяющих вершины v и u, т.е. это кратность ребра (v,u). Тогда

Обозначим m(G) – число ребер в графе G. Т.к. каждое ребро будет учитываться в двух локальных степенях v и u, то запишем:

(1)

 

Теорема. Число вершин нечетной локальной степени в графе четно.

Доказательство. Воспользуемся формулой (1), т.е. сумма всех локальных степеней четна. Тогда, удалив из суммы все четные слагаемые, получим четное число, представляющее собой сумму нечетных степеней. Теорема доказана.

Граф называется однородным в степени k, если локальные степени всех вершин равны k. Примерами однородных графов являются правильные треугольники, многоугольники, многогранники.

Для однородных графов можно записать:

,

            где n – число вершин графа G.

            Для куба:

            Пусть G – ориентированный граф. Тогда введем следующие обозначения:

¾                            od(v) – число дуг, выходящих из вершины;

¾                            id(v) – число дуг, заходящих в вершину.

Это локальные степени графа.

Петли, если они есть, считаются по одному разу и в od(v), и в id(v).

Аналогично считаются две кратности. Обозначим как ρo(v,u), ρi(v,u) число дуг, выходящих из v в u и из u в v соответственно.

            Ориентированный граф называется однородным, если для "vÎV выполняется следующее: od(v) = id(v) = k.

Бесконечный граф

Примеры бесконечных однородных графов.

Бесконечные однородные графы http://uchit.net/catalog/Informatika_programmirovanie/141366/img136.jpg

Бесконечные однородные графы находят широкое применение в задачах трассировки печатных соединений, т.к. их использование позволяет разбивать коммутационное поле печатных плат на элементарные ячейки одинаковой формы.

Бесконечным графом называется пара (V(G)E(G)), где V(G) — бесконечное множество элементов, называемое вершинами, а E(G) — бесконечное семейство неупорядоченных пар элементов из V(G), называемых ребрами.

http://www.intuit.ru/EDI/11_09_13_2/1378902874-22974/tutorial/138/objects/6/files/6_1.gif

 

Если оба множества V(G) и E(G) — счетны, то G называется счетным графом. Заметим, что наши определения исключают те случаи, когда V(G) — бесконечно, а E(G) — конечно. Такие объекты являются всего лишь конечными графами с бесконечным множеством изолированных вершин. Когда E(G) — бесконечно, а V(G) — конечно, такие объекты являются конечными графами с бесконечным числом петель или кратных ребер.

Некоторые определения таких понятий, как "смежный", "инцидентный", "изоморфный", "подграф", "объединение", "связный", "компонента" переносятся на бесконечные графы. 

Степенью вершины v бесконечного графа называется мощность множества ребер, инцидентных v Степень вершины может быть конечной или бесконечной. Бесконечный граф, все вершины которого имеют конечные степени, называется локально конечным. Хорошо известным примером такого графа является бесконечная квадратная решетка, часть которой изображена на рисунке. Локально счетный бесконечный граф — это граф, все вершины которого имеют счетную степень. Под счетным множеством здесь и в дальнейшем понимается бесконечное множество, допускающее взаимно однозначное отображение на множество натуральных чисел.

Теорема Каждый связный локально счетный бесконечный граф является счетным.

Доказательство

Пусть v — произвольная вершина такого бесконечного графа, и пусть v_{1} — множество вершин, смежных vv_{2} — множество всех вершин, смежных вершинам из v_{1}, и т.д. По условию теоремы v_{1} — счетно и, следовательно, множества v_{2},v_{3},\ldotsтоже счетны. Здесь используется тот факт, что объединение не более чем счетного множества счетных множеств счетно. Следовательно, \{v\},v_{1},v_{2},\ldots — последовательность множеств, объединение которых счетно. Кроме того, эта последовательность содержит каждую вершину бесконечного графа в силу его связности. Отсюда и следует нужный результат.

Следствие Каждый связный локально конечный бесконечный граф является счетным.

Помимо этого, на бесконечный граф G можно перенести понятие маршрута, причем тремя различными способами:

1.      Конечный маршрут в G определяется так. Маршрутом в данном графе G называется конечная последовательность ребер вида \{v_{0},v_{1}\}\{v_{1},v_{2}\} \dts\{v_{m-1},v_{m}\}. Маршрут можно обозначить и так: v_{0} \to v_{1} \to v_{2} \to \ldots \tov_{m}.

2.      Бесконечным в одну сторону маршрутом в G с начальной вершиной v_{0} называется бесконечная последовательность ребер вида \{v_{0},v_{1}\}\{v_{1},v_{2}\}\ldots.

3.      Бесконечным в обе стороны маршрутом в графе G называется бесконечная последовательность ребер вида \ldots,\{v_{-2},v_{-1}\},\{v_{-1},v_{0}\}\{v_{0},v_{1}\},\{v_{1},v_{2}\},\ldots

Бесконечные в одну сторону и в обе стороны цепи и простые цепи определяются очевидным образом, так же как и понятия длины цепи и расстояния между вершинами. Бесконечные простые цепи не так уж трудно обнаружить.

Теорема 6.1. (Кениг, 1936) Пусть G — связный локально конечный бесконечный  граф, тогда для любой вершины vсуществует бесконечная в одну сторону простая цепь с начальной вершиной v.

Доказательство

Если z — произвольная вершина графа G, отличная от v, то существует нетривиальная простая цепь от v до z, отсюда следует, что в G имеется бесконечно много простых цепей с начальной вершиной v. Поскольку степень v конечна, то бесконечное множество таких простых цепей должно начинаться с одного и того же ребра. Если таким ребром является \{ v,v_{1} \}, то, повторяя эту процедуру для вершины v_{1}, получим новую вершину v_{2} и соответствующее ей ребро \{v_{1},v_{2}\}. Продолжая таким образом, получим бесконечную в одну сторону простую цепь v\to v_{1} \to v_{2}\ldots.

Важное значение леммы Кенига состоит в том, что она позволяет получить результаты о бесконечных графах из соответствующих результатов для конечных графов. Типичным примером является следующая теорема.

Теорема 6.2. Пусть G — счетный граф, каждый конечный подграф которого планарен, тогда и G планарен.

Доказательство Так как G — счетный граф, его вершины можно занумеровать в последовательность v_{1},v_{2},v_{3},\ldots. Исходя из нее, построим строго возрастающую последовательность G_{1} \subset G_{2} \subset G_{3}\ldots подграфов графа G, выбирая в качестве G_{k} подграф с вершинами v_{1}\dts v_{k} и ребрами графа G, соединяющими только эти вершины между собой. Далее, примем на веру тот факт, что графы G_{i} могут быть уложены на плоскости конечным числом, скажем m(i), топологически различных способов, и построим еще один бесконечный граф H. Его вершины w_{ij} ({i\ge 1}{1\lej\le m(i))} пусть соответствуют различным укладкам графов \{G_{i}\}, а его ребра соединяют те из вершин w_{ij} и w_{kl}, для которых k=i+1 и плоская укладка, соответствующей w_{ij}. Мы видим, что граф H связен и локально конечен, поэтому, как следует из леммы Кенига, он содержит бесконечную в одну сторону простую цепь. А так как граф G является счетным, то эта бесконечная простая цепь и дает требуемую плоскую укладку графа G.

Стоит подчеркнуть, что если принять дальнейшие аксиомы теории множеств, в частности, аксиому выбора для несчетных множеств, то многие результаты можно перенести и на такие бесконечные графы, которые необязательно являются счетными.

Задание

1.                        Изобразить конечные и бесконечные графы.

2.                        Определите, какие графы изображены

http://matica.org.ua/images/stories/ODM/image121.jpg

A

http://matica.org.ua/images/stories/ODM/image122.jpg

B

http://matica.org.ua/images/stories/ODM/image123.jpg

C

http://matica.org.ua/images/stories/ODM/image124.jpgD

http://matica.org.ua/images/stories/ODM/image125.jpg

E

http://matica.org.ua/images/stories/ODM/image126.jpg

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 а, б.

    

333

Рисунок 1

 

На упрощённой схеме части города (графе) мостам соответствуют линии (рёбра графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:

Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа всегда чётно. Невозможно начертить граф, который имел бы нечётное число нечётных вершин.

Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.

Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

Давайте  четко сформулируем поставленную задачу. При каком условии можно обойти все ребра графа, пройдя каждое ровно один раз? Решение оказалось очень простым. Сосчитаем, сколько ребер выходит из каждой вершины. Одни из этих чисел будут четными, а другие - нечетными. Будем и сами вершины называть четными, если из них выходит четное число ребер, и нечетными в противном случае. Как мы уже знаем: количество ребер, выходящих из данной вершины, называется степенью вершины. Вершина графа, имеющая нечетную степень, называется нечетной, а четную степень – четной.

Граф кёнигсбергских мостов имел четыре нечётные вершины, следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

 

     Решая задачу про кенигсбергские мосты, Эйлер установил, в частности, свойства графа:

­   Если все вершины графа четные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине.

­   Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение надо начинать от любой нечетной вершины, а закончить на другой нечетной вершине.

­   Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.

     В задаче о кенигсбергских мостах все четыре вершины соответствующего графа нечетные, то есть нельзя пройти по всем мостам один раз и закончить путь там, где он был начат.

 

Задачи:

1. Между девятью планетами Cолнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля — Меркурий, Плутон — Венера, Земля — Плутон, Плутон — Меркурий, Меркурий — Венера, Уран — Нептун, Нептун — Сатурн, Сатурн — Юпитер, Юпитер — Марс и Марс — Уран. По каждому маршруту ракеты летают в обе стороны. Можно ли долететь на рейсовых ракетах от Земли до Марса?

2. В государстве 100 городов. Из каждого города выходит 4 дороги. Сколько всего дорог в государстве?

3. Экспозиция картинной галереи представляет собой систему коридоров, на обеих стенах которых развешаны картины:

Можно ли предложить такой маршрут осмотра экспозиции, при котором

посетитель проходит вдоль каждой стены ровно один раз?

12

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) – остов, с минимальной суммой весов входящих в него ребер.

Алгоритм Краскала вычисляет для заданного взвешенного неориентированного графа G остовное дерево с наименьшей суммой весов ребер— остовное дерево наименьшего веса. В новой задаче множество вершин при поиске остовного дерева наименьшего веса не меняется.

Минимальный остов графа. Дан взвешенный граф.

Строим граф, присоединяя к пустому графу на множестве вершин заданного графа ребро наименьшего веса. К полученному графу последовательно присоединяем остальные ребра, выбирая на каждом шаге ребро наименьшего веса, не образующее цикл с имеющимися ребрами. В нашем случае начинаем с ребра весом 13 – наименьшего в графе. На рисунках дана последовательность действий. Ребро весом 19 не включается в остов, так как оно образует цикл с ребрами

весом 14 и 13.

Выполнение алгоритма Краскала:

1. Начальная фаза. Минимальный покрывающий лес пуст.
http://urban-sanjoo.narod.ru/kruskal/g_kruskal00.gif

2. Перебираем ребра в порядке возрастания веса: первое ребро с весом 2. Добавляем его к А. 
http://urban-sanjoo.narod.ru/kruskal/g_kruskal01.gif

3. Следующее безопасное ребро с весом 6. Добавляем его. 
http://urban-sanjoo.narod.ru/kruskal/g_kruskal02.gif

4-8. Добавляем остальные безопасные ребра.
http://urban-sanjoo.narod.ru/kruskal/g_kruskal03.gif       http://urban-sanjoo.narod.ru/kruskal/g_kruskal04.gif       http://urban-sanjoo.narod.ru/kruskal/g_kruskal05.gifhttp://urban-sanjoo.narod.ru/kruskal/g_kruskal06.gif       http://urban-sanjoo.narod.ru/kruskal/g_kruskal07.gif

 

Пример выполнения алгоритма Краскаля. Заштрихованные ребра принадлежат растущему лесу.

http://urban-sanjoo.narod.ru/kruskal/kruskal.gif

 

Изучить инструкцию к практической работе.

Для запуска программы необходимо активировать exe – файл с названием «Краскал.exe» запустится программа. Рисунок главной формы изображен на ри­сунке.

Безымянный1Безымянный

На главной форме программы изображены: текстовое поле  необходимое для ввода количество узлов графа, для которого нужно будет найти остов мини­мального веса, затем нужно нажать кнопку «ОК». Далее нужно занести веса в матрицу весов  «Дано» вводить нужно только по горизонтали, а по вертикали программа заполнит поля автоматически. Далее нужно расставить узлы нашего графа, для этого одним щелчком по полю «Данный граф» создастся  узел, он бу­дет помечен синей точкой аналогично выполнить для остальных вершин графа. Также узлы можно расставить случайным образом, для этого нужно пометить флажок «Разместить узлы случайно» и нажать кнопку «Рисовать» при каждом нажатии на кнопку вершины будут размещаться случайно.

После того, когда граф на рисован необходимо найти «Остов минималь­ного веса» с помощью алгоритма Краскала, для этого нажимать кнопку «Вычис­лить». Остов минимального веса будет изображен в поле «Полученный мини­мальный остов» и в поле «Результат» будет показан результат виде матрицы ве­сов.

Безымянный

Задание:

Проработать две первые задачи. Третью и четвертую решить самостоятельно,  используя программное обеспечение Kraskal .

 

Задача №1. Дан взвешенный связный неориентированный граф, состоя­щий из пяти вершин. Необходимо найти остов минимального веса с помощью ал­горитма Краскала.

ав

Выбираем вершину начала построения остова минимального веса, напри­мер, первую вершину.

 

Копия ав

Шаг 1. Найдено ребро минимального веса: 1-2=6. Полученный  остов на рисунок.

 

Копия (2) ав

Шаг 2. Найдено ребро минимального веса: 2-3=7. Полученный остов на рисунок.

 

Копия (3) ав

Шаг 3. Найдено ребро минимального веса: 3-4=9. Полученный остов  на рисунок.

Копия (4) ав

Шаг 4. Найдено ребро минимального веса: 3-5=11.

Рассмотрены все вершины и инцидентные ребра этим вершинам, остав­шиеся образуют цикл в полученном минимальном  остове. А это не удовлетворяет условиям поставленной задачи.

На четвертом шаге получили окончательный остов минимального веса, ко­торый представлен на рисунке.

При изменении вершины начала построения конфигурация остова мини­мального веса не измениться, а измениться лишь последовательность построения ребер остова.

Например, если в качестве начальной вершины выбрать четвертую вер­шину, то последовательность этапов построения остова минимального веса будет выглядеть следующим образом:

Шаг 1. 4-3=9;

Шаг 2. 3-2=7;

Шаг 3. 2-1=6;

Шаг 4. 3-5=11;

При этом конфигурация остова останется прежней. Решим данную задачу с помощью программной модели. Чтобы решить данную задачу необходимо по­строить матрицу весов, матрица представлена на рисунке.

Безымянный

Матрица весов

Полученный минимальный остов с помощью программной модели изо­бражен на рисунке.

точечный рисунок

Полученный минимальный остов

После проверки вычислений вручную и программной модели результат одинаковый, это означает, что программная модель работает и функционирует верно.

 

Задача №2. Дан взвешенный, связный, неориентированный граф, состоя­щий из девяти вершин. Необходимо найти остов минимального веса с помощью ал­горитма Краскала. Исходный граф на рисунке.

Backup_of_Задача1

Выбираем вершину начала построения остова минимального веса, напри­мер, первую вершину.

 

точечный рисунок

Шаг 1. Найдено ребро минимального веса: AC=1. Полученный  остов на рисунок.

 

точечный рисунок9

Шаг 2. Найдено ребро минимального веса: CF=3, AB=4, AC=4. Полученный  остов на рисунок.

у

Шаг 3. Найдено ребро минимального веса: FD=4, EK=3, AE=4. Полученный  остов на рисунок.

па

Шаг 4. Найдено ребро минимального веса: KH=5, KG=4. Рассмотрены все вершины и инцидентные ребра этим вершинам, остав­шиеся ребра образуют цикл в полученном минимальном  остове. А это не удовлетворяет условиям поставленной задачи.

На четвертом шаге получен окончательный остов минимального веса, ко­торый представлен на рисунке.

Решим данную задачу с помощью программной модели. Чтобы решить данную задачу необходимо по­строить матрицу весов.

Таблица 1. Матрица весов

 

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. Найти минимальное остовное дерево в неориентированном нагруженном графе. Результат проверить программным обеспечением.

 

а)

б)

в)

Порядок выполнения работы:

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).

 

3Таким образом, матрица смежности графа, изображенного на рисунке 1, имеет вид

Надпись: 		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.

 

 

4Матрица смежности полностью определяет структуру графа. Например, сумма всех элементов строки xi матрицы дает полустепень исхода вершины xi, а сумма элементов столбца xi - полустепень захода вершины xi. Множество столбцов, имеющих 1 в строке xi есть множество Г(xi), а множество строк, которые имеют 1 в столбце xi совпадает с множеством Г-1(xi).

Надпись: 		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

Петли на графе представляют собой элементы, имеющие 1 на главной диагонали матрицы, например a22, a66 для графа, изображенного на рисунке 1.

В случае неориентированного графа матрица смежности является симметричной относительно главной диагонали (рисунок 2).

 

Надпись: Рисунок 2.

Матрица инцидентности

Пусть дан граф G с n вершинами и m дугами. Матрица инцидентности графа G обозначается через B=[bij] и является матрицей размерности n x m, определяемой следующим образом:

bij=1, если xi является начальной вершиной дуги aj;

bij=-1, если xi является конечной вершиной дуги aj;

bij=0, если xi не является концевой вершиной дуги aj.

Для графа, приведенного на рисунке 1, матрица инцидентности имеет вид:

Надпись: 		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

 

 

 

 

 

 

 

 

Поскольку каждая дуга инцидентна двум различным вершинам (за исключением  случая, когда дуга образует петлю), то каждый столбец содержит один элемент, равный 1, и один - равный -1. Петля в матрице инцидентности не имеет адекватного математического представления (в программной реализации допустимо задание одного элемента bij=1).

Если G является неориентированным графом (рисунок 2), то его матрица инцидентности определяется следующим образом:

bij=1, если xi является концевой вершиной дуги aj;

bij=0, если xi не является концевой вершиной дуги aj.

Надпись: 		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

 

 

 

 

 

 

 

 

 

Матрица инцидентности, как способ задания графов, успешно применяется при описании мультиграфов (графов, в которых смежные вершины могут соединяться несколькими параллельными дугами).

Инструкция к практической работе

Задача. Для неориентированного графа, изображённого на рисунке, постройте матрицу смежности и матрицу инцидентности.

 

Решение:

Матрица смежности

Матрица инцидентности

Задача.  Дана матрица

Постройте орграф, для которого данная матрица является матрицей смежности. Найдите матрицу инцидентности орграфа.

Решение: Для построения орграфа его вершине однозначно сопоставим точку на плоскости. Данная матрица смежности имеет четыре строки и четыре столбца, следовательно, в орграфе четыре вершины 1, 2, 3, 4.

Проанализируем элементы матрицы:

 при вершине 1 нет петель;

 из вершины 1 выходят две стрелки к вершине 2;

 из вершины 1 не выходит ни одной стрелки к вершине 3;

 из вершины 1 не выходит ни одной стрелки к вершине 4;

 из вершины 2 не выходит ни одной стрелки к вершине 1;

 при вершине 2 нет петель;

 из вершины 2  выходит одна стрелка к вершине 3;

 из вершины 2 не выходит ни одной стрелки к вершине 4;

 из вершины 3 выходит одна стрелка к вершине 1;

 из вершины 3 не выходит ни одной стрелки к вершине 2;

 при вершине 3 нет петель;

 из вершины 3  выходит  одна стрелка к вершине 4;

 из вершины 4  выходит 3  стрелки к вершине 1;

 из вершины 4  выходит одна стрелка к вершине 2;

 из вершины 4 не выходит ни одной стрелки к вершине 3;

 при вершине 4 нет петель.

Строим орграф.

 

 

 

 

 

 

Для построения графа запишем матрицу инцидентности:

Здесь четыре строки по числу вершин и 9 столбцов по числу дуг.

Задание:

Для графа заданного матрицей смежности

1.            найти матрицу инцидентности

2.            построить граф

3.            Используя программное обеспечение, изобразите граф и проверьте матрицу.

Вариант 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) можно указать пару различных вершин, которые не соединяются цепью, то граф называется несвязным.

Пример связного и несвязного графов.

Компонента связности графа — некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.

Для ориентированных графов определено понятие сильной компоненты связности

Пример компонент связности графа.

Рассмотрим пример двусвязного графа 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) размерности  (n− количество вершин) для данного ориентированного графа: она состоит из нулей и единиц, номера строк – индексы вершин , из которых исходят дуги, номера столбцов – индексы вершин, в которые дуги входят (если есть дуга, исходящая из вершины vi и входящая в vj, то элемент матрицы смежности, стоящий на пересечении i-той строки и j-того столбца равен 1, иначе – 0.).

Для того, чтобы выделить компоненты сильной связности, необходимо сначала найти матрицу достижимости T(D)

Матрица достижимости ориентированного графа D − квадратная матрица T(D)=[tij] порядка n, элементы которой равны

             

 

ориентированного графа по (1) формуле  (T(D)=sign[E+A+A2+A3+… An-1]), затем находим матрицу сильной связности S(D) ориентированного графа (она должна быть симметрической) по (2) формуле (S(D)=T(D)&TT(D) (TT-транспонированная матрица, &- поэлементное умножение)).

Алгоритм выделения компонент сильной связности

1. Присваиваем p=1 (p − количество компонент связности), .

2. Включаем в множество вершин Vp компоненты сильной связности Dp вершины, соответствующие единицам первой строки матрицы Sp. В качестве матрицы A(Dp) возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из Vp.

3. Вычеркиваем из Sp строки и столбцы, соответствующие вершинам из Vp. Если не остается ни одной строки (и столбца), то p- количество компонент сильной связности. В противном случае обозначим оставшуюся после вычеркивания срок и столбцов матрицу как Sp+1, присваиваем p=p+1 и переходим к п. 2.

Пример выполнения задания 1

Выделим компоненты связности ориентированного графа, изображенного на рисунке 1. В данной задаче количество вершин n=5.

Рисунке 1.

Значит, для данного ориентированного графа матрица смежности будет иметь размерность 5×5 и будет выглядеть следующим образом

                                                                 .

Найдем матрицу достижимости для данного ориентированного графа по формуле (1)

                                         , ,

                                                          ,

Следовательно,

.

Таким образом, матрица сильной связности, полученная по формуле (2), будет следующей:

.

Присваиваем p=1  и составляем множество вершин первой компоненты сильной связности D1: это те вершины, которым соответствуют единицы в первой строке матрицы S(D). Таким образом, первая компонента сильной связности состоит из одной вершины .

Вычеркиваем из матрицы S1(D) строку и столбец, соответствующие вершине v1, чтобы получить матрицу S2(D):

                                               .

Присваиваем p=2. Множество вершин второй компоненты связности составят те вершины, которым соответствуют единицы в первой строке матрицы S2(D), то есть . Составляем матрицу смежности для компоненты сильной связности  исходного графа D − в ее качестве возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из V2:

                                                           .

Вычеркиваем из матрицы S2(D) строки и столбцы, соответствующие вершинам из V2 ,чтобы получить матрицу S3(D), которая состоит из одного элемента:

                                                                  

и присваиваем p=3. Таким образом, третья компонента сильной связности исходного графа, как и первая, состоит из одной вершины .

Таким образом, выделены 3 компоненты сильной связности ориентированного графа D:

 

       D1:

D2:

 

       D3:

 

Максимальный поток и минимальный разрез

Теорема Форда-Фалкерсона 1 (о максимальном потоке и минимальном разрезе).

В любой сети существует максимальный поток. Величина максимального потока равна пропускной способности минимального разреза.

Теорема Форда-Фалкерсона 2.

Поток, вычисленный с помощью алгоритма Форда-Фалкерсона имеет максимальную величину, а разрез , где -множество вершин, помеченных при последнем помечивании, имеет минимальную пропускную способность.

 

Нахождение максимального потока и построение минимального разреза в сети с использованием алгоритма  Форда-Фалкерсона

В данной задаче основным параметром на дугах сети является  пропускная способность. Пропускная способность показывает, сколько единиц потока может быть передано по дугам сети. Таким образом, потоком в сети D = [N, M] называется неотрицательная вещественная функция, удовлетворяющая условиям:

1. ограниченности: поток по любой дуге сети не превосходит пропускной способности этой дуги ;

2. сохранения: суммарный поток, заходящий в любую вершину сети (кроме истока и стока), равен суммарному потоку, выходящему из этой вершины.

Дуга сети называется насыщенной, если поток по этой дуге равен пропускной способности этой дуги, т. е. .

Разрезом сети называется множество дуг, удаление которых из сети приводит к тому, что исток и сток оказываются несвязанными.

Пропускной способностью разреза называется число, равное сумме пропускных способностей дуг этого разреза. Разрез называется минимальным, если имеет наименьшую пропускную способность.

Отыскание минимального разреза – одна из основных задач анализа транспортных сетей. В силу конечности графа минимальный разрез может быть найден перебором всех разрезов, но этот путь, конечно, неприемлем для достаточно больших графов.

Минимальный разрез можно отыскать при помощи теоремы Форда – Фалкерсона: в любой транспортной сети величина любого максимального потока равна пропускной способности любого минимального разреза.

Для нахождения максимального потока в сети разработан алгоритм Форда – Фалкерсона. Перед началом выполнения алгоритма все вершины сети нумеруются произвольным образом, кроме источника и стока (источник получает минимальный номер 1, сток – максимальный , где  – число узлов).

Алгоритм состоит из следующих основных шагов:

1. Определить начальный поток в сети, сложив потоки по дугам, выходящим из источника.

2. Вершинам сети присвоить целочисленные метки, а дугам – знаки «+» и «–» по следующим правилам:

а) вершине-истоку присвоить метку ;

б) находим непомеченную вершину , смежную помеченной вершине . Если поток по соединяющей вершины  дуге меньше пропускной способности этой дуги, то происходит помечивание, иначе переходим к рассмотрению следующей вершины. Если вершина  является образом помеченной вершины , то происходит прямое помечивание (дуга в прямом направлении допустима): вершина  получает метку, равную номеру вершины , соединяющая вершины  дуга получает метку «+», переходим к рассмотрению следующей вершины. Если вершина  не имеет ни одного помеченного прообраза, поток по дуге в прямом направлении больше 0, то происходит обратное помечивание (дуга допустима в обратном направлении): вершина  получает метку, равную номеру вершины  (являющейся в данном случае ее образом), соединяющая вершины  дуга получает метку «–», происходит переход к рассмотрению следующей вершины. Процесс помечивания продолжается до тех пор, пока все удовлетворяющие этим условиям вершины не получат метку.

3. Если в результате процедуры помечивания вершина-сток метки не получила, то текущий поток – максимальный, переход к шагу 5. В противном случае перейти к пункту 4.

4. Рассмотреть последовательность вершин L, метка каждой из которых равна номеру следующей за ней вершины, и множество дуг МL, соединяющих соседние вершины из L.

Построение нового потока по схеме:

а) Если дуга принадлежит множеству МL (смотри выше) и имеет знак «+», то новый поток по этой дуге = старый поток по этой дуге + Δ (схему нахождения смотри далее).

б) Если дуга принадлежит множеству МL и имеет знак «–», то новый поток по этой дуге = старый поток по этой дугеΔ.

в) Если дуга не принадлежит множеству МL, то поток по дуге оставляем без изменения.

Схема нахождения Δ:

I. , где для нахождения  рассматриваются все дуги, принадлежащие множеству МL и имеющие знак «+», и для каждой такой дуги вычисляется разность между пропускной способностью дуги и потоком по этой дуге (). Затем из этих значений разностей выбирается минимальное значение и присваивается .

II. Для нахождения  рассматриваются все дуги, принадлежащие множеству МL и имеющие знак «–». Затем из этих дуг выбирается дуга с минимальным потоком (), и значение потока по этой дуге присваивается .

Перейти к шагу 2.

5. Определяем максимальный поток, складывая начальный поток и все полученные изменения потока.

В оптимальном решении, т. е. когда найден максимальный поток, минимальный разрез образуется насыщенными дугами.

Пример № 1 выполнения задания 2

На заданной сети  найти максимальный поток из X4 в X1 и минимальный разрез.
Image 
Решение
Необходимо заполнить таблицу:

 

 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

 


Image

После первого шага увеличиваем потоки в дугах, которые сначала были везде = 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
     Image, т.е. максимальный поток = 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
      Image        
     Т.е. величина минимального разреза совпадает с максимальным потоком.

Пример № 2 выполнения задания № 2.

Постановка задачи поиска максимального потока: найти максимальный поток из  в  для транспортной сети (рисунок) с помощью алгоритма Форда – Фалкерсона:

Решение:

Алгоритм

Конкретные действия

1.

 1-я итерация

 

1. .

2.1 (Второй шаг, первая итерация – подобное обозначение идет далее для всех шагов алгоритма). Производим помечивание вершин и дуг, результат показан на рисунке. Вершина 6 получила метку .

2.

2-я итерация

 

3.1.  .

4.1. ;

;

.

2.2. Заново осуществляется помечивание. Вершина 6 снова получает метку  (смотри рисунок).

3.

3-я итерация

 

 

3.2. .

4.2. ;

;

.

2.3. Осуществляется помечивание. При этом из вершины 3 прямых допустимых дуг не выходит, однако дуга 2–3 является допустимой в обратном направлении, и вершина 2 получает метку . Вершина 6 получает метку  (смотри  рисунок).

4.

4-я итерация

 

3.3. .

4.3. ;

;

;

;

.

2.4. Осуществляется помечивание. При этом из вершины 3 допустимые дуги не выходят. Вершина 6 не получает метку (смотри рисунок). Переходим к шагу 5.

5.

 

 

5. .

Минимальный разрез образуют насыщенные дуги 3–6 и 5–6. Пропускная способность минимального разреза . Условия теоремы Форда – Фалкерсона выполняются   задача решена правильно.

Алгоритм Форда – Фалкерсона используется при решении многих практических задач. Одна из них – задача об источниках и потребителях.

 

Задание:

1. С помощью матрицы смежности найти компоненты сильной связности ориентированного графа D. При решении использовать программу Grafoanalizator1.3.3 rus, Простой граф

Вариант1

Вариант 2

Вариант 3

2. Дана сеть:

Определить максимальный поток в сети при начальных значениях дуговых потоков: , , , , , , .

Варианты значений пропускных способностей дуг для задания:

 Порядок выполнения работы:

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.

практическая работа. Интернет ссылка: http://inf.reshuege.ru/test?theme=203

Теоретическая часть:

В основе построения большинства алгоритмов на графах лежит систематический перебор вершин графа, при котором каждая вершина просматривается в точности один раз, а количество просмотров ребер графа ограничено заданной константой (лучше – не более одного раза).

Один из основных методов проектирования графовых алгоритмов – это поиск (или обход графа) в глубину (depth first search, DFS), при котором начиная с произвольной вершины v0, ищется ближайшая смежная вершина v, для которой в свою очередь осуществляется поиск в глубину (т.е. снова ищется ближайшая, смежная с ней вершина) до тех пор, пока не встретится ранее просмотренная вершина, или не закончится список смежности вершины v (то есть вершина полностью обработана). Если нет новых вершин, смежных с v, то вершина v считается использованной, идет возврат в вершину, из которой попали в вершину v, и процесс продолжается до тех пор, пока не получим v = v0. Иными словами, поиск в глубину из вершины v основан на поиске в глубину из всех новых вершин, смежных с вершиной  v.

Путь, полученный методом поиска в глубину, в общем случае не является кратчайшим путем из вершины v в вершину u. Это общий недостаток поиска в глубину.  На рисунке показан путь, полученный обходом графа в глубину.

 

http://wwwcdl.bmstu.ru/iu7/stage9.files/image004.gif

Указанного недостатка лишен другой метод обхода графа – поиск в ширину (breadth first search, BFS). Обработка вершины v осуществляется путем просмотра сразу всех новых соседей этой вершины. При этом полученный путь является кратчайшим путем из одной вершины в другую.

показан путь, найденных методом поиска в ширину

http://wwwcdl.bmstu.ru/iu7/stage9.files/image005.gif 

При использовании алгоритмов DFS и BFS графы обходят разными способами, получая при этом некоторые подграфы, которые имеют специфические названия: каркасы, остовы или стягивающие деревья. Все вершины исходного графа входят в полученное стягивающее дерево, а все ветви дерева – это множество ребер из все множеств ребер графа.

Произвольный путь в графе, проходящий через каждое ребро графа точно один раз, называется эйлеровым путем. При этом, если по некоторым вершинам путь проходит неоднократно, то он является непростым. Если путь замкнут, то имеем эйлеров цикл. Для существования эйлерова пути в связном графе необходимо и достаточно, чтобы граф содержал не более двух вершин нечетной степени.

Путь в графе, проходящий в точности один раз через каждую вершину графа (а не каждое ребро) и соответствующий цикл называются гамильтоновыми и существуют не для каждого графа, как и эйлеров путь. В отличие от эйлеровых путей неизвестно ни одного простого необходимого и достаточного условия для существования гамильтоновых путей. Неизвестен даже алгоритм полиномиальной сложности, проверяющий существование гамильтонова пути в произвольном графе. Проблема существования гамильтонова пути принадлежит к классу так называемых NP-полных задач.

В теории алгоритмов классом NP (от англ. non-deterministic polynomial) называют множество задач распознавания (англ.), решение которых при наличии некоторых дополнительных сведений (так называемого сертификата решения) можно «быстро» (за время, не превосходящее полинома от размера данных) проверить на машине Тьюринга.

NP-полная задача — задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро».

При   решении   некоторых   практических   задач возникает  необходимость  поиска   максимального пути ( пути  с  наибольшей  суммой  длин  дуг).  Такая задача   сводится   к  задаче   нахождения  минимального   пути  заменой   знаков   при   длинах  дуг ( в  матрице весов  C)  на   противоположные .  При   этом  необходимым   является   требование   отсутствия   в  ориентированном графе  контуров  положительной  длины .

Поиск путей

знать:

o    если в город R можно приехать только из городов X, Y, и Z, то число различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть   NR = N+ N+ NZ, где NQ обозначает число путей из вершины A в некоторую вершину Q

o    число путей конечно, если в графе нет циклов – замкнутых путей

Пример задания:

 На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

 

Решение (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В

9)      подставляем результаты пп. 6 и 7 в формулу п. 5:

N = NВ + 2NЕ + 2NД

10)   в город Д можно приехать только из Б и В, поэтому

Д = 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)      теперь для удобства «обратного хода» вершины можно отсортировать так[1], чтобы сначала шли все вершины, в которые можно доехать только из начальной точки А:

Б ← А

Г ← А

затем на каждом шаге добавляем те вершины, в которые можно доехать из уже добавленных в список (и из исходной точки):

В ← АБГ

Е ← Г

далее добавляем все вершины, куда можно доехать из А, Б, Г, В и Е:

Д ← БВ

Ж ← ВЕ

на следующем шаге добавляем вершину И

И ←Д

и, наконец, конечную. вершину

К ←ИДЖЕ

именно в таком порядке мы и будем вычислять количество путей для каждой вершины

[1] Такая процедура называется топологической сортировкой графа.

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.

Возможные ловушки и проблемы:

o    очень важна аккуратность и последовательность; сначала идем от конечной точки к начальной, выписывая все вершины, из которых можно приехать в данную; затем идем обратно, определяя числовые значения

o    построение полного дерева маршрутов – занятие трудоемкое и достаточно бесперспективное, даже грамотные учителя информатики здесь в большинстве случаев что-то забывают и ошибаются

 

Решение (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.

Возможные проблемы:

o    при большом количестве маршрутов  легко запутаться и что-то пропустить 

o    Решение (5 вариант, графический):

o    1)      Главную идею решения: (число дорог в город N есть сумма дорог, приводящих в города, из которых есть прямой проезд в город N), отразим на самой схеме, показывая на ней ЧИСЛО ДОРОГ, приводящих в каждый город.

o    2)      Последовательность очевидна: начинаем с Б и Г (городов, куда есть по 1-й дороге из А) 

3)      Посчитаем дороги в В: 1 (из A)+ 1(дороги города Б)+ 1(дороги города В)= 3

4)      Аналогично посчитаем дороги в  Д, И, Е, Ж:

5)      Определяем число дорог в город К, как сумму дорог в города, с которыми он связан: Д, И, Ж, Е.

6)      Ответ: 13.

Задания:

Выполнить задание и проверить с помощью программы Grin, Простой граф.

1. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

http://inf.reshuege.ru/get_file?id=2625

2. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

http://inf.reshuege.ru/get_file?id=2626

 

3. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

http://inf.reshuege.ru/get_file?id=2630

4. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

http://inf.reshuege.ru/get_file?id=2631

5. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

http://inf.reshuege.ru/get_file?id=2632

6. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

http://inf.reshuege.ru/get_file?id=2633

7. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

http://inf.reshuege.ru/get_file?id=2634

8. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

http://inf.reshuege.ru/get_file?id=2637

9. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

http://inf.reshuege.ru/get_file?id=2641

10. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

http://inf.reshuege.ru/get_file?id=2642

11.  На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

http://inf.reshuege.ru/get_file?id=2643

12. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З?

http://inf.reshuege.ru/get_file?id=2644

13. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

http://inf.reshuege.ru/get_file?id=2645

14. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

http://inf.reshuege.ru/get_file?id=2646

15. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З?

http://inf.reshuege.ru/get_file?id=2647

16. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

http://inf.reshuege.ru/get_file?id=3026

17. На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H?

http://inf.reshuege.ru/get_file?id=3028

18. На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город M?

http://inf.reshuege.ru/get_file?id=3029

19. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

http://inf.reshuege.ru/get_file?id=3031

20. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город M?

http://inf.reshuege.ru/get_file?id=3092

21. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? http://inf.reshuege.ru/get_file?id=3651

22. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И?

http://inf.reshuege.ru/get_file?id=3652

23. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

http://inf.reshuege.ru/get_file?id=3653

24. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И?

http://inf.reshuege.ru/get_file?id=3654

25. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И?

http://inf.reshuege.ru/get_file?id=3655

26. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З?

http://inf.reshuege.ru/get_file?id=3656

27. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Е?

http://inf.reshuege.ru/get_file?id=2644

28. На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город E?

http://inf.reshuege.ru/get_file?id=3029

29. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З?

http://inf.reshuege.ru/get_file?id=2626

30. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

http://reshuege.ru:89/files/4191.png

Порядок выполнения работы:

 

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, практическая работа.

Теоретическая часть:

Нахождение кратчайшего пути на сегодняшний день является жизненно необходимой задачей и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в сетях и т.п.

Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом. Поиск кратчайшего пути ведется между двумя заданными вершинами в графе. Результатом является путь, то есть последовательность вершин и ребер, инцидентных двум соседним вершинам, и его длина.

Описываемый в данном разделе алгоритм позволяет находить в графе кратчайший путь между двумя выделенными вершинами  и  при положительных длинах дуг. Этот алгоритм предложенный в 1959 г. Дейкстрой, считается одним из наиболее эффективных алгоритмов решения задачи.

Главная идея, лежащая в основе алгоритма Дейкстры, предельно проста. Предположим, что нам известны  вершин, ближайших к вершине  (близость любой вершины x к вершине  определяется длиной кратчайшего пути, ведущего из  в ). Пусть также известны сами кратчайшие пути, соединяющие вершину  с выделенными m вершинами). Покажем теперь, как может быть определена -я ближайшая к  вершина.

 Окрасим вершину  и  ближайших к ней вершин. Построим для каждой неокрашенной вершины  пути, непосредственно соединяющие с помощью дуг  каждую окрашенную вершину  с . Выберем из этих путей кратчайший, и будем считать его условно кратчайшим путем из вершины  в вершину .

 Какая же из неокрашенных вершин является -й ближайшей к  вершиной? Та, для которой условно кратчайший путь имеет наименьшую длину. Это обусловливается тем, что кратчайший путь из вершины  в -ю ближайшую вершину при положительном значении длин всех дуг должен содержать в качестве промежуточных лишь окрашенные вершины, т. е. вершины, входящие в число  вершин, ближайших к вершине .

 Итак, если известны  ближайших к  вершин, то -я ближайшая к  вершина может быть найдена так, как это описано выше. Начиная с , описанная процедура может повторяться до тех пор, пока не будет получен кратчайший путь, ведущий из вершины  к вершине .

 

Алгоритм работает только для графов без рёбер отрицательного веса.

Любая задача,требующая нахождения оптимальных маршрутов может быть выполнена с помощью алгоритма Дейкстры. Это касается и сетей, и транспортных потоков, и обработка графов. Очень часто используется не сам алгоритм в чистом виде, а его модификация.

Примеры:

1. При эвакуации населения из очагов бедствия оптимальные маршруты до пунктов сбора транспорта для каждой группы людей(дом,улица,школа и т.д) в штабе МЧС рассчитывает программа на основе алгоритма Дейкстры.

2. Компьютерная игра. Указываете точку назначения для персонажа и он движется туда по кратчайшему маршруту. Это тоже алгоритм Дейкстры.

3. Дана сеть автомобильных дорог, соединяющих города Гомельской области. Некоторые дороги односторонние. Найти кратчайшие пути от города Гомеля до каждого города области (если двигаться можно только по дорогам).

4. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Милана до Минска.

Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.

OSPF разбивает процесс построения таблицы маршрутизации на 2 этапа.

Второй этап состоит в нахождении оптимальных маршрутов с помощью полученного графа. Задача нахождения оптимального пути на графе является достаточно сложной и ёмкой. В протоколе OSPF для её решения используется итеративный алгоритм Дейкстры. Каждый маршрутизатор считает себя центром сети и ищет оптимальный маршрут до каждой известной ему сети. В каждом найденном таким образом маршруте запоминается только один шаг - до следующего маршрутизатора, в соответствии с принципом одношаговой маршрутизации. Данные об этом шаге и попадают в таблицу маршрутизации. Если несколько маршрутов имеют одинаковую метрику до сети назначения, то в таблице маршрутизации запоминаются первые шаги всех этих маршрутов".

Алгоритм

1. Каждой вершине  в ходе алгоритма присваивается число , равное длине кратчайшего пути из вершины  в вершину  и включающем только окрашенные вершины. Положить  и  для всех остальных вершин графа. Окрашиваем вершину  и полагаем , где  – последняя окрашенная вершина.

2. Для каждой неокрашенной вершины  пересчитывается величина  по следующей формуле:

  

3. Если  для всех неокрашенных вершин, то алгоритм заканчивается т. к. отсутствуют пути из вершины  в неокрашенные вершины. Иначе окрашивается та вершина, для которой величина  является минимальной. Окрашивается и дуга, ведущая в эту вершину в соответствии с выражением   и полагаем .

4. Если , кратчайший путь из  в  найден. Иначе переходим к шагу 2.

Каждый раз окрашивается вершина и дуга, заходящая в эту вершину. Окрашенные дуги не могут образовывать цикл, а образуют в исходном графе дерево с корнем (началом) в вершине . Это дерево называют ориентированным деревом кратчайших путей. Путь из  в  принадлежит этому дереву. При поиске одного кратчайшего пути процедура наращивания завершается при достижении конечной вершины этого пути. Нам же необходимо получить все кратчайшие пути начинающиеся в вершине №1. Для этого процедуру наращивания ориентированного дерева продолжается до тех пор, пока все вершины не будут включены. Таким образом, мы получаем ориентированное дерево кратчайших путей, которое является покрывающим деревом графа.

 Иногда в графе имеются несколько кратчайших путей. Кратчайший путь будет единственным, если в алгоритме ни разу не возникает неоднозначность при окрашивании дуги.

Отметим, что главным условием успешного применения алгоритма Дейкстры к задаче на графе является неотрицательность длин дуг этого графа

Для графа с отрицательными весами применяется более общий алгоритм — Алгоритм Дейкстры с потенциалами.

Пример выполнения задания.

Требуется найти кратчайшие расстояния от 1-й вершины до всех остальных для графа, представленного на рисунке:

Алгоритм

Конкретные действия

1.

Инициализация.

Cтартовая вершина, от которой строится дерево кратчайших путей - вершина № 1.

Задаем стартовые условия: d(1)=0, d(x)=∞.

Окрашиваем вершину № 1, y=1.

Находим ближайшую вершину к окрашенной нами, используя формулу: .

Составим матрицу длин кратчайших дуг для данного графа.

№/№

1

2

3

4

5

6

1

7

9

14

2

7

10

15

3

9

10

11

2

4

15

11

6

5

6

9

6

14

2

9

или

 

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.

Находим ближайшую вершину к окрашенной нами, используя формулу: .

Составим матрицу длин кратчайших дуг для данного графа.

№/№

1

2

3

4

5

6

1

10

18

8

2

10

16

9

21

3

16

15

4

7

9

12

5

23

6

15

23

 

или

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. Какое программное обеспечение лучше подходит для вычисления пути?

 

 

 

 

 

 

 

Просмотрено: 0%
Просмотрено: 0%
Скачать материал
Скачать материал "Методические рекомендации по выполнению практических работ по междисциплинарному курсу «МДК.01.02. Математический аппарат для построения компьютерных сетей»"

Методические разработки к Вашему уроку:

Получите новую специальность за 3 месяца

Специалист по работе с молодежью

Получите профессию

Копирайтер

за 6 месяцев

Пройти курс

Рабочие листы
к вашим урокам

Скачать

Скачать материал

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

6 625 522 материала в базе

Скачать материал

Другие материалы

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

  • Скачать материал
    • 23.12.2016 5549
    • DOCX 9.5 мбайт
    • 88 скачиваний
    • Рейтинг: 4 из 5
    • Оцените материал:
  • Настоящий материал опубликован пользователем Богданова Татьяна Сергеевна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт

    Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.

    Удалить материал
  • Автор материала

    Богданова Татьяна Сергеевна
    Богданова Татьяна Сергеевна
    • На сайте: 8 лет и 3 месяца
    • Подписчики: 5
    • Всего просмотров: 40696
    • Всего материалов: 19

Ваша скидка на курсы

40%
Скидка для нового слушателя. Войдите на сайт, чтобы применить скидку к любому курсу
Курсы со скидкой

Курс профессиональной переподготовки

Технолог-калькулятор общественного питания

Технолог-калькулятор общественного питания

500/1000 ч.

Подать заявку О курсе

Курс профессиональной переподготовки

Теория и методика обучения информатике в начальной школе

Учитель информатики в начальной школе

300/600 ч.

от 7900 руб. от 3950 руб.
Подать заявку О курсе
  • Сейчас обучается 94 человека из 34 регионов

Курс повышения квалификации

Применение компьютерных моделей при обучении математике и информатике в рамках ФГОС ООО

72 ч. — 180 ч.

от 2200 руб. от 1100 руб.
Подать заявку О курсе
  • Сейчас обучается 47 человек из 24 регионов

Курс профессиональной переподготовки

Информационные технологии в профессиональной деятельности: теория и методика преподавания в образовательной организации

Преподаватель информационных технологий

300/600 ч.

от 7900 руб. от 3950 руб.
Подать заявку О курсе
  • Сейчас обучается 188 человек из 53 регионов

Мини-курс

Анализ межпредметных связей: связь педагогики с научными дисциплинами

10 ч.

1180 руб. 590 руб.
Подать заявку О курсе

Мини-курс

Особенности психологической помощи детям

6 ч.

780 руб. 390 руб.
Подать заявку О курсе
  • Сейчас обучается 396 человек из 65 регионов

Мини-курс

Дизайн-проектирование: практические и методологические аспекты

4 ч.

780 руб. 390 руб.
Подать заявку О курсе