Изменения

__TOC__ {{Определение|definition='''Минимально узкое остовное дерево''' (англ. ''Minimum bottleneck spanning tree'', ''MBST'') в связанном взвешенном неориентированном графе <tex>-</tex> это [[Остовные деревья: определения, лемма о безопасном ребре|остовное дерево]] графа, у которого максимальное ребро минимально. }}{{Определение|definition='''Узким ребром ''' (англ. ''bottleneck edge'') в графе назовём максимальное по весу. }}{{Определение|definition=Остовное дерево является '''минимально узким''' (англ. ''minimum bottleneck''), если в графе нет остовного дерева с меньшим узким ребром.== Задача MBST и минимальное остовное дерево =={{Определение с MBST|definition=Минимальное остовное дерево является minimum bottleneck spanning tree.

== Свойства минимального узкого остовного дерева =={{Утверждение с MBST|statement=Каждое минимальное остовное дерево является <tex>\mathrm{MBST}</tex>.|proof=Предположим, если минимальное остовное не является <tex>\mathrm{MBST}</tex>, значит в графе существует набор ребер которые мы не взяли в наш остов, при замене на которые, наше дерево станет <tex>\mathrm{MBST}</tex>. Так же Также рёбра вне остова должны быть меньше рёбер из остова, чтобы уменьшить минимальное максимально ребро. Но по определению <tex>\mathrm{MST}</tex>, сумма рёбер дерева минимальна, значит вне остова нету рёбер с меньшим весом. Так как наше предположение неверно, <tex>\mathrm{MST }</tex> является MBST. <tex>\mathrm{{Определение с MBST|definition=Minimum bottleneck spanning tree не всегда является минимальным остовным деревом}</tex>.

{{Утверждение с MBST|statement=<tex>\mathrm{MBST}</tex> не всегда является минимальным остовным деревом.|proof=Рассмотрим пример, где <tex>\mathrm{MBST }</tex> не является минимальным остовным деревом:

== Является ли остовное дерево MBST Проверка остовного дерева на узкость ==

|definition=Проверка остовного дерева Проверить остовное дерево в графе на <tex>\mathrm{MBST}</tex>.

Если у нас получится соединить Построим новый граф, добавим туда все вершины графа, используя рёбра меньше максимального из нашего остова. Если в результате у нас получится связный граф, значит мы сможем построить другой остоввыделить из него остовное дерево с меньшим узким ребром <tex>-</tex> наше дерево не самое узкое. Иначе, в котором максимальное ребро меньше нашего максимальногодля связности графа нам необходимо добавить максимальные рёбра <tex>-</tex> наше дерево является минимально узким. Для этого найдём Найдём максимальное ребро в нашем дереве. Соединим все вершины, между которыми Добавим рёбра с весом меньше максимального при помощи [[СНМ (наивные реализации)|СНМ]], чтобы определить его связность. Если в результате у нас все вершины лежат в одном множестве, значит наше дерево не является <tex>\mathrm{MBST}</tex>, иначе оно <tex>\mathrm{MBST}</tex>.

Максимальное ребро мы ищем линейно за количество рёбер в дереве По каждому ребру пройдём один раз, для поиска максимального, займёт <tex>O(N)</tex>, где <tex>N -</tex> число рёбер в графе.<br>Работа с СНМ займет <tex>O(N\alpha(V))</tex>, где <tex>\alpha</tex> — обратная функция Аккермана, которая не превосходит <tex>4</tex> во всех практических приложениях и которую можно принять за константу.<br>В результате получаем алгоритм работающий за линейное время <tex>O(N)</tex>. 

'''functionbool''' ifMBST('''Edge'''[] e, '''Edge'''[] tree): '''int''' united = 0, <font color=green>// Сколько вершин мы объединили</font> '''int''' maxEdge = -Inf<tex>\infty</tex> '''for''' i = 1 '''to ''' tree.size maxEdge = max(maxEdge, tree[i].cost) <font color=green>// Поиск максимального ребра в дереве</font> '''for''' i = 1 '''to ''' n '''if''' e[i].cost >= maxEdge <font color=green>// Не соединяем вершины, если ребро не меньше максимального</font>

'''if''' find(e[i].from]) != find(e[i].to) <font color=green>// Объединяем вершины, если они в разных множествах</font>

'''if''' united == e.size - 1 <font color=green>// Дерево подходит, если в результате мы соединили все вершины</font> '''return''''' true''

'''return''''' false''