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

Определение:

Минимально узкое остовное дерево (англ. 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м. также

• Алгоритм Краскала
• Остовные деревья: определения, лемма о безопасном ребре
• СНМ (наивные реализации)

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

• Википедия — Minimum bottleneck spanning tree