Алгоритм MST с ожидаемым линейным временем

Алгоритм MST с ожидаемым линейным временем — это рандомизированный алгоритм вычисления минимального остовного леса без взвешенного графа изолированных вершин . Его разработали Дэвид Каргер , Филип Кляйн и Роберт Тарджан . ^[1] Алгоритм основан на методах алгоритма Борувки, а также на алгоритме проверки минимального остовного дерева за линейное время. ^[2]^[3] Он сочетает в себе парадигмы проектирования алгоритмов «разделяй и властвуй» , жадных алгоритмов и рандомизированных алгоритмов для достижения ожидаемой линейной производительности .

Детерминированные алгоритмы, которые находят минимальное связующее дерево, включают алгоритм Прима , алгоритм Краскала , алгоритм обратного удаления и алгоритм Борувки .

Обзор

Ключевой особенностью алгоритма является шаг случайной выборки, который делит граф на два подграфа путем случайного выбора ребер для включения в каждый подграф. Алгоритм рекурсивно находит минимальный остовный лес первой подзадачи и использует решение в сочетании с алгоритмом проверки линейного времени, чтобы отбросить ребра в графе, которые не могут находиться в минимальном остовном дереве. Процедура, взятая из алгоритма Борувки, также используется для уменьшения размера графа при каждой рекурсии .

Черничная степь

Каждая итерация алгоритма основана на адаптации алгоритма Борувки, называемой шагом Борувки :

 Input: A graph G with no isolated vertices
   1 For each vertex v, select the lightest edge incident on v 
   2 Create a contracted graph G' by replacing each component of G connected by the edges selected in step 1 with a single vertex
   3 Remove all isolated vertices, self-loops, and non-minimal repetitive edges from G' 
 Output: The edges selected in step 1 and the contracted graph G'

Шаг Борувки эквивалентен внутреннему циклу алгоритма Борувки, который выполняется за время O ( m ), где — количество ребер в G. m При этом, поскольку каждое ребро можно выбрать не более двух раз (по одному разу по каждой инцидентной вершине), максимальное количество несвязных компонент после шага 1 равно половине числа вершин. Таким образом, шаг Борувки уменьшает количество вершин в графе как минимум в два раза и удаляет как минимум n /2 ребер, где n — количество вершин в G .

Пример исполнения Черничной степи

Изображение	Описание
	Самое светлое ребро, попадающее в каждую вершину, выделено зеленым цветом.
	Граф сжимается, и каждый компонент, соединенный ребрами, выбранными на шаге 1, заменяется одной вершиной. Это создаст два суперузла. Все ребра исходного графа остаются.
	Ребра, образующие петли на суперузлах, удаляются.
	Неминимальные избыточные ребра между суперузлами удаляются.
	Результатом одного шага Борувки на примере графа является граф с двумя суперузлами, соединенными одним ребром.

F-тяжелые и F-легкие края

На каждой итерации алгоритм удаляет ребра с определенными свойствами, которые исключают их из минимального остовного дерева . Они называются F-тяжелыми ребрами и определяются следующим образом. Пусть F лес на графе H. — F-тяжелое ребро — это ребро e, соединяющее вершины u , v, которого строго больше веса самого тяжелого ребра на пути от u до v в F. вес (Если путь не существует в F, он считается имеющим бесконечный вес). Любое ребро, которое не является F-тяжелым, является F-легким . Если F является подграфом G , то любое F-тяжелое ребро в G не может находиться в минимальном остовном дереве G по свойству цикла . Учитывая лес, F-тяжелые ребра могут быть вычислены за линейное время с использованием алгоритма проверки минимального остовного дерева. ^[2]^[3]

Алгоритм

Входные данные: граф G без изолированных вершин.

Если G пуст, вернуть пустой лес
Создайте сжатый граф G', выполнив два последовательных шага Борувки на G.
Создайте подграф H, выбрав каждое ребро в G' с вероятностью 1/2. Рекурсивно примените алгоритм к H, чтобы получить минимальный остовный лес F .
Удалите все F-тяжелые ребра из G' (где F — лес из шага 3), используя алгоритм проверки остовного дерева с минимальным линейным временем. ^[2]^[3]
Рекурсивно примените алгоритм к G', чтобы получить минимальный остовный лес.

Выходные данные: минимальный остовный лес G' и сжатые ребра ступенек Борувки.

Корректность

Корректность доказывается индукцией по числу вершин графа. Базовый случай тривиально верен. Пусть T* — минимальное остовное дерево G . Каждое ребро, выбранное на шаге Борувки, находится в T* по свойству разреза , и ни одно из ребер, удаленных для формирования сжатого графа, не находится в T* по свойству разреза (для избыточных ребер) и свойству цикла (для самоциклов). Остальные ребра T*, не выбранные на шаге 2, образуют минимальное остовное дерево сжатого графа по свойству разреза (пусть каждый разрез является суперузлом). Каждое удаленное F-тяжелое ребро не входит в минимальное остовное дерево по свойству цикла . Наконец, F' — минимальное остовное дерево сжатого графа по индуктивному предположению. Таким образом, F' и ребра, сжатые ребрами ступенек Борувки, образуют минимальное остовное дерево.

Производительность

Ожидаемая производительность является результатом этапа случайной выборки. Эффективность шага случайной выборки описывается следующей леммой, которая ограничивает количество F-легких ребер в G, тем самым ограничивая размер второй подзадачи.

Лемма о случайной выборке

Лемма . Пусть H — подграф G, образованный включением каждого ребра G независимо с вероятностью p, пусть F — минимальный остовный лес H. и Ожидаемое количество F -легких ребер в G не превышает n/p где n — количество вершин в G. ,

рассмотрим ребра G по мере их добавления к H. Чтобы доказать лемму , Количество F-легких ребер в G не зависит от порядка выбора ребер H , поскольку минимальный остовный лес H одинаков для всех порядков выбора. Для доказательства рассмотрим выбор ребер для H , беря ребра G по одному в порядке веса ребра от самого легкого до самого тяжелого. Пусть e будет текущим рассматриваемым краем. Если концы e находятся в двух несвязных компонентах H, то e — самое легкое ребро, соединяющее эти компоненты, и если оно добавлено к H, оно окажется в F по свойству разреза . Это также означает, что e является F-легким независимо от того, добавлено ли оно к H или нет , поскольку впоследствии рассматриваются только более тяжелые ребра. Если обе конечные точки e находятся в одном и том же компоненте H , то он (и всегда будет) F-тяжелым из-за свойства цикла . Ребро e затем добавляется к H с вероятностью p .

Максимальное количество F-легких ребер, добавленных к H, равно n -1, поскольку любое минимальное остовное дерево H имеет n -1 ребер. После того, как n добавлено к H -1 F-легких ребер , ни одно из последующих рассматриваемых ребер не станет F-легким по свойству цикла . Таким образом, количество F-легких ребер в G ограничено количеством F-легких ребер, рассматриваемых для H до того, как n -1 F-легких ребер фактически будут добавлены к H . Поскольку любое ребро F-light добавляется с вероятностью p, это эквивалентно подбрасыванию монеты с вероятностью p выпадения орла до тех пор, пока n не появится равно количеству F-лёгких ребер в G. -1 орла. Общее количество подбрасываний монеты Распределение количества подбрасываний монеты задается обратным биномиальным распределением с параметрами n -1 и p . Для этих параметров ожидаемое значение этого распределения равно ( n -1)/ p .

Ожидаемый анализ

Если игнорировать работу, проделанную в рекурсивных подзадачах, общий объем работы, выполняемой за один вызов алгоритма, линейно зависит от количества ребер во входном графе. Шаг 1 занимает постоянное время. Шаги Борувки могут выполняться за время, линейное по количеству ребер, как указано в разделе «Шаг Борувки» . Шаг 3 перебирает ребра и подбрасывает одну монету для каждого, чтобы число ребер было линейным. Шаг 4 может быть выполнен за линейное время с использованием модифицированного алгоритма проверки минимального остовного дерева за линейное время. ^[2]^[3] Поскольку работа, выполняемая за одну итерацию алгоритма, линейна по количеству ребер, работа, выполняемая за один полный запуск алгоритма (включая все рекурсивные вызовы), ограничена постоянным коэффициентом, умноженным на общее количество ребер в исходной задаче, и все рекурсивные подзадачи.

Каждый вызов алгоритма создает не более двух подзадач, поэтому набор подзадач образует двоичное дерево . Каждый шаг Борувки уменьшает количество вершин как минимум в два раза, поэтому после двух шагов Борувки количество вершин уменьшается в четыре раза. Таким образом, если исходный граф имеет n вершин и m ребер, то на глубине d дерева каждая подзадача находится на графе не более n /4 ^д вершины. Также дерево имеет не более log ₄ n уровней.

