Эйлеровы и полуэйлеровы графы. Гамильтоновы графы

Л.В. Командина

 

ИССЛЕДОВАНИЕ ОПЕРАЦИЙ.

ЗАДАЧИ НА ГРАФАХ
И СЕТЯХ

Методические рекомендации

для студентов специальности
«Прикладная математика»

 

2010

УДК 519.8(075)

ББК 22.18я73

К63

 

Автор: доцент кафедры прикладной математики и механики УО «ВГУ им. П.М. Машерова», кандидат физико-математических наук Л.В. Командина

 

Р е ц е н з е н т ы:

доцент кафедры информатики и информационных технологий УО «ВГУ им. П.М. Машерова», кандидат биологических наук А.А. Чиркина; старший преподаватель кафедры прикладной
математики и механики УО «ВГУ им. П.М. Машерова» О.Г. Казанцева

 

 

Научный редактор: заведующий кафедрой кафедры прикладной математики и механики
УО «ВГУ им. П.М. Машерова», кандидат физико-математических наук,
доцент Л.В. Маркова

 

 

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

 

 

УДК 519.8(075)

ББК 22.18я73

 

Ó Командина Л.В., 2010

Ó УО «ВГУ им. П.М. Машерова», 2010

СОДЕРЖАНИЕ

Введение.............................................................................................. 4

§ 1. Неориентированные графы.......................................................... 4

§ 2. Эйлеровы и полуэйлеровы графы. Гамильтоновы графы....... 11

§ 3. Деревья и их свойства................................................................. 17

§ 4. Остовное дерево графа. Алгоритмы Прима и Краскала.......... 19

§ 5. Ориентированные графы............................................................ 24

§ 6. Задача построения кратчайшего пути из заданной вершины.. 27

§ 7. Общая задача построения кратчайшего пути........................... 33

§ 8. Задача о максимальном потоке.................................................. 42

§ 9. Некоторые обобщения задачи о максимальном потоке............ 53

§ 10. Задача о назначениях............................................................... 56

§ 11. Задания к лабораторным работам........................................... 65

11.1. Лабораторная работа «Построение остовного дерева минимального веса»..................................................................................................... 65

11.2. Лабораторная работа «Нахождение кратчайшего пути на сети» 67

11.3. Лабораторная работа «Нахождение на сети потока максимальной величины»..................................................................................................... 70

11.4. Лабораторная работа «Нахождение оптимального назначения» 70

Литература........................................................................................ 71

 

Введение

 

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

В предлагаемом учебном издании излагаются основные понятия теории графов. В четырех первых параграфах рассматриваются неориентированные графы и задача построения остовного дерева минимального веса. Затем рассматриваются ориентированные графы и задача построения кратчайшего пути (алгоритм Дейкстры и алгоритм Флойда), задача о максимальном потоке (алгортим Форда-Фалкерсона) и ее некоторые обобщения, классическая задача о назначениях и некоторые ее варианты. В предложенном перечне литературы [1–5, 7] можно найти дополнительный материал по указанным задачам.

 

Неориентированные графы

 

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

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

Второе множествоопределяется следующим образом

,

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

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

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

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

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

Вершины в графе могут отличаться друг от друга количеством ребер, которым они инцидентны (принадлежат). Степеньювершины называется число ребер графа, инцидентных данной вершине. Например, на рис. 1.1а вершина имеет степень = 3, на рис. 1.2 для вершины степень равна = 5, для вершины степень равна
= 0, а на рис. 1.3 для вершины степень равна = 1.

Встречается другое обозначение степени вершины: .

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

Граф называется простым, если он не содержит петель и параллельных ребер (рис. 1.1). Простой граф называется полным, если в нем каждая пара вершин смежна. Граф, содержащий хотя бы два парал-лельных ребра, называется мультиграфом (рис. 1.2, рис. 1.3). Граф, содержащий хотя бы одно ребро вида петля, называется псевдографом (рис. 1.2).

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

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

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

, (1.1)

либо последовательностью ребер:

, (1.2)

где =, =, …, =, либо последовательностью и вершин и ребер

.

Говорят, что маршрут соединяет вершины и. Маршрут, все ребра которого различны, называется цепью. Цепь, все вершины которой различны, называется простой цепью.

Маршрут (1.1), у которого, называется циклическим маршрутом. Если (1.1) является цепью (простой цепью), то при условии имеем цикл ( простой цикл ).

