172
правки
Изменения
Нет описания правки
'''Топологическая сортировка''' ориентированного ациклического графа <tex>G = (V, E)</tex> представляет собой такое линейное упорядочение всех его вершин, что если <tex>(u, v) \in E(G)</tex>, то <tex>u</tex> при таком упорядочении располагается до <tex>v\ </tex> (если граф не является ацикличным, такая сортировка невозможна).
== Постановка задачи ==
{{Теорема
|statement=<tex>G</tex> — ациклический ориентированный граф, тогда <tex>\exists \ \varphi : V \to \{ 1..n \} , uv \in E \Rightarrow \varphi (u) < \varphi (v) </tex>
|proof=
Определим <tex>leave[u]</tex> как порядковый номер окраски вершины <tex>u</tex> в черный цвет в результате работы алгоритма <tex>dfs</tex>, см. [[Обход в глубину, цвета вершин]]. Рассмотрим функцию <tex>\varphi = n + 1 - leave[u] </tex>. Очевидно, что такая функция подходит под критерий функции <tex>\varphi</tex> из условия теоремы, если выполняется следующее утверждение:
{{Утверждение
|statement=<tex>G</tex> — ациклический ориентированный граф, тогда <tex>uv \in E \Rightarrow leave[u] > leave[v]</tex>
|proof=
Рассмотрим произвольное ребро <tex>(u, v)</tex>, исследуемое процедурой <tex>dfs</tex>. При исследовании вершина <tex>v</tex> не может быть серой, так как серые вершины в процессе работы <tex>dfs</tex> всегда образуют простой путь в графе, и факт попадания в серую вершину <tex>v</tex> означает, что в графе есть цикл из серых вершин, что противоречит условию утверждения.
}}
}}
