Точки сочленения: какой узел нельзя выключать

Коротко

Точка сочленения - вершина, удаление которой (вместе с её рёбрами) увеличивает число компонент. Если мост - это «единственный канал», то точка сочленения - «единственный узел», через который идёт связь: выключил сервер, и часть сети осталась сама по себе. Ищется тем же обходом и той же величиной low, но критерий чуть другой - с НЕстрогим неравенством: вершина v (не корень обхода) является точкой сочленения, если у неё есть ребёнок to с low[to] >= tin[v]. У корня своё правило: он точка сочленения тогда и только тогда, когда у него в дереве обхода два или больше детей. Разница > против >= - ровно разница между «оторвать ребро» и «выдернуть вершину».

Если ты помнишь критерий точки сочленения, отдельное правило для корня и понимаешь, почему у моста строгое неравенство, а тут нестрогое, листай до «Теперь сам».

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

Возьми граф из прошлого урока: два треугольника, соединённые ребром c-d. Ребро - мост, это мы выяснили. Прежде чем читать дальше, ответь: будут ли точками сочленения сами вершины c и d? А теперь посмотри на простейший случай - граф из двух вершин и одного ребра a-b. Ребро a-b - мост. Являются ли a и b точками сочленения?

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

Инфраструктура города. Мост через реку - критичное РЕБРО. А развязка, через которую идут все дороги с севера на юг, - критичный УЗЕЛ: перекрой её, и город разделится, хотя ни одна отдельная дорога не была единственной. Ещё пример: в компании есть сотрудник, через которого идёт вся связь между двумя отделами. Уволится - отделы перестанут общаться, хотя каналов связи у каждого много.

Механизм: тот же low, другой критерий

timer = 0
tin = [-1] * V
low = [0] * V
cut = set()

def dfs(v, parent):
    global timer
    tin[v] = low[v] = timer; timer += 1
    children = 0
    for to in adj[v]:
        if to == parent:
            continue
        if tin[to] != -1:
            low[v] = min(low[v], tin[to])       # обратное ребро
        else:
            dfs(to, v)
            low[v] = min(low[v], low[to])
            if low[to] >= tin[v] and parent != -1:
                cut.add(v)                      # НЕстрогое неравенство
            children += 1
    if parent == -1 and children > 1:
        cut.add(v)                              # правило корня

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

Два отличия от поиска мостов, и оба содержательные.

Неравенство нестрогое. Для моста требовалось low[to] > tin[v]: из поддерева нельзя дотянуться даже до самой v. Для точки сочленения достаточно low[to] >= tin[v]: из поддерева нельзя дотянуться ВЫШЕ v. Разница - случай low[to] == tin[v], когда обратное ребро ведёт ровно в v: ребро тогда не мост (есть обходной путь через это обратное ребро), но сама v всё равно критична - убери её, и поддерево отвалится вместе с обходным путём.

У корня своё правило. Условие про low для корня бессмысленно: над ним ничего нет, и у любого его ребёнка low >= tin[корня] = 0 выполняется всегда. Корень критичен ровно тогда, когда его поддеревья не связаны между собой иначе, чем через него, - а это и означает «детей в дереве обхода два или больше».

Правило

Вершина v, не являющаяся корнем обхода, - точка сочленения ⇔ у неё есть ребёнок to в дереве обхода с low[to] >= tin[v]. Корень обхода - точка сочленения ⇔ у него два или больше детей в дереве обхода. Всё находится за один обход, O(V + E). Строгое неравенство даёт мосты, нестрогое - точки сочленения; концы моста не обязаны быть точками сочленения (висячая вершина степени 1 - не точка сочленения).

Разбор: два треугольника и мост между ними

Тот же граф: a-b, b-c, c-a, c-d, d-e, e-f, f-d. Времена из прошлого урока: tin = {a:0, b:1, c:2, d:3, e:4, f:5}, low = {a:0, b:0, c:0, d:3, e:3, f:3}.

Корень a: сколько у него детей в дереве обхода? Один - b (ребро a-c оказалось обратным: в неориентированном графе любое не-древесное ребро называют обратным, с какого конца на него ни смотри). Значит a не точка сочленения: убери её, и b-c-d-e-f останутся связными через b-c.
b: ребёнок c, low[c] = 0 >= tin[b] = 1? Нет, 0 < 1 → не точка сочленения.
c: ребёнок d, low[d] = 3 >= tin[c] = 2? Да → c - точка сочленения. Логично: убери c, и второй треугольник отвалится.
d: ребёнок e, low[e] = 3 >= tin[d] = 3? Да → d - точка сочленения. Обрати внимание: здесь сработало именно РАВЕНСТВО. Убери d, и первый треугольник с e, f разъединится.
e: ребёнок f, low[f] = 3 >= tin[e] = 4? Нет → не точка сочленения (есть обратное ребро f-d в обход).
f: детей нет → не точка сочленения.

Ответ: точки сочленения - c и d, то есть оба конца моста. А теперь обещанный контрпример: граф из двух вершин a-b. Ребро - мост, но a - корень с одним ребёнком (не точка сочленения), а b - лист без детей (тоже нет). Вывод: у моста концы критичны, только если из них есть куда отваливаться - висячая вершина точкой сочленения не бывает.

Разбор: почему у корня считают детей

Возьми звезду: центр s соединён с x, y, z, между собой они не соединены. Запустим обход из s. Он войдёт в x, вернётся (у x других рёбер нет), войдёт в y, вернётся, войдёт в z. Получается три РАЗНЫХ ребёнка в дереве обхода - и это значит, что между x, y, z нет никаких других путей: будь они связаны, обход добрался бы до второго из x и ребёнком корня он бы не стал.

Теперь запустим обход из x того же графа: tin[x]=0, tin[s]=1, tin[y]=2, tin[z]=3. Корень x имеет одного ребёнка - s, значит корнем-точкой сочленения он не является. А s - не корень, и у её детей y и z обратных рёбер нет вовсе, поэтому low[y]=2 и low[z]=3. Проверяем общее правило: low[y]=2 >= tin[s]=1 - выполняется (с запасом, а не по равенству) → s точка сочленения. Ответ совпал: критична именно s, и от выбора старта он не зависит - что и требуется, ведь точка сочленения это свойство ГРАФА, а не обхода.

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

Первое: применить к корню общее правило про low - корень будет объявлен точкой сочленения почти всегда, потому что low[to] >= 0 выполняется у любого ребёнка. Второе: считать детей корня как «число соседей» - нет, нужны дети в ДЕРЕВЕ ОБХОДА: у корня может быть пять соседей и один ребёнок, если остальные достигаются через него же. Третье: перепутать неравенства и искать точки сочленения строгим > - тогда потеряются вершины, в которые обратное ребро заходит ровно в них. Четвёртое: думать, что концы моста всегда критичны, - висячая вершина не критична, отваливаться от неё нечему. Пятое: забыть про кратные рёбра и пропуск родителя - для точек сочленения пропуск по вершине безопаснее, чем для мостов (второе параллельное ребро не меняет ответ), но если код общий, держи номера рёбер. Шестое: забыть внешний цикл по вершинам - в несвязном графе КАЖДАЯ компонента имеет свой корень, и правило «два ребёнка» применяется к каждому из них отдельно.

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

Точки сочленения отвечают на вопрос «какой узел нельзя выключать», и это ежедневная задача в эксплуатации: какой маршрутизатор, какой сервис, какой дата-центр критичен. Сети планируют так, чтобы точек сочленения не было вовсе - это называется двусвязностью и об этом следующий урок. В анализе социальных сетей точки сочленения - «брокеры», связывающие сообщества: их удаление разваливает структуру, и их же исследуют как самых влиятельных. В анализе программ похожие рассуждения ведут к доминаторам в графе потока управления (каждый путь к точке B проходит через A) - это уже другой алгоритм, но вопрос того же сорта. Практический вывод для проектирования: если узел получился точкой сочленения, его либо дублируют, либо добавляют обходной путь; первый шаг - уметь их найти, и это один обход.

Теперь сам

Граф: 1-2, 2-3, 3-4, 4-2, 4-5. Обход стартует из вершины 1. Найди все точки сочленения и все мосты, сравни списки.

Ответ. Обход: вход 1 (tin=0), ребро 1-2 → вход 2 (tin=1), ребро 2-3 → вход 3 (tin=2), ребро 3-4 → вход 4 (tin=3), ребро 4-2: двойка посещена и не родитель → обратное, low[4] = min(3, tin[2]=1) = 1; ребро 4-5 → вход 5 (tin=4, low=4), возврат: low[4] = min(1, 4) = 1, проверка ребра 4-5: low[5]=4 > tin[4]=3 → мост, и для точки сочленения low[5]=4 >= tin[4]=3 → вершина 4 - точка сочленения. Возврат в 3: low[3] = min(2, low[4]=1) = 1; ребро 3-4: low[4]=1 > tin[3]=2? нет → не мост; 1 >= 2? нет → тройка не точка сочленения. Возврат в 2: low[2] = min(1, low[3]=1) = 1; ребро 2-3: low[3]=1 > tin[2]=1? нет → не мост; 1 >= 1? да → вершина 2 - точка сочленения. Возврат в 1: корень, детей один (только двойка) → не точка сочленения; ребро 1-2: low[2]=1 > tin[1]=0 → мост. Итог: мосты 1-2 и 4-5; точки сочленения 2 и 4. Сравни списки: вершина 1 - конец моста, но не точка сочленения (она висячая), и вершина 5 тоже. А вершина 2 стала критичной по РАВЕНСТВУ low[3] = tin[2]: цикл 2-3-4-2 цепляется за неё снизу, и убрав двойку, мы оторвём его от единицы.

Главное

Точка сочленения - вершина, удаление которой увеличивает число компонент. Находится тем же обходом и той же величиной low, что и мосты, но критерий с НЕстрогим неравенством: не-корень v - точка сочленения ⇔ у него есть ребёнок to с low[to] >= tin[v], то есть из поддерева to нельзя дотянуться ВЫШЕ v. Разница со строгим неравенством - случай low[to] == tin[v]: обратное ребро заходит ровно в v, поэтому ребро не мост (обходной путь есть), а вершина всё равно критична. Корень обхода разбирают отдельно: он точка сочленения ⇔ у него ДВА или больше детей в дереве обхода (общее правило для корня выполнялось бы всегда). Концы моста не обязаны быть точками сочленения: висячая вершина степени 1 не критична - от неё нечему отваливаться. Всё за один обход, O(V + E). Практический смысл - «какой узел нельзя выключать»: критичные маршрутизаторы, сервисы, брокеры в социальных сетях; проектируют обычно так, чтобы таких вершин не было вовсе.