Минимально критичное остовное дерево (Bnunbgl,uk tjnmncuky kvmkfuky ;yjyfk)

Перейти к навигации Перейти к поиску

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

Определения

[править | править код]

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

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

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

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

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

[править | править код]
Минимально критичное ориентированное остовное дерево G(V,E)

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

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

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

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

[править | править код]

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

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

[править | править код]

Для ориентированного графа алгоритм Камерини фокусируется на нахождении множества рёбер, которые имеют максимальную критичную цену MBSA. Делается это путём разбиения множества рёбер E на два множества A и B и поддержки множества T, которое является множеством, для которого известно, что GT не имеет ориентированного остовного дерева. Множество T расширяется множеством B, если максимальное ориентированное остовное дерево графа не является ориентированным остовным деревом графа G, в противном случае мы уменьшаем множество E, удаляя A. Общая сложность алгоритма по времени выполнения равна [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, для которого известно, что не содержит какого-либо ориентированного остовного дерева с корнем в вершине «a». Первоначально T пусто
  2. UH берёт множество (E-T) рёбер графа G и возвращает such that:
    1. для a ∈ A и b ∈ B
  3. BUSH(G) возвращает максимальное ориентированное дерево графа G с корнем в вершине «a»
  4. Окончательным результатом будет S
После первой итерации этого алгоритма мы получаем F и F не является ориентированным остовным деревом графа G, так что выполняем код
На второй итерации мы получаем и снова не является ориентированным остовным деревом графа G, так что выполняем код
На третьей итерации мы получаем и является ориентированным остовным деревом графа G, так что выполняем код

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

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

[править | править код]

Габов и Тарьян предложили образующую MBSA модификацию алгоритма Дейкстры кратчайшего пути с одним источником. Их алгоритм работает за время , если используется фибоначчиева куча[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      если wF или ∉ Tree то
 6        добавляем w в F;          
 7        c(w) = c(v,w);
 8        p(w) = v;     
 9      иначе
 10       если wF и c(w) > c(v,w) то
 11         c(w) = c(v,w);
 12         p(w) = v;

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

На первом шаге алгоритма мы выбираем корень s из графа G, на рисунке выше вершина 6 является корнем s. Затем мы находим все рёбра (6,w) ∈ E и их цены c(6,w), где w ∈ V.
Переходим в вершину 5 графа G, и находим все рёбра (5,w) ∈ E и их цены cost c(5,w), где w ∈ V.
Переходим в вершину 4 графа G, находим все рёбра (4,w) ∈ E и их цены c(4,w), where w ∈ V. Мы обнаруживаем, что ребро (4,5) > ребра (6,5), так что мы сохраняем ребро (6,5) и удаляем ребро (4,5).
Переходим в вершину 1 графа G, находим все рёбра (1,w) ∈ E и их цены c(1,w), где w ∈ V. Мы обнаруживаем, что ребро (5,2) > ребра (1,2), так что мы удаляем ребро (5,2) и сохраняем ребро (1,2).
Переходим в вершину 2 графа G, находим все рёбра (2,w) ∈ E и их цены c(2,w), где w ∈ V.
Переходим в вершину 3 графа G, находим все рёбра (3,w) ∈ E и их цены c(3,w), где w ∈ V. Мы обнаруживаем, что ребро (3,4) > ребра (6,4), так что мы удаляем ребро (3,4) и сохраняем ребро (6,4).
После просмотра всех вершин графа G алгоритм завершается.

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

Примечания

[править | править код]
  1. В оригинале — бутылочное горлышко (bottleneck). Иногда переводится как «Минимально узкое остовное дерево», что выглядит не вполне логично.
  2. Everything about Bottleneck Spanning Tree. Дата обращения: 9 сентября 2019. Архивировано 5 мая 2018 года.
  3. Murali, 2009.
  4. in question 3 you have a proof for this claim (англ.) (pdf).
  5. 1 2 3 4 5 Traboulsi, 2014.
  6. 1 2 Camerini, 1978, с. 10.
  7. Cui Yuxiang. Minimum Bottleneck Spanning Tree (2013). Дата обращения: 26 сентября 2019. Архивировано 4 марта 2016 года.
  8. 1 2 Gabow, Tarjan, 1988, с. 411–417.

Литература

[править | править код]