25
правок
Изменения
Новая страница: «== Формулировка задачи== Даны ориентированный граф <tex> G = \langle V, E \rangle </tex> и две вершины <tex> s, t…»
== Формулировка задачи==
Даны ориентированный граф <tex> G = \langle V, E \rangle </tex> и две вершины <tex> s, t</tex> в нем. Необходимо проверить, правда ли, что в графе <tex> G </tex> существует путь из вершины <tex> s </tex> в вершину <tex> t </tex>. Эту задачу принято называть <tex> REACH </tex>.
== Утверждение ==
Задача <tex> REACH </tex> [[NL-полнота|NL-полна]].
Даны ориентированный граф <tex> G = \langle V, E \rangle </tex> и две вершины <tex> s, t</tex> в нем. Необходимо проверить, правда ли, что в графе <tex> G </tex> существует путь из вершины <tex> s </tex> в вершину <tex> t </tex>. Эту задачу принято называть <tex> REACH </tex>.
== Утверждение ==
Задача <tex> REACH </tex> [[NL-полнота|NL-полна]].
