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

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

Визначення ред.

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

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

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

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

Примітки ред.

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

Це незавершена стаття з математики.
Ви можете допомогти проєкту, виправивши або дописавши її.

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

[1]