Чтобы рассуждать о дереве рекурсии, пусть левая дочерняя проблема будет подзадачой в рекурсивном вызове на шаге 3, а правая дочерняя проблема будет подзадачой в рекурсивном вызове на шаге 5. Подсчитайте общее количество ребер в исходной задаче и всех подзадачах. путем подсчета количества ребер в каждом левом пути дерева. Левый путь начинается либо с правого дочернего элемента, либо с корня и включает в себя все узлы, достижимые по пути левых дочерних элементов. Левые пути двоичного дерева показаны синим кружком на диаграмме справа.

Каждое ребро в левой дочерней задаче выбирается из ребер родительской задачи (за вычетом ребер, сжатых на этапах Борувки ) с вероятностью 1/2. Если родительская задача имеет x ребер, то ожидаемое количество ребер в левой дочерней задаче не превышает x /2. Если x заменить случайной величиной X , то в силу линейности ожидания ожидаемое количество ребер в левой дочерней задаче Y определяется выражением $E[Y]\leq E[X]/2$ . Таким образом, если ожидаемое количество ребер в задаче наверху левого пути равно k , то сумма ожидаемого числа ребер в каждой подзадаче на левом пути не превышает $\sum _{d=0}^{\infty }{\frac {k}{2^{d}}}=2k$ (см. Геометрический ряд ). Корень имеет m ребер, поэтому ожидаемое количество ребер равно 2 m плюс удвоенное ожидаемое количество ребер в каждой правой подзадаче.

Ожидаемое количество ребер в каждой правой подзадаче равно количеству F-легких ребер в родительской задаче, где F — минимальное остовное дерево левой подзадачи. Число F-лёгких ребер меньше или равно удвоенному числу вершин в подзадаче по лемме о выборке . Число вершин в подзадаче на глубине d равно n /4. ^д поэтому общее количество вершин во всех правых подзадачах определяется выражением $\sum _{d=1}^{\infty }{\frac {2^{d-1}n}{4^{d}}}=n/2$ . Таким образом, ожидаемое количество ребер в исходной задаче и всех подзадачах не превышает 2 m + n . Поскольку n не более 2 m для графа без изолированных вершин, алгоритм работает за ожидаемое время O ( m ).

Анализ худшего случая

Время выполнения в худшем случае эквивалентно времени выполнения алгоритма Борувки . Это происходит, если все ребра добавляются либо к левой, либо к правой подзадаче при каждом вызове. В этом случае алгоритм идентичен алгоритму Борувки , который работает за O (min{ n ², m log n }) на графе с n вершинами и m ребрами.

Ссылки

^ Каргер, Дэвид Р.; Кляйн, Филип Н.; Тарьян, Роберт Э. (1995). «Рандомизированный алгоритм линейного времени для поиска минимальных остовных деревьев». Журнал АКМ . 42 (2): 321. CiteSeerX 10.1.1.39.9012 . дои : 10.1145/201019.201022 . S2CID 832583 .
^ Jump up to: ^а ^б ^с ^д Диксон, Брэндон; Раух, Моника; Тарьян, Роберт Э. (1992). «Проверка и анализ чувствительности минимальных остовных деревьев в линейном времени». SIAM Journal по вычислительной технике . 21 (6): 1184. CiteSeerX 10.1.1.49.25 . дои : 10.1137/0221070 .
^ Jump up to: ^а ^б ^с ^д Кинг, Валери (1995). Упрощенный алгоритм проверки минимального связующего дерева . Материалы 4-го международного семинара по алгоритмам и структурам данных. Лондон, Великобритания, Великобритания: Springer-Verlag. стр. 440–448.

[1] Каргер, Дэвид Р.; Кляйн, Филип Н.; Тарьян, Роберт Э. (1995). «Рандомизированный алгоритм линейного времени для поиска минимальных остовных деревьев». Журнал АКМ . 42 (2): 321. CiteSeerX 10.1.1.39.9012 . дои : 10.1145/201019.201022 . S2CID 832583 .

[MST-V1-2] Jump up to: ^а ^б ^с ^д Диксон, Брэндон; Раух, Моника; Тарьян, Роберт Э. (1992). «Проверка и анализ чувствительности минимальных остовных деревьев в линейном времени». SIAM Journal по вычислительной технике . 21 (6): 1184. CiteSeerX 10.1.1.49.25 . дои : 10.1137/0221070 .

[MST-V2-3] Jump up to: ^а ^б ^с ^д Кинг, Валери (1995). Упрощенный алгоритм проверки минимального связующего дерева . Материалы 4-го международного семинара по алгоритмам и структурам данных. Лондон, Великобритания, Великобритания: Springer-Verlag. стр. 440–448.

[1]

[2]

[3]