Конспект: топологическая сортировка и сильная связность

Понятия

Топологический порядок - расстановка вершин, при которой каждое ребро u → v идёт вперёд. Существует ⇔ граф ацикличен (ДАГ). Обычно НЕ единственный.

Компоненты сильной связности (КСС) - классы взаимной достижимости: u ~ v, если есть путь в обе стороны. Вершина вне циклов образует компоненту из себя одной.

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

Критический путь - самая длинная цепочка зависимостей; его длина равна числу уровней параллельности и является нижней границей времени при любом числе исполнителей.

Что унести

корректность обхода: для любого ребра u → v в ДАГе  tout[u] > tout[v]
критерий Кана:       выписано < V вершин  ⇔  в графе цикл

Косарайю (компоненты за O(V + E)):

1) обход по графу, вершины копятся в порядке ВЫХОДА
2) развернуть все рёбра
3) обход по развёрнутому графу в порядке УБЫВАНИЯ времени выхода
   каждое дерево второго обхода = одна компонента

Работает потому, что вершина с максимальным tout лежит в компоненте-ИСТОКЕ конденсации, а после разворота исток становится стоком - выйти из него нельзя. Алгоритм Тарьяна делает то же за ОДИН обход без разворота (меньше памяти, тоньше рассуждение).

Тихие ошибки: записать вершину при входе; забыть разворот списка; не проверить цикл; во втором проходе Косарайю взять исходный граф или порядок номеров; пересчитывать входящие степени на каждом такте (O(тактов·E) вместо O(V + E)).

Применение: системы сборки и пакетные менеджеры (порядок и внятный отчёт о циклах - группой, а не «цикл найден»), планировщики и CI (уровни параллельности), пересчёт формул, порядок запуска служб, взаимно рекурсивные функции в компиляторах, 2-SAT, дедлоки.

Куда это ведёт

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