Первая страница / Теория / Графы. Покрывающие деревья /

Минимальные остовные деревья

Голосование: 5, 0

Введение

В статье рассматривается алгоритм построения минимального остовного дерева (minimum-spanning-tree), предложенный Чазелом (Bernard Chazelle) и изложенный в [1]. Алгоритм работает за время O(mα(m,n)), где α - обратная функция Аккермана (functional inverse of Ackermann's function), описанная в [2], а n и m - количество вершин и ребер в графе соответственно.

Задача о нахождении минимального остовного дерева имеет долгую и богатую историю. В действительности данная задача возможно старейшая открытая проблема в алгоритмике. Согласно [3] "это краеугольный камень проблемы комбинаторной оптимизации и в некотором смысле её колыбель" ("this is cornerstone problem of combinatorial optimization and in a sense its cradle"). История проблемы и описание некоторых других алгоритмов её решения достаточно подробно изложены в статье [4].

Данная статья не претендует на полное рассмотрение всех аспектов, связанных с алгоритмом, в частности, опущены вопросы доказательства корректности и времени работы. В начале статьи приведены общие принципы работы алгоритма, а далее более подробно рассмотрены все его шаги.

Постановка задачи

Пусть имеется связный неориентированный граф G, на ребрах которого задана весовая функция c(e). Связный подграф графа G, являющийся деревом и содержащий все его вершины, называют покрывающим деревом (spanning-tree) этого графа (иногда используют термин остовное дерево или остов). Весом остовного дерева будем считать сумму весов всех его ребер. Тогда возникает задача о нахождении минимального покрывающего дерева, т.е. такого, что его вес меньше, либо равен весу любого из покрывающих деревьев для данного графа. Будем обозначать минимальное покрывающее дерево графа G как MST(G).

За разъяснением некоторых понятий и определений из теории графов, здесь не приведенных, можно обращаться к [6].

Алгоритм в целом

Подграф C графа G назовем конденсируемым (contractible), если его пересечение с MST(G) связно. Это понятие нам будет полезно, потому что мы можем получить MST(G) из MST(C) и MST(G'), где G' - граф, полученный из G путем конденсации C в одну вершину. Предыдущие алгоритмы определяют конденсируемые подграфы в процессе работы, при этом исследованная часть MST "наращивается". Первая идея заключается в том, что мы обратим этот процесс, т.е. будем определять, является ли C конденсируемым до вычисления его MST. Преимущество должно быть очевидно. Найти MST(C) легче, если мы знаем, что C - конденсируемый подграф, тогда нужно будет рассматривать только ребра, оба конца которых лежат в C. В противном случае нам так же нужно проверять ребра, у которых только одна вершина принадлежит C. Это позволяет использовать метод "разделяй и властвуй" (divide-and-conquer approach). Возникает проблема - как искать конденсируемые подграфы без нахождения MST в то же время. Нет эффективных методов для решения данной проблемы, и поэтому мы будем использовать такую структуру как Soft Heap (см. [5]), в дальнейшем - куча.

Для вычисления MST(G) мы разделим граф на непересекающиеся конденсируемые подграфы подходящего размера. Затем мы сконденсируем каждый подграф в вершину, полученный граф мы снова разделяем на конденсируемые компоненты и т.д. Будем повторять этот процесс, пока G не сожмется в одну вершину. Таким образом, у нас сформируется иерархия подграфов, которая хорошо представляется сбалансированным деревом Τ: его листья являются вершинами G, а промежуточная вершина z c детьми {zi} соответствует подграфу Cz, вершинами которого являются конденсации графов {Czi}. Назовем минором графа G граф, полученный из G путем выполнения некоторой последовательности конденсаций, тогда каждый уровень Τ представляет собой определенный минор графа G и каждый Cz является конденсируемым подграфом некоторого минора. В этом сопоставлении уровень листьев соответствует G, в то время как корень дерева соответствует всему графу G, сконденсированному в одну вершину. Имея в наличии Τ, мы можем найти MST каждого Cz рекурсивно. Т.к. подграфы Cz конденсируемы, то склеивание деревьев MST(Cz) даст нам MST(G).

Мы имеем свободу в выборе высоты d дерева Τ и количества вершин nz в каждом Cz (что, как мы должны заметить, так же является количеством детей z). Дерево Τ строится за время O(m+d3n) (доказательство данной оценки приводится в [1]). Если d выбирается большое, то nz становится маленьким; при этом рекурсивная обработка каждого Cz производится быстро, но построение дерева Τ производится медленно. И наоборот - маленькая высота ускоряет построение Τ, но делает Cz больше, что делает рекурсию более дорогой по времени. Для выбора этих величин в игру вступает функция Аккермана (см. [2]), предоставляя наиболее выгодное соотношение. Пусть dz высота z в Τ, определим высоту как максимальную длину пути вниз по дереву до листа. Следует выбирать nz следующим образом:

при dz=1: nz = S(t,1)3
при dz>1: nz=S(t-1,S(t,dz-1))3, где
t=min{i>0|n<=S(i,d)3}, d=c⌈(m/n)1/3⌉, для достаточно большой константы c.

Сейчас мы не рассматриваем некоторые технические трудности, связанные с построением Τ, но они будут рассмотрены в последствии. Сейчас же мы рассмотрим очень важный аспект – повреждение ребер, неизбежный продукт использования Soft Heap.

Повреждение ребер

В течение построения Τ, некоторые ребра становятся поврежденными, т.е. их веса становятся больше. По сути, все еще хуже - вес поврежденного ребра может быть увеличен несколько раз. Все эти проблемы связанны с Soft Heap (приближенной очередью с приоритетами), которую мы используем для нахождения конденсируемых подграфов (подробнее об этом позже).

Некоторые поврежденные ребра создают проблемы, в то время как другие - нет. Чтобы понять этот феномен – один из самых занимательных аспектов анализа алгоритма, мы должны обсудить, как происходит построение Τ.

Очень заманчиво строить Τ снизу вверх слой за слоем, но это является ошибкой. Конечно, необходимо поддерживать связную структуру. Итак, вместо этого мы будем строить Τ в порядке обратном обходу в глубину от корня: сначала детей, потом их родителей. Пусть z текущая запись, посещенная в Τ, и пусть z1zk = z - активный путь, т.е. путь из корня z1. Подграфы Cz1, … , Czk в данный момент строятся, и когда Czk будет готов, он будет сконденсирован в вершину, которая добавится в Cz(k-1). Незначительный технический нюанс: если zi+1 самый левый ребенок zi, т.е. первый по времени посещенный ребенок, то Czi еще не имеет вершин, а значит, имеет смысл выкинуть её из активного пути. Избегая записей с одним ребенком, мы обеспечиваем, что каждый из Cz1, …, Czk сейчас имеет хотя бы одну вершину, которая является вершиной G или конденсацией связанного подграфа.

Пусть ребро E из G имеет ровно одну вершину в объединении Cz1, Cz2, …, Czk, тогда говорим, что ребро E - граничного типа. Конечно, тип ребра меняется во времени последовательно: не посещенное, граничное, принадлежащее Cz вдоль активного пути, сконденсированное. Повреждение может вызвать проблемы с ребром, только когда оно граничного типа (в этот момент оно находится в Soft Heap). Во-первых, повреждение может оказаться фатальным: если все ребра повредятся, мы будем решать задачу с полностью неверными данными? Но, в действительности, чудесным образом повреждение причиняет вред только в одной специфической ситуации: будем говорить, что ребро становится плохим, если повреждается граничное ребро в то время, когда оно инцидентно Cz, которая сконденсирована в одну вершину. Ребро, ставшее однажды плохим, останется плохим, но, как и у всех поврежденных ребер, вес плохого ребра может увеличиваться и в дальнейшем.

В дополнение можно показать, что если никакие ребра никогда не станут плохими, то алгоритм будет вести себя также, как если никакие ребра не повреждались бы, не обращая внимания на то, что случается в реальности. Таким образом, нам нужно бороться с плохими ребрами, а не с поврежденными. Мы можем ограничить количество плохих ребер числом (m/2+d3n). Количество поврежденных ребер, которые не станут плохими, нам не важно.

Как только Τ построено, мы восстанавливаем все веса ребер к их оригинальным значениям и удаляем все плохие ребра. Далее рекурсивно обрабатываем то, что осталось от Cz-ов, чтобы получить покрывающий лес (граф, полученный путем объединения минимальных покрывающих деревьев компонент связности графа G). В итоге мы возвращаем плохие ребра и снова рекурсивно обрабатываем, чтобы получить MST(G). В этих разнообразных рекурсиях есть некоторые хитрости, которые мы объясним впоследствии. А этот обзор мы закончим кратким обзором Soft Heap.

Soft Heap

Приоритетная очередь, названная Soft Heap - основное средство для выбора хороших ребер кандидатов. Данная структура хранит элементы с ключами из строго упорядоченного множества и поддерживает нижеследующие операции:

  • Create(S) - создание пустой очереди S;
  • Insert(S,x) - добавление нового элемента x к очереди S;
  • Meld(S,S') - создание новой очереди с элементами, содержащимися в S и S' (предполагается, что их множества не пересекаются) и уничтожение S и S';
  • Delete(S,x) - удаление элемента x из S;
  • Findmin(S) - получение элемента с наименьшим ключом.
Особенность Soft Heap заключается в том, что она может в любое время увеличить размер определенных ключей. Такие ключи и соответствующие им элементы назовем поврежденными. В действительности findmin возвращает элементы с минимальным текущим (не настоящим) ключом. Параметр Ε (error rate) контролирует количество повреждений.

Подробное описание Soft Heap с примером реализации можно найти в статье [3], а здесь же имеет смысл привести важное свойство:

Теорема 1.1 [3]

Начиная с пустой кучи, выполнив произвольную последовательность операций, включающую в себя n операций insert, для любого 1<Ε<=1/2, Soft Heap с пропорцией ошибок Ε выполняет каждую итерацию за константное амортизированное время, кроме insert, для которой требуется O(log(1/Ε)) времени. Структура данных никогда не содержит более чем Εn поврежденных элементов в любой момент времени.

Алгоритм

Мы начнем с обзора хорошо известной процедуры, известной как фаза Борувки. Мы выбираем вершину и конденсируем самое легкое ребро, инцидентное ей. Как хорошо известно, это превращает граф G в граф с тем же множеством ребер, не принадлежащих MST. Мы чистим граф G, если необходимо удаляем петли, которые могут появиться в процессе (для начала будем считать, что граф может иметь кратные ребра). Мы можем обобщить этот процесс, выбирая самое легкое ребро смежное каждой вершине G, и конденсируя каждую компоненту связности графа, образованного выбранными ребрами. Затем снова чистим граф. Это называется фазой Борувки; она легко производится за время O(m), за один проход по графу. При этом выбрасывается как минимум половина вершин. Эта простая процедура полезна для уменьшения числа вершин и играет важную роль в алгоритме MST.

Чтобы построить MST связанного графа G с n вершинами и m ребрами, мы вызываем функцию msf(G,t) со значением параметра t:

t=min{i>0|n<=S(i,d)3}, где d=c⌈(m/n)1/3⌉   (1)
Здесь и далее мы обозначаем как c достаточно большую целую константу. Функция msf принимает как параметры целое число t>=1 и граф с различными весами ребер (случай с одинаковыми весам легко сводится к данному), и возвращает его минимальный покрывающий лес. Мы более не считаем, что исходный граф должен быть связанным. Выбор t произволен и влияет только на время выполнения. Частный выбор в (1) лучший возможный, но из-за рекурсивной природы алгоритма необходимо позволить t изменяться как параметру.

msf(G,t)
1: Если t=1 или n=O(1), то возвращаем MST(G) построенное алгоритмом Борувки
2: Выполняем c последовательных фаз Борувки
3: Строим T и формируем граф B плохих ребер
4: FUz∈Τ msf(Cz\B,t-1)
5: Возвращаем msf(FB,t)∪{ребра, сконденсированные на 2 шаге}

Шаги 1 и 2: Фазы Борувки

Случай t=1 особенный. Мы решаем задачу за время O(n2) выполняя фазу Борувки пока G не сконденсируется в одну вершину. Если мы аккуратно будем удалять кратные ребра (оставляя только самые легкие в каждой группе) и следить, чтобы граф не содержал кратных ребер, то легко выполним все фазы за суммарное время O(n2+(n2)/2+(n2)/4+…)=O(n2). Тогда, если n=O(1), то мы построим MST за время O(m). Мы будем применять алгоритм к каждой компоненте связности G отдельно. Цель этого действия в том, что можно полагать в дальнейшем, что граф G связен.

Смысл шага два заключается лишь в том, чтобы уменьшить число вершин. Фазы Борувки превращают граф G в граф G0 с n0<=n/(2c) вершинами и m0<m ребрами. Эта трансформация требует O(n+m) времени.

Шаг 3: Строительство иерархии Τ

При t>1 начинаем построение дерева Τ. Определим предполагаемый размер nz для каждой Cz:

nz=S(t-1,S(t,dz-1))3, где dz - это высота z в Τ.
Мы используем слово "предполагаемый" потому, что данный размер не всегда может быть достигнут в алгоритме. Это не более чем технический, но довольно глубокий аспект этого алгоритма, объяснение которого лучше опустить.

Обсудим центральную часть алгоритма. Пусть z1, z2, …, zk=z обозначает активный путь. Как показано на рисунке 1, подграфы Cz1, …, Czk сейчас находятся в процессе построения и соединены между собой в цепь с уменьшающимися весами ребер. Алгоритм время от времени отбрасывает ребра из G0 (термин "отбрасывает" имеет техническое значение и применяется к ребрам, удаленным из рассмотрения в специфических обстоятельствах, которые разъясняются ниже). Каждый из графов Cz должен содержать все неотброшенные ребра G0, концы которых являются вершинами Сz, поэтому, чтобы задать какой-либо Cz, достаточно хранить только его вершины (напомним, что вершины Cz не обязательно являются вершинами G0). Условия, описанные ниже, поддерживаются в любое время по отношению к текущему графу G0 (т.е. оригинальному графу G0, исключая все предварительно отброшенные ребра). Определим важное понятие рабочего веса: в любое время, рабочий вес ребра - это текущий вес, если ребро плохое, и оригинальный вес в противном случае. Таким образом, мы различаем три вида весов - оригинальный, текущий и рабочий.

  • Условие 1:
    Для всех i<k, мы храним ребро (называемое звеном цепи), объединяющее Czi и Cz(i+1), чей текущий вес:

    • Больше, чем у любого граничного ребра инцидентного Cz1 ∪ … ∪ Czi
    • Меньше, чем рабочий вес для любого ребра, объединяющего различные Czj (j<=i)
    Так же мы храним минимальное звено, если оно существует, для каждой пары i<j: это ребро с минимальным рабочим весом объединяющее различные Czi и Czj.
    Рис. 1
    Рис. 1. Цепь подграфов вдоль активного пути, где веса ребер представленны высотой.

  • Условие 2:
    Для всех j граничные ребра (u,v), где u принадлежит Czj, содержатся либо в куче H(j), либо в какой-то куче H(i,j), где 0<=i<j. Никакое ребро не может содержаться сразу в нескольких кучах. Нахождение в H(j) подразумевает, что v инцидентно хотя бы одному ребру, содержащемуся в H(i,j); нахождение же в H(i,j) подразумевает, что v смежно с Czi, но не смежно ни с каким Czl, где l удовлетворяет условию (i<l<j). Мы добавляем i=0, чтобы обозначить, что v не смежно никакому Czl (l<j). Всем кучам мы устанавливаем пропорцию ошибок 1/c. Основной смысл условия состоит в том, чтобы активный путь соответствовал убывающей цепи ребер, соединяющей различные Cz. Данное условие необходимо, чтобы быть уверенными в том, что получаемые подграфы конденсируемы. Звено цепи между Czi и Cz(i+1) - это ребро, дающее Cz(i+1) его первую вершину. Впоследствии, когда Cz(i+1) растет, более легкие по весу ребра могут соединять его с Czi, значит звено цепи, скорее всего, не будет соответствовать минимальному звену между Czi и Cz(i+1).

Зачем нам так много Soft Heap? Говоря кратко - чтобы бороться с плохими ребрами. Проблема в том, что когда плохие ребра удаляются из Soft Heap, Теорема 1.1 позволяет появиться новым поврежденным ребрам в том же объёме. Эти новые поврежденные ребра могут стать плохими и снова быть удалены. Повторение данного процесса может иметь губительные последствия. Возможно, каждое ребро графа станет плохим. Мы используем отдельные кучи для создания эффекта буферов, чтобы противостоять этому процессу. Этот механизм полагается на структурные свойства минимальных покрывающих деревьев и хитрое взаимодействие между кучами.

Дерево Τ строится в порядке обхода в глубину, используя стек, две операции push и pop которого заменены операциями сжатия(retraction) и расширения(extension) активного пути соответственно:

  • Сжатие:
    Происходит при k>=2, когда последний подграф Czk достиг своего целевого размера, т.е. количество его вершин nzk достигло значения

    nz=S(t-1,S(t,dzk-1))3, где dzk - это высота zk в Τ.
    Напомним, что этот предполагаемый размер так же является числом детей zk в Τ (в частном случае dzk=1, предполагаемый размер равен S(t,1)3=8). Подграф Czk конденсируется и становится новой вершиной подграфа Cz(k-1). Эта вершина связана с Cz(k-1) через звено цепи (и возможно другие ребра) между Cz(k-1) и подграфом Czk (сейчас сконденсированным). В результате Cz(k-1) приобретает новую вершину и одно или несколько новых ребер, и концом активного пути становится z(k-1). Незначительная деталь: из-за вышеупомянутых сокращений активного пути, принимающих участие в формировании активного пути, чтобы избежать Cz без вершин, мы должны добавить новую запись z(k-1) и zk в случае, если их высоты отличаются более чем на единицу (высоты подразумеваются здесь по отношению к полному, а не частично построенному дереву Τ). Способ поддержания условия один за O(k) очевиден, способ же поддержания условия два не столь ясен, поэтому мы его поясним. Вот что мы делаем: кучи H(k) и H(k-1,k) уничтожаются. Все поврежденные ребра отбрасываются (заметьте, что эти ребра не являвшиеся плохими, становятся таковыми). Все оставшиеся ребра мы разделяем на подмножества - кластеры, состоящие из ребер имеющих общие концы, ведущие за пределы цепи. Для каждого кластера по очереди выбираем ребро (r,s) наименьшего веса и отбрасываем остальные (если есть). После добавляем выбранное ребро в кучу, выбранную соответственно условию два. Конкретно, если (r,s) взято из H(k) и вершина s является общей c ребром из H(k-1,k), или если оно взято из H(k-1,k), тогда по условию два s уже является общим с каким-то H(i,k-1), следовательно, оно может быть добавлено в H(k-1). В противном случае, (r,s) взято из H(k) и по условию два вершина s является общей с ребром из некоторой кучи H(i,k), при i<k–1. Ребро (r,s) должно быть вставлено в H(i,k). Т.е. получаем, что для каждого i<k-1, H(i,k) сливается с H(i,k-1) и становится кучей H(i,k-1).

    Пара замечаний:

    • Добавляя (r,s) в H(i,k), мы вставляем в кучу, по крайней мере, второе ребро, заканчивающееся в s.
    • Как только H(i,k) объединяется с H(i,k-1), у нас может быть ребро (r,s), добавленное в H(k-1) вместо H(i,k), но все же удовлетворяющее условию два. Мы не делаем этого из-за риска получить ребра, скачущие между H(*) на каждом сжатии, что было бы слишком дорого по времени.

  • Расширение:
    Делаем операцию findmin для всех куч и извлекаем граничное ребро (u,v) минимального текущего веса. Назовем его расширяющим ребром. Из всех минимальных звеньев с рабочим весом не более чем c(u,v) находим одно (a,b), инцидентное Ci, где индекс i минимален. Если такое ребро существует, то мы выполняем операцию слияние (fusion):

    Мы конденсируем целый отрезок цепи Cz(i+1) ∪ … ∪ Czk в вершину a (см. рисунок 2). Будет удобнее разделить этот процесс на два шага: конденсируем ребра с обоими концами в Cz(i+1) ∪ … ∪ Czk. Назовем получившуюся вершину b' и сконденсируем ребро или ребра, соединяющее a и b'. Далее мы обновляем все минимальные звенья, это легко можно сделать за время O(k2). Для обновления куч мы представим способ в явной форме. Мы расширяем уничтожение куч по сравнению со способом, описанным в сжатии, чтобы включить не только кучи H(k) и H(k-1,k), а все H(i+1) … H(k) и H(j,j'), для i<=j<j'. Мы выкидываем все поврежденные ребра из этих куч, так как с этого момента они становятся плохими. После чего перегруппировываем оставшиеся ребра по кластерам и для каждого кластера по очереди снова добавляем ребро (r,s) c наименьшим текущим весом в кучу, а все остальные отбрасываем. Как и раньше различаем два случая:

    1. Если ребро (r,s) находилось в какой-либо из куч H(j,j') или H(j'), в случае H(j') так же необходимо, чтобы имелось ребро из H(j,j') с вершиной s, где i<=j<j', тогда по условию два для него s также является общей вершиной с ребром (r',s) из некоторой кучи H(h,l), где h<i<=l. Как мы объясняли выше, ребро (r',s) перемещается в H(h,i) при слиянии куч, если оно еще не там, т.е. если l>i, то по условию два мы можем вставить (r,s) в H(i).
    2. Если же (r,s) находилось в H(j), где i<j, и s являлось концом ребра из какой-то H(h,j), где h<j, то мы вставляем ребро (r,s) в H(h,j).
    В конце концов, для каждого h и j, где h<i<j, мы сливаем H(h,j) в H(h,i). Заметим, что по условию один и по выбору вершины a, оно не может быть продвинуто вниз по цепи ниже u; подсказка: рассматриваем звено цепи, составляя цепь из того же Cz, что и (u,v). Следовательно, принадлежало ли u изначально последнему Cz в цепи или нет, она принадлежит ему сейчас. Не обращая внимания, имеет ли место слияние, мы расширяем цепь, превращая u в Сzk, состоящий из одной вершины, и расширяющее ребро (u,v) делаем звеном цепи, инцидентным ему. Конец активного пути сейчас - zk. Заметим, что это не тот же zk, что и раньше: без слияния, новое значение k - это старое плюс 1; со слиянием оно равно i+1. Старые граничные ребра, инцидентные v, перестают быть граничного типа: удаляем их из своих куч и находим среди них минимальное звено между v и каждым Cz1, …, Cz(k-1). Добавляем новые граничные ребра, инцидентные v, в соответствующие H(i,k); в случае кратных ребер, оставляем только с самым маленьким весом в каждой группе и отбрасываем остальные.
    Рис. 2
    Рис. 2. Все три подграфа справа от Czi сжимаются в b и потом в a.

Объяснив как работает сжатие и расширение, мы просмотрели построение Τ. Для каждой данной вершины, высоты, по крайней мере, 1, мы выполняем расширение и сопутствующие ему операции, пока это возможно (добавление в стек), останавливаясь только, когда условия размера для сжатия в вершине выполняются (удаление из стека). Т.к. нет условия для сжатия корня z1, то алгоритм остановится, только когда граничные ребра кончатся и расширение станет более невозможным.

Замечания:

  • Слияние - это не сжатие в Czi, т.к. ребро (a,b) так же конденсируется, а не становится ребром Czi; слияние, в отличии от сжатия, не увеличивает количества вершин в Czi. Слияние помогает преодолеть сложности, хотя оно неприятно для разработчика алгоритма, но благоприятно для времени выполнения. В действительности, можно представить весь алгоритм, как уменьшение до одного гигантского слияния, и вычисление MST за линейное время.
  • При формировании кластеров происходит отбрасывание ребер раз и навсегда. Из-за этого никакие ребра из H(0,j) никогда не отбрасываются, множество неотброшенных ребер покрывает G0, и алгоритм никогда не остановится, если какие-либо вершины останутся неисследованными. Напомним, что мы предполагаем, что граф G0 связан. Если это не так, мы просто выполняем построение Τ для каждой его компоненты связанности.
  • В третьем шаге B содержит вершины из G0, но на следующем шаге ребра из B имеют концы в Cz. Эта двусмысленность упрощает сохранение плохих ребер и легко разрешается в данных обстоятельствах.

Шаг 4: Рекурсивная обработка подграфов Τ

Построив дерево Τ, мы рассматриваем каждую запись z: напомним, что Cz не включает отброшенных ребер. Пусть Cz\B означает подграф графа Cz, полученный удалением всех плохих ребер (не все плохие ребра могут быть отброшены). Мы применяем алгоритм рекурсивно к Cz\B после возвращения весов всех ребер к их изначальным значениям и уменьшения параметра t на единицу. Единственный эффект, который имеет изменение этого параметра – это перемена целевых размеров для вершин дерева Τ, которое будет построено. Получившееся множество F – множество ребер, объединяющих вершины в Cz. И вновь мы понимаем это двусмысленно, что позволяет нам использовать их как ребра G0 на пятом шаге. Отличие между вершинами Cz и детьми z должно быть очевидно, его бы не было в отсутствии слияний. Рассмотрим первое слияние в вершину a графа Cz. Перед ним вершина a соответствовала u ребенку z, мы имеем в виду, что a - это сконденсированный граф Cu. Что происходит после слияния? С точки зрения рассмотрения a в четвертом шаге - ничего. Вершина a все еще относится к тому же Cu, и шаг 4 рекурсивно обрабатывает Cu\B. После мы обрабатываем часть Τ, относящуюся к части цепи Cz(i+1) ∪ … ∪ Czk саму по себе. Последующие слияния обрабатываются таким же образом.

Возвращаясь к частичному слиянию b' в a всех ребер, соединяющих a и b'. Мы включаем в F ребро (a,b'), только если оно не являлось плохим. В данном частном случае ребро (a,b') является минимальным покрывающим деревом для группы не плохих и не отброшенных ребер, соединяющих (a,b').

Шаг 5: Конечная рекурсия

На третьем шаге мы собираем все плохие ребра, которые появились в течение создания Τ и формируем граф B. Его мы добавляем к ребрам F, чтобы собрать FB подграф G0. Подчеркнем, что имеются в виду изначальные вершины графа G0, а не сконденсированные вершины, которые были получены в течение построения Τ. Теперь вывод msf(FB,t) рассматривается как множество ребер с концами в G, а не G0. Добавив к нему ребра, сконденсированные на втором шаге, мы получим минимальное покрывающее дерево графа G.

Литература

  1. B. Chazelle. A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity. — Journal of the ACM, 47 (2000), 1028-1047.
  2. R.E. Tarjan. Efficiency of a good but not linear set-union algorithm. — J. ACM, 22 (1975), 215-225.
  3. J. Nesetril. A few remarks on the history of MST-problem. — Archivum Mathematicum, Brno, 33 (1997), 15-22. Prelim. version in KAM Series, Charles University, Prague, No. 97-338 (1997).
  4. Рыбаков Глеб. Минимальные остовные деревья.
  5. B. Chazelle. The Soft Heap: An Approximate Priority Queue with Optimal Error Rate. — Journal of the ACM, 47 (2000), 1012-1027.
  6. Ф. Харари. Теория графов, 2-е изд. — М.: Едиториал УРРС, 2003. — 296 с.

Визуализаторы

  1. Мандриков E., Курбацкий Е. Минимальное остовное дерево (2006).

Авторы: Мандриков Е., Курбацкий Е.


Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий