Мінімальне кістякове дерево: відмінності між версіями
[неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
м Igor Yalovecky перейменував сторінку з Мінімальне остовне дерево на Мінімальне кістякове дерево поверх перенаправлення |
Немає опису редагування |
||
Рядок 1:
'''Мінімальне
▲'''Мінімальне остовне дерево''' (мінімальне [[кістякове дерево]]) у зв'язаному, зваженому, [[неорієнтований граф|неорієнтованому графі]] — це кістяк цього графа, що має мінімальниу можливу вагу, де під вагою дерева розуміється сума ваг входячих до нього ребер.
==Визначення ==
Існує декілька [[алгоритм]]ів для знаходження мінімального остовного дерева. Деякі найбільш відомі з них перераховані нижче:▼
Нехай маємо граф <math>G = (V, E),</math> де <math>V</math> це множина вершин, а <math>E</math> це множина ребер. І для кожного ребра <math>(u, v) \in E</math> відома його вага <math>w(u, v).</math> Мінімальним кістяковим деревом називається множина <math>T \subseteq E,</math> що поєднує всі вершини і чия повна вага
:<math>w(T) = \sum_{(u,v) \in T} w(u, v)</math>
є найменшою.<ref>{{Introduction to Algorithms|chapter=23 Minimum spanning tree|edition=3|pages=624}}</ref>
== Алгоритми знаходження МКД ==
▲Існує декілька [[алгоритм]]ів для знаходження мінімального
* [[Алгоритм Прима]];
* [[Алгоритм Крускала]];
Рядок 10 ⟶ 15:
* [[Алгоритм двох китайців]]
==
{{reflist}}
[[Категорія:Теорія графів]]
|