Задача поиска кратчайшего остова

Задача поиска кратчайшего остова состоит в следующем: для нагруженного графа требуется построить остовное дерево , сумма длин ребер которого минимальна.

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

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

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

Применение сформулированного выше алгоритма выглядит следующим образом. В матрице отыскивается минимальный элемент, который вычеркивается, а соответствующее ему ребро заносится в сеть, если при этом не образуется цикл. Затем эти действия повторяются. Таким образом, на первых пяти шагах работы алгоритма будут выбраны ребра {1, 5}, {2, 6}, {4, 5}, {3, 7}, {7, 9}. Из оставшихся ребер минимальную длину имеет ребро {1, 4}, но в сеть оно не включается, так как образует цикл с уже выбранными ребрами. На следующих этапах алгоритма в сеть будут включены ребра {5, 8}, {2, 7} и {1, 2}.

Для обоснования алгоритма предположим, что дерево , которое он строит, состоит из ребер , для которых .

Рассмотрим любое другое дерево и упорядочим его ребра по возрастанию длин. Пусть первые ребер дерева такие же, как в дереве , а -е ребро отличается от (). Присоединим к дереву ребро . Тогда возникнет цикл, в который входит ребро и какие-то ребра из дерева . Среди этих ребер обязательно найдется ребро , длина которого не меньше, чем длина ребра : иначе ребро образовало бы цикл с ребрами меньшей длины, что исключается правилом выбора очередного ребра в рассмотренном алгоритме. Удалим из дерева ребро , заменив его ребром . В результате получим дерево, длина которого не больше, чем длина дерева . Аналогичным путем вводим в дерево ребра , при этом всякий раз длина дерева не увеличится. Это означает, что дерево действительно кратчайшее.