Алгоритм Каргерса - Википедия - Kargers algorithm

График и два его разреза. Пунктирная линия красного цвета - разрез с тремя пересекающимися краями. Пунктирная линия зеленого цвета - это минимальный разрез этого графа, пересекающий только два ребра.

В Информатика и теория графов, Алгоритм Каргера это рандомизированный алгоритм вычислить минимальный разрез связанного график. Это было изобретено Дэвид Каргер и впервые опубликовано в 1993 году.^[1]

Идея алгоритма основана на концепции сжатие края ${ Displaystyle (и, v)}$ в неориентированном графе ${ Displaystyle G = (V, E)}$. Неформально говоря, сжатие ребра объединяет узлы ${ displaystyle u}$ и ${ displaystyle v}$ в один, уменьшив общее количество узлов графа на единицу. Все остальные кромки, соединяющиеся либо ${ displaystyle u}$ или же ${ displaystyle v}$ "присоединяются" к объединенному узлу, эффективно создавая мультиграф. Базовый алгоритм Каргера итеративно сжимает случайно выбранные ребра, пока не останется только два узла; эти узлы представляют собой резать в исходном графике. Повторяя этот базовый алгоритм достаточное количество раз, можно с высокой вероятностью найти минимальный разрез.

Проблема глобального минимума сокращения

А резать ${ displaystyle (S, T)}$ в неориентированном графе ${ Displaystyle G = (V, E)}$ является разбиением вершин ${ displaystyle V}$ на два непустых непересекающихся множества ${ Displaystyle S чашка T = V}$. В Cutset реза состоит из краев ${ Displaystyle {, уф в Е двоеточие и в S, v в Т , }}$ между двумя частями. размер (или же масса) разреза в невзвешенном графе - это мощность разреза, то есть количество ребер между двумя частями,

${ Displaystyle вес (S, T) = | {, uv in E двоеточие и в S, v in T , } | ,.}$

Есть ${ Displaystyle 2 ^ {| V |}}$ способы выбора для каждой вершины, принадлежит ли она ${ displaystyle S}$ или чтобы ${ displaystyle T}$, но два из этих вариантов делают ${ displaystyle S}$ или же ${ displaystyle T}$ пустые и не вызывают порезов. Среди оставшихся вариантов - поменять ролями ${ displaystyle S}$ и ${ displaystyle T}$ не меняет разрез, поэтому каждый разрез учитывается дважды; поэтому есть ${ displaystyle 2 ^ {| V | -1} -1}$ отчетливые разрезы. минимальная проблема среза - найти среди этих разрезов разрез наименьшего размера.

Для взвешенных графов с положительным весом ребер ${ Displaystyle с двоеточием E rightarrow mathbf {R} ^ {+}}$ вес разреза - это сумма весов ребер между вершинами в каждой части

${ Displaystyle вес (S, T) = сумма _ {uv in E двоеточие и in S, v in T} w (uv) ,,}$

что согласуется с невзвешенным определением для ${ displaystyle w = 1}$.

Разрез иногда называют «глобальным разрезом», чтобы отличать его от «${ displaystyle s}$-${ displaystyle t}$ вырезать »для данной пары вершин, что имеет дополнительное требование, чтобы ${ displaystyle s in S}$ и ${ displaystyle t in T}$. Каждый глобальный разрез - это ${ displaystyle s}$-${ displaystyle t}$ вырезать для некоторых ${ displaystyle s, t in V}$. Таким образом, задача минимального разреза может быть решена за полиномиальное время путем перебора всех вариантов ${ displaystyle s, t in V}$ и решая полученный минимум ${ displaystyle s}$-${ displaystyle t}$ решить проблему с помощью теорема о максимальном потоке и минимальном отсечении и алгоритм полиномиального времени для максимальный поток, такой как алгоритм push-relabel, хотя такой подход не оптимален. Лучшие детерминированные алгоритмы для задачи глобального минимума разреза включают Алгоритм Стоера – Вагнера, который имеет время работы ${ Displaystyle О (мн + п ^ {2} журнал п)}$.^[2]

Алгоритм сокращения

Фундаментальная операция алгоритма Каргера представляет собой форму сжатие края. Результат стягивания края ${ Displaystyle е = {и, v }}$ новый узел ${ displaystyle uv}$. Каждый край ${ Displaystyle {ш, и }}$ или же ${ Displaystyle {ш, в }}$ за ${ Displaystyle ш notin {и, v }}$ к концам сжатого ребра заменяется ребром ${ Displaystyle {ш, уф }}$ к новому узлу. Наконец, суженные узлы ${ displaystyle u}$ и ${ displaystyle v}$ со всеми их инцидентными ребрами удаляются. В частности, полученный граф не содержит петель. Результат сужения края ${ displaystyle e}$ обозначается ${ displaystyle G / e}$.

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

