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

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

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

Визначення

Нехай маємо граф $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)$

є найменшою.

Алгоритми пошуку

Існує декілька алгоритмів для побудови мінімального кістякового дерева:

• Алгоритм Прима;
• Алгоритм Крускала;
• Алгоритм Борувки;
• Алгоритм двох китайців.