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

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

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

Визначення

Нехай маємо граф $G=(V,E),$ де $V$ це множина вершин, а $E$ це множина ребер. І для кожного ребра $(u,v)\in E$ відома його вага $w(u,v).$ Мінімальним кістяковим деревом називається множина $T\subseteq E,$ що поєднує всі вершини і чия повна вага

$w(T)=\sum _{(u,v)\in T}w(u,v)$

є найменшою.

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

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

• Алгоритм Прима;
• Алгоритм Крускала;
• Алгоритм Борувки.

Див. також

• Алгоритм двох китайців