Минимальное остовное дерево

Задача нахождения минимального остовного дерева появилась как конкретная формулировка более общей цели проектирования сети — поиска хорошего способа соединения множества точек с прокладкой ребер между ними.

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

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

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

И в этом случае легко находится пример, в котором в минимальном остовном дереве присутствуют ребра с большим уровнем трафика.

На более общем уровне будет разумно спросить: а является ли остовное дерево правильным решением для подобных задач планирования сетей? Дерево обладает тем свойством, что уничтожение любого ребра ведет к потере связности; это означает, что дерево не обеспечивает защиты от сбоев.

Вместо минимальной стоимости можно выбрать критерий жизнеспособности — например, искать связную сеть с минимальной стоимостью, которая останется связной после удаления одного любого ребра.

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