Изменения

__TOC__ {{УтверждениеОпределение|statementdefinition=Минимальное '''Минимально узкое остовное дерево является minimum ''' (англ. ''Minimum bottleneck spanning tree.|proof=Предположим'', если минимальное остовное не является ''MBST, значит '') в связанном взвешенном неориентированном графе существует набор ребер которые мы не взяли в наш остов<tex>-</tex> [[Остовные деревья: определения, при замене на которые, наше лемма о безопасном ребре|остовное дерево станет MBST. Так же рёбра вне остова должны быть меньше рёбер из остова]] графа, чтобы уменьшить минимальное максимально у которого максимальное ребро. Но по определению MST, сумма рёбер дерева минимальна, значит вне остова нету рёбер с меньшим весом. Так как наше предположение неверно, MST является MBSTминимально.

{{Определение|definition='''Узким ребром''' (англ. ''bottleneck edge'') в графе назовём максимальное по весу.}}{{Определение|definition=Остовное дерево является '''минимально узким''' (англ. ''minimum bottleneck''), если в графе нет остовного дерева с меньшим узким ребром.}}== Свойства минимального узкого остовного дерева =={{Утверждение с MBST|statement=Каждое минимальное остовное дерево является <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|statement=Minimum bottleneck spanning tree <tex>\mathrm{MBST}</tex> не всегда является минимальным остовным деревом.|proof=Рассмотрим пример, где <tex>\mathrm{MBST }</tex> не является минимальным остовным деревом:

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

<h4>=== Алгоритм</h4>===Если у нас получится соединить Построим новый граф, добавим туда все вершины графа, используя рёбра меньше максимального из нашего остова. Если в результате у нас получится связный граф, значит мы сможем построить другой остоввыделить из него остовное дерево с меньшим узким ребром <tex>-</tex> наше дерево не самое узкое. Иначе, в котором максимальное ребро меньше нашего максимальногодля связности графа нам необходимо добавить максимальные рёбра <tex>-</tex> наше дерево является минимально узким. Для этого найдём Найдём максимальное ребро в нашем дереве. Соединим все вершины, между которыми Добавим рёбра с весом меньше максимального при помощи [[СНМ (наивные реализации)|СНМ]], чтобы определить его связность. Если в результате у нас все вершины лежат в одном множестве, значит наше дерево не является <tex>\mathrm{MBST}</tex>, иначе оно MBST.<h4tex>Асимптотика\mathrm{MBST}</h4tex>.=== Асимптотика ===Максимальное ребро мы ищем линейно за количество рёбер в дереве По каждому ребру пройдём один раз, для поиска максимального, займёт <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>. === Псевдокод ===Все рёбра графа будем хранить в списке <tex>\mathtt{e}</tex>, а рёбра остовного дерева в списке <tex>\mathtt{tree}</tex>.<br>В каждом ребре <tex>\mathtt{Edge}</tex> храним следующую информацию:* <h4tex>Псевдокод\mathtt{from}, \mathtt{to}</tex> {{---}} соединяемые вершины* <tex>\mathtt{cost}</h4tex>{{---}} вес ребра

'''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>

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

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