45
правок
Изменения
Нет описания правки
'''Минимально узкое остовное дерево''' (англ. ''Minimum bottleneck spanning tree'', ''MBST'') в связанном взвешенном неориентированном графе <tex>-</tex> это [[Остовные деревья: определения, лемма о безопасном ребре|остовное дерево]] графа, у которого максимальное ребро минимально. Узким ребром в графе назовём максимальное по весу. Остовное дерево является минимально узким, если в графе нет остовного дерева с меньшим узким ребром.
== Задача MBST и минимальное остовное дерево ==
{{Утверждение
|statement=Минимальное остовное дерево является minimum bottleneck spanning tree.
}}
== Является ли остовное дерево MBST ==
{{Задача
|definition=Проверка остовного дерева на MBST.
}}
Если у нас получится соединить все вершины графа, используя рёбра меньше максимального из нашего остова, значит мы сможем построить другой остов, в котором максимальное ребро меньше нашего максимального. Для этого найдём максимальное ребро в нашем дереве. Соединим все вершины, между которыми рёбра с весом меньше максимального при помощи [[СНМ (наивные реализации)|СНМ]]. Если в результате у нас все вершины лежат в одном множестве, значит наше дерево не является MBST, иначе оно MBST.
Максимальное ребро мы ищем линейно за количество рёбер в дереве <tex>O(N)</tex>.<br>Работа с СНМ займет <tex>O(N\alpha(V))</tex>, где <tex>\alpha</tex> — обратная функция Аккермана, которая не превосходит <tex>4</tex> во всех практических приложениях и которую можно принять за константу.<br>В результате получаем алгоритм работающий за линейное время <tex>O(N)</tex>.
<code>
'''function''' ifMBST():
'''return''' false
</code>
==Cм. также==
*[[Алгоритм Краскала]]
*[[Остовные деревья: определения, лемма о безопасном ребре]]
*[[СНМ (наивные реализации)]]
==Источники информации==
*[https://en.wikipedia.org/wiki/Minimum_bottleneck_spanning_tree Википедия — Minimum bottleneck spanning tree]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья]]
[[Категория: Построение остовных деревьев]]