Успешный запуск алгоритма Каргера на 10-вершинном графе. Минимальный крой имеет размер 3.

   процедура договор(${ Displaystyle G = (V, E)}$):   пока ${ displaystyle | V |> 2}$       выберите ${ displaystyle e  in E}$ равномерно случайно ${ Displaystyle G  leftarrow G / e}$   возвращаться единственный врезанный ${ displaystyle G}$

Когда график представлен с использованием списки смежности или матрица смежности, операция сжатия одной кромки может быть реализована с линейным числом обновлений в структуре данных для общего времени выполнения ${ Displaystyle O (| V | ^ {2})}$. В качестве альтернативы процедуру можно рассматривать как выполнение Алгоритм Краскала для строительства минимальное остовное дерево в графе, у ребер которого есть веса ${ Displaystyle ш (е_ {я}) = пи (я)}$ согласно случайной перестановке ${ displaystyle pi}$. Удаление самого тяжелого края этого дерева приводит к двум компонентам, описывающим разрез. Таким образом, процедура сокращения может быть реализована как Алгоритм Краскала во время ${ Displaystyle O (| E | log | E |)}$.

Случайный выбор ребер в алгоритме Каргера соответствует выполнению алгоритма Крускала на графе со случайными рангами ребер, пока не останется только два компонента.

Наиболее известные реализации используют ${ Displaystyle O (| E |)}$ время и пространство, или ${ Displaystyle O (| E | log | E |)}$ время и ${ Displaystyle O (| V |)}$ пространство соответственно.^[1]

Вероятность успеха алгоритма сокращения

В графике ${ Displaystyle G = (V, E)}$ с ${ Displaystyle п = | В |}$ вершин, алгоритм сжатия возвращает минимальный разрез с полиномиально малой вероятностью ${ Displaystyle { binom {п} {2}} ^ {- 1}}$. Каждый граф имеет ${ displaystyle 2 ^ {n-1} -1}$ порезы^[3] среди которых самое большее ${ Displaystyle { tbinom {п} {2}}}$ можно минимальные порезы. Следовательно, вероятность успеха для этого алгоритма намного лучше, чем вероятность случайного выбора разреза, которая не превышает ${ Displaystyle { tbinom {п} {2}} / (2 ^ {п-1} -1)}$

Например, график цикла на ${ displaystyle n}$ вершин ровно ${ Displaystyle { binom {п} {2}}}$ минимальные разрезы, задаваемые каждым выбором из 2 кромок. Процедура сжатия находит каждый из них с равной вероятностью.

Чтобы установить оценку вероятности успеха в целом, пусть ${ displaystyle C}$ обозначают края определенного минимального размера разреза ${ displaystyle k}$. Алгоритм сжатия возвращает ${ displaystyle C}$ если ни одно из случайных ребер не принадлежит сечению ${ displaystyle C}$. В частности, сокращение первого края позволяет избежать ${ displaystyle C}$, что происходит с вероятностью ${ displaystyle 1-k / | E |}$. Минимальная степень ${ displaystyle G}$ по крайней мере ${ displaystyle k}$ (иначе вершина минимальной степени вызовет меньший разрез), поэтому ${ displaystyle | E | geq nk / 2}$. Таким образом, вероятность того, что алгоритм сжатия выберет ребро из ${ displaystyle C}$ является

${ displaystyle { frac {k} {| E |}} leq { frac {k} {nk / 2}} = { frac {2} {n}}.}$

Вероятность ${ displaystyle p_ {n}}$ что алгоритм сжатия на ${ displaystyle n}$-вершинный граф избегает ${ displaystyle C}$ удовлетворяет повторение ${ displaystyle p_ {n} geq left (1 - { frac {2} {n}} right) p_ {n-1}}$, с ${ displaystyle p_ {2} = 1}$, который может быть расширен как

${ displaystyle p_ {n} geq prod _ {i = 0} ^ {n-3} { Bigl (} 1 - { frac {2} {ni}} { Bigr)} = prod _ { i = 0} ^ {n-3} { frac {ni-2} {ni}} = { frac {n-2} {n}} cdot { frac {n-3} {n-1} } cdot { frac {n-4} {n-2}} cdots { frac {3} {5}} cdot { frac {2} {4}} cdot { frac {1} { 3}} = { binom {n} {2}} ^ {- 1} ,.}$

