Минимально критичное остовное дерево ( англ. minimum bottleneck spanning tree , MBST) во взвешенном неориентированном графе — это остовное дерево , в котором наиболее тяжёлое ребро весит как можно меньше. Критичное ребро — это самое тяжёлое ребро в остовном дереве. Остовное дерево является минимальным критичным остовным деревом, если граф не содержит остовного дерева с критичным ребром меньшего веса . Для ориентированного графа аналогичная задача известна как минимально критичное ориентированное остовное дерево ( англ. Minimum Bottleneck Spanning Arborescence , MBSA).

Определения

Неориентированные графы

В неориентированном графе ${\displaystyle G(V,E)}$ и функция ${\displaystyle w:E\to \mathbb {R} }$ , пусть S будет множеством всех остовных деревьев ${\displaystyle T_{i}}$ . Пусть ${\displaystyle B(T_{i})}$ будет максимальным по весу ребром для любого остовного дерева ${\displaystyle T_{i}}$ . Мы определяем подмножество минимально критичных остовных деревьев S ′ так, что для любого ${\displaystyle T_{j}\in S'}$ и ${\displaystyle T_{k}\in S}$ мы имеем ${\displaystyle B(T_{j})\leqslant B(T_{k})}$ для всех i и k .

Граф на рисунке справа является примером MBST, красные рёбра графа образуют MBST графа ${\displaystyle G(V,E)}$ .

Ориентированные графы

Ориентированное остовное дерево орграфа ${\displaystyle G(V,A)}$ — это ориентированное (корневое) дерево, которое содержит ориентированный путь из указанной вершины L в каждую вершину графа. Вершина L называется корнем ориентированного остовного дерева. Критичная дуга — это самая тяжёлая дуга в ориентированном остовном дереве. Ориентированное остовное дерево называется минимально критичным ( англ. Minimum Bottleneck Spanning Arborescence , MBSA), если орграф не содержит ориентированного остовного дерева с критичной дугой меньшего веса.

Граф справа является примером MBSA, красные рёбра в графе образуют MBSA графа ${\displaystyle G(V,A)}$ .

Свойства

Любое минимальное остовное дерево (MST, англ. minimum spanning tree ) неизбежно является минимально критичным, но не любое минимально критичное обязательно будет минимальным .

Алгоритм Камерини для неориентированных графов

Камерини в 1978 году предложил алгоритм, использующийся для получения минимально критичного остовного дерева (MBST) для данного неориентированного связного взвешенного графа. Алгоритм разбивает все рёбра графа на такие два множества ${\displaystyle B}$ и ${\displaystyle A}$ , что веса рёбер из множества ${\displaystyle B}$ не превосходят весов из множества ${\displaystyle A}$ . Если подграф ${\displaystyle G_{B}}$ , состоящий из рёбер множества ${\displaystyle B}$ , связен, алгоритм рекурсивно ищет MBST в ${\displaystyle G_{B}}$ , и оно будет являться MBST для исходного графа. Если же ${\displaystyle G_{B}}$ не связен, алгоритм комбинирует каждую его компоненту связности в новую супервершину, затем рекурсивно вычисляет MBST в графе, образованном этими супервершинами и рёбрами из множества ${\displaystyle A}$ . Произвольный лес из рёбер множества ${\displaystyle B}$ , компоненты связности которого совпадают с компонентами связности ${\displaystyle G_{B}}$ , добавляется в MBST исходного графа. Процесс продолжается, пока в графе не останется единственное ребро, связывающее две (супер-) вершины (оно добавляется в MBST). MBST состоит из всех рёбер, найденных на предыдущих шагах .

Псевдокод

Функция имеет два входных параметра: граф G и массив w весов всех рёбер графа G . Возвращается множество рёбер, составляющих MBST графа G .

 1  function MBST(граф G, веса w)
 2  E ← множество рёбер графа G 
 3  если | E | = 1 то возвращаем E иначе
 4     A ← половина рёбер из E, чьи веса не меньше, чем медиана веса
 5     B ← E - A
 6     F ← лес графа GB
 7     если F является остовным деревом то
 8        возвращаем MBST(GB,w)
 9     иначе
 10       возвращаем ${\displaystyle MBST((G_{A})_{\eta },w)\cup F}$

Выше ${\displaystyle (G_{A})_{\eta }}$ является подграфом, составленным из супервершин (трактуя вершины в несвязной компоненте как одну вершину) и рёбер из A .

Время работы

Алгоритм работает за время O ( E ), где E является числом рёбер. Эта граница достигается за счёт того, что

• рёбра разбиваются на два множества с помощью алгоритма поиска медианы за время O ( E )
• находится лес за время O ( E )
• рассматривается половина рёбер множества E на каждой итерации, ${\displaystyle O(E+E/2+E/4+\dots +1)=O(E)}$

Пример

На следующем примере зелёные рёбра используются для образования MBST, а красные штриховые области показывают супервершины, полученные при работе алгоритма.

	Алгоритм делит пополам множество рёбер с учётом весов. Зелёным цветом показаны рёбра, вес которых мал насколько это возможно.
	Имеется остовное дерево в подграфе, образованном исключительно рёбрами из меньшего набора рёбер. Повторяем поиск MBST в этом подграфе.
	Нет остовного дерева в текущем подграфе, образованном рёбрами в текущем меньшем наборе рёбер. Комбинируем вершины разъединённых компонент с супервершинами (показаны красным пунктиром), а затем находим MBST в подграфе, образованном супервершинами и рёбрами в большем наборе рёбер. Лес, образованный каждой разъединённой компонентой, будет частью MBST исходного графа.
	Повторяем аналогичные шаги путём комбинирования вершин в супервершины.
	Алгоритм получает MBST из рёбер, найденных по ходу работы алгоритма.

Алгоритмы MBSA для ориентированных графов

Есть два алгоритма для ориентированных графов — алгоритм Камерини для поиска MBSA и алгоритм Габова и Тарьяна .

Алгоритм Камерини для MBSA

Для ориентированного графа алгоритм Камерини фокусируется на нахождении множества рёбер, которые имеют максимальную критичную цену MBSA. Делается это путём разбиения множества рёбер E на два множества A и B и поддержки множества T , которое является множеством, для которого известно, что G _T не имеет ориентированного остовного дерева. Множество T расширяется множеством B , если максимальное ориентированное остовное дерево графа ${\displaystyle G(B\cup T)}$ не является ориентированным остовным деревом графа G , в противном случае мы уменьшаем множество E , удаляя A . Общая сложность алгоритма по времени выполнения равна ${\displaystyle O(E\log E)}$ .

Псевдокод

 1  function MBSA(G, w, T)
 2  E ← множество рёбер графа G; 
 3  если | E - T | > 1 то
 4     A ← UH(E-T);
 5     B ← (E - T) - A;
 6     F ← BUSH(GBUT);
 7     если F является ориентированным остовным деревом графа G то
 8        S ← F; MBSA((GBUT),w,T);
 9     иначе
 10       MBSA(G,w,TUB);

1. T представляет подмножество E, для которого известно, что ${\displaystyle G_{T}}$ не содержит какого-либо ориентированного остовного дерева с корнем в вершине «a». Первоначально T пусто
2. UH берёт множество (E-T) рёбер графа G и возвращает ${\displaystyle A\subset (E-T)}$ such that:
   1. ${\displaystyle |A|=\left\lfloor {\frac {(|E-T|)}{2}}\right\rfloor }$
   2. ${\displaystyle W_{a}\geqslant W_{b}}$ для a ∈ A и b ∈ B
3. BUSH(G) возвращает максимальное ориентированное дерево графа G с корнем в вершине «a»
4. Окончательным результатом будет S

Пример

	После первой итерации этого алгоритма мы получаем F и F не является ориентированным остовным деревом графа G , так что выполняем код ${\displaystyle MBSA(G,w,T\cup B)}$
	На второй итерации мы получаем ${\displaystyle F'}$ и ${\displaystyle F'}$ снова не является ориентированным остовным деревом графа G , так что выполняем код ${\displaystyle MBSA(G,w,T'\cup B')}$
	На третьей итерации мы получаем ${\displaystyle F''}$ и ${\displaystyle F''}$ является ориентированным остовным деревом графа G , так что выполняем код ${\displaystyle MBSA(G_{T''\cup B''},w,T'')}$
${\displaystyle MBSA(G_{T''\cup B''},w,T'')}$	когда мы выполняем ${\displaystyle MBSA(G_{T''\cup B''},w,T'')}$ , ${\displaystyle |E-T|}$ равно 1, а значит не превосходит 1, так что алгоритм возвращает конечный результат, равный ${\displaystyle S=F''}$ .

Алгоритм Габова и Тарьяна для MBSA

Габов и Тарьян предложили образующую MBSA модификацию алгоритма Дейкстры кратчайшего пути с одним источником. Их алгоритм работает за время ${\displaystyle O(E+V\log V)}$ , если используется фибоначчиева куча .

Псевдокод

 Для графа G(V,E), F является набором вершин из V. 
 Начально F = s, где s является стартовой точкой графа G и c(s) = ∞

 1  function MBSA-GT(G, w, T)
 2    Выбираем v с минимальным c(v) из F; 
 3    Удаляем его из F;
 4    для всех ребер(v,w) выполняем
 5      если w ∉ F или ∉ Tree то
 6        добавляем w в F;          
 7        c(w) = c(v,w);
 8        p(w) = v;     
 9      иначе
 10       если w ∈ F и c(w) > c(v,w) то
 11         c(w) = c(v,w);
 12         p(w) = v;

Пример

Следующий пример показывает работу алгоритма.

Другой подход предложили Тарьян и Габов с границей ${\displaystyle O(E\log ^{*}V)}$ для разреженных графов, который очень похож на алгоритм Камерини для MBSA, но вместо разбиения множества рёбер на два множества на каждой итерации, вводятся ${\displaystyle K(i)}$ , в которых i является числом осуществлённых разбиений, или, другими словами, номер итерации, а ${\displaystyle K(i)}$ является возрастающей функцией, которая отражает число множеств, которые получаем в результате разбиений на каждой итерации. ${\displaystyle K(i)=2^{k(i-1)}}$ с ${\displaystyle k(1)=2}$ . Алгоритм находит ${\displaystyle \lambda ^{*}}$ , которое является значением веса критичного ребра в любом MBSA. После того, как найдено ${\displaystyle \lambda ^{*}}$ , любое ориентированное остовное дерево в ${\displaystyle G(\lambda ^{*})}$ является MBSA, в котором ${\displaystyle G(\lambda ^{*})}$ является графом, в котором все цены рёбер ${\displaystyle \leqslant \lambda ^{*}}$ .

Примечания

Литература

• Ahmad Traboulsi. . — 2014. 4 марта 2016 года.
• Murali T. M. . — 2009.
• Camerini P.M. The min-max spanning tree problem and some extensions // . — 1978. — Т. 7 , вып. 1 . — doi : .
• Harold N. Gabow, Robert E. Tarjan. // Journal of Algorithms. — 1988. — Т. 9 , вып. 3 . — ISSN . — doi : .

Для улучшения этой статьи желательно : Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии . После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.