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

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

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

Визначення

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

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

є найменшою.

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

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

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

Примітки

1. Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 23 Мінімальні кістякові дерева. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .