9.5.2. Схема алгоритма построения кратчайшего остова

Рассмотрим следующую схему алгоритма построения кратчайшего остова. Пусть Т — множество непересекающихся деревьев, являющихся подграфами графа G. Вначале Т состоит из отдельных вершин графа G, в конце Т содержит един­ственный элемент — кратчайший остов графа G.

Алгоритм 9.6. Построение кратчайшего остова

Вход: граф G(V, E), заданный матрицей длин ребер С.

Выход: кратчайший остов Т.

T: = V

while в Т больше одного элемента do

взять любое поддерево из Т

найти к нему ближайшее

соединить эти деревья в Т

end while

ТЕОРЕМА Алгоритм 9.6 строит кратчайший остов.

доказательство

Пусть T_i и T_j — два произвольных поддерева G, Т_i  T_j  0. Положим

_i,j:= .

Так как с самого начала все вершины G покрыты деревьями из Т, то _i,j всегда реализуется на некотором ребре с длиной c_i,j. Далее индукцией по шагам алго­ритма 9.6 покажем, что все ребра, включенные в Т, принадлежат кратчайшему остову — SST. Вначале выбранных ребер нет, поэтому их множество включа­ется в кратчайший остов. Пусть теперь все ребра, добавленные в Т, принадлежат SST. Рассмотрим очередной шаг алгоритма. Пусть на этом шаге добавлено ребро (i, j), соединяющее поддерево Т_i с поддеревом Tj. Если (i, j)  SST, то, посколь­ку SST является деревом и, стало быть, связен, (i*, j*)  SST, соединяющее T_i с остальной частью SST. Тогда удалим из SST ребро (i*, j*) и добавим ребро (i, j): SST’ : = SST- (i*, j*) + (i, j). Полученный подграф SST’ является остовом, причем более коротким, чем SST, что противоречит выбору SST. 

ЗАМЕЧАНИЕ

Различные способы выбора поддерева для наращивания на первом шаге тела цикла дают различные конкретные варианты алгоритма построения SST.