На рис. 1.2 последовательность является маршрутом, последовательность является цепью, а последовательность является простой цепью.

Нетрудно убедиться в справедливости следующих утверждений.

Лемма 1.1. Если в последовательности (1.1) вершины и различны, то маршрут их соединяющий содержит простую цепь.

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

.

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

Лемма 1.2. Любой циклический маршрут содержит простой цикл.

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

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

.

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

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

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

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

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

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

Пусть – простой граф, в котором, . Графу ставят в соответствие либо матрицу смежности, либо матрицу инцидентности.

Матрица смежности – это квадратная матрица порядка n (строки и столбцы этой матрицы соответствуют вершинам графа ), элементы которой определяются следующим образом:

 

Из определения вытекает, что матрица смежности неориентированного графа – это симметрическая матрица, все элементы главной диагонали равны нулю. Кроме этого число единиц в строке (столбце) равно степени соответствующей вершины. В случае мультиграфа ненулевой элемент матрицы равен числу ребер, соединяющих вершины i и j. Очевидно, что любой симметрической матрице с целыми неотрицательными элементами можно поставить в соответствие мультиграф, а если ненулевые элементы матрицы равны 1, то – простой граф.

Матрицы смежности графов, представленных на рис.1.1а и рис.1.3, имеют вид:

, .

Матрица инцидентности – это n´ m-матрица, строки этой матрицы соответствуют вершинам графа, а столбцы – ребрам. Если ребра графа обозначить через, то элементы матрицы определяются следующим образом:

 

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

Составим матрицы инцидентности для графов, представленных на рис.1.1а и рис.1.3. Слева от матрицы перечислим вершины, а сверху – ребра графа. Получим

 

Из определения матриц смежности и инциденций видно, что они чаще всего относятся к так называемым слабо заполненным матрицам (среди элементов матриц большой процент нулевых элементов). С точки зрения программирования этот способ задания графов является расточительным. В микроэлектронике исследуются графы, которые имеют до 2000 вершин, средняя степень которых 6 – 8. Матрица смежности содержит 4000000 элементов, из которых только примерно 16000 равны единице, а остальные – нули [5].

Существует еще один способ задания графа – списки смежности. Каждой вершине i графа ставится в соответствие список вершин, смежных с вершиной i. Например, для графа, представленного на рис.1.1а, списки смежности следующие:

= (i₂, i₄), = (i₁, i₃, i₄), = (i₂, i₄), = (i₁, i₂, i₃);

для графа, представленного на рис. 1.3:

= (i₂, i₂, i₄), = (i₁, i₁, i₃, i₄, i₅), = (i₂, i₄),

= (i₁, i₂, i₃), = (i₂, i₆), = (i₅).

 

Задания

1. Доказать теорему Эйлера.

2. Доказать лемму 1.2.

3. Доказать лемму 1.4.

4. Доказать лемму 1.5.

5. Изобразить граф по заданным спискам смежности:

S(1) = (3, 5), S(2) = (3, 4), S(3) = (1, 2, 4, 5),

S(4) = (2, 3, 5); S(5) = (1, 3, 4).

6.

Составить матрицу смежности, матрицу инцидентности и списки смежности для графа G на рис.1.4.

7. Изобразить графы по заданным матрицам смежности:

а) , б) .

8. Изобразить графы по заданным матрицам инцидентности:

а) , б) .

 

Деревья и их свойства

 

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

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

Теорема 3.1. Пусть, где, . Тогда следующие утверждения эквивалентны:

1) – дерево.

2) не содержит циклов и.

3) – связный граф и.

4) Любые две вершины соединяет единственная простая цепь.

5) не содержит циклов, и если соединить ребром любую пару несмежных вершин, то новый граф содержит ровно один цикл.

Доказательство. Схема: 1) Û 2); 1) Þ 5) Þ 4) Þ 1); 1) Û 3).

1) Þ 2). Имеем связный граф без циклов. Согласно лемме 1.3 в нем существует вершина, степень которой равна 1, т.е. висячая вершина. Ей инцидентно висячее ребро. Удалим и вершину, и ребро из графа. Новый граф также связный и не содержит циклов (лемма 1.4). Повторим процедуру удаления. Через шага останутся две вершины и одно ребро им инцидентное. Таким образом, в исходном графе число ребер на единицу меньше числа вершин, т.е..

