Использование обхода в глубину для топологической сортировки — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
'''Топологическая сортировка''' ориентированного ациклического графа <tex>G = (V, E)</tex> представляет собой такое линейное упорядочение всех его вершин, что если <tex>(u, v) \in E(G)</tex>, то <tex>u</tex> при таком упорядочении располагается до <tex>v\ </tex> (если граф не является ациклическим, такая сортировка невозможна).
+
'''Топологическая сортировка''' [[Ориентированный граф|ориентированного]] [[Основные определения теории графов|ациклического графа]] <tex>G = (V, E)</tex> представляет собой такое линейное упорядочение всех его [[Основные определения теории графов|вершин]], что если <tex>(u, v) \in E(G)</tex>, то <tex>u</tex> при таком упорядочении располагается до <tex>v\ </tex> (если граф не является ациклическим, такая сортировка невозможна).
  
 
== Постановка задачи ==
 
== Постановка задачи ==
Строка 9: Строка 9:
 
|statement=<tex>G</tex> — ациклический ориентированный граф, тогда <tex>uv \in E \Rightarrow leave[u] > leave[v]</tex>
 
|statement=<tex>G</tex> — ациклический ориентированный граф, тогда <tex>uv \in E \Rightarrow leave[u] > leave[v]</tex>
 
|proof=
 
|proof=
Рассмотрим произвольное ребро <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>.
+
Рассмотрим произвольное [[Основные определения теории графов|ребро]] <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>.
 
}}
 
}}
 
Таким образом, теорема доказана.
 
Таким образом, теорема доказана.

Версия 08:04, 25 октября 2011

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

Постановка задачи

Теорема:
[math]G[/math] — ациклический ориентированный граф, тогда [math]\exists \ \varphi : V \to \{ 1..n \} , uv \in E \Rightarrow \varphi (u) \lt \varphi (v) [/math]
Доказательство:
[math]\triangleright[/math]

Определим [math]leave[u][/math] как порядковый номер окраски вершины [math]u[/math] в черный цвет в результате работы алгоритма [math]dfs[/math], см. Обход в глубину, цвета вершин. Рассмотрим функцию [math]\varphi = n + 1 - leave[u] [/math]. Очевидно, что такая функция подходит под критерий функции [math]\varphi[/math] из условия теоремы, если выполняется следующее утверждение:

Утверждение:
[math]G[/math] — ациклический ориентированный граф, тогда [math]uv \in E \Rightarrow leave[u] \gt leave[v][/math]
[math]\triangleright[/math]
Рассмотрим произвольное ребро [math](u, v)[/math], исследуемое процедурой [math]dfs[/math]. При исследовании вершина [math]v[/math] не может быть серой, так как серые вершины в процессе работы [math]dfs[/math] всегда образуют простой путь в графе, и факт попадания в серую вершину [math]v[/math] означает, что в графе есть цикл из серых вершин, что противоречит условию утверждения. Следовательно, вершина [math]v[/math] должна быть белой либо черной. Если вершина [math]v[/math] — белая, то она становится потомком [math]u[/math], так что [math]leave[u] \gt leave[v][/math]. Если [math]v[/math] — черная, значит, работа с ней уже завершена и значение [math]leave[v][/math] уже установлено. Поскольку мы все еще работаем с вершиной [math]u[/math], значение [math]leave[u][/math] еще не определено, так что, когда это будет сделано, будет выполняться неравенство [math]leave[u] \gt leave[v][/math]. Следовательно, для любого ребра [math](u, v)[/math] ориентированного ациклического графа выполняется условие [math]leave[u] \gt leave[v][/math].
[math]\triangleleft[/math]
Таким образом, теорема доказана.
[math]\triangleleft[/math]

Алгоритм

Из определения функции [math]\varphi[/math] мгновенно следует алгоритм топологической сортировки:

doTopSort(graph G) {
   fill(visited, false);
   time = 0;
   for (Vertex v : v in graph G) {
      if (!visited[v]) {
         dfs(v);
      }
   }
}
dfs(u) {
   visited[u] = true;
   for (Vertex v : exists edge uv) {
      if (!visited[v]) {
         dfs(v);
      }
   }
   topSortAnswer[u] = n - time++;
}

Время работы этого алгоритма соответствует времени работы алгоритма поиска в глубину, то есть равно [math]O(V+E)[/math].

Источники

  • Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, второе издание. Пер. с англ. — Издательский дом "Вильямс", 2007. — 1296 с. — Глава 22. Элементарные алгоритмы для работы с графами.