Мінімальне остовне дерево

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Мінімальне остовне дерево (мінімальне кістякове дерево) у зв'язаному, зваженому, неорієнтованому графі — це кістяк цього графа, що має мінімальниу можливу вагу, де під вагою дерева розуміється сума ваг входячих до нього ребер.

Існує декілька алгоритмів для знаходження мінімального остовного дерева. Деякі найбільш відомі з них перераховані нижче:

Див. також[ред.ред. код]

Посилання[ред.ред. код]

  • Романовский И. В. Дискретный анализ, 3-е изд., перераб. и доп. - СПб.:Невский Диалект; БХВ-Петербург, 2003. - 320 с.: ил. (233 страница) - ISBN 5-7940-0114-3