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

[неперевірена версія][неперевірена версія]
Вилучено вміст Додано вміст
м Igor Yalovecky перейменував сторінку з Мінімальне остовне дерево на Мінімальне кістякове дерево поверх перенаправлення
Немає опису редагування
Рядок 1:
'''Мінімальне остовнекістякове дерево''' (мінімальне [[кістякове дерево]]) у зв'язаному, зваженому, [[неорієнтований граф|неорієнтованому графі]] — це кістяк цього графа, що має мінімальниумінімальну можливу вагу, де під вагою дерева розуміється сума ваг входячих до ньогойого ребер.
{{Стаття, з якої нема посилань|дата=червень 2013}}
'''Мінімальне остовне дерево''' (мінімальне [[кістякове дерево]]) у зв'язаному, зваженому, [[неорієнтований граф|неорієнтованому графі]] — це кістяк цього графа, що має мінімальниу можливу вагу, де під вагою дерева розуміється сума ваг входячих до нього ребер.
 
==Визначення ==
Існує декілька [[алгоритм]]ів для знаходження мінімального остовного дерева. Деякі найбільш відомі з них перераховані нижче:
Нехай маємо граф <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}}
* Романовский И. В. '''Дискретный анализ''', 3-е изд., перераб. и доп. - СПб.:Невский Диалект; БХВ-Петербург, 2003. - 320 с.: ил. (233 страница) - '''ISBN 5-7940-0114-3'''
 
[[Категорія:Теорія графів]]