Определение минимального остова

Для взвешенного графа остов с минимальной суммой весов вошедших в него ребер

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

Алгоритм построения системы независимых циклов графа

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

2. Выбираем очередное неотмеченное ребро и строим цикл, включающий это ребро и ребра остова. Он обязательно существует, так как вершины остова связны. Рассмотренное ребро отмечается и, если есть еще неотмеченные ребра, то выполняется шаг 2, иначе - шаг 3.

3. По формуле Эйлера производится проверка числа построенных циклов (для самопроверки).

Пример:

x₂ x₂

1 3 1 3

x₁ 2 x₃ x₁ 2 x₃

7 4 5 7 4 5

x₅ 6 x₄ x₅ 6 x₄

Рис.43

1 2 3 4 5 6 7

По формуле Эйлера

Включим и получим цикл

Включим и получим цикл

Включим и получим цикл

Определение кратчайшего пути на графе методом Дейкстры

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

Рассмотрим алгоритм, который определяет путь из s в вершину t и который имеет минимальную длину. В этом алгоритме считается, что все дуги графа имеют положительную длину. Алгоритм включает в себя 3 этапа:

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

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

3. Если , то мы заканчиваем процедуру. Кратчайший путь из вершины s в вершину t найден. В противном случае вернуться к шагу 2.

Заключение:

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

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

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

Пример: найти кратчайший путь из вершины s в вершину t методом Дейкстры

Строим матрицу расстояний

Рис. 44

3

s

c

a

s

c

4

3

s

d

c

4

a

3

3

c

s

d

c

4

a

b

3

3

7

c

s

t

d

c

4

a

b

2

3

3

7

Получили кратчайший путь (s, c), (c, d), (d, t), длина которого равна 8.