Изменения

'''Топологическая сортировка''' [[Ориентированный граф|ориентированного ]] [[Основные определения теории графов|ациклического графа ]] <tex>G = (V, E)</tex> представляет собой такое линейное упорядочение всех его [[Основные определения теории графов|вершин]], что если <tex>(u, v) \in E(G)</tex>, то <tex>u</tex> при таком упорядочении располагается до <tex>v\ </tex> (если граф не является ациклическим, такая сортировка невозможна).

Рассмотрим произвольное [[Основные определения теории графов|ребро ]] <tex>(u, v)</tex>, исследуемое процедурой <tex>dfs</tex>. При исследовании вершина <tex>v</tex> не может быть серой, так как серые вершины в процессе работы <tex>dfs</tex> всегда образуют простой путь в графе, и факт попадания в серую вершину <tex>v</tex> означает, что в графе есть цикл из серых вершин, что противоречит условию утверждения. Следовательно, вершина <tex>v</tex> должна быть белой либо черной. Если вершина <tex>v</tex> — белая, то она становится потомком <tex>u</tex>, так что <tex>leave[u] > leave[v]</tex>. Если <tex>v</tex> — черная, значит, работа с ней уже завершена и значение <tex>leave[v]</tex> уже установлено. Поскольку мы все еще работаем с вершиной <tex>u</tex>, значение <tex>leave[u]</tex> еще не определено, так что, когда это будет сделано, будет выполняться неравенство <tex>leave[u] > leave[v]</tex>. Следовательно, для любого ребра <tex>(u, v)</tex> ориентированного ациклического графа выполняется условие <tex>leave[u] > leave[v]</tex>.