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

Минимально критичное остовное дерево (англ. minimum bottleneck spanning tree, MBST) во взвешенном неориентированном графе — это остовное дерево, в котором наиболее тяжёлое ребро весит как можно меньше. Критичное ребро^[1] — это самое тяжёлое ребро в остовном дереве. Остовное дерево является минимальным критичным остовным деревом, если граф не содержит остовного дерева с критичным ребром меньшего веса^[2]. Для ориентированного графа аналогичная задача известна как минимально критичное ориентированное остовное дерево (англ. 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^[3].

Граф на рисунке справа является примером 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) неизбежно является минимально критичным, но не любое минимально критичное обязательно будет минимальным^[4][5].

Камерини в 1978 году предложил^[6] алгоритм, использующийся для получения минимально критичного остовного дерева (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 состоит из всех рёбер, найденных на предыдущих шагах^[5].

Функция имеет два входных параметра: граф G и массив w весов всех рёбер графа G^[7]. Возвращается множество рёбер, составляющих 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 и алгоритм Габова и Тарьяна^[5].

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

 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 модификацию алгоритма Дейкстры кратчайшего пути с одним источником. Их алгоритм работает за время ${\displaystyle O(E+V\log V)}$, если используется фибоначчиева куча^[8].

 Для графа 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 ^{*}}$^[5][8].

• Ahmad Traboulsi. Bottleneck Spanning Trees. — 2014. Архивировано 4 марта 2016 года.
• Murali T. M. Applications of Minimum Spanning Trees. — 2009.
• Camerini P.M. The min-max spanning tree problem and some extensions // Information Processing Letters. — 1978. — Т. 7, вып. 1. — doi:10.1016/0020-0190(78)90030-3.
• Harold N. Gabow, Robert E. Tarjan. Algorithms for two bottleneck optimization problems // Journal of Algorithms. — 1988. — Т. 9, вып. 3. — ISSN 0196-6774. — doi:10.1016/0196-6774(88)90031-4.

На эту статью не ссылаются другие статьи Википедии. Пожалуйста, установите ссылки в соответствии с принятыми рекомендациями. (10 сентября 2019)

У этой статьи есть несколько проблем, помогите их исправить: Необходимо проверить качество перевода c неуказанного языка, исправить содержательные и стилистические ошибки. Вы можете помочь улучшить эту статью (см. также рекомендации по переводу). Оригинал не указан. Пожалуйста, укажите его. (9 сентября 2019) Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. Статью следует исправить согласно стилистическим правилам Википедии. (9 сентября 2019) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.