Минимальный разрез стягиванием: алгоритм Каргера

Если ты выполнишь стягивание руками, выведешь оценку 2/(n(n − 1)) и посчитаешь, сколько прогонов нужно для заданной надёжности, - листай до «Теперь сам».

Как думаешь, насколько часто угадывает один прогон

Граф - два плотных клубка по четыре вершины, соединённые двумя рёбрами. Минимальный разрез очевиден: перерезать эти два ребра. Алгоритм ничего не знает о клубках: он просто склеивает концы случайного ребра, пока не останутся две вершины.

Попробуй угадать до чтения: в какой доле прогонов он остановится именно на разрезе из двух рёбер - почти всегда, в половине случаев, в каждом шестом? Ответ - в каждом шестом, 49 раз из 300. Чаще всего он выдаёт разрез из трёх рёбер. И всё-таки из этого получается надёжный алгоритм.

На что это похоже

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

Если на карте есть узкий перешеек - две области, связанные с остальной страной всего парой границ, - то выбрать наугад именно границу перешейка трудно: границ в стране много, а на перешейке их две. Скорее всего, сначала сольются области внутри каждой половины, и перешеек доживёт до конца. Малочисленность разреза и есть то, что его защищает.

Механизм: стягивание и вероятность уцелеть

Граф считаем связным. Разрез графа - разбиение вершин на две непустые части; его размер - число рёбер между частями. Минимальный разрез - разрез наименьшего размера. В отличие от разреза в сети из раздела про потоки, здесь не заданы исток и сток: ищется самое слабое место графа вообще.

Стягивание ребра (u, v): вершины u и v заменяются одной. Все рёбра, шедшие к u или v, идут теперь к ней; рёбра между u и v исчезают. Если к обеим вершинам вело по ребру из одной и той же третьей вершины, получаются два параллельных ребра, и оба сохраняются.

пока вершин больше двух:
    выбрать ребро равновероятно среди всех оставшихся
    стянуть его
ответ: рёбра между двумя оставшимися вершинами

Каждая оставшаяся вершина - склеенное множество исходных, так что две последние вершины задают разрез исходного графа. Он может оказаться не минимальным.

Почему минимальный разрез имеет шанс. Зафиксируем один минимальный разрез C, его размер - k. Прогон выдаст именно C, если ни одно ребро C не было стянуто. Оценим первый шаг. Степень каждой вершины не меньше k: иначе рёбра этой вершины образовали бы разрез меньше минимального. Значит, рёбер в графе не меньше n · k / 2 - сумма степеней, делённая пополам. Случайное ребро попадает в C с вероятностью

k / (число рёбер) ≤ k / (n·k/2) = 2/n

После стягивания вершин n − 1, а минимальный разрез нового графа не меньше k (любой его разрез - это разрез исходного). Рассуждение повторяется с n − 1, n − 2 и так до трёх вершин. Вероятность уцелеть на всех шагах:

(1 − 2/n) · (1 − 2/(n−1)) · … · (1 − 2/3)
  = (n−2)/n · (n−3)/(n−1) · (n−4)/(n−2) · … · 2/4 · 1/3
  = 2 / (n · (n − 1))

Произведение сокращается: числитель каждой дроби встречается знаменателем через одну. Остаются 2 · 1 сверху и n · (n − 1) снизу.

Один прогон слаб, но прогоны независимы. Вероятность, что T прогонов все промахнулись мимо C, не больше (1 − 2/(n(n−1)))ᵀ. Поскольку 1 − x ≤ e⁻ˣ, при T = n(n − 1) · ln n это не больше e^(−2 ln n) = 1/n².

Правило

Алгоритм Каргера: стягивать равновероятно выбранное ребро, сохраняя параллельные рёбра, пока не останутся две вершины. Один прогон выдаёт данный минимальный разрез с вероятностью не меньше 2 / (n(n − 1)). Наименьший разрез из n(n − 1) · ln n независимых прогонов минимален с вероятностью не меньше 1 − 1/n². Следствие: у графа не больше n(n − 1) / 2 разных минимальных разрезов - прогон выдаёт каждый из них с вероятностью не меньше 2 / (n(n − 1)), эти исходы несовместны, и сумма их вероятностей не больше единицы.

Разбор: два клубка и триста прогонов

Стягивание реализовано без перестройки графа. Рёбра перемешиваются, и по ним идут в случайном порядке: ребро, концы которого уже в одной склеенной вершине, пропускается (оно бы исчезло при стягивании), остальные объединяют свои части. Части хранит система непересекающихся множеств из раздела про кучи. Выбрать следующее по случайному порядку ребро, которое ещё не исчезло, - то же самое, что выбрать равновероятно среди оставшихся.

import random

def koren(roditel, v):
    while roditel[v] != v:
        roditel[v] = roditel[roditel[v]]
        v = roditel[v]
    return v

def styanut(n, ryobra):
    roditel = list(range(n))
    poryadok = list(range(len(ryobra)))
    random.shuffle(poryadok)
    chastej = n
    for nomer in poryadok:
        if chastej == 2:
            break
        a = koren(roditel, ryobra[nomer][0])
        b = koren(roditel, ryobra[nomer][1])
        if a != b:
            roditel[a] = b
            chastej = chastej - 1
    razrez = 0
    for rebro in ryobra:
        if koren(roditel, rebro[0]) != koren(roditel, rebro[1]):
            razrez = razrez + 1
    return razrez

