3. Кратчайший остов (SST) графа

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

Рис. 7.11. (см. скан)

сетью трубопроводов; тогда наименьшая общая длина труб, которая должна быть использована для строительства (при условии, что вне городов «разветвления» трубопроводов не допускаются), определяется кратчайшим остовом соответствующего графа. Не совсем непосредственно, а как промежуточный шаг, кратчайший остов используется при решении задачи о коммивояжере, которая довольно часто встречается на практике и детально рассматривается в гл. 10.

Следует отметить, что SST графа не имеет никакого отношения к дереву, дающему все кратчайшие пути, выходящие из некоторой выбранной вершины. Так для графа, показанного на рис. 7.11(a), где числа, стоящие около ребер, являются их весами, дерево, дающее все кратчайшие пути, выходящие из вершины изображено на рис. 7.11 (б), a SST - на рис. 7.11 (в).

Задача построения кратчайшего остова (SST) графа является одной из немногих задач теории графов, которые можно считать

полностью решенными. Итак, пусть два произвольных поддерева, полученных путем добавления ребер при построении SST. Если символ использовать также для обозначения множества вершин данного поддерева, то может быть определено как кратчайшее из расстояний между вершинами из и вершинами из Ту, т. е.

Легко показать, что многократное применение нижеследующей операции приводит к построению SST графа.

Операция Для поддерева найти такое поддерево чтобы будет тем ребром, вес которого соответствует величине в выражении (7.1). Тогда ребро принадлежит SST и может быть добавлено к другим ребрам частично сформированного SST.

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

Многие методы, позволяющие строить SST графов, основываются на частных случаях описанной выше операции [40, 48, 41, 46, 17, 35, 26]. Первый из таких методов был предложен Краскалом [40].