Повторение алгоритма сокращения

10 повторов схватки. 5-й повтор находит минимальный разрез размера 3.

Повторяя алгоритм сжатия ${ displaystyle T = { binom {n} {2}} ln n}$ раз с независимым случайным выбором и возвращением наименьшего разреза, вероятность не найти минимальный разрез составляет

${ displaystyle left [1 - { binom {n} {2}} ^ {- 1} right] ^ {T} leq { frac {1} {e ^ { ln n}}} = { frac {1} {n}} ,.}$

Общее время работы для ${ displaystyle T}$ повторений для графика с ${ displaystyle n}$ вершины и ${ displaystyle m}$ края ${ Displaystyle О (Тм) = О (п ^ {2} м журнал п)}$.

Алгоритм Каргера – Стейна

Расширение алгоритма Каргера за счет Дэвид Каргер и Клиффорд Штайн достигает улучшения на порядок.^[4]

Основная идея состоит в том, чтобы выполнять процедуру сжатия, пока график не достигнет ${ displaystyle t}$ вершины.

   процедура договор(${ Displaystyle G = (V, E)}$, ${ displaystyle t}$):   пока ${ displaystyle | V |> t}$       выберите ${ displaystyle e  in E}$ равномерно случайно ${ Displaystyle G  leftarrow G / e}$   возвращаться ${ displaystyle G}$

Вероятность ${ displaystyle p_ {n, t}}$ что эта процедура сокращения позволяет избежать определенного разреза ${ displaystyle C}$ в ${ displaystyle n}$-вершинный граф

${ displaystyle p_ {n, t} geq prod _ {i = 0} ^ {nt-1} { Bigl (} 1 - { frac {2} {ni}} { Bigr)} = { binom {t} {2}} { Bigg /} { binom {n} {2}} ,.}$

Это выражение приблизительно ${ Displaystyle т ^ {2} / п ^ {2}}$ и становится меньше чем ${ displaystyle { frac {1} {2}}}$ вокруг ${ Displaystyle т = п / { sqrt {2}}}$. В частности, вероятность того, что ребро из ${ displaystyle C}$ сокращается, растет к концу. Это мотивирует идею перехода на более медленный алгоритм после определенного количества шагов сокращения.

   процедура fastmincut (${ Displaystyle G = (V, E)}$):   если ${ displaystyle | V |  leq 6}$:       возвращаться mincut (${ displaystyle V}$)   еще:       ${ Displaystyle т  leftarrow  lceil 1+ | V | / { sqrt {2}}  rceil}$       ${ displaystyle G_ {1}  leftarrow}$ договор(${ displaystyle G}$, ${ displaystyle t}$)       ${ displaystyle G_ {2}  leftarrow}$ договор(${ displaystyle G}$, ${ displaystyle t}$)       возвращаться мин {fastmincut (${ displaystyle G_ {1}}$), fastmincut (${ displaystyle G_ {2}}$)}

Анализ

Вероятность ${ Displaystyle P (п)}$ алгоритм находит конкретное сечение ${ displaystyle C}$ задается рекуррентным соотношением

${ displaystyle P (n) = 1- left (1 - { frac {1} {2}} P left ({ Bigl lceil} 1 + { frac {n} { sqrt {2}}) } { Bigr rceil} right) right) ^ {2}}$

с раствором ${ Displaystyle P (n) = Omega left ({ frac {1} { log n}} right)}$. Время работы fastmincut удовлетворяет

${ displaystyle T (n) = 2T left ({ Bigl lceil} 1 + { frac {n} { sqrt {2}}} { Bigr rceil} right) + O (n ^ {2 })}$

с раствором ${ Displaystyle Т (п) = О (п ^ {2} журнал п)}$. Для достижения вероятности ошибки ${ Displaystyle О (1 / п)}$, алгоритм можно повторить ${ Displaystyle О ( журнал п / P (п))}$ раз, для общего времени работы ${ displaystyle T (n) cdot { frac { log n} {P (n)}} = O (n ^ {2} log ^ {3} n)}$. Это улучшение на порядок по сравнению с исходным алгоритмом Каргера.

Граница улучшения

Чтобы определить минимальный разрез, нужно коснуться каждого ребра в графе хотя бы один раз, т.е. ${ Displaystyle Theta (п ^ {2})}$ время в плотный граф. Алгоритм min-cut Каргера – Стейна занимает время выполнения ${ Displaystyle О (п ^ {2} ln ^ {O (1)} п)}$, что очень близко к этому.

Рекомендации