Мосты. Конденсация графа

Мосты и точки сочленения

Определение. Мостом называется ребро, при удалении которого связный неориентированный граф становится несвязным.

Определение. Точкой сочленения называется вершина, при удалении которой связный неориентированный граф становится несвязным.

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

Наивный подход

Наивный алгоритм поочерёдно удаляет каждое ребро \((u, v)\) и проверяет наличие пути \(u \leadsto v\). Это требует \(O(m \cdot (n + m))\) операций. Если ограничиться только рёбрами дерева обхода (см. ниже), сложность снижается до \(O(n \cdot (n + m))\), но это всё ещё медленно.

Классификация рёбер при DFS

Запустим DFS из произвольной вершины неориентированного графа. Все рёбра разделятся на два типа:

  • Рёбра дерева (tree edges) — те, по которым DFS переходил в новые вершины.

  • Обратные рёбра (back edges) — те, по которым DFS не переходил (вели в уже посещённую вершину).

Заметим, что обратное ребро \((u, v)\) не может быть мостом: если его удалить, то путь от \(u\) до \(v\) всё равно существует — по рёбрам дерева обхода, которые образуют связное остовное дерево.

Значит, проверять нужно только рёбра дерева.

Ключевое наблюдение

Обратные рёбра в неориентированном графе всегда ведут «вверх» — к предку в дереве обхода, но не в другие ветки. Если бы такое ребро вело в другую ветку, DFS увидел бы его раньше, и оно стало бы ребром дерева.

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

Чтобы определить, является ли ребро дерева \((v, u)\) (где \(v\) — родитель, \(u\) — ребёнок) мостом, введём вспомогательную функцию \(fup\):

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

Значение \(fup_v\) вычисляется во время DFS:

\[ fup_v = \min \begin{cases} h_v, &\\ fup_u, &\text{ребро } (v, u) \text{ — ребро дерева} \\ h_u, &\text{ребро } (v, u) \text{ — обратное} \end{cases} \]

где \(h_v\) — глубина вершины \(v\) в дереве обхода.

Критерий: ребро дерева \((v, u)\) является мостом тогда и только тогда, когда

\[h_v < fup_u\]

Если это неравенство выполняется, то никакая вершина из поддерева \(u\) не имеет обратного ребра в \(v\) или выше. Следовательно, удаление ребра \((v, u)\) разрывает связь между \(v\) и \(u\).

Реализация

std::vector<std::vector<int>> adj(n);
std::vector<bool> visited(n, false);
std::vector<int> depth(n, 0);
std::vector<int> fup(n, 0);

void dfs(int v, int parent = -1) {
    visited[v] = true;
    depth[v] = fup[v] = (parent == -1 ? 0 : depth[parent] + 1);

    for (int u : adj[v]) {
        if (u == parent) continue;

        if (visited[u]) {
            // обратное ребро — обновляем fup глубиной предка
            fup[v] = std::min(fup[v], depth[u]);
        } else {
            // ребро дерева — рекурсивно обходим
            dfs(u, v);
            fup[v] = std::min(fup[v], fup[u]);

            if (depth[v] < fup[u]) {
                // ребро (v, u) — мост
            }
        }
    }
}

Сложность: \(O(n + m)\) — один проход DFS.

Точки сочленения

Задача поиска точек сочленения решается аналогично.

Вершина \(v\) является точкой сочленения, если для какого-то её ребёнка \(u\) в дереве обхода из поддерева \(u\) нельзя добраться до строгого предка \(v\), не используя ребро \((v, u)\). Формально:

\[h_v \leq fup_u\]

Неравенство нестрогое: если из поддерева \(u\) можно добраться только до самой \(v\) (\(fup_u = h_v\)), то при удалении \(v\) поддерево \(u\) всё равно отсоединится.

Особый случай — корень: корень DFS-дерева является точкой сочленения тогда и только тогда, когда у него более одного ребёнка в дереве обхода. Если корень удалить, его поддеревья станут несвязными.

std::vector<std::vector<int>> adj(n);
std::vector<bool> visited(n, false);
std::vector<int> depth(n, 0);
std::vector<int> fup(n, 0);

void dfs(int v, int parent = -1) {
    visited[v] = true;
    depth[v] = fup[v] = (parent == -1 ? 0 : depth[parent] + 1);
    int children = 0;

    for (int u : adj[v]) {
        if (u == parent) continue;

        if (visited[u]) {
            fup[v] = std::min(fup[v], depth[u]);
        } else {
            dfs(u, v);
            fup[v] = std::min(fup[v], fup[u]);
            ++children;

            if (depth[v] <= fup[u] && parent != -1) {
                // v — точка сочленения (не корень)
            }
        }
    }

    if (parent == -1 && children > 1) {
        // v — корень и точка сочленения
    }
}

Сложность: \(O(n + m)\).

Компоненты сильной связности

Ранее мы научились топологически сортировать ациклические ориентированные графы. Но в циклических ориентированных графах тоже можно выделить полезную структуру — для этого нужно понятие сильной связности.

Определение. Две вершины ориентированного графа связаны сильно (англ. strongly connected), если существует направленный путь из первой во вторую и из второй в первую. Иными словами, они обе лежат на каком-то направленном цикле.

Отношение сильной связности транзитивно: если \(a\) и \(b\) сильно связаны, и \(b\) и \(c\) сильно связаны, то \(a\) и \(c\) тоже сильно связаны. Поэтому все вершины разбиваются на компоненты сильной связности (КСС) — максимальные подмножества вершин, внутри которых все вершины попарно сильно связаны.

Граф с тремя компонентами сильной связности

Простейший пример КСС — цикл. Но это может быть и полный граф, или сложное пересечение нескольких циклов.

Конденсация графа

Часто удобно рассматривать граф, в котором каждая КСС сжата в одну вершину. Такой граф называется конденсацией и всегда является ациклическим (DAG).

Если мы знаем, какие вершины лежат в каждой КСС, то построить граф конденсации несложно: заменяем в каждом ребре номера вершин на номера их компонент и объединяем списки смежности. Поэтому основная задача — найти сами компоненты.

Алгоритм Косарайю

Лемма. Пусть \(A\) и \(B\) — две различные КСС, и в графе конденсации есть ребро \(A \to B\). Тогда:

\[ \max_{a \in A}(tout_a) > \max_{b \in B}(tout_b) \]

Доказательство. Рассмотрим два случая в зависимости от того, в какую из компонент DFS зайдёт первым.

Случай 1: первой достигнута \(A\). В некоторый момент DFS заходит в вершину \(v \in A\), а все остальные вершины \(A\) и \(B\) ещё не посещены. Так как существует ребро из \(A\) в \(B\), из \(v\) достижима вся компонента \(B\). Значит, DFS из \(v\) посетит все вершины \(A\) и \(B\), и они станут потомками \(v\) в дереве обхода. Для любой вершины \(u \in A \cup B\), \(u \neq v\), выполнено \(tout[v] > tout[u]\), что и требовалось.

Случай 2: первой достигнута \(B\). Из \(B\) по условию нельзя попасть в \(A\) (иначе \(A\) и \(B\) были бы одной КСС). Значит, DFS выйдет из всех вершин \(B\) ещё до того, как войдёт в \(A\).

Следствие. Вершина с максимальным \(tout\) принадлежит КСС, в которую не входят рёбра из других компонент.

Из этого факта следует алгоритм:

  1. Запускаем DFS и сортируем вершины по убыванию \(tout\) (аналог топологической сортировки, но для циклического графа).
  2. Рассмотрим первую вершину в этом порядке. В её КСС не входят рёбра из других компонент. Значит, если развернуть все рёбра (построить транспонированный граф), то из этой вершины по транспонированному графу достижима ровно её КСС — и ничего больше.
  3. Помечаем найденную компоненту и повторяем для следующей непомеченной вершины.

Реализация

std::vector<std::vector<int>> adj(n);      // исходный граф
std::vector<std::vector<int>> adj_rev(n);  // транспонированный граф
std::vector<bool> visited(n, false);
std::vector<int> order;                    // порядок по убыванию tout
std::vector<int> component(n, -1);         // номер КСС для каждой вершины
int num_components = 0;

// первый DFS: топологическая сортировка по tout
void dfs1(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u]) {
            dfs1(u);
        }
    }
    order.push_back(v);
}

// второй DFS: маркировка компонент на транспонированном графе
void dfs2(int v) {
    component[v] = num_components;
    for (int u : adj_rev[v]) {
        if (component[u] == -1) {
            dfs2(u);
        }
    }
}
// построение транспонированного графа
for (int v = 0; v < n; ++v) {
    for (int u : adj[v]) {
        adj_rev[u].push_back(v);
    }
}

// первый проход: определяем порядок выхода
for (int v = 0; v < n; ++v) {
    if (!visited[v]) {
        dfs1(v);
    }
}

// второй проход: выделяем КСС в порядке убывания tout
std::reverse(order.begin(), order.end());
for (int v : order) {
    if (component[v] == -1) {
        dfs2(v);
        ++num_components;
    }
}

После выполнения алгоритма номера компонент component[v] будут упорядочены топологически: если в графе конденсации есть ребро из компоненты \(i\) в компоненту \(j\), то \(i < j\).

Сложность: \(O(n + m)\) — два прохода DFS и построение транспонированного графа.