Построение экономического дерева
Граф называется подграфом графа , когда выполняется условие:
.
Остовным подграфом графа является подграф, содержащий все вершины данного графа.
Остовный подграф, являющийся деревом, называется остовом. Т.е. на каждой области связности графа графом порождается дерево.
Несвязный граф не имеет остова. Связный граф может иметь много остовов.
Задача:
Во взвешенном связном графе требуется найти остов минимального веса. (SST - Shortest Skeleton Tree - стандартное обозначение для кратчайшего остова).
Эта задача может возникнуть, например, при проектировании линий электропередач или сети дорог, когда требуется заданные центры соединить некоторой системой каналов связи так, чтобы любые два центра были связаны либо непосредственно соединяющим их каналом, либо через другие центры и каналы, и чтобы общая длина (стоимость) каналов связи была минимальной. В этой ситуации заданные центры можно считать вершинами полного графа с весами ребер, равными длинам (стоимости) соединяющих эти центры каналов. Тогда искомая сеть будет кратчайшим остовным подграфом полного графа. Очевидно, что этот кратчайший остовный подграф должен быть деревом.
Поскольку полный граф содержит различных остовных деревьев, то решение этой задачи “слепым” перебором вариантов потребовало бы чрезвычайно больших вычислений даже при относительно малых п. Однако для ее решения имеются эффективные алгоритмы. Примером таких алгоритмов являются алгоритмы Дж. Краскала (1956 г.) и Р. Прима (1957 г.), применимые к произвольному связному графу.