Дерево Гомори-Ху: минимальные разрезы для всех пар за n − 1 поток

Если ты знаешь, что хранит дерево Гомори-Ху, как его строят n − 1 потоком и как по нему ответить на запрос о разрезе, листай до «Теперь сам».

Как думаешь, сколько разных разрезов у всех пар

Сеть каналов связи между 24 площадками. Для каждой пары площадок нужно знать, какую суммарную пропускную способность надо выбить, чтобы их разъединить. Это 276 пар - 276 вычислений максимального потока.

Прежде чем читать дальше, попробуй угадать: если разрез {a, b} | {c, d} минимальный между a и c, то для пары b и d, стоящих по разные стороны того же разреза, он тоже годится как разрез. Может быть, много пар делят одни и те же разрезы? Сколько тогда различных ответов среди 276?

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

Генеалогическое древо слабых мест. Вместо таблицы «насколько крепко связаны каждые двое» в семье рисуют дерево, где у каждой ветки подписано, насколько она прочна. Чтобы узнать, как прочна связь двух родственников, находишь их на дереве и смотришь на самую слабую ветку между ними. Таблица на сотни ячеек свелась к дереву на два десятка подписей.

Механизм: дерево разрезов и построение Гасфилда

СВОЙСТВО
мин. разрез(u, v) = наименьший вес ребра на пути u … v в дереве
и более того: удаление этого ребра делит вершины ровно так,
как этот минимальный разрез

ПОСТРОЕНИЕ (вариант Гасфилда, без сжатия вершин)
otec[i] = 0 для всех i
для i = 1 .. n−1:
    t = otec[i]
    найти мин. разрез между i и t - величина c, сторона S ∋ i
    для j != i, j != 0:
        если j ∈ S и otec[j] == t: otec[j] = i
    если t != 0 и otec[t] ∈ S:
        otec[i], otec[t] = otec[t], i
        вес[i], вес[t] = вес[t], c
    иначе: вес[i] = c

Почему достаточно n−1 представителей. Можно выбрать согласованную систему минимальных разрезов, которая укладывается в дерево: каждое ребро задаёт один разрез, рёбер n−1. Любая величина ответа для пары равна весу одного из этих рёбер, поэтому различных величин не больше n−1. Это не ограничивает число всех оптимальных разделений. В цикле из четырёх единичных рёбер их шесть: четыре изолируют одну вершину, ещё два разделяют цикл на пары соседей. Все имеют ёмкость 2, то есть значение ответа всего одно.

Почему пересадка otec[j] = i. Вершины, оказавшиеся на стороне i в разрезе между i и otec[i], дальше «висят» на i. Переподвешивать иногда нужно уже обработанных потомков тоже: их известный вес при этом сохраняется. Если старый родитель вершины t оказался на стороне i, меняем местами i и t в дереве, перенося старый вес и новый разрез. Без этой перестройки недостаточно проверить только величины ответов: разбиение, полученное удалением ребра, тоже должно иметь указанную ёмкость.

Объясним сохранение известного веса при переподвешивании обработанной вершины j. До шага j и i - дети одного родителя t. Удаление ребра j–t отделяет поддерево j ёмкости α. Вершина i в него не входит. После подвешивания j под i это же поддерево остаётся по одну сторону нового ребра j–i, поэтому ёмкость его разреза не изменилась и равна α.

Почему α остаётся минимумом для новой пары? Новый i–t-разрез S содержит j, поэтому его ёмкость β не меньше минимальной j–t-ёмкости α. Любой разрез между j и i отделяет t от одной из этих вершин, значит стоит не меньше α или β, а потому не меньше α. Старое поддерево j даёт разрез ровно α, что завершает обоснование. Использован инвариант: для уже обработанных рёбер разделение дерева реализует сохранённую минимальную ёмкость. Для ещё необработанной вершины вес определяется позднее собственным вызовом потока.

Наименьший вес рёбер дерева - минимальная ёмкость разреза всей сети: меньше разреза у сети нет ни между какими двумя вершинами.

Правило

Дерево Гомори-Ху хранит минимальные разрезы всех пар неориентированной сети: разрез между u и v равен наименьшему весу на пути между ними в дереве. Его строят n − 1 максимальным потоком: для каждой вершины i - разрез с текущим родителем, затем переподвешивание вершин и, когда необходимо, обмен положения i и её родителя с переносом весов. При единичных ёмкостях минимум веса в дереве равен рёберной связности.

Разбор: четыре площадки

каналы: a–b 3,  b–c 2,  a–c 1,  c–d 4         порядок вершин: a b c d

i = b, родитель a:  мин. разрез a | b = 4 ({a} против остальных: 3 + 1)
    сторона b: {b c d}  → c и d (родитель a) переподвешиваем к b
i = c, родитель b:  мин. разрез c | b = 3 ({c d} против {a b}: 2 + 1)
    сторона c: {c d}    → d переподвешиваем к c
i = d, родитель c:  мин. разрез d | c = 4

дерево:  a —4— b —3— c —4— d

запрос a … d: путь a–b–c–d, наименьшее 3
проверка: разрез {c d} | {a b} = b–c 2 + a–c 1 = 3  ✓

Три потока ответили на все шесть пар. Самое слабое место всей сети - ребро дерева весом 3: разделить сеть дешевле, чем отрезав {c, d}, нельзя.

Разбор: 24 площадки и проверка всех пар

