Просмотр исходного текста страницы Сильно связный граф NL-complete/Решение Сеилов

*[[Сильно связный граф NL-complete]]

Обозначим этот язык за M. проверим, что он в NL: Для этого нужно перебрать все пары вершин a, b (их хранение на рабочей ленте займет не более log(n)) памяти, где n - размер графа. Необходимо проверить существование пути между a, b. Для этого запускаем недетерминированное блуждание по графу от а до b. Каждый раз храним лишь вершину b и последнюю вершину <math>a_i</math>в пути от a до b и счетчик i - длина текущего пути (для записи счетчика нужно O(log(n))). Если нет пути длиной не больше n, то вообще нет пути. Если путь есть, то недетерминированное блуждание его найдет. Значит, M в NL. Докажем NL-полноту.

Известно, что задача PATH NL-полная ({G,a,b} - в графе G есть путь от a до b). Покажем, как свести задачу PATH к M (найдем логарифмическую сводимость f(x) такую, что x в PATH тогда и только тогда, когда f(x) в M)

Скопируем на выходную ленту все описание графа. Затем для каждой вершины i (кроме a и b) добавим в граф ребра (i->a) и (b->i). Ясно, что это можно сделать на логарифмической памяти (сформировали описание ребра, скопировали его на выходную ленту, очистили рабочую ленту). 

Покажем, что полученный граф F сильно связен тогда и только тогда, когда в G есть путь из a в b.
Пусть есть путь из a в b. тогда из любой вершины i можно попасть в вершину a, далее - в b, и из b в j. 
Пусть граф F сильно связен. в F из a можно попасть в b. значит и, в G из a можно попасть в b, т.к. не добавили никаких полезных ребер, которые могли бы принадлежать пути из a в b.