2) Þ 1). Имеем граф без циклов, в котором. Предположим, что он несвязный. Тогда в нем можно выделить компоненты связности. Пусть для определенности их две. Каждая из них по определению является деревом, а значит, в каждой из них число ребер на единицу меньше числа вершин. Тогда в графе число вершин n больше числа ребер m на 2. Противоречие.

1) Þ 5). Имеем связный граф без циклов. Пусть i , j – две несмежные вершины графа. В силу связности в существует простая цепь, соединяющая эти две вершины. Добавим ребро, тем самым образуется цикл, который обозначим через C. Докажем, что он единственный методом от противного. Пусть кроме цикла C образовался еще один цикл C₁ (рис. 3.2), понятно, что он одержит ребро, т.к. в исходном графе циклов не было. Очевидно, что тогда образуется третий цикл: вершина i, затем обход по циклу C до вершины j, затем обход по циклу C₁ до вершины i. Заметим, что этот цикл не содержит ребра, а значит, существует в исходном графе G. Противоречие.

5) Þ 4). Имеем граф без циклов. Пусть i , j – две несмежные вершины графа. Добавим ребро и тем самым образуем единственный цикл, который начинается в вершине j и заканчивается ребром. Но это означает, что в графе существует единственная простая цепь, соединяющая эти две вершины.

4) Þ 1). Имеем граф, в котором любые две вершины соединяет единственная простая цепь. Значит, граф – связный и не содержит циклов (ибо в противном случае для несмежных вершин существовали бы, по крайней мере, две цепи, их соединяющих). Другими словами, – дерево.

3) Þ 1). Пусть – связный граф и. Предположим, что в G существует цикл. В любом цикле число вершин равно числу ребер. Поэтому в силу второго условия в графе имеются вершины и ребра, не входящие в рассматриваемый цикл. Найдем все висячие вершины и инцидентные им висячие ребра, удалим их. Для нового графа имеем соотношение: , где m₁ – число ребер, n₁ - число вершин в графе. Если в графе имеется еще один цикл, то удалим из него ребро, не принадлежащее рассматриваемому графу. Получим граф, для которого, . Продолжим этот процесс, через конечное число шагов получим граф, состоящий из рассматриваемого цикла, для которого. Таким образом, в исходном графе число ребер не меньше числа вершин: . Противоречие. Итак, – связный граф без циклов, т.е. дерево.

1) Þ 3). (Самостоятельно).

Теорема доказана.

Теорема 3.2. В любом дереве, для которого ï Uï ³ 2, не менее двух висячих вершин (рис. 3.3).

Задания

1. Доказать, что в теореме 3.1 что из утверждения 1) следует утверждение 3).

2. Доказать теорему 3.2.

 

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

 

Ориентированный граф G (или орграф ), как и неориентированный, определяется заданием двух множеств I и U и обозначается также: .

Элементы множества I, как и прежде, называются вершинами. Будем их обозначать буквами i , j. Вершины изображают точками плоскости или пространства.

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

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

Для ориентированного графа вводятся понятия полустепени заходавершины – количество дуг, заходящих в, и полустепени исхода – количество дуг, исходящих из. Понятно, что + =. На рис. 5.1а для вершины i₂ имеем: , , .

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

Если в графе G множество U содержит как ребра, так и дуги, то граф называется смешанным. Смешанный граф преобразуется в орграф путем замены ребра {i, j} на две дуги и. На рис. 5.1б представлен пример смешанного графа. После замены ребра на дуги и, ребра на дуги и получим орграф, который представлен на рис. 5.1в.

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

, , …, , . (5.1)

Задать маршрут (5.1) можно и последовательностью его вершин:

, (5.2)

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

Если в ориентированном маршруте (ориентированной цепи, пути) начало и конец совпадают: , то получаем циклический ориентированный маршрут ( ориентированный цикл, контур ).

На рис.5.1в последовательность вершин задает ориентированную цепь; последовательность вершин задает путь, который можно записать как последовательность дуг

, , ,

последовательность дуг, , задает контур.

Нетрудно убедиться, что справедлива

Лемма 5.1. Любой ориентированный маршрут содержит путь.

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

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

Так же как и для неориентированного графа вводятся понятие подграфа и понятие компоненты связности. Очевидно, что для ориентированного графа остается верной лемма 1.4.

Рассмотрим способы задания ориентированного графа. Как и неориентированный граф его можно задать рисунком или с помощью матрицы. Для простого орграфа G, в котором, , матрица смежности – это квадратная матрица А порядка n (строки и столбцы этой матрицы соответствуют вершинам графа G). Элементы матрицы определяются следующим образом:

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

