Русская Википедия:Минимально критичное остовное дерево
Минимально критичное остовное дерево (Шаблон:Lang-en, MBST) во взвешенном неориентированном графе — это остовное дерево, в котором наиболее тяжёлое ребро весит как можно меньше. Критичное ребро[1] — это самое тяжёлое ребро в стягивающем дереве. Стягивающее дерево является минимальным критичным остовным деревом, если граф не содержит стягивающего дерева с критичным ребром меньшего весаШаблон:R. Для ориентированного графа аналогичная задача известна как минимально критичное стягивающее ориентированное дерево (Шаблон:Lang-en, MBSA).
Определения
Неориентированные графы
В неориентированном графе <math>G(V, E)</math> и функция <math>w : E \to \R</math>, пусть Шаблон:Math будет множеством всех остовных деревьев <math>T_i</math>. Пусть <math>B(T_i)</math> будет максимальным по весу ребром для любого остовного дерева <math>T_i</math>. Мы определяем подмножество минимально критичных остовных деревьев S′ так, что для любого <math>T_j \in S'</math> и <math>T_k \in S</math> мы имеем <math>B(T_j) \leqslant B(T_k)</math> для всех i и kШаблон:Sfn.
Граф на рисунке справа является примером MBST, красные рёбра графа образуют MBST графа <math>G(V, E)</math>.
Ориентированные графы
Ориентированное стягивающее дерево графа G — это ориентированное дерево графа G, которое содержит ориентированный путь из указанной вершины L в каждую вершину подмножества V′ графа <math>V \{L\}</math>. Вершина L называется корнем стягивающего ориентированного дерева. Ориентированное дерево является стягивающим ориентированным деревом, если <math>V' = V\{L\}</math>. MBST в этом случае является стягивающим ориентированным деревом с наименьшим критичным ребром. MBST в этом случае называется минимально критичным стягивающим ориентированным деревом (Шаблон:Lang-en, MBSA).
Граф справа является примером MBSA, красные рёбра в графе образуют MBSA графа <math>G(V, E)</math>.
Свойства
MST (минимальное остовное дерево, Шаблон:Lang-en) неизбежно является MBST, но MBST не обязательно будет MSTШаблон:RШаблон:Sfn.
Алгоритм Камерини для неориентированных графов
Камерини предложилШаблон:Sfn алгоритм, использующийся для получения минимально критичного остовного дерева (MBST) для данного неориентированного связного со взвешенными рёбрами графа в 1978 году. Алгоритм делит рёбра на два множества. Веса рёбер в одном множестве не превосходят весов в другом. Если остовное дерево существует в подграфе, состоящем из рёбер исключительно набора с меньшими весами, алгоритм вычисляет MBST в подграфе и MBST этого подграфа будет в точности MBST исходного графа. Если остовное дерево не существует, алгоритм комбинирует каждую отдельную компоненту в новую супервершину, затем вычисляет MBST в графе, образованном этими супервершинами и рёбрами из множестве рёбер с бо́льшими весами. Лес в каждой отдельной компоненте является частью MBST исходного графа. Продолжаем процесс, пока в графе не останутся две (супер-) вершины и соединяющее их единственное ребро с минимальным весом будет добавлено. MBST состоит из всех рёбер, найденных на предыдущих шагахШаблон:Sfn.
Псевдокод
Процедура имеет два входных параметра. G является графом, w является массивом весов всех рёбер графа GШаблон:R.
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 возвращаем <math>MBST((G_A)_\eta, w) \cup F</math>
Выше <math>(G_A)_\eta</math> является подграфом, составленным из супервершин (трактуя вершины в несвязной компоненте как одну вершину) и рёбер из A.
Время работы
Алгоритм работает за время O(E), где E является числом рёбер. Эта граница достигается за счёт того, что
- рёбра разбиваются на два множества с помощью алгоритма поиска медианы за время O(E)
- находится лес за время O(E)
- рассматривается половина рёбер множества E на каждой итерации, <math>O(E + E/2 + E/4 + \dots + 1) = O(E)</math>
Пример
На следующем примере зелёные рёбра используются для образования MBST, а красные штриховые области показывают супервершины, полученные при работе алгоритма.
| Файл:Camerini Algorithm 1.svg | Алгоритм делит пополам множество рёбер с учётом весов. Зелёным цветом показаны рёбра, вес которых мал насколько это возможно. |
| Файл:Camerini Algorithm 2.svg | Имеется остовное дерево в подграфе, образованном исключительно рёбрами из меньшего набора рёбер. Повторяем поиск MBST в этом подграфе. |
| Файл:Camerini Algorithm 3.svg | Нет остовного дерева в текущем подграфе, образованном рёбрами в текущем меньшем наборе рёбер. Комбинируем вершины разъединённых компонент с супервершинами (показаны красным пунктиром), а затем находим MBST в подграфе, образованном супервершинами и рёбрами в большем наборе рёбер. Лес, образованный каждой разъединённой компонентой, будет частью MBST исходного графа. |
| Файл:Camerini Algorithm 4.svg | Повторяем аналогичные шаги путём комбинирования вершин в супервершины. |
| Файл:Camerini Algorithm 1.svg | Алгоритм получает MBST из рёбер, найденных по ходу работы алгоритма. |
Алгоритмы MBSA для ориентированных графов
Есть два алгоритма для ориентированных графов — алгоритм Камерини для поиска MBSA и алгоритм Габова и ТарьянаШаблон:Sfn.
Алгоритм Камерини для MBSA
Для ориентированного графа алгоритм Камерини фокусируется на нахождении множества рёбер, которые имеют максимальную критичную цену MBSA. Делается это путём разбиения множества рёбер E на два множества A и B и поддержки множества T, которое является множеством, для которого известно, что GT не имеет стягивающего ориентированного дерева. Множество T расширяется множеством B, если максимальное ориентированное стягивающее дерево графа <math>G(B \cup T)</math> не является стягивающим ориентированным деревом графа G, в противном случае мы уменьшаем множество E, удаляя A. Общая сложность алгоритма по времени выполнения равна <math>O(E \log E)</math>Шаблон:SfnШаблон:Sfn.
Псевдокод
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);
- T представляет подмножество E, для которого известно, что <math>G_T</math> не содержит какого-либо стягивающего ориентированного дерева с корнем в вершине «a». Первоначально T пусто
- UH берёт множество (E-T) рёбер графа G и возвращает <math>A \subset (E-T)</math> such that:
- <math>|A| = \left \lfloor \frac{(|E-T|)}{2} \right \rfloor</math>
- <math>W_a \geqslant W_b</math> для a ∈ A и b ∈ B
- BUSH(G) возвращает максимальное ориентированное дерево графа G с корнем в вершине «a»
- Окончательным результатом будет S
Пример
| Файл:MBSA Example 1.svgФайл:MBSA Example 2.svgФайл:MBSA Example 3.svg | После первой итерации этого алгоритма мы получаем Шаблон:Mvar и Шаблон:Mvar не является стягивающим ориентированным деревом графа Шаблон:Mvar, так что выполняем код <math>MBSA(G,w,T \cup B)</math> | ||
| Файл:MBSA Example 4.svgФайл:MBSA Example 5.svgФайл:MBSA Example 6.svg | На второй итерации мы получаем <math>F'</math> и <math>F'</math> снова не является стягивающим ориентированным деревом графа Шаблон:Mvar, так что выполняем код <math>MBSA(G,w,T' \cup B')</math> | ||
| Файл:MBSA Example 7.svgФайл:MBSA Example 8.svgФайл:MBSA Example 9.svg | На третьей итерации мы получаем <math>F</math> и <math>F</math> является стягивающим ориентированным деревом графа Шаблон:Mvar, так что выполняем код <math>MBSA(G_{T\cup B}, w, T)</math> | ||
|
E-T|</math> равно 1, а значит не превосходит 1, так что алгоритм возвращает конечный результат, равный <math>S = F</math>. |
Алгоритм Габова и Тарьяна для MBSA
Габов и Тарьян предложили образующую MBSA модификацию алгоритма Дейкстры кратчайшего пути с одним источником. Их алгоритм работает за время <math>O(E + V \log V)</math>, если используется фибоначчиева кучаШаблон:Sfn.
Псевдокод
Для графа 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;
Пример
Следующий пример показывает работу алгоритма.
Другой подход предложили Тарьян и Габов с границей <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Шаблон:Sfn.
Примечания
Литература
Шаблон:Изолированная статья Шаблон:Rq
- ↑ В оригинале — бутылочное горлышко (bottleneck). Иногда переводится как «Минимально узкое остовное дерево», что выглядит не вполне логично.
.png){kind=link}
