6.31. Построение деревьев минимальной общей длины

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

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

Для нахождения дерева минимальной общей длины пометим ребра в соответствии с увеличением их длины

так, что длина меньше или равна если После этого выберем и добавим к этому ребру если не образует цикла с Далее будем продолжать рассмотрение ребер в порядке возрастания их индексов и выбирать ребро всякий раз, когда оно не образует цикла с уже выбранным множеством. В противном случае ребро отбрасывается. Во всех случаях после окончания такого процесса мы получим дерево минимальной общей длины (доказательство дано в [56]).