Минимально критичное остовное дерево (, MBST) во взвешенном неориентированном графе — это остовное дерево, в котором наиболее тяжёлое ребро весит как можно меньше. Критичное реброВ оригинале — бутылочное горлышко (bottleneck). Иногда переводится как «Минимально узкое остовное дерево», что выглядит не вполне логично. — это самое тяжёлое ребро в остовном дереве. Остовное дерево является минимальным критичным остовным деревом, если граф не содержит остовного дерева с критичным ребром меньшего веса. Для ориентированного графа аналогичная задача известна как минимально критичное ориентированное остовное дерево (, MBSA).

Определения

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

В неориентированном графе и функция , пусть будет множеством всех остовных деревьев . Пусть будет максимальным по весу ребром для любого остовного дерева . Мы определяем подмножество минимально критичных остовных деревьев S′ так, что для любого и мы имеем для всех i и k.

Граф на рисунке справа является примером MBST, красные рёбра графа образуют MBST графа .

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

Ориентированное остовное дерево орграфа  — это ориентированное (корневое) дерево, которое содержит ориентированный путь из указанной вершины L в каждую вершину графа. Вершина L называется корнем ориентированного остовного дерева. Критичная дуга — это самая тяжёлая дуга в ориентированном остовном дереве. Ориентированное остовное дерево называется минимально критичным (, MBSA), если орграф не содержит ориентированного остовного дерева с критичной дугой меньшего веса.

Граф справа является примером MBSA, красные рёбра в графе образуют MBSA графа .

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

Алгоритм Камерини для неориентированных графов Камерини в 1978 году предложил алгоритм, использующийся для получения минимально критичного остовного дерева (MBST) для данного неориентированного связного взвешенного графа. Алгоритм разбивает все рёбра графа на такие два множества и , что веса рёбер из множества не превосходят весов из множества . Если подграф , состоящий из рёбер множества , связен, алгоритм рекурсивно ищет MBST в , и оно будет являться MBST для исходного графа. Если же не связен, алгоритм комбинирует каждую его компоненту связности в новую супервершину, затем рекурсивно вычисляет MBST в графе, образованном этими супервершинами и рёбрами из множества . Произвольный лес из рёбер множества , компоненты связности которого совпадают с компонентами связности , добавляется в 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 возвращаем Выше является подграфом, составленным из супервершин (трактуя вершины в несвязной компоненте как одну вершину) и рёбер из A.

Время работы Алгоритм работает за время O(E), где E является числом рёбер. Эта граница достигается за счёт того, что рёбра разбиваются на два множества с помощью алгоритма поиска медианы за время O(E) находится лес за время O(E) рассматривается половина рёбер множества E на каждой итерации,

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

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

Алгоритм Камерини для MBSA Для ориентированного графа алгоритм Камерини фокусируется на нахождении множества рёбер, которые имеют максимальную критичную цену MBSA. Делается это путём разбиения множества рёбер E на два множества A и B и поддержки множества T, которое является множеством, для которого известно, что GT не имеет ориентированного остовного дерева. Множество T расширяется множеством B, если максимальное ориентированное остовное дерево графа не является ориентированным остовным деревом графа G, в противном случае мы уменьшаем множество E, удаляя A. Общая сложность алгоритма по времени выполнения равна .

Псевдокод 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, для которого известно, что не содержит какого-либо ориентированного остовного дерева с корнем в вершине «a». Первоначально T пусто UH берёт множество (E-T) рёбер графа G и возвращает such that:

для a ∈ A и b ∈ B BUSH(G) возвращает максимальное ориентированное дерево графа G с корнем в вершине «a» Окончательным результатом будет S

Пример После первой итерации этого алгоритма мы получаем и не является ориентированным остовным деревом графа , так что выполняем код На второй итерации мы получаем и снова не является ориентированным остовным деревом графа , так что выполняем код На третьей итерации мы получаем и является ориентированным остовным деревом графа , так что выполняем код когда мы выполняем , равно 1, а значит не превосходит 1, так что алгоритм возвращает конечный результат, равный .

Алгоритм Габова и Тарьяна для MBSA Габов и Тарьян предложили образующую MBSA модификацию алгоритма Дейкстры кратчайшего пути с одним источником. Их алгоритм работает за время , если используется фибоначчиева куча.

Псевдокод Для графа 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;

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

Другой подход предложили Тарьян и Габов с границей для разреженных графов, который очень похож на алгоритм Камерини для MBSA, но вместо разбиения множества рёбер на два множества на каждой итерации, вводятся , в которых i является числом осуществлённых разбиений, или, другими словами, номер итерации, а является возрастающей функцией, которая отражает число множеств, которые получаем в результате разбиений на каждой итерации. с . Алгоритм находит , которое является значением веса критичного ребра в любом MBSA. После того как найдено , любое ориентированное остовное дерево в является MBSA, в котором является графом, в котором все цены рёбер .

Примечания

Литература

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