Программа строит дерево Гомори-Ху для случайной сети и затем проверяет его ответ для каждой из 276 пар отдельным вычислением потока.

import random
from collections import deque

rng = random.Random(20)
n = 24
w = [[0] * n for _ in range(n)]       # неориентированная сеть каналов
for _ in range(70):
    u, v = rng.randrange(n), rng.randrange(n)
    if u != v:
        c = rng.randint(1, 9)
        w[u][v] += c
        w[v][u] += c
potokov = 0


def razrez(s, t):                     # мин. разрез: величина и сторона s
    global potokov
    potokov += 1
    cap = [row[:] for row in w]
    znach = 0
    while True:
        otec, och = {s: None}, deque([s])
        while och and t not in otec:
            u = och.popleft()
            for v in range(n):
                if cap[u][v] > 0 and v not in otec:
                    otec[v] = u
                    och.append(v)
        if t not in otec:
            return znach, set(otec)   # достижимые из s - его сторона
        put, v = [], t
        while otec[v] is not None:
            put.append((otec[v], v))
            v = otec[v]
        d = min(cap[a][b] for a, b in put)
        for a, b in put:
            cap[a][b] -= d
            cap[b][a] += d
        znach += d


otec, ves = [0] * n, [0] * n          # дерево Гомори-Ху по Гасфилду
for i in range(1, n):
    t = otec[i]
    cut, storona = razrez(i, t)
    for j in range(1, n):
        if j != i and j in storona and otec[j] == t:
            otec[j] = i
    if t != 0 and otec[t] in storona:
        otec[i], otec[t] = otec[t], i
        ves[i], ves[t] = ves[t], cut
    else:
        ves[i] = cut


def po_derevu(u, v):                  # минимум рёбер дерева на пути u–v
    sos = {x: [] for x in range(n)}
    for i in range(1, n):
        sos[i].append((otec[i], ves[i]))
        sos[otec[i]].append((i, ves[i]))
    luchshee, och = {u: float("inf")}, deque([u])
    while och:
        x = och.popleft()
        for y, c in sos[x]:
            if y not in luchshee:
                luchshee[y] = min(luchshee[x], c)
                och.append(y)
    return luchshee[v]


print("потоков на дерево:", potokov)
potokov = 0
for u in range(n):
    for v in range(u + 1, n):
        assert po_derevu(u, v) == razrez(u, v)[0]
print("потоков на проверку всех пар:", potokov, "- все совпали")
for edge in range(1, n):
    side, stack = set(), [edge]
    while stack:
        v = stack.pop()
        if v in side:
            continue
        side.add(v)
        for j in range(1, n):
            if j != edge:
                if j == v:
                    stack.append(otec[j])
                elif otec[j] == v:
                    stack.append(j)
    cap = sum(w[a][b] for a in side
              for b in range(n) if b not in side)
    assert cap == ves[edge]
print("разрезы по рёбрам дерева:", n - 1, "- все совпали")
print("минимальная ёмкость разреза сети:", min(ves[1:]))

потоков на дерево: 23
потоков на проверку всех пар: 276 - все совпали
разрезы по рёбрам дерева: 23 - все совпали
минимальная ёмкость разреза сети: 10

Проверять только величины недостаточно. Возьми треугольник с ёмкостями 0–1:1, 0–2:2, 1–2:3. Разрез между 1 и 0 стоит 3 и отделяет {1,2}; между 2 и 1 стоит 4 и отделяет {0,2}. Если только подвесить 2 под 1, получится дерево 0–1 веса 3 и 1–2 веса 4. Величины ответов верны, но удаление второго ребра изолирует {2}, чей настоящий разрез стоит 5.

Условие otec[t] ∈ S исправляет именно этот случай: после обмена дерево имеет рёбра 0–2 веса 3 и 2–1 веса 4. Теперь удаление рёбер даёт разрезы нужной ёмкости. Поэтому программа проверяет и все пары, и каждое разделение по ребру, суммируя ёмкости пересекающих его каналов исходной сети.

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

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

Первая ошибка - строить дерево для ОРИЕНТИРОВАННОЙ сети: там разрез u → v и v → u различаются, и симметричное дерево всех пар в общем случае не существует. Вторая - брать в качестве стороны разреза любые вершины, а не достижимые из i в остаточной сети: переподвешивание выйдет неверным, и дерево начнёт врать для части пар. Третья - путать дерево Гомори-Ху с остовным деревом сети: его рёбра не обязаны быть каналами, а веса - не ёмкости каналов, а величины разрезов (в примере ребро дерева a–b весит 4, хотя канал a–b - 3). Четвёртая - вычислять рёберную связность n·(n−1)/2 потоками: хватает n − 1 даже без дерева - зафиксировать одну вершину и найти разрезы до всех остальных.

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

Анализ надёжности сетей: насколько трудно разъединить два дата-центра, какая пара площадок связана хуже всех, какие каналы стоит дублировать. Кластеризация графов: рёбра дерева с малыми весами - места, где граф естественно распадается на группы. Задачи на «все пары» вообще: если ответ для пары зависит от минимального разреза, дерево Гомори-Ху сводит n² вычислений к n и даёт структуру, по которой отвечают на запрос обходом дерева.

Теперь сам

Дерево Гомори-Ху: p —5— q —2— r —7— s, r —6— x. Каков минимальный разрез между p и x? Между s и x? Чему равна минимальная ёмкость разреза всей сети?