NL-полнота задачи о достижимости в графе — различия между версиями
Joshik (обсуждение | вклад) (Новая страница: «== Формулировка задачи== Даны ориентированный граф <tex> G = \langle V, E \rangle </tex> и две вершины <tex> s, t…») |
Joshik (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Формулировка задачи== | == Формулировка задачи== | ||
| − | Даны ориентированный граф <tex> G = \langle V, E \rangle </tex> и две вершины <tex> s, t</tex> в нем. Необходимо проверить, правда ли, что в графе <tex> G </tex> существует путь из вершины <tex> s </tex> в вершину <tex> t </tex>. Эту задачу принято называть <tex> | + | Даны ориентированный граф <tex> G = \langle V, E \rangle </tex> и две вершины <tex> s, t</tex> в нем. Необходимо проверить, правда ли, что в графе <tex> G </tex> существует путь из вершины <tex> s </tex> в вершину <tex> t </tex>. Эту задачу принято называть <tex> st-connectivity </tex> или <tex> STCON </tex>. |
== Утверждение == | == Утверждение == | ||
| − | Задача <tex> | + | Задача <tex> STCON </tex> [[NL-полнота|NL-полна]]. |
| + | |||
| + | == Доказательство == | ||
| + | Для доказательства [[NL-полнота|NL-полноты]] необходимо показать, что эта задача NL-трудная и принадлежит [[NL|классу NL]]. | ||
| + | |||
| + | === Доказательство принадлежности задачи STCON классу NL === | ||
| + | |||
| + | === Доказательство NL-трудности задачи STCON === | ||
Версия 13:58, 6 апреля 2010
Содержание
Формулировка задачи
Даны ориентированный граф и две вершины в нем. Необходимо проверить, правда ли, что в графе существует путь из вершины в вершину . Эту задачу принято называть или .
Утверждение
Задача NL-полна.
Доказательство
Для доказательства NL-полноты необходимо показать, что эта задача NL-трудная и принадлежит классу NL.
