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

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

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

Визначення[ред.ред. код]

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

Алгоритми знаходження МКД[ред.ред. код]

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

Див. також[ред.ред. код]

Примітки[ред.ред. код]

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