Алгоритм Каргера

Основной задачей является поиск узких мест в различных сетях. Примеры:

• Обнаружение сообществ в социальных сетях[2].
• Определение уязвимостей у потенциального противника с целью разрушения его транспортной сети.
• Сегментация изображений[3][4].

Операция стягивания ребра алгоритма Каргера.

Основной операцией алгоритма Каргера является одна из форм стягивания ребра. Для выполнения этой операции на произвольном ребре ${\displaystyle e=\{u,v\}}$ происходит объединение вершин графа ${\displaystyle u}$ и ${\displaystyle v}$ в одну ${\displaystyle uv}$. Если удаляется вершина ${\displaystyle v}$, то каждое ребро вида ${\displaystyle \{v,x\}}$ заменяется на ребро вида ${\displaystyle \{u,x\}}$. Петли удаляются, и после этой операции граф не содержит петель.

Алгоритм представляет собой равновероятный выбор случайного имеющегося ребра и объединение вершин согласно описанной операции. Результатом работы алгоритма является пара вершин, множество рёбер между которыми является разрезом графа. Этот разрез может быть не минимальным, но вероятность того, что этот разрез минимальный существенно больше, чем для случайно выбранного разреза.

Пример успешной работы алгоритма для графа с 10 вершинами. Минимальный разрез равен трём.

Алгоритм Каргера
повторить n − 2 раза
  выбрать случайно ребро e
  стянуть ребро e
результат число рёбер между двумя последними вершинами