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

Определение. Остовным деревом графа G = (V, X) называют его подграф-дерево Т = (V_Т , X_Т), содержащий все вершины графа G (V_Т = V, X_Т Í Х).

Остовные деревья используются при формировании систем уравнений, описывающих функционирование электрических, гидравлических, механических и других систем. Представления структуры молекул в виде деревьев также позволили эффективно решить целый ряд прикладных задач в химии.

Остовные деревья могут быть выделены в графе неединственным образом. На рис.1.9 приведен пример графа и его различных остовных деревьев.

Рис. 1.9. Пример графа и его различных остовных деревьев

Наиболее часто в практических приложениях решают задачу об определении во взвешенном графе (псевдографе) G = (V, X, D)остовного дерева с минимальным суммарным весов ребер, входящих в него ― остовного дерева минимального веса. К такой постановке сводятся задачи об оптимальном покрытии некоторой территории с выделенными населенными пунктами сетью дорог, телеграфных коммуникаций и т. д.

Для решения этой задачи используют алгоритм Прима.