Обход в глубину (продолжение)

Топологическая сортировка: определение, необходимость отсутствия циклов. Добавление фиктивной вершины, серия DFS. Определение цикла по ребру IN->IN. Время входа(tin) и выхода(tout) для вершины. Порядок топ. сорт. = порядок убывания tout. Доказательство. Сильная связность, компоненты сильной связности. Конденсация графа, сохранение достижимости, ацикличность. Поиск компонент сильной связности: прямой DFS + обратный DFS. Лемма о соотношении времён выхода двух компонент с ребром. Доказательство корректности алгоритма.

Эйлеров цикл (ор. граф). Критерий существования: слабая связность и равенство степеней входа/выхода. Док-во сильной связности. DFS по рёбрам, пометки рёбер, код. Список рёбер в порядке выхода - развёрнутый эйлеров цикл. Время работы O(V + E). Доказательство: первый возврат в стартовой вершине; в момент выписывания ребра сохраняется связность пути; обход затрагивает все вершины и рёбра графа.

Обход в глубину в неориентированном графе. Ориентация рёбер (при первом просмотре). Деление рёбер на корневые и обратные. Дерево обхода. Отсутствие прямых и перекрёстных рёбер. Двусвязность, мосты и точки сочленения. Критерий точки сочленения: для корня дерева, в общем случае (на основе обратных рёбер из поддерева сына). Функция верхнего: самый верхний конец обратных рёбер из поддерева. Способы сравнения вершин: по высоте, по времени входа. Рекуррентное соотношение для функции верхнего.