Изменения

Перейти к: навигация, поиск

Минимально узкое остовное дерево

15 байт убрано, 22:01, 8 января 2017
Свойства минимального узкого остовного дерева
== Свойства минимального узкого остовного дерева ==
{{Определение с MBST
|definition=Каждое минимальное остовное дерево является minimum bottleneck spanning tree<tex>\mathrm{MBST}</tex>.
|proof=Предположим, если минимальное остовное не является <tex>\mathrm{MBST}</tex>, значит в графе существует набор ребер которые мы не взяли в наш остов, при замене на которые, наше дерево станет <tex>\mathrm{MBST}</tex>. Также рёбра вне остова должны быть меньше рёбер из остова, чтобы уменьшить минимальное максимально ребро. Но по определению <tex>\mathrm{MST}</tex>, сумма рёбер дерева минимальна, значит вне остова нету рёбер с меньшим весом. Так как наше предположение неверно, <tex>\mathrm{MST}</tex> является <tex>\mathrm{MBST}</tex>.
}}
{{Определение с MBST
|definition=Minimum bottleneck spanning tree <tex>\mathrm{MBST}</tex> не всегда является минимальным остовным деревом.
|proof=Рассмотрим пример, где <tex>\mathrm{MBST}</tex> не является минимальным остовным деревом:
<div class="tleft" style="clear:none">[[Файл:MBST-example.png|left|thumb|700px|Пример MBST дерева.]]</div>
<div class="tleft" style="clear:none">[[Файл:MSTisMBST.png|left|thumb|700px|Пример MST дерева.]]</div>
}}
 
== Проверка остовного дерева на узкость ==
{{Задача
Анонимный участник

Навигация