В информатике и теории графов , алгоритм Karger в это рандомизированное алгоритм для вычисления минимального разреза связного графа . Он был изобретен Дэвидом Каргером и впервые опубликован в 1993 году [1].
Идея алгоритма основана на концепции стягивания ребра. в неориентированном графе . Неформально говоря, сжатие ребра объединяет узлы а также в один, уменьшив общее количество узлов графа на единицу. Все остальные кромки, соединяющиеся либо или же "прикрепляются" к объединенному узлу, эффективно создавая мультиграф . Базовый алгоритм Каргера итеративно сжимает случайно выбранные ребра, пока не останется только два узла; эти узлы представляют собой разрез в исходном графе. Повторяя этот базовый алгоритм достаточное количество раз, можно с большой вероятностью найти минимальный разрез.
Глобальная проблема минимального разреза
покрой в неориентированном графе является разбиением вершин на два непустых непересекающихся множества . Cutset разреза состоит из ребермежду двумя частями. Размер (или вес ) разрез в невзвешенной графе мощность на cutset, то есть, число ребер между двумя частями,
Есть способы выбора для каждой вершины, принадлежит ли она или чтобы , но два из этих вариантов делают или же пустые и не вызывают порезов. Среди оставшихся вариантов, поменять ролями а также не меняет разрез, поэтому каждый разрез учитывается дважды; поэтому естьотчетливые порезы. Задача минимального разреза - найти разрез наименьшего размера среди этих разрезов.
Для взвешенных графов с положительным весом ребер вес разреза - это сумма весов ребер между вершинами в каждой части
что согласуется с невзвешенным определением для .
Разрез иногда называют «глобальным разрезом», чтобы отличить его от «- вырезать »для данной пары вершин, что имеет дополнительное требование, чтобы а также . Каждый глобальный разрез - это- вырезать для некоторых . Таким образом, задача минимального разреза может быть решена за полиномиальное время путем перебора всех вариантов и решая полученный минимум -вырезать задачу с использованием теоремы о максимальном потоке и минимальном разрезе и алгоритма с полиномиальным временем для максимального потока , такого как алгоритм push-relabel , хотя этот подход не является оптимальным. Лучшие детерминированные алгоритмы для решения задачи глобального минимума разреза включают алгоритм Стоера – Вагнера , время работы которого составляет. [2]
Алгоритм сокращения
Основная операция алгоритма Каргера - это форма сжатия ребер . Результат стягивания края новый узел . Каждый край или же для до концов сжатого ребра заменяется ребром к новому узлу. Наконец, суженные узлы а также со всеми их инцидентными ребрами удаляются. В частности, полученный граф не содержит петель. Результат сужения края обозначается .
Алгоритм сжатия многократно сжимает случайные ребра в графе, пока не останется только два узла, после чего останется только один разрез.
процедурный договор (): пока выберите равномерно наугад вернуть единственный врезанный
Когда граф представлен с использованием списков смежности или матрицы смежности , операция сокращения одного края может быть реализована с линейным числом обновлений в структуре данных для общего времени выполнения. В качестве альтернативы, процедуру можно рассматривать как выполнение алгоритма Крускала для построения минимального остовного дерева в графе, у ребер которого есть веса. согласно случайной перестановке . Удаление самого тяжелого края этого дерева приводит к двум компонентам, описывающим разрез. Таким образом, процедура сокращения может быть реализована подобно алгоритму Крускала во времени..
Наиболее известные реализации используют время и пространство, или время и пространство соответственно. [1]
Вероятность успеха алгоритма сокращения
В графике с участием вершин, алгоритм сжатия возвращает минимальный разрез с полиномиально малой вероятностью . Каждый граф имеетразрезы, [3] среди которых не болееможно минимальные порезы. Следовательно, вероятность успеха для этого алгоритма намного лучше, чем вероятность случайного выбора разреза, которая не превышает.
Например, график цикла на вершин ровно минимальные разрезы, задаваемые каждым выбором из 2 кромок. Процедура сжатия находит каждый из них с равной вероятностью.
Чтобы дополнительно установить нижнюю границу вероятности успеха, пусть обозначают края определенного минимального размера разреза . Алгоритм сжатия возвращает если ни одно из случайных ребер не принадлежит сечению . В частности, сжатие первого края позволяет избежать, что происходит с вероятностью . Минимальная степень по по крайней мере (в противном случае вершина минимальной степени индуцировала бы меньший разрез, где одно из двух разбиений содержит только вершину минимальной степени), поэтому . Таким образом, вероятность того, что алгоритм сжатия выберет ребро из является
Вероятность что алгоритм сжатия на -вершинный граф избегает удовлетворяет повторение , с участием , который может быть расширен как
Повторение алгоритма сокращения
Повторяя алгоритм сжатия раз с независимым случайным выбором и возвращением наименьшего разреза, вероятность не найти минимальный разрез составляет
Общее время работы для повторений для графика с вершины и края .
Алгоритм Каргера – Стейна
Расширение алгоритма Каргера, разработанное Дэвидом Каргером и Клиффордом Штайном, дает улучшение на порядок. [4]
Основная идея - выполнять процедуру сжатия до тех пор, пока график не достигнет вершины.
процедурный договор (, ): пока выберите равномерно наугад возвращаться
Вероятность что эта процедура сокращения позволяет избежать определенного разреза в -вершинный граф
Это выражение примерно и становится меньше чем вокруг . В частности, вероятность того, что ребро изсокращается, растет к концу. Это мотивирует идею перехода на более медленный алгоритм после определенного количества шагов сокращения.
процедура fastmincut (): если : return mincut ( ) else : договор( , ) договор( , ) return min {fastmincut ( ), fastmincut ( )}
Анализ
Вероятность алгоритм находит конкретное сечение задается рекуррентным соотношением
с раствором . Время работы fastmincut удовлетворяет
с раствором . Для достижения вероятности ошибки, алгоритм можно повторить раз, для общего времени работы . Это улучшение на порядок по сравнению с исходным алгоритмом Каргера.
Граница улучшения
Чтобы определить min-разрез, нужно коснуться каждого ребра в графе хотя бы один раз, что является время в плотном графе . Алгоритм min-cut Каргера – Стейна занимает время выполнения, что очень близко к этому.
Рекомендации
- ^ a b Каргер, Дэвид (1993). «Глобальные минимальные сокращения в RNC и другие разветвления простого алгоритма минимальных сокращений» . Proc. 4-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам .
- ^ Stoer, M .; Вагнер, Ф. (1997). «Простой алгоритм min-cut». Журнал ACM . 44 (4): 585. DOI : 10,1145 / 263867,263872 .
- ^ Патриньяни, Маурицио; Пиццония, Маурицио (2001), «Сложность проблемы сопоставления и сокращения», в Brandstädt, Andreas ; Ле, Ван Банг (ред.), Теоретико-графические концепции в компьютерных науках: 27-й международный семинар, WG 2001, Больтенхаген, Германия, 14-16 июня 2001 г., Proceedings , Lecture Notes in Computer Science, 2204 , Berlin: Springer, pp. . 284-295, DOI : 10.1007 / 3-540-45477-2_26 , МР 1905640.
- ^ Каргер, Дэвид Р .; Стейн, Клиффорд (1996). «Новый подход к проблеме минимального сокращения» (PDF) . Журнал ACM . 43 (4): 601. DOI : 10,1145 / 234533,234534 .