Число помеченных деревьев с n вершинами равно .
Стягивающим (или остовным) деревом связного графа G называется произвольный его подграф, содержащий все вершины G и являющийся деревом. Остовным лесом графа G называется произвольный его подграф, содержащий все вершины G и являющийся лесом. Таким образом, компоненты связности остовного леса графа G являются стягивающими деревьями компонент G.
Построить остовный лес нетрудно: достаточно последовательно удалять из графа ребра, входящие в циклы, до тех пор, пока не будет построен ациклический граф (лес), который, очевидно, будет остовным для исходного графа.
Граф называется взвешенным, если каждому его ребру l
поставлено в соответствие неотрицательное число 
(вес ребра). Весом графа G = <V;E> называют сумму весов всех
его рeбер: 
Рассмотрим следующую задачу. Имеется n пунктов. Для любой пары пунктов i и j известна стоимость сооружения дороги между ними - cij . Требуется выбрать сеть дорог такую, чтобы любые два пункта соединялись каким-либо маршрутом и при этом стоимость ее сооружения была наименьшей.
Если рассмотреть полный граф порядка n, вершины которого будут соответствовать указанным (географическим) пунктам, а рeбра будут иметь вес, равный стоимости сооружения дороги между соответствующими пунктами, то задача формулируется так: в данном графе найти стягивающее дерево наименьшего веса. Существуют эффективные алгоритмы нахождения стягивающего дерева минимального веса в связном взвешенном графе. При описании следующих алгоритмов G = <V;E> будет обозначать исходный граф, а T = <V; P> - искомое дерево.
