Минимально узкое остовное дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Асимптотика)
м
 
(не показаны 4 промежуточные версии 2 участников)
Строка 1: Строка 1:
 +
__TOC__
 +
 
{{Определение
 
{{Определение
 
|definition='''Минимально узкое остовное дерево''' (англ. ''Minimum bottleneck spanning tree'', ''MBST'') в связанном взвешенном неориентированном графе <tex>-</tex> [[Остовные деревья: определения, лемма о безопасном ребре|остовное дерево]] графа, у которого максимальное ребро минимально.
 
|definition='''Минимально узкое остовное дерево''' (англ. ''Minimum bottleneck spanning tree'', ''MBST'') в связанном взвешенном неориентированном графе <tex>-</tex> [[Остовные деревья: определения, лемма о безопасном ребре|остовное дерево]] графа, у которого максимальное ребро минимально.
 
}}
 
}}
 
{{Определение
 
{{Определение
|definition=Узким ребром в графе назовём максимальное по весу.
+
|definition='''Узким ребром''' (англ. ''bottleneck edge'') в графе назовём максимальное по весу.
 
}}
 
}}
 
{{Определение
 
{{Определение
|definition=Остовное дерево является минимально узким, если в графе нет остовного дерева с меньшим узким ребром.
+
|definition=Остовное дерево является '''минимально узким''' (англ. ''minimum bottleneck''), если в графе нет остовного дерева с меньшим узким ребром.
 
}}
 
}}
 
== Свойства минимального узкого остовного дерева ==
 
== Свойства минимального узкого остовного дерева ==
{{Свойство MBST
+
{{Утверждение с MBST
|definition=Каждое минимальное остовное дерево является <tex>\mathrm{MBST}</tex>.
+
|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>.
 
|proof=Предположим, если минимальное остовное не является <tex>\mathrm{MBST}</tex>, значит в графе существует набор ребер которые мы не взяли в наш остов, при замене на которые, наше дерево станет <tex>\mathrm{MBST}</tex>. Также рёбра вне остова должны быть меньше рёбер из остова, чтобы уменьшить минимальное максимально ребро. Но по определению <tex>\mathrm{MST}</tex>, сумма рёбер дерева минимальна, значит вне остова нету рёбер с меньшим весом. Так как наше предположение неверно, <tex>\mathrm{MST}</tex> является <tex>\mathrm{MBST}</tex>.
 
}}
 
}}
{{Свойство MBST
+
{{Утверждение с MBST
|definition=<tex>\mathrm{MBST}</tex> не всегда является минимальным остовным деревом.
+
|statement=<tex>\mathrm{MBST}</tex> не всегда является минимальным остовным деревом.
 
|proof=Рассмотрим пример, где <tex>\mathrm{MBST}</tex> не является минимальным остовным деревом:
 
|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">[[Файл:MBST-example.png|left|thumb|700px|Пример MBST дерева.]]</div>
Строка 28: Строка 30:
 
Найдём максимальное ребро в нашем дереве. Добавим рёбра с весом меньше максимального при помощи [[СНМ (наивные реализации)|СНМ]], чтобы определить его связность. Если в результате у нас все вершины лежат в одном множестве, значит наше дерево не является <tex>\mathrm{MBST}</tex>, иначе оно <tex>\mathrm{MBST}</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>.
+
По каждому ребру пройдём один раз, для поиска максимального, займёт <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>.
  
 
=== Псевдокод ===
 
=== Псевдокод ===

Текущая версия на 02:24, 9 января 2017


Определение:
Минимально узкое остовное дерево (англ. Minimum bottleneck spanning tree, MBST) в связанном взвешенном неориентированном графе [math]-[/math] остовное дерево графа, у которого максимальное ребро минимально.


Определение:
Узким ребром (англ. bottleneck edge) в графе назовём максимальное по весу.


Определение:
Остовное дерево является минимально узким (англ. minimum bottleneck), если в графе нет остовного дерева с меньшим узким ребром.

Свойства минимального узкого остовного дерева[править]

Утверждение c MBST:
Каждое минимальное остовное дерево является [math]\mathrm{MBST}[/math].
[math]\triangleright[/math]
Предположим, если минимальное остовное не является [math]\mathrm{MBST}[/math], значит в графе существует набор ребер которые мы не взяли в наш остов, при замене на которые, наше дерево станет [math]\mathrm{MBST}[/math]. Также рёбра вне остова должны быть меньше рёбер из остова, чтобы уменьшить минимальное максимально ребро. Но по определению [math]\mathrm{MST}[/math], сумма рёбер дерева минимальна, значит вне остова нету рёбер с меньшим весом. Так как наше предположение неверно, [math]\mathrm{MST}[/math] является [math]\mathrm{MBST}[/math].
[math]\triangleleft[/math]
Утверждение c MBST:
[math]\mathrm{MBST}[/math] не всегда является минимальным остовным деревом.
[math]\triangleright[/math]

Рассмотрим пример, где [math]\mathrm{MBST}[/math] не является минимальным остовным деревом:

Пример MBST дерева.
Пример MST дерева.
[math]\triangleleft[/math]

Проверка остовного дерева на узкость[править]

Задача:
Проверить остовное дерево в графе на [math]\mathrm{MBST}[/math].

Алгоритм[править]

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

Асимптотика[править]

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

Псевдокод[править]

Все рёбра графа будем хранить в списке [math]\mathtt{e}[/math], а рёбра остовного дерева в списке [math]\mathtt{tree}[/math].
В каждом ребре [math]\mathtt{Edge}[/math] храним следующую информацию:

  • [math]\mathtt{from}, \mathtt{to}[/math] — соединяемые вершины
  • [math]\mathtt{cost}[/math] — вес ребра

  bool ifMBST(Edge[] e, Edge[] tree):
     int united = 0      // Сколько вершин мы объединили 
     int maxEdge = -[math]\infty[/math]
     for i = 1 to tree.size
        maxEdge = max(maxEdge, tree[i].cost)      // Поиск максимального ребра в дереве 
     for i = 1 to n
        if e[i].cost >= maxEdge                   // Не соединяем вершины, если ребро не меньше максимального 
           continue
        if find(e[i].from]) != find(e[i].to)      // Объединяем вершины, если они в разных множествах 
           united++
        unite(e[i].from,e[i].to)
     if united == e.size - 1                      // Дерево подходит, если в результате мы соединили все вершины 
        return true
     else 
        return false

Cм. также[править]

Источники информации[править]