Мінімальне кістякове дерево у зв язаному зваженому неорієнтованому графі це кістяк цього графу що має мінімальну можливу

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

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

Визначення Редагувати

Нехай маємо граф де — множина вершин, а — множина ребер. І для кожного ребра відома його вага Мінімальним кістяковим деревом називається множина що поєднує всі вершини і чия повна вага

є найменшою.

Алгоритми пошуку Редагувати

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

Примітки Редагувати

Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (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.