Сильная связность и конденсация: любой граф - это ДАГ из кусков

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

Как думаешь, что делать с циклом в зависимостях

Система сборки нашла цикл: модуль A зависит от B, B от C, C от A. Топологического порядка нет. Прежде чем читать дальше, подумай: значит ли это, что дальше работать нельзя? И что осмысленного можно сказать про такой граф - ведь остальные-то модули в цикл не входят и их порядок очевиден.

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

Города и односторонние дороги. Внутри центра можно проехать от любого перекрёстка к любому - сколько угодно петляя. Но из центра в спальный район дорога есть, а обратно нет. Стянем центр в одну точку, район в другую - получится простая схема со стрелками в одну сторону, без колец. Так устроен любой город с односторонним движением: кольца - внутри районов, а между районами всегда есть направление.

Механизм: отношение, разбиение, конденсация

u ~ v  ⟺  есть путь u → ... → v  И  есть путь v → ... → u

это отношение эквивалентности:
    рефлексивно  - из вершины в неё саму путь длины ноль есть всегда
    симметрично  - условие записано симметрично
    транзитивно  - пути склеиваются

значит вершины разбиваются на классы - компоненты сильной связности

Компонента из одной вершины - не вырожденный случай, а самый частый: если вершина не лежит ни на одном цикле, её компонента состоит из неё одной. В ациклическом графе КСС ровно V штук.

Конденсация строится так: каждую компоненту заменяем одной вершиной; ребро между компонентами проводим, если в исходном графе было хоть одно ребро из какой-нибудь вершины первой в какую-нибудь вершину второй (кратные рёбра схлопываем, петли выбрасываем).

Правило

Вершины u и v сильно связаны, если достижимы друг из друга; это эквивалентность, и она разбивает граф на компоненты сильной связности. Компонента из одной вершины - обычное дело: в ациклическом графе компонент ровно V. Конденсация (каждая компонента - одна вершина) ВСЕГДА ациклична, поэтому любой ориентированный граф представим как ДАГ из сильно связных кусков, к которому применима топологическая сортировка.

Разбор: находим компоненты руками

Граф: a→b, b→c, c→a, c→d, d→e, e→d, d→f.

Проверяем попарную достижимость. Из a в b - прямо; из b в a - через c (b→c→a). Значит a ~ b. Аналогично a ~ c. Компонента {a, b, c} - это цикл.

d и e: d→e и e→d - сильно связаны, компонента {d, e}.

f: из f рёбер нет вовсе, значит вернуться из неё никуда нельзя - компонента {f} из одной вершины. Заметь: d→f есть, а обратного пути нет, поэтому d и f в разных компонентах.

Итого три компоненты: {a,b,c}, {d,e}, {f}. Конденсация: три вершины и рёбра {a,b,c} → {d,e} (из-за c→d) и {d,e} → {f} (из-за d→f). Циклов в ней нет, топологический порядок - {a,b,c}, {d,e}, {f}.

И вот практический вывод для задачи из начала урока: система сборки, нашедшая цикл, не обязана сдаваться. Она может стянуть каждый цикл в группу, отсортировать ГРУППЫ топологически и сказать честно: «вот эти три модуля придётся собирать вместе, а всё остальное - в таком порядке». Это куда полезнее, чем «обнаружена циклическая зависимость».

Разбор: почему конденсация ациклична

Докажем от противного. Пусть в конденсации есть цикл из компонент C₁ → C₂ → ... → C_k → C₁, и пусть k >= 2 (петли мы выбросили).

Ребро C_i → C_{i+1} означает, что в исходном графе есть ребро из какой-то вершины C_i в какую-то вершину C_{i+1}. Значит из ЛЮБОЙ вершины C_i можно добраться до любой вершины C_{i+1}: внутри C_i дойдём до начала ребра (компонента сильно связна), перейдём по ребру, а внутри C_{i+1} дойдём куда угодно. Пройдя по всему циклу компонент, получаем: из любой вершины C₁ достижима любая вершина C₂, и наоборот - из C₂ через остальные компоненты обратно в C₁.

Но это в точности определение сильной связности: значит вершины C₁ и C₂ лежат в ОДНОЙ компоненте. Противоречие - мы считали их разными. Следовательно цикла в конденсации нет.

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

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

Первое: путать сильную связность со связностью «если забыть направления» (её называют слабой). Граф a→b, c→b слабо связен, но сильных компонент в нём три - из b никуда не уйти. Вторая ошибка - считать, что компоненты можно найти простым обходом: обход из вершины даёт ДОСТИЖИМЫЕ вершины, а нужны те, что достижимы взаимно; наивный способ требует запускать обход из каждой вершины и пересекать множества - O(V·(V+E)), и на больших графах это неприемлемо (следующий урок - как за O(V + E)). Третье: забывать про компоненты из одной вершины и удивляться, что их большинство. Четвёртое: ОСТАВЛЯТЬ при конденсации рёбра, которые превращаются в петли (то есть рёбра внутри одной компоненты), - тогда «ациклическая» конденсация окажется с петлями. Их выбрасывают; а если факт «внутри компоненты есть цикл» нужен по смыслу задачи, его отмечают признаком у вершины, а не ребром. Пятое: думать, что конденсация - это «упрощение графа»: она теряет внутреннюю структуру компонент, и восстановить по ней исходный граф нельзя.

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

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

Теперь сам

Граф: 1→2, 2→3, 3→1, 3→4, 4→5, 5→6, 6→4, 2→6. Найди компоненты сильной связности, построй конденсацию и выпиши её топологический порядок.