http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=176.59.0.238&*Викиконспекты - Вклад участника [ru]2026-04-23T17:55:40ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE_%D1%83%D0%B7%D0%BA%D0%BE%D0%B5_%D0%BE%D1%81%D1%82%D0%BE%D0%B2%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&diff=59351Минимально узкое остовное дерево2017-01-08T19:01:53Z<p>176.59.0.238: /* Свойства минимального узкого остовного дерева */</p>
<hr />
<div>{{Определение<br />
|definition='''Минимально узкое остовное дерево''' (англ. ''Minimum bottleneck spanning tree'', ''MBST'') в связанном взвешенном неориентированном графе <tex>-</tex> [[Остовные деревья: определения, лемма о безопасном ребре|остовное дерево]] графа, у которого максимальное ребро минимально.<br />
}}<br />
{{Определение<br />
|definition=Узким ребром в графе назовём максимальное по весу.<br />
}}<br />
{{Определение<br />
|definition=Остовное дерево является минимально узким, если в графе нет остовного дерева с меньшим узким ребром.<br />
}}<br />
== Свойства минимального узкого остовного дерева ==<br />
{{Определение с MBST<br />
|definition=Каждое минимальное остовное дерево является <tex>\mathrm{MBST}</tex>.<br />
|proof=Предположим, если минимальное остовное не является <tex>\mathrm{MBST}</tex>, значит в графе существует набор ребер которые мы не взяли в наш остов, при замене на которые, наше дерево станет <tex>\mathrm{MBST}</tex>. Также рёбра вне остова должны быть меньше рёбер из остова, чтобы уменьшить минимальное максимально ребро. Но по определению <tex>\mathrm{MST}</tex>, сумма рёбер дерева минимальна, значит вне остова нету рёбер с меньшим весом. Так как наше предположение неверно, <tex>\mathrm{MST}</tex> является <tex>\mathrm{MBST}</tex>.<br />
}}<br />
{{Определение с MBST<br />
|definition=<tex>\mathrm{MBST}</tex> не всегда является минимальным остовным деревом.<br />
|proof=Рассмотрим пример, где <tex>\mathrm{MBST}</tex> не является минимальным остовным деревом:<br />
<div class="tleft" style="clear:none">[[Файл:MBST-example.png|left|thumb|700px|Пример MBST дерева.]]</div><br />
<div class="tleft" style="clear:none">[[Файл:MSTisMBST.png|left|thumb|700px|Пример MST дерева.]]</div><br />
}}<br />
<br />
== Проверка остовного дерева на узкость ==<br />
{{Задача<br />
|definition=Проверить остовное дерево в графе на <tex>\mathrm{MBST}</tex>.<br />
}}<br />
=== Алгоритм ===<br />
Построим новый граф, добавим туда все рёбра меньше максимального из нашего остова. Если в результате у нас получится связный граф, значит мы сможем выделить из него остовное дерево с меньшим узким ребром <tex>-</tex> наше дерево не самое узкое. Иначе, для связности графа нам необходимо добавить максимальные рёбра <tex>-</tex> наше дерево является минимально узким. <br />
Найдём максимальное ребро в нашем дереве. Добавим рёбра с весом меньше максимального при помощи [[СНМ (наивные реализации)|СНМ]], чтобы определить его связность. Если в результате у нас все вершины лежат в одном множестве, значит наше дерево не является <tex>\mathrm{MBST}</tex>, иначе оно <tex>\mathrm{MBST}</tex>.<br />
=== Асимптотика ===<br />
По каждому ребру пройдём один раз, для поиска максимального, займёт <tex>O(N)</tex>.<br>Работа с СНМ займет <tex>O(N\alpha(V))</tex>, где <tex>\alpha</tex> — обратная функция Аккермана, которая не превосходит <tex>4</tex> во всех практических приложениях и которую можно принять за константу.<br>В результате получаем алгоритм работающий за линейное время <tex>O(N)</tex>.<br />
=== Псевдокод ===<br />
Все рёбра графа будем хранить в списке <tex>\mathtt{e}</tex>, а рёбра остовного дерева в списке <tex>\mathtt{tree}</tex>.<br><br />
В каждом ребре <tex>\mathtt{Edge}</tex> храним следующую информацию:<br />
* <tex>\mathtt{from}, \mathtt{to}</tex> {{---}} соединяемые вершины<br />
* <tex>\mathtt{cost}</tex> {{---}} вес ребра<br />
<code><br />
'''bool''' ifMBST('''Edge'''[] e, '''Edge'''[] tree):<br />
'''int''' united = 0 <font color=green>// Сколько вершин мы объединили</font> <br />
'''int''' maxEdge = -<tex>\infty</tex><br />
'''for''' i = 1 '''to''' tree.size<br />
maxEdge = max(maxEdge, tree[i].cost) <font color=green>// Поиск максимального ребра в дереве</font> <br />
'''for''' i = 1 '''to''' n<br />
'''if''' e[i].cost >= maxEdge <font color=green>// Не соединяем вершины, если ребро не меньше максимального</font> <br />
'''continue'''<br />
'''if''' find(e[i].from]) != find(e[i].to) <font color=green>// Объединяем вершины, если они в разных множествах</font> <br />
united++<br />
unite(e[i].from,e[i].to)<br />
'''if''' united == e.size - 1 <font color=green>// Дерево подходит, если в результате мы соединили все вершины</font> <br />
'''return''' ''true''<br />
'''else''' <br />
'''return''' ''false''<br />
</code><br />
<br />
==Cм. также==<br />
*[[Алгоритм Краскала]]<br />
*[[Остовные деревья: определения, лемма о безопасном ребре]]<br />
*[[СНМ (наивные реализации)]]<br />
<br />
==Источники информации==<br />
*[https://en.wikipedia.org/wiki/Minimum_bottleneck_spanning_tree Википедия — Minimum bottleneck spanning tree]<br />
<br />
[[Категория: Алгоритмы и структуры данных]] <br />
[[Категория: Остовные деревья]]<br />
[[Категория: Построение остовных деревьев]]</div>176.59.0.238