Відкрити головне меню

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

Приклад мінімального кістякового дерева в планарному графі. Кожне ребро має позначку з вагою, яка приблизно пропорційно його довжині.

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

ВизначенняРедагувати

Нехай маємо граф   де   це множина вершин, а   це множина ребер. І для кожного ребра   відома його вага   Мінімальним кістяковим деревом називається множина   що поєднує всі вершини і чия повна вага

 

є найменшою.[1]

Алгоритми знаходження МКДРедагувати

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

Див. такожРедагувати

ПриміткиРедагувати

  1. Томас Кормен; Чарльз Лейзерсон, Рональд Рівест , Кліффорд Штайн (2009) [1990]. 23 Minimum spanning tree. Вступ в алгоритми (вид. 3rd). MIT Press і McGraw-Hill. с. 624. ISBN 0-262-03384-4.