Остовные деревья графа

Пусть – связный граф.

Определение. Остовным деревом связного графа называют всякий его остовный подграф, который является деревом.

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

На рис. 10 показаны два различных остовных дерева (Т ₁ и Т ₂) исходного графа .