Элементарные преобразования деревьев

Рассмотрим два (ориентированных или неориентированных) остовных дерева и графа .

,

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

Рис.3. Остовы T₀ и T₄.

Существует теорема, согласно которой дерево T_k может быть получено из дерева T₀ с помощью серий из k элементарных преобразований при =k.