Описание тега minimum-spanning-tree

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

Одним из примеров может быть кабельная телекомпания, прокладывающая кабель в новый район. Если ограничить прокладку кабеля только на определенных путях, тогда будет график, показывающий, какие точки соединены этими путями. Некоторые из этих путей могут быть более дорогими, потому что они длиннее или требуют более глубокого прокладки кабеля; эти пути будут представлены ребрами с большим весом. Остовное дерево для этого графа будет подмножеством тех путей, которые не имеют циклов, но все же соединяются с каждым домом. Возможно несколько остовных деревьев. Минимальное остовное дерево будет с наименьшей общей стоимостью.

(Источник: Википедия)