Мосты и точки сочленения: поиск уязвимых мест графа

Коротко

Оба находятся одним обходом в глубину с помощью алгоритма Тарьяна.

Зачем это нужно

Представьте компьютерную сеть. Мост — это канал связи, обрыв которого разделит сеть на изолированные части. Точка сочленения — сервер, отказ которого приведёт к тому же.

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

• анализ надёжности сетей и инфраструктуры;
• поиск критических дорог в транспортной сети;
• выявление уязвимых узлов в социальных графах;
• декомпозиция графа на компоненты рёберной двусвязности.

    1 --- 2 --- 3
          |
          4 --- 5

мост: ребро 2-4  (и 4-5, и 1-2, и 2-3)
точка сочленения: вершины 2 и 4

Удалите ребро 2–4 — граф распадётся на {1,2,3} и {4,5}.

Наивный подход и почему он плох

Очевидное решение: удалить каждое ребро по очереди и проверить связность обходом. Это O(E) удалений по O(V + E) на проверку — итого O(E·(V+E)). На графе с 10⁵ рёбер безнадёжно.

Алгоритм Тарьяна находит всё за один обход.

Две ключевые величины

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

tin[v] — время входа. Порядковый номер, когда мы впервые попали в вершину. Просто счётчик.

low[v] — минимальное время входа, достижимое из поддерева вершины v, если разрешено пройти не более чем по одному обратному ребру.

low[v] = min(
    tin[v],                         # сама вершина
    tin[u] для обратных рёбер v→u,  # прыжок назад к предку
    low[child] для детей в дереве   # что могут достичь потомки
)

Смысл low простой: насколько высоко в дереве обхода может «дотянуться» поддерево, минуя ребро к родителю.

Критерий моста

Ребро (parent, child) является мостом, если

low[child] > tin[parent]

Читается так: из поддерева ребёнка нельзя попасть в родителя или выше никаким обходным путём. Значит единственная связь — это само ребро, и его удаление разорвёт граф.

Если low[child] ≤ tin[parent], существует обратное ребро в обход, и мост не образуется.

Критерий точки сочленения

Похоже, но с двумя отличиями.

Для обычной вершины: v — точка сочленения, если у неё есть ребёнок child с low[child] >= tin[v]. Обратите внимание: здесь нестрогое неравенство. Достаточно, чтобы поддерево не могло подняться выше самой вершины.

Для корня обхода: корень — точка сочленения, если у него больше одного ребёнка в дереве обхода. У корня нет родителя, поэтому общий критерий к нему неприменим.

Реализация на Python

def find_bridges_and_articulations(graph: dict):
    n = len(graph)
    tin = {}          # время входа
    low = {}
    visited = set()
    timer = 0

    bridges = []
    articulations = set()

    def dfs(v, parent=None) -> None:
        nonlocal timer

        visited.add(v)
        tin[v] = low[v] = timer
        timer += 1
        children = 0

        for to in graph[v]:
            if to == parent:
                continue          # не возвращаемся по ребру, откуда пришли

            if to in visited:
                # обратное ребро — можем прыгнуть к предку
                low[v] = min(low[v], tin[to])
            else:
                dfs(to, v)
                low[v] = min(low[v], low[to])
                children += 1

                # проверка моста
                if low[to] > tin[v]:
                    bridges.append((v, to))

                # проверка точки сочленения для НЕ корня
                if parent is not None and low[to] >= tin[v]:
                    articulations.add(v)

        # корень — точка сочленения, если детей больше одного
        if parent is None and children > 1:
            articulations.add(v)

    for v in graph:
        if v not in visited:
            dfs(v)

    return bridges, sorted(articulations)


graph = {
    1: [2],
    2: [1, 3, 4],
    3: [2],
    4: [2, 5],
    5: [4],
}

bridges, articulations = find_bridges_and_articulations(graph)
print('мосты:', bridges)                  # [(2, 3), (4, 5), (2, 4), (1, 2)]
print('точки сочленения:', articulations) # [2, 4]

Проверим на графе с циклом:

cycle = {1: [2, 3], 2: [1, 3], 3: [1, 2]}
print(find_bridges_and_articulations(cycle))
# ([], [])  — в цикле нет ни мостов, ни точек сочленения

Логично: в цикле любое ребро можно обойти с другой стороны.

Тонкость с кратными рёбрами

Условие if to == parent: continue содержит скрытую проблему. Если между двумя вершинами есть два параллельных ребра, ни одно из них не мост — но код пропустит оба возврата и ошибочно объявит ребро мостом.

Правильное решение — пропускать не по вершине-родителю, а по идентификатору ребра:

def dfs(v, parent_edge=-1):
    for to, edge_id in graph[v]:
        if edge_id == parent_edge:
            continue
        ...

Тогда второе параллельное ребро будет обработано как обратное, и мост не найдётся. В задачах с кратными рёбрами это обязательная поправка.

Почему строгое и нестрогое неравенства различаются

Тонкий момент, который часто спрашивают.

Для моста нужно low[child] > tin[v]: если из поддерева достижима сама вершина v (равенство), значит есть обходной путь, и ребро не критично.

Для точки сочленения достаточно low[child] >= tin[v]: если поддерево дотягивается только до v, но не выше, то удаление самой v отрежет это поддерево. Равенство здесь уже опасно.

Разница в одном символе, а смысл принципиально разный.

Глубина рекурсии

На больших графах (10⁵ вершин и больше) рекурсивный обход упирается в лимит стека Python. Варианты:

import sys
sys.setrecursionlimit(300000)

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

Связанные понятия

Компоненты рёберной двусвязности — части графа, внутри которых нет мостов. Получаются удалением всех мостов.

Компоненты вершинной двусвязности (блоки) — части, внутри которых нет точек сочленения.

Дерево блоков — конденсация графа, где каждая двусвязная компонента сжата в вершину. Часто используется для задач на деревьях после такого сжатия.

Частые ошибки

Использование low[to] вместо tin[to] для обратных рёбер. При обратном ребре берём именно время входа, а не значение low. Иначе алгоритм может «протащить» слишком маленькое значение и пропустить мосты.

Строгое неравенство для точек сочленения. Даст неверный ответ там, где поддерево дотягивается ровно до вершины.

Забытая обработка корня. Корень с двумя детьми — точка сочленения, но общий критерий его не поймает.

Пропуск родителя по вершине при кратных рёбрах. Разобрано выше.

Что запомнить

• Мост — ребро, точка сочленения — вершина, удаление которых разрывает граф.
• Оба ищутся одним обходом в глубину за O(V + E).
• tin — время входа, low — самый ранний достижимый предок из поддерева.
• Мост: low[child] > tin[v] (строго). Точка сочленения: low[child] >= tin[v] (нестрого).
• Корень обхода — точка сочленения, если у него больше одного ребёнка.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→