Файл: 9. Гамильтоновы графы. Достаточные условия гамильтоновости графа. 17.docx

C *  E * D * C * A.Стрелка со звездочкой означает, что на соответствующем шаге выбранное продолжение маршрута является единственно возможным.Описанный метод можно применить для прохождения лабиринтов. Коридорам лабиринта соответствуют ребра графа, развилкам и тупикам – вершины. Следует обойти граф, как указано выше, пройдя каждый коридор по два раза: по одному в каждом направлении. Начало и конец каждого коридора следует отмечать стрелками, как указано в алгоритме. Стрелка с точкой ставится в конце коридора, если в соответствующую развилку попали в первый раз. Так как в результате весь лабиринт будет пройден, когда-нибудь будет найден выход. При повторном прохождении лабиринта следует идти только по стрелкам, для которых отсутствуют встречные стрелки.

9. Гамильтоновы графы. Достаточные условия гамильтоновости графа.

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

10. Взвешенные графы. Минимальное остовное дерево и алгоритмы его построения.

Взвешенным графом называется граф, вершинам и/или ребрам которого присвоены «весы» — обычно некоторые числа. Пример взвешенного графа — транспортная сеть, в которой ребрам присвоены весы: они показывают стоимость перевозки груза по ребру и пропускные способности дуг.

1. 
   Остовным деревом графа называется его подграф, являющийся деревом и содержащий все вершины графа.
   

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

---

минимального остовного дерева, то есть остовного дерева с минимальным суммарным весом ребер. Упражнение 5.4.1. Докажите, что минимальное остовное дерево существует.Опишем жадный алгоритм для построения минимального остовного дерева.

1. 
   Находим ребро с минимальным весом и включаем его в строящееся остовное дерево.
   
2. 
   Из оставшихся ребер отбрасываем те, при добавлении которых к уже построенному дереву образуется цикл. Среди оставшихся находим ребро с минимальным весом и включаем его в строящееся остовное дерево.
   
3. 
   Пункт 2 повторяем, пока не будет построено дерево.
   

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

3. 
   П остроить минимальное остовное дерево для графа, изображенного на рис. 26.
   

Шаг 1. Начальной вершине А присваиваем окончательную метку 0, всем остальным вершинам – временные метки +.Шаг 2. Для вершины A_i, метка которой получила на предыдущем шаге окончательное значение a_i, определяем все возможные продолжения маршрута. Каждой не имеющей окончательной метки вершине A_j, в которую из a_i ведет ребро с весом b_ij, присваиваем новую временную метку a_i +b_ij, если это число меньше ее старой метки.Шаг 3. Из всех временных меток выбирается наименьшая и объявляется окончательной. В случае равенства меток выбирается любая из них.Шаг 4. Если вершина В получила окончательную метку, алгоритм останавливается. В противном случае возвращаемся к шагу 2.

---

11. Кратчайшие пути на графах. Алгоритмы Декстры и Белламана- Мура.

Зада́ча о кратча́йшем пути́ — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь. Алгори́тм Де́йкстры — алгоритм на графах, находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.Алгоритм Беллмана —Мура — алгоритм поиска кратчайшего  пути во взвешенном графе. За время {\displaystyle O(|V|\cdot |E|)} алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана — Форда допускает рёбра с отрицательным весом. 

12. Кратчайшие пути между всеми парами вершин графа. Алгоритм Флойда.

Зада́ча о кратча́йшем пути́ — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.Метод Флойда непосредственно основывается на том факте, что в графе с положительными весами ребер всякий неэлементарный (содержащий более 1 ребра) кратчайший путь состоит из других кратчайших путей. Этот алгоритм более общий по сравнению с алгоритмом Дейкстры, так как он находит кратчайшие пути между любыми двумя вершинами графа. В алгоритме Флойда используется матрица A размером nxn, в которой вычисляются длины кратчайших путей. Элемент A[i,j] равен расстоянию от вершины i к вершине j, которое имеет конечное значение, если существует ребро (i,j), и равен бесконечности в противном случае.

---

Алгоритм Флойда Основная идея алгоритма. Пусть есть три вершины i, j, k и заданы расстояния между ними. Если выполняется неравенство A[i,k]+A[k,j]путь i->j путем i->k->j. Такая замена выполняется систематически в процессе выполнения данного алгоритма.

Шаг 0. Определяем начальную матрицу расстояния A₀ и матрицу последовательности вершин S₀. Каждый диагональный элемент обеих матриц равен 0, таким образом, показывая, что эти элементы в вычислениях не участвуют. Полагаем k = 1.

Основной шаг k. Задаем строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения замены описанной выше, ко всем элементам A[i,j] матрицы A_k-1. Если выполняется неравенство  , тогда выполняем следующие действия:

1. 
   создаем матрицу A_k путем замены в матрице A_k-1 элемента A[i,j] на сумму A[i,k]+A[k,j] ;
   
2. 
   создаем матрицу S_k путем замены в матрице S_k-1 элемента S[i,j] на k. Полагаем k = k + 1 и повторяем шаг k.
   

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

На каждой итерации перебираются все пары вершин и путь между ними сокращается при помощи i -й вершины.

13. Упорядочивание дуг и вершин ориентированного графа. Алгоритм Фалкерсона.

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

1) вершины первой группы не имеют предшествующих вершин, а вершины последней группы последующих;

2) вершины любой другой группы не имеют предшествующих в следующей группе;

3) вершины одной и той же группы дугами не соединяются.

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

---

алгоритма Фалкерсона.Алгоритм Фалкерсона (движение вперед) для упорядочения вершин:1. Находят вершины графа, в которые не входит ни одна дуга. Они образуют первую группу. Нумеруют вершины группы в натуральном порядке 1, 2, ... . При этом присвоение номеров вершинам внутри группы может быть сделано не единственным образом, что не имеет значения.2. Мысленно вычеркиваем все пронумерованные вершины и дуги, из них выходящие. В получившемся графе найдется, по крайней мере, одна вершина, в которую не входит ни одна дуга. Этой вершине, входящей во вторую группу, присваивается очередной номер и т.д. Этот шаг повторяется до тех пор, пока все вершины не будут упорядочены (пронумерованы).Алгоритм Фалкерсона для упорядочения дуг:1. Найти дуги, не имеющие непосредственно предшествующих (они образуют I группу).2. Вычеркнуть найденные дуги; после этого появится, по крайней мере, одна новая дуга, не имеющая непосредственно предшествующей (в графе без дуг I группы). Такие дуги составляют II группу. Повторять этот шаг, пока все дуги не будут разбиты на группы. В заключение упорядочения дугам присваивают новые обозначения с индексами 1, 2, ... .Пример. Графическим способом упорядочить вершины и дуги заданного орграфа.Решение. Используя алгоритм Фалкерсона, упорядочим вершины и дуги заданного орграфа.

---