Задача о кратчайшем соединении

 

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

На рис. 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