WikiSort.ru - Не сортированное

Примеры

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

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

Алгоритм

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

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

Псевдокод

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