Як визначити основне дерево?

Основне дерево – ациклічний зв'язковий підграф даного зв'язкового неорієнтованого графа, до якого входять усі його вершини.

Визначення: основне дерево (англ. spanning tree) графа – ациклічний зв'язковий підграф даного зв'язкового неорієнтованого графа, в який входять всі його вершини.

Головна відмінність від задачі про мінімальному остовному Дерево при цьому полягає в тому, що дозволяється додавати додаткові точки розгалуження з метою ще сильніше зменшити суму довжин ребер.