Определение. Граф называется взвешенным, если на множестве его ребер определена весовая функция , то есть каждому ребру е поставлен в соответствие его вес .

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

Практическую значимость остовных деревьев дает популярная форма задачи Кэли.

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

В терминах теории графов эту задачу можно сформулировать так. Рассмотрим граф , где V – города, Е – дороги, , - стоимость строительства дороги. Задача заключается в том, чтобы построить связный граф , содержащий все вершины графа, и имеющем минимальный вес .

Очевидно, что граф - дерево, в противном случае можно бы было удалить одно ребро, не нарушая связности графа, но уменьшая вес.