Построение экономического дерева

Граф называется подграфом графа , когда выполняется условие:

.

Остовным подграфом графа является подграф, содержащий все вершины данного графа.

Остовный подграф, являющийся деревом, называется остовом. Т.е. на каждой области связности графа графом порождается дерево.

Несвязный граф не имеет остова. Связный граф может иметь много остовов.

Задача:

Во взвешенном связном графе требуется найти остов минимального веса. (SST - Shortest Skeleton Tree - стандартное обозначение для кратчайшего остова).

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

Поскольку полный граф содержит различных остовных деревьев, то решение этой задачи “слепым” перебором вариантов потребовало бы чрезвычайно больших вычислений даже при относитель­но малых п. Однако для ее решения имеются эффектив­ные алгоритмы. Примером таких алгоритмов являются алгоритмы Дж. Краскала (1956 г.) и Р. Прима (1957 г.), примени­мые к произвольному связному графу.