Проектирование и анализ алгоритма

На самом деле условие, обратное, выполняется, и для доказательства этого факта мы воспользуемся эффективным алгоритмом вычисления топологического упорядочения. Ключевым фактором станет определение отправной точки: с какого узла должно начинаться топологическое упорядочение?

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

В каждом направленном ациклическом графе G существует узел v, не имеющий входящих ребер.

Выбираем любой узел v и начинаем переходить по ребрам в обратном направлении от v; так как v содержит как минимум одно входящее ребро (u, v), можно перейти к u; так как ребро u содержит как минимум одно входящее ребро (x, u), можно вернуться обратно к x; и т. д.

Этот процесс может продолжаться бесконечно, так как каждый обнаруженный узел имеет входящее ребро. Но после n + 1 шагов какой-то узел w неизбежно будет посещен дважды. Если обозначить C серию узлов, встреченных между последовательными посещениями w, то C очевидным образом образует цикл.

Существование такого узла v — все, что необходимо для построения топологического упорядочения G. Докажем посредством индукции, что каждый DAG имеет топологическое упорядочение.

Это утверждение очевидно истинно для DAG с одним или двумя узлами. Теперь допустим, что оно истинно для DAG с количеством узлов до n. В DAG G с n + 1 узлом будет присутствовать узел v, не имеющий входящих ребер; его существование гарантировано по (3.19). Узел v ставится на первое место в топологическом упорядочении; такое размещение безопасно, поскольку все ребра из v указывают вперед.

Теперь заметим, что граф G − {v} является DAG, поскольку удаление v не может привести к образованию циклов, не существовавших ранее. Кроме того, граф G − {v} содержит n узлов, что позволяет нам применить предположение индукции для получения топологического упорядочения G − {v}.

Присоединим узлы G − {v} в этом порядке после v; в полученном упорядочении G все ребра будут указывать вперед, а следовательно, оно является топологическим упорядочением.

Итак, положение, обратное (3.18), успешно доказано.