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

'''Минимально критичное остовное дерево''' ({{lang-en|minimum bottleneck spanning tree}}, MBST) во взвешенном неориентированном графе  — это [[остовное дерево]], в котором наиболее тяжёлое ребро весит как можно меньше. Критичное ребро<ref>В оригинале  — бутылочное горлышко (bottleneck). Иногда переводится как «Минимально узкое остовное дерево>», что выглядит не вполне логично.</ref>  — это самое тяжёлое ребро в стягивающем дереве. Стягивающее дерево является минимальным критичным основным деревом, если граф не содержит стягивающего дерева с критичным ребром меньшего веса{{r|BST}}. Для ориентированного графа аналогичная задача известна как '''минимально критичное стягивающее ориентированное дерево''' ({{lang-en|Minimum Bottleneck Spanning Arborescence}}, MBSA)'''.

В неориентированном графе <math>G(V, E)</math> и функция <math>w : E \to \R</math>, пусть {{math|''S''}} будет множеством всех остовных деревьев <math>T_i</math>. Пусть <math>B(T_i)</math> будет максимальным по весу ребром для любого остовного дерева <math>T_i</math>. Мы определяем подмножество минимально критичных остовных деревьев ''S''&prime;′ так, что для любого <math>T_j \in S'</math> и <math>T_k \in S</math> мы имеем <math>B(T_j) \leqslant B(T_k)</math> для всех ''i'' и ''k''{{sfn|Murali|2009}}.

Ориентированное стягивающее дерево графа ''G''  — это ориентированное дерево графа ''G'', которое содержит ориентированный путь из указанной вершины ''L'' в каждую вершину подмножества ''V''&prime;′ графа <math>V \{L\}</math>. Вершина ''L'' называется корнем стягивающего ориентированного дерева. Ориентированное дерево является стягивающим ориентированным деревом, если <math>V' = V\{L\}</math>. MBST в этом случае является стягивающим ориентированным деревом с наименьшим критичным ребром. MBST в этом случае называется минимально критичным стягивающим ориентированным деревом ({{lang-en|Minimum Bottleneck Spanning Arborescence}}, MBSA).

Камерини предложил{{sfn|Camerini|1978|с=10}} [[алгоритм]], использующийся для получения минимально критичное остовное дерево (MBST) для данного неориентированного связного [[Взвешенный граф|со взвешенными рёбрами графа]] в 1978 году. Алгоритм делит рёбра на два множества. Веса рёбер в одном множестве не превосходят весов в другом. Если [[остовное дерево]] существует в подграфе, состоящем из рёбер исключительно набора с меньшими весами, алгоритм вычисляет MBST в подграфе и MBST этого подграфа будет в точности MBST исходного графа. Если [[остовное дерево]] не существует, алгоритм комбинирует каждую отдельную компоненту в новую супервершину, затем вычисляет MBST в графе, образованном этими супервершинами и рёбрами из множестве рёбер с бо́льшими весами. Лес в каждой отдельной компоненте является частью MBST исходного графа. Продолжаем процесс, пока в графе не останутся две (супер-) вершины и соединяющее их единственное ребро с минимальным весом будет добавлено. MBST состоит из всех рёбер, найденных на предыдущих шагах{{sfn|Traboulsi|2014}}.

Алгоритм работает за время ''[[«O» большое и «o» малое|O]]''(''E''), где ''E'' является числом рёбер. Эта граница достигается за счёт того, что

* рёбра разбиваются на два множества с помощью алгоритма поиска медианы за время ''O''(''E'')

* находится лес за время ''O''(''E'')

* рассматривается половина рёбер множества E на каждой итерации, <math>O(E + E/2 + E/4 + \dots + 1) = O(E)</math>

| Алгоритм делит пополам множество рёбер с учётом весов. Зелёным цветом показаны рёбра, вес которых мал насколько это возможно.

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

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

# T представляет подмножество E, для которого известно, что <math>G_T</math> не содержит какого-либо стягивающего ориентированного дерева с корнем в вершине “a”«a». Первоначально T пусто

## <math>W_a \geqslant W_b</math> для a &isin;∈ A и b &isin;∈ B

# BUSH(G) возвращает максимальное ориентированное дерево графа G с корнем в вершине “a”«a»

|

{| border=0 cellspacing=0 cellpadding=5

12 ''p''(''w'') = ''v'';''

|[[Файл:MBSA-GT-example-1.png|frame|827x827px|На первом шаге алгоритма мы выбираем корень s из графа G, на рисунке выше вершина 6 является корнем s. Затем мы находим все рёбра (6,w) &isin;∈ E и их цены c(6,w), где w &isin;∈ V.]]

|[[Файл:MBSA-GT-example-2.png|frame|815x815px|Переходим в вершину 5 графа G, и находим все рёбра (5,w) &isin;∈ E и их цены cost c(5,w), где w &isin;∈ V.]]

|[[Файл:MBSA-GT-example-7.png|frame|885x885px|Переходим в вершину 4 графа G, находим все рёбра (4,w) &isin;∈ E и их цены c(4,w), where w &isin;∈ V. Мы обнаруживаем, что ребро (4,5) > ребра (6,5), так что мы сохраняем ребро (6,5) и удаляем ребро (4,5).]]

|[[Файл:MBSA-GT-example-3.png|frame|880x880px|Переходим в вершину 1 графа G, находим все рёбра (1,w) &isin;∈ E и их цены c(1,w), где w &isin;∈ V. Мы обнаруживаем, что ребро (5,2) > ребра (1,2), так что мы удаляем ребро (5,2) и сохраняем ребро (1,2).]]

|[[Файл:MBSA-GT-example-4.png|frame|797x797px|Переходим в вершину 2 графа G, находим все рёбра (2,w) &isin;∈ E и их цены c(2,w), где w &isin;∈ V.]]

|[[Файл:MBSA-GT-example-5.png|frame|876x876px| Переходим в вершину 3 графа G, находим все рёбра (3,w) &isin;∈ E и их цены c(3,w), где w &isin;∈ V. Мы обнаруживаем, что ребро (3,4) > ребра (6,4), так что мы удаляем ребро (3,4) и сохраняем ребро (6,4).]]

Другой подход предложили Тарьян и Габов с границей <math>O(E \log^* V)</math> для разреженных графов, который очень похож на алгоритм Камерини для MBSA, но вместо разбиения множества рёбер на два множества на каждой итерации, вводятся <math>K(i)</math>, в которых ''i'' является числом осуществлённых разбиений, или, другими словами, номер итерации, а <math>K(i)</math> является возрастающей функцией, которая отражает число множеств, которые получаем в результате разбиений на каждой итерации. <math>K(i) = 2^{k(i - 1)}</math> с <math>k(1) = 2</math>. Алгоритм находит <math>\lambda^*</math>, которое является значением веса критичного ребра в любом MBSA. После того, как найдено <math>\lambda^*</math>, любое стягивающее ориентированное дерево в <math>G(\lambda^*)</math> является MBSA, в котором <math>G(\lambda^*)</math> является графом, в котором все цены рёбер <math>\leqslant \lambda^*</math>{{sfn|Traboulsi|2014}}{{sfn|Gabow, Tarjan|1988|с=411–417}}.

{{примечания|2|refs=

<ref name=Q3>{{citationcite web| title = in question 3 you have a proof for this claim | url =https://stanford.edu/~rezab/discrete/Midterm/midterm2016_soln.pdf | format=pdf|lang=en}}</ref>

.<ref name=Cui>{{citationcite web| last1author = Cui | first1 = Yuxiang | title = Minimum Bottleneck Spanning Tree | url = http://people.scs.carleton.ca/~maheshwa/courses/5703COMP/Talks/MBST/slides.pdf | year date= 2013 http }} {{Wayback|url=http://people.scs.carleton.ca/~maheshwa/courses/5703COMP/Talks/MBST/slides.pdf |date=20160304130339 }}</ref>}}

{{rq|checktranslate|style|grammar}}