ryobra = []
for dolya in [0, 4]:
    for i in range(4):
        for j in range(i + 1, 4):
            ryobra.append([dolya + i, dolya + j])
ryobra.append([0, 4])
ryobra.append([3, 7])

random.seed(36)
opytov = 300
luchshij = len(ryobra)
udach = 0
po_razmeru = {}
for opyt in range(opytov):
    r = styanut(8, ryobra)
    luchshij = min(luchshij, r)
    po_razmeru[r] = po_razmeru.get(r, 0) + 1
    if r == 2:
        udach = udach + 1
print(len(ryobra), luchshij, round(udach / opytov, 3), round(2 / (8 * 7), 3))
for r in sorted(po_razmeru):
    print(r, po_razmeru[r])

14 2 0.163 0.036
2 49
3 141
4 87
5 13
6 8
7 1
8 1

В графе 14 рёбер: по шесть в каждом клубке и два между ними. Наименьший разрез за триста прогонов - 2, как и должно быть. Но посмотри на распределение: разрез из двух рёбер найден в 49 прогонах, а чаще всего, 141 раз, прогон выдавал разрез из трёх рёбер. Это отделение одной вершины степени три: у четырёх вершин графа, не связанных с чужим клубком, ровно по три ребра.

Одиночный прогон ошибается в пяти случаях из шести. Работает только минимум по многим прогонам.

Разбор: сколько прогонов нужно и чего гарантия не обещает

Оценка для восьми вершин: 2 / (8 · 7) = 0,036. В опыте вышло 0,163 - в четыре с половиной раза лучше. Оценка рассчитана на самый неудобный граф; на этом графе рёбер больше, чем n · k / 2 = 8, и попасть случайным ребром в разрез труднее.

Число прогонов по формуле: n(n − 1) · ln n = 56 · ln 8 ≈ 116, и тогда вероятность промаха не больше 1/64. По измеренной частоте промах после 116 прогонов - (1 − 0,163)¹¹⁶, около одной миллиардной.

Цена. Один прогон в программе выше - перемешивание и проход по рёбрам, порядка m действий. Всего n² · ln n прогонов дают m · n² · ln n. Для графа на тысячу вершин это миллионы прогонов - дороже, чем n − 1 вычислений максимального потока. Улучшение Каргера и Штайна опирается на то, что опасны только поздние стягивания: пока вершин много, вероятность задеть разрез мала. Граф стягивают до n / √2 вершин один раз, а дальше делают две независимые попытки и в каждой поступают так же. Общее время падает до O(n² · log³ n).

Граница - гарантия не превращается в точность. Найденный разрез всегда настоящий: его рёбра и правда разделяют граф. Но убедиться, что меньшего нет, можно только другим алгоритмом. Ошибка односторонняя в необычном смысле: ответ никогда не меньше истинного, а больше бывает.

Что ломается без этого

Случайная пара вершин вместо случайного ребра. Если склеивать две случайные вершины, а не концы случайного ребра, оценка 2/n пропадает: она получена из того, что рёбер разреза мало среди всех рёбер.

Удаление параллельных рёбер. После стягивания между двумя вершинами бывает несколько рёбер, и каждое должно участвовать в жребии. Если оставить одно, плотные места графа перестают притягивать выбор, и вероятность задеть разрез растёт.

Один прогон. В разборе он верен в одном случае из шести. Алгоритм - это серия прогонов с минимумом.

Взвешенный граф как невзвешенный. Если у рёбер есть веса, ребро нужно выбирать с вероятностью, пропорциональной весу: ребро веса 5 - это пять параллельных рёбер.

Зачем это в работе

Надёжность сетей. Минимальный разрез - наименьшее число каналов, отказ которых разделяет сеть на две части. Следствие про n(n − 1) / 2 минимальных разрезов даёт больше, чем одно число: слабых мест не может быть слишком много, и при достаточном числе повторных прогонов все они с высокой вероятностью встретятся среди найденных разрезов.

Разбиение на группы. Разрезать граф связей по самому слабому месту - исходная идея многих методов кластеризации и сегментации изображений, где вершины - пиксели, а вес ребра - сходство соседей.

История вопроса показывает, зачем нужны такие алгоритмы даже там, где есть точные. Стягивание придумано в 1993 году и оказалось заметно проще потоковых методов. Из него вырос алгоритм, находящий минимальный разрез за время, почти линейное от числа рёбер; а в 2024 году показано, что почти линейное время достижимо и без случайности. Рандомизированное решение часто приходит первым и показывает, что задача проще, чем казалось.

Теперь сам

1. Граф на 10 вершинах. Какова нижняя оценка вероятности, что один прогон выдаст данный минимальный разрез?
2. Граф - кольцо из пяти вершин. Чему равен размер минимального разреза и сколько у графа разных минимальных разрезов?
3. Наименьшая степень вершины в графе равна 3. Может ли минимальный разрез иметь размер 4?
4. Сколько прогонов нужно по формуле для графа на 100 вершинах, чтобы вероятность промаха была не больше 1/n²? ln 100 ≈ 4,605.
5. После нескольких стягиваний между вершинами x и y оказалось три параллельных ребра, а всего в графе осталось 12 рёбер. С какой вероятностью следующим будет стянуто ребро между x и y?