Задача
о кратчайшем соединении
Известны
точки, в которых будут расположены населенные пункты (города) и известны трассы
дорог, которые можно построить, а также стоимость их строительства.
На рис. 1
указаны населенные пункты A, B, C, D, E, F; арабские цифры около проектируемых участков дорог –
стоимость их строительства; римские цифры – номера дуг. Требуется определить,
какие из дорог следует построить, чтобы полученная схема дорог позволяла
попасть из любого города в любой и из всех возможных схем имела наименьшую
стоимость строительства.
Ясно, что
сформулированная задача может быть формализована с помощью теории графов.

Рис. 1
Определение 1 Взвешенным графом (графом с весами на дугах) будем называть четверку
, где
– граф,
.
Отображение r называется
весовым отображением. Если
, то
называют весом дуги и.
Если
– путь или цепь на
графе G, то ее весом
называют величину
.
Весом графа
называют величину
.
Аналогично определяется вес подграфа и частичного
графа.
Сформулируем
задачу о соединении городов на языке теории графов. Дан конечный связный
взвешенный граф
. Требуется найти связный частичный граф минимального веса.
Определение 2 Покрывающим деревом
связного графа называется его частичный граф, который является деревом. Если G не является связным графом, то говорят о покрывающем
лесе, т.е. о деревьях, покрывающих его компоненты связности.
Теорема 1 Решение задачи о соединении
городов – покрывающее дерево.
Теорема 2 (алгоритм Краскала)
Последовательность
дуг покрывающего
дерева минимального веса может быть найдена с помощью следующего алгоритма:
1) и1 – дуга минимального веса из множества U, не
являющаяся петлей;
2) если уже определен начальный отрезок
последовательности
, то дуга
выбирается из
множества
так, что выполнено два
условия:
а) добавление дуги
к
не приводит к
образованию циклов;
б)
из дуг, удовлетворяющих условию а), дуга
обладает наименьшим
весом.
Пример Применим
алгоритм Краскала к графу, к графу, приведенному на
рис. 1, – схеме дорог. На первом шаге выбирается дуга u1=III, затем u2=I, u3=V (далее
отпадает возможность выбора дуги IV), u4=VIII (далее
отпадает возможность выбора дуги VI), u5=IX (далее
отпадает возможность выбора дуг II, X, VII). Процесс
выбора дуг автоматически оборвался. Покрывающее дерево минимального веса
приведено на рис. 2. Пунктиром обозначены дуги, не вошедшие в это дерево.
.

Рис.2