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

Материал из Викиконспекты
Версия от 23:31, 8 января 2017; Nemzs (обсуждение | вклад) (Асимптотика)
Перейти к: навигация, поиск
Определение:
Минимально узкое остовное дерево (англ. Minimum bottleneck spanning tree, MBST) в связанном взвешенном неориентированном графе [math]-[/math] остовное дерево графа, у которого максимальное ребро минимально.


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


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

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

Утверждение 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м. также

Источники информации