Мосты: какое ребро разваливает сеть

Если ты знаешь определение low, умеешь считать его по трём случаям и помнишь критерий моста low[to] > tin[v], листай до «Теперь сам».

Как думаешь, как проверить ребро на «единственность»

Сеть из десятков тысяч узлов, надо найти каналы, обрыв которых разделит сеть. Прежде чем читать дальше, прикинь цену очевидного способа: убрать ребро, запустить обход, посмотреть, все ли достижимы, вернуть ребро на место - и так для каждого из E рёбер. Для V = 10⁴ и E = 10⁵ это 10⁵ × (10⁴ + 10⁵) операций. Сколько это по времени - и есть ли способ обойтись одним обходом?

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

Река с островами и мостами. Чтобы понять, какой мост критичен, не надо взрывать каждый по очереди и смотреть, что отвалилось. Достаточно пройти по островам и спросить у каждого: «есть ли отсюда обходной путь на тот берег, минуя этот мост?» Если из всей части суши за мостом обратной дороги нет ни одной - мост критичен. Именно этот вопрос и считает величина low.

Механизм: величина low и критерий

tin[v]  - время входа в вершину (из прошлой главы)
low[v]  - минимальное tin, куда можно попасть из поддерева v,
          спустившись по древесным рёбрам и не больше одного раза
          поднявшись по ОБРАТНОМУ ребру

low[v] = min( tin[v],
              tin[u]  по всем ОБРАТНЫМ рёбрам v → u,
              low[c]  по всем детям c в дереве обхода )

timer = 0
tin = [-1] * V
low = [0] * V
bridges = []

def dfs(v, parent_edge):
    global timer
    tin[v] = low[v] = timer; timer += 1
    for (to, edge_id) in adj[v]:            # храним НОМЕР ребра, не только соседа
        if edge_id == parent_edge:
            continue                        # то самое ребро, по которому пришли
        if tin[to] != -1:                   # уже посещена - обратное ребро
            low[v] = min(low[v], tin[to])
        else:
            dfs(to, edge_id)
            low[v] = min(low[v], low[to])
            if low[to] > tin[v]:
                bridges.append(edge_id)     # МОСТ

for v in range(V):                          # граф может быть несвязным:
    if tin[v] == -1:                        # запускаем обход из каждой непосещённой вершины
        dfs(v, -1)

Почему пропускать надо по номеру РЕБРА, а не по номеру вершины: если между v и to есть два параллельных ребра, второе из них - честное обратное ребро, и благодаря ему ни одно из двух не является мостом. Код, пропускающий «все рёбра в родителя», этого не заметит и объявит мост там, где его нет.

Правило

low[v] - минимальное время входа, достижимое из поддерева v при спуске по древесным рёбрам и не более чем одном подъёме по обратному ребру; считается как минимум из tin[v], времён входа по обратным рёбрам и low детей. Древесное ребро v → to - МОСТ тогда и только тогда, когда low[to] > tin[v], то есть из поддерева to не дотянуться ни до v, ни выше. Все мосты находятся за один обход, O(V + E). Ребро, по которому пришли, пропускают по НОМЕРУ РЕБРА: при кратных рёбрах пропуск по вершине даёт ложные мосты.

Разбор: считаем low на графе

Граф: a-b, b-c, c-a (треугольник), c-d, d-e, e-f, f-d (второй треугольник). Стартуем из a, соседи в алфавитном порядке.

вход a: tin=0, low=0
  ребро a-b (b белая) → вход b: tin=1, low=1
    ребро b-a: пришли не по нему, a посещена → ОБРАТНОЕ: low[b] = min(1, tin[a]=0) = 0
    ребро b-c (c белая) → вход c: tin=2, low=2
      ребро c-a: обратное → low[c] = min(2, 0) = 0
      ребро c-d (d белая) → вход d: tin=3, low=3
        ребро d-e → вход e: tin=4, low=4
          ребро e-f → вход f: tin=5, low=5
            ребро f-d: обратное → low[f] = min(5, tin[d]=3) = 3
          возврат в e: low[e] = min(4, low[f]=3) = 3
        возврат в d: low[d] = min(3, low[e]=3) = 3
        проверка ребра d-e: low[e]=3 > tin[d]=3? нет → не мост
        проверка ребра e-f: low[f]=3 > tin[e]=4? нет → не мост
        проверка ребра c-d: low[d]=3 > tin[c]=2 → МОСТ
      возврат в b: low[b] = min(0, low[c]=0) = 0
      проверка ребра b-c: low[c]=0 > tin[b]=1? нет → не мост
  возврат в a: ребро a-c: c уже посещена и пришли мы не по нему → обратное,
                low[a] = min(0, tin[c]=2) = 0 (в дереве обхода у a остаётся ОДИН ребёнок - b)
                проверка ребра a-b: low[b]=0 > tin[a]=0? нет → не мост

Единственный мост - c-d, как и видно на схеме. Разберись, почему критерий сработал именно так: low[d] = 3 означает, что самое «высокое», куда можно дотянуться из всего поддерева d, - это сам d (время 3); наверх, к c (время 2) или выше, обратных рёбер нет. А low[c] = 0 означает, что из поддерева c есть путь аж до a - значит ребро b-c обходится, и мостом не является.

Разбор: почему критерий верен

Докажем в обе стороны. Пусть v → to - древесное ребро.

Если low[to] > tin[v], ребро - мост. Величина low[to] - это самое раннее время входа, достижимое из поддерева to. Условие low[to] > tin[v] означает, что из этого поддерева нельзя дотянуться обратным ребром ни до v, ни до чего-либо, что вошло раньше v. А любой путь из поддерева to наружу обязан пройти либо по ребру v → to (то есть через удаляемое ребро), либо по какому-то обратному ребру вверх - которого нет. Значит, убрав ребро, мы отрезаем всё поддерево to от остального графа.

Если low[to] <= tin[v], ребро не мост. Существует вершина x в поддереве to с обратным ребром в вершину y, где tin[y] <= tin[v], то есть y - сам v или его предок. Тогда после удаления v → to путь всё равно есть: из v спускаемся... точнее, из поддерева to идём в x, по обратному ребру в y, а из y по дереву обратно в v. Связность сохранилась.

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

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

Первое: пропускать родителя по номеру вершины - на кратных рёбрах появляются ложные мосты. Второе: обновлять low[v] значением low[to] для ОБРАТНОГО ребра (то есть писать low[v] = min(low[v], low[to]) вместо tin[to]). На мостах в неориентированном графе ответ чаще всего не меняется, но смысл величины теряется: по обратному ребру разрешён ОДИН подъём, а чужое low означало бы второй. В алгоритме Тарьяна для компонент сильной связности, где та же конструкция работает на ориентированном графе, такая подмена уже даёт неверный ответ - поэтому привыкать надо сразу к tin. Третье: писать критерий как low[to] >= tin[v] - это критерий ТОЧКИ СОЧЛЕНЕНИЯ, а не моста; со строгим неравенством ищут мосты. Четвёртое: забыть, что мост может быть и в несвязном графе - обход надо запускать из каждой непосещённой вершины. Пятое: применять это к ориентированному графу - там понятия другие (сильная связность, компоненты), и критерий не работает.

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

Мосты - это точки отказа. В сетевой инфраструктуре поиск мостов показывает каналы, обрыв которых разделит сеть на части: такие места резервируют в первую очередь. В распределённых системах то же про связи между дата-центрами. В анализе дорожных сетей мосты - участки, ремонт которых отрежет район. Кроме прикладного смысла, low - это рабочий инструмент, который встретится ещё не раз: на той же величине стоят поиск точек сочленения (следующий урок), выделение компонент рёберной двусвязности, алгоритм Тарьяна для компонент сильной связности, а в олимпиадных задачах - целое семейство построений на «дереве блоков». Общий приём стоит запомнить: обход в глубину может считать по дороге не только времена, но и АГРЕГАТ по поддереву, а агрегат, посчитанный при возврате из рекурсии, отвечает на вопросы про структуру целиком.

Теперь сам

Граф: 1-2, 2-3, 3-1, 3-4, 4-5. Посчитай tin и low при обходе из вершины 1 (соседи по возрастанию) и найди все мосты.