Изменения
Нет описания правки
{{Определение|definition='''Минимально узкое остовное дерево''' (англ. ''Minimum bottleneck spanning tree'', ''MBST'') в связанном взвешенном неориентированном графе <tex>-</tex> это [[Остовные деревья: определения, лемма о безопасном ребре|остовное дерево]] графа, у которого максимальное ребро минимально. }}{{Определение|definition=Узким ребром в графе назовём максимальное по весу. }}{{Определение|definition=Остовное дерево является минимально узким, если в графе нет остовного дерева с меньшим узким ребром.}}== Задача MBST и минимальное остовное дерево Свойства минимального узкого остовного дерева ==
{{Определение с MBST
|definition=Минимальное Каждое минимальное остовное дерево является minimum bottleneck spanning tree.|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 не всегда является минимальным остовным деревом.
|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>
}}
== Является ли остовное дерево MBST Проверка остовного дерева на узкость ==
{{Задача
|definition=Проверка остовного дерева Проверить остовное дерево в графе на <tex>\mathrm{MBST}</tex>.
}}
=== Алгоритм ===
=== Асимптотика ===
По каждому ребру пройдём один раз, для поиска максимального, займёт <tex>O(N)</tex>.<br>Работа с СНМ займет <tex>O(N\alpha(V))</tex>, где <tex>\alpha</tex> — обратная функция Аккермана, которая не превосходит <tex>4</tex> во всех практических приложениях и которую можно принять за константу.<br>В результате получаем алгоритм работающий за линейное время <tex>O(N)</tex>.
=== Псевдокод ===
Все рёбра графа будем хранить в списке <tex>\mathtt{e}</tex>, а рёбра остовного дерева в списке <tex>\mathtt{tree}</tex>.<br>В каждом ребре <tex>\mathtt{Edge}</tex> храним следующую информацию:* <tex>\mathtt{from}, \mathtt{to}</tex> {{---}} соединяемые вершины* <tex>\mathtt{cost}</tex> {{---}} вес ребра
<code>
'''bool''' ifMBST('''Edge'''[] e, '''Edge'''[] tree):
'''int''' united = 0 <font color=green>// Сколько вершин мы объединили</font>
'''int''' maxEdge = -<tex>\infty</tex>
