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

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

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

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

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