Матрица инцидентности – это n´ m-матрица В (строки этой матрицы соответствуют вершинам графа G, а столбцы – дугам). Элементы матрицы определяются следующим образом:

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

Матрицы смежности и инцидентности графа, представленного на рис.5.1а имеют вид:

, .

Еще один способ задания орграфа – списки смежности. Каждой вершине i графа ставится в соответствие список вершин, недостижимых из вершины i посредством одной дуги. Например, для графа, представленного на рис.5.1а, списки смежности следующие:

= (i₄), = (i₁, i₃), = Æ, = (i₂, i₃).

 

Задания

1. Доказать лемму 5.1.

2. Составить матрицу смежности и матрицу инцидентности орграфа, представленного на рис.5.1в.

 

Алгоритм Дейкстры

Шаг 0. Каждой вершине i сети G ставим в соответствие метку:

 

– постоянная метка, остальные метки временные.

Шаг k. Определены вершины с постоянными метками: , и p – последняя вершина, получившая постоянную метку.

1 этап (этап обновления меток).

1) Находим – множество вершин, соседних справа для вершины р.

2) Находим: из множества исключаем вершины, имеющие постоянные метки, т.е. = \.

3) Для каждой вершины i Î пересчитываем метки по правилу:

=,

где – прежняя временная метка вершины i, – новая временная метка вершины i, – постоянная метка вершины р, – длина дуги.

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

1) Формируем множество I_k – множество вершин с временными метками.

2) Находим вершину с минимальной временной меткой:

=. (6.1)

3) Метка – становится постоянной, вершина.

Выход из алгоритма (принцип останова).

Если, то – минимальная длина пути из заданной вершины s в заданную вершину t.

Если = Æ и вершина t имеет временную метку, равную ¥, то в сети не существует пути из вершины s в вершину t.

Замечание 1. Алгоритм может быть модифицирован таким образом, что кроме значения минимального пути будет получен и сам путь, например, в виде последовательности вершин. Для этого метку вершины на шаге обновления меток дополним информацией о вершине, через которую пересчитывается минимум в (6.1), т.е. метка вершины будет состоять из двух частей. Как только вершина t получит постоянную метку, по второй части метки определим предшествующую ей вершину. По второй части метки последней определим ей предшествующую вершину и т.д., пока не доберемся до вершины s.

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

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

Если на некотором шаге ⁺(p) = Æ и некоторые вершины имеют временную метку, равную ¥, то в сети не существует пути из вершины s до этих вершин.

Пример. На сети, представленной на рис. 6.1, найти кратчайший путь из вершины s до вершины t.

 

Итерация 0. ℓ (s) = 0, ℓ (i) = ¥, iÎ {1, 2, 3, 4, 5, t}, p = s.

Дальнейшие вычисления на каждой итерации оформим в виде таблиц.

Итерация 1.
p			первая часть метки ℓ ’(i)	вторая часть метки	Результат сравнения	Вид метки
s	1, 2, 3		ℓ ’(1) = min{¥; 0+7}=7, ℓ ’(2) = min{¥; 0+1}=1, ℓ ’(3) = min{¥; 0+3}=3.	s s s	(min)	врем. пост.врем.

 

Итерация 2.
p			первая часть метки ℓ ’(i)	вторая часть метки	Результат сравнения	Вид метки
соседние справа для вершины р
	4, 5		ℓ ’(4) = min{¥; 1+2}=3, ℓ ’(5) = min{¥; 1+4}=5.		(min)	врем. врем.
другие вершины с временными метками
			ℓ ’(1) = 7, ℓ ’(3) = 3.	s s	(min)	врем. пост.

 

Замечание. Выбор вершины р неоднозначен, можно выбрать либо вершину 4, либо вершину 3. Полагаем р = 3.

 

Итерация 3.
p			первая часть метки ℓ ’(i)	вторая часть метки	Результат сравнения	Вид метки
соседние справа для вершины р
			ℓ ’ (5) = min{5; 3+4}=5.			врем.
другие вершины с временными метками
			ℓ ’(1) = 7, ℓ ’(4) = 3.	s	(min)	врем. пост.

 

Итерация 4.
p			первая часть метки ℓ ’(i)	вторая часть метки	Результат сравнения	Вид метки
соседние справа для вершины р
	t	t	ℓ ’(t) = min{¥; 3+3}=6.			врем.
другие вершины с временными метками
			ℓ ’(1) = 7, ℓ ’(5) = 5.	s	(min)	врем. пост.

 

Итерация 5.
p			первая часть метки ℓ ’(i)	вторая часть метки	Результат сравнения	Вид метки
соседние справа для вершины р
	4, t	t	ℓ ’(t) = min{6; 5+3}=6		(min)	пост.
другие вершины с временными метками
			ℓ ’(1) = 7	s		врем.

 

Так как вершина t получила постоянную метку, то решение закончено. Длина кратчайшего пути из заданной вершины s в вершину t равна 6. По второй части метки вершин восстанавливаем этот путь: t 4 2 s.

Замечание 3. Алгоритм неприменим к сетям, где есть отрицательные веса дуг. На рис. 6.2 представлена сеть, где ℓ _1t = –2. Согласно алгоритму Дейкстры минимальный путь из вершины s в вершину t равен 3 (вершина t является 1-ой ближайшей). На самом деле минимальный путь проходит через вершину 1, его длина равна 2.

 

Алгоритм Флойда

Шаг 0. Формируем две n´ n-матрицы:

– матрица расстояний, где

(7.1)

– справочная матрица, где = i, .

Шаг k. Известны матрицы и. Находим матрицы, и =:

1) в матрице выделяем k-ый столбец и k-ую строку (назовем их базовыми),

2) вычисляем элементы новых матриц по правилу, используя элементы базовых строки и столбца:

если, то (7.2)

если, то (7.3)

Выход из алгоритма (принцип останова).

Если k = n + 1, то найденная матрица является матрицей искомых расстояний. Справочная матрица служит для определения вершин, через которые пройдет соответствующий минимальный путь. Значение показывает номер t вершины, предшествующей вершине j на пути из вершины i. Далее значение показывает номер вершины, предшествующий вершине t на пути из вершины i. И так далее, пока значение элемента i-ой строки не будет равно i.

Поясним смысл шага 1. Базовыми являются первая строка и первый столбец. Рассмотрим элемент матрицы, где. Согласно формулам (7.2) и (7.3) сравниваются две величины: – длина дуги непосредственно из вершины i в вершину j, и – длина «обходного» пути из вершины i в вершину j через вершину 1 (см. рис.7.1). Элементу присваивается значение, равное меньшему из сравниваемых величин. Очевидно, что при или (не существует «обходного» пути из вершины i в вершину j через вершину 1) значение =. В случае, когда, изменяется соответствующий элемент справочной матрицы: = 1. Так фиксируется вершина, через которую проходит «обходной» путь.

Теорема 1. Пусть – взвешенный орграф, в котором нет контуров отрицательной длины. Если в матрице элемент, то

а) есть длина минимального пути из вершины i в вершину j, где промежуточными вершинами являются вершины из;

б) в матрице элемент – номер вершины, которая непосредственно предшествует вершине j на пути из i в j.

Доказательство. Пусть k – некоторое целое неотрицательное число, не большее. В соответствие ему поставим множество вершин.

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

Если k = 0, то множество промежуточных вершин пусто, положим =.

Пусть k > 0. Для пары вершин i и j, , строим все пути (если они существуют) из i в j такие, что промежуточными вершинами могут быть лишь вершины из множества, сравниваем длины всех построенных путей, выбираем наименьшее значение. Это значение и есть элемент матрицы. Если же указанного выше пути не существует, то полагаем = ¥.

Докажем, что =, где матрица определена на k-том шаге алгоритма Флойда.

Воспользуемся методом математической индукции по числу k, .

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

Пусть утверждение справедливо для.

Докажем его для. Согласно алгоритму Флойда элементы матриц и находим либо по формуле (7.2):

, (7.4)

либо по формуле (7.3):

, . (7.5)

Базовыми являются m-ая строка и m-ый столбец. Сравниваем две величины: – длина пути из вершины i в вершину j, и – длина «обходного» пути из вершины i в вершину j через вершину m (см. рис. 7.1). Причем по индуктивному предположению числа, , – длины кратчайших путей, где промежуточными вершинами могут быть вершины из множества. Понятно, что – длина самого короткого «обходного» пути из вершины i в вершину j через вершины из множества. Поэтому формулы (7.4) или (7.5) дают значение кратчайшего пути из вершины i в вершину j через вершины из множества.

123456Следующая ⇒

Поделиться: