Конспект раздела: графы - представление и обход

Понятия

Граф - V вершин и E рёбер; ориентированный, взвешенный, простой или мультиграф. Дерево - связный граф без циклов, V − 1 рёбер. Разреженный (E ≈ V) против плотного (E ≈ V²) решает всё.

Обход в глубину - каркас раздела: пометка при ВХОДЕ, цена O(V + E), запуск из каждой непосещённой вершины.

Времена tin / tout и теорема о скобках: отрезки вложены или не пересекаются; проверка «предок ли» - O(1).

Цвета: белая, СЕРАЯ (на текущем пути), чёрная. Ребро в серую вершину - цикл (в неориентированном графе - кроме ребра к родителю).

Топологический порядок ориентированного графа существует ⇔ граф ацикличен. Компоненты сильной связности - классы взаимной достижимости; их конденсация всегда ациклична.

low[v] - минимальное время входа, достижимое из поддерева при одном подъёме по обратному ребру. Даёт мосты и точки сочленения.

Двудольность ⇔ нет нечётных циклов. Планарность ограничена формулой Эйлера V − E + F = 2 для связного плоского графа.

LCA - наименьший общий предок; двоичные подъёмы, эйлеров обход, разреженная таблица.

Что унести

Представление выбирают под операции:

Что вытаскивается из ОДНОГО обхода в глубину:

пометки            → достижимость, компоненты связности
цвета              → циклы (ребро в СЕРУЮ вершину)
порядок выхода     → топологическая сортировка (перевернуть)
два обхода + разворот → компоненты сильной связности (Косарайю)
low = min(tin, tin по обратным, low детей)
   low[to] >  tin[v] → мост
   low[to] >= tin[v] → точка сочленения (у корня: два ребёнка)
tin / tout         → «предок ли» за O(1), эйлеров обход, LCA через RMQ
чередование цветов → двудольность

Ключевые оценки: обход O(V + E); Кан O(V + E) плюс уровни параллельности (их число - длина критического пути); Косарайю - два обхода; мосты и точки сочленения - один обход; LCA - O(log V) двоичными подъёмами или O(1) разреженной таблицей по эйлерову обходу.

Ловушки, каждая из которых даёт неверный ответ молча:

• искать цикл по visited вместо цветов - ребро в чёрную вершину циклом не является;
• забыть внешний цикл по вершинам - обойдётся одна компонента;
• пометить вершину при выходе - бесконечная рекурсия;
• пропускать родителя по номеру ВЕРШИНЫ при кратных рёбрах - ложные мосты;
• перепутать > и >= в критериях моста и точки сочленения;
• применить общее правило к корню при поиске точек сочленения;
• забыть проверку «одна вершина - предок другой» в LCA - ответ на уровень выше;
• строить разреженную таблицу для суммы - перекрытие посчитается дважды;
• рекурсия на цепочке из миллиона вершин - переполнение стека.

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

Дальше появляются веса: кратчайшие пути (Дейкстра на очереди с приоритетами из раздела про кучи, Беллман-Форд, Флойд) и остовные деревья (Крускал на непересекающихся множествах, Прим на куче). Следующий раздел собирает их из деталей, сделанных здесь и в разделе 9.