\documentstyle[12pt,russcorr]{article}
\hfuzz=1pt
\tolerance=1000
\emergencystretch=10pt
\begin{document}

\section{Графовые грамматики и машины: случай ограниченного ветвления}

Напомним,  что  контекстно-свободной  графовой    грамматикой
называется    следующая    совокупность:    конечное     множество
нетерминалов, начальный нетерминал, конечное множество терминалов,
конечное множество правил вывода. Правило вывода имет вид 
$\xi\longrightarrow G$,
где $\xi$ --- нетерминал, а $G$ ---  граф  с  висячими  (т.е. инцидентными
только одной вершине) ребрами, число которых обозначим через $V(G)$.
В $G$, как и во всех  рассматриваемых  графах,  могут  быть  кратные
ребра, но нет петель. Каждая вершина графа $G$  помечена  терминалом
или нетерминалом. Ребра при  каждой  вершине  из $G$  перенумерованы
(ребро  может  иметь  различные   номера   относительно   концов).
Независимо от  этой  нумерации  указана  нумерация  висячих  ребер
графа $G$, называемая нумерацией  соответствия.  Применение  правила
$\xi\longrightarrow G$ к некоторому  графу  заключается  в  замене  некоторой  
его
вершины $a$, помеченой $\xi$ и имеющей степень ветвления $V(G)$,  на  граф
$G$, при этом каждое  ребро $l$  инцидентное $a$   отождествляется  с
висячим  ребром  из $G$,  имеющим  тот   же   номер   в   нумерации
соответствия, что и $l$ относительно $a$. Граф $A$ назовем  выводимым  в
грамматике, если все его вершины помечены терминалами и  он  может
быть выведен за конечное  число  шагов  из  одновершинного  графа,
помеченного начальным нетерминалом. Докажем следующую лемму.

ЛЕММА. {\it Для любой грамматики $\Gamma$  существует  эквивалентная  ей
грамматика $\Gamma_{1}$ такая, что в ней  нет правил вида $\xi\longrightarrow 
E$, где $E$ ---
одновершинный граф, вершина которого помечена нетерминалом.}

ДОКАЗАТЕЛЬСТВО. Рассмотрим ориентированный граф $О$,  вершинами
которого являются нетерминалы $G$,  а  два   нетерминала $\xi_{1}$  и $\xi_{2}$
соединены направленным ребром $\overrightarrow{\xi_{1}\xi_{2}}$ если  в 
$\Gamma$  существует  правило
$\xi_{1}\longrightarrow \xi_{2}$, где $\xi_{2}$ --- одновершинный граф с 
вершиной, помеченной $\xi_{2}$. $О$
разбивается на частично упорядоченные  классы  взаимно  достижимых
вершин.  Для  каждого  класса  все  его  элементы  заменим   одним
нетерминалом.  Оставшиеся  правила  вида $\xi_{1}\longrightarrow \xi_{2}$   
ликвидируем,
добавив для каждого правила $\xi_{2}\longrightarrow G$ правило 
$\xi_{1}\longrightarrow G$. Очевидно, что
полученная грамматика эквивалентна $\Gamma$. Лемма доказана.

Из  доказанной  леммы  следует,   что   можно   рассматривать
грамматики только с такими правилами,  которые  увеличивают  число
вершин выводимого графа. Будем считать,  что  все  рассматриваемые
далее грамматики такие.

Выводимые в одной грамматике графы могут  представлять  собой
достаточно богатое семейство. Например, как  показывает  следующая
теорема, любое выводимое семейство можно  снабдить  гамильтоновыми
циклами так что новое семейство тоже будет выводимо.

ТЕОРЕМА 1. {\it Для  любой  графовой  грамматики $\Gamma$   существует
грамматика $\Gamma_{1}$ такая, что для  любого  графа $G$,  выводимого  в 
$\Gamma$,
существует граф $G_{1}$,  выводимый  в $\Gamma_{1}$, со  следующими  
свойствами.
Вершины $G_{1}$ взаимнооднозначно  соответствуют  вершинам $G$,  включая
разметку. Множество ребер $G_{1}$  есть  объединение  множества  ребер,
соответствующих  ребрам $G$  с  той   же   нумерацией,   и   ребер,
составляющих гамильтонов  цикл  в $G_{1}$.  Ребра  этого  цикла  имеют
максимальный при каждой  вершине  номер  в  одном  из  направлений
обхода и на 1 меньший в противоположном.}

ДОКАЗАТЕЛЬСТВО. В графах, являющихся правыми частями правил 
$\Gamma$
с  начальным  нетерминалом   в   левой   части,   добавим   ребра,
составляющие гамильтонов  цикл.  В  правых  частях  других  правил
добавим ребра, составляющие гамильтонову цепь, и два висячих ребра
по краям этой цепи. Выбрав  направление  обхода,  присвоим  номера
добавленным ребрам в соответствии с  последним  условием  теоремы.
Получим грамматику $\Gamma_{1}$. Справедливость  утверждения  теоремы  
легко
доказывается индукцией  по выводу $G$. Теорема 1 доказана.

В  [1]  доказано,  что   проблема   существования   в   графе
гамильтонова цикла NP-полна для произвольного графа.

А.О.Слисенко в [2] доказал, что для графов, выводимых в одной
грамматике, эта проблема решается за  полиноминальное  от  размера
графа время и степень полинома зависит от грамматики. Наша цель  ---
обобщить идеи, использованные А.О.Слисенко.

Мы  обобщаем  проблему   существования   гамильтонова   цикла
следующим   образом.   Рассматриваем   конечные   связные    графы
ограниченной степени  ветвления,  в  которых  для  каждой  вершины
задана нумерация инцидентных ей  ребер.  В  каждой  вершине  графа
стоит буква из некоторого конечного алфавита (разные вершины могут
быть одинаково помечены).  Одна  из  вершин  выделена  в  качестве
начальной. Мы будем  рассматривать  машины  Тьюринга  специального
вида, работающие на таких графах. Опишем детерминированную машину,
работающую на графах со степенью ветвления $\leq N$,  у  которой  число
посещений каждой вершины $\leq К$. Она задается набором $\langle 
A,Q,q_{0},F\rangle$, где
$A$ --- конечный алфавит, включащюий в себя алфавит разметки графов  и
дополнительный рабочий алфавит, $Q$ --- конечное  множество  состояний
машины, $q_{0}$  ---  выделенное  начальное  состояние, $F$  ---  программа.
Программа $F$ это функция. Область ее определения это  множество
пятерок $\langle q,a,n,m,k\rangle$, где $q\in Q$ --- текущее состояние  машины, 
$a\in A$ ---
буква, которой помечена текущая вершина, $n\leq N$ ---  степень  ветвления
текущей вершины, $m\leq n$ --- номер  относительно  текущей  вершины  того
ребра, по которому машина  последний  раз  пришла  в  эту  вершину
(перед началом  работы $m=0$), $k\leq K+1$  ---  число  посещений  текущей
вершины  с  учетом  текущего  посещения.   Если $k\leq K$, а $q$   ---
незаключительное  состояние,  то  значением\quad $F$   является   набор
$\langle q',a',n'\rangle$. Здесь $q'\in Q$ --- новое  состояние  машины, $a'\in A$  ---  
новая
пометка текущей вершины, $n'\leq n$ --- номер ребра,  по  которому  машина
сдвигается из текущей  вершины.  Если $k=K+1$,  значением  является
безрезультатная остановка. Если $q$ --- заключительное состояние, $k\leq K$,
то машина допускает граф.  В  начале  работы  машина  находится  в
начальной вершине и в начальном состоянии. Потом она  естественным
образом действует по своей программе и заканчивает работу.

ТЕОРЕМА 2. {\it Для  любого  связного  графа  существует  машина,
которая, работая на нем, обходит все его вершины и кончает  работу
в начальной вершине.}

ДОКАЗАТАЛЬСТВО. Опишем  машину ${\cal M}$, которая, обходя все 
вершины
графа, одновременно строит его остовное дерево.  Пусть $S_{0}$  ---
степень ветвления  при  начальной  вершине $a_{0}$.  Работа  машины ${\cal 
M}$
состоит из $S_{0}$ этапов.  На $n$-ом  этапе  она  обходит  все  еще  не
посещенные вершины, соединимые с $a_{0}$ путем, проходящим через  ребро
с номером $n$ и не проходящим по уже посещенным вершинам.  Обозначим
множество таких вершин через $C$.  Перед  началом $n$-ого  этапа $a_{0}$
помечается числом $n$, чтобы помнить номер этапа. ${\cal M}$ смещается из 
$a_{0}$
по $n$-му ребру и попадает в вершину $a_{1}$. Если в $a_{1}$ ${\cal M}$ уже 
была, то $a_{1}$
помечена некоторым числом. В этом случае ${\cal M}$ смещается обратно в 
$a_{0}$
и $n$-ый этап заканчивается.  В  противном  случае ${\cal M}$  запоминает  в
разметке $a_{1}$ номер ребра $a_{1}a_{0}$ относительно $a_{1}$ и  обходит  
множество
$C\setminus \{a_{1}\}$ вершин, соединимых с $a_{1}$ путями, не  проходящими  
через  уже
посещенные  вершины.  Для  этого  рекурсивно  запускается  та   же
процедура, что и для $a_{0}$. Закончив обход, ${\cal M}$  возвращается  в 
$a_{0}$  и
$n$-ый этап заканчивается. В силу связности графа любая его  вершина
соединима  с  начальной  и  будет  посещена  на  некотором  этапе.
Поскольку из каждой вершины рекурсивная процедура запускается один
раз, то каждое ребро будет пройдено не более четырех раз.  Поэтому
число посещений любой вершины ограничено. Теорема 2 доказана.

Каждой машине соответствует допускаемое ей множество  графов.
Назовем  множества,  которые   распознаются   некоторой   машиной,
распознаваемыми.

ТЕОРЕМА 3. {\it Дополнение распознаваемого множества до  множества
всех графов с той же максимальной степенью ветвления и с разметкой
в том же алфавите распознаваемо. Объединение  и  пересечение  двух
распознаваемых  множеств,  алфавиты  разметки  которых  совпадают,
являются распознаваемыми.}

ДОКАЗАТЕЛЬСТВО. Машина, распознающая  дополнение,  получается
из машины, распознающей само множество, переменой местами остановки
в заключительном состоянии и  безрезультатной  остановки.  В  силу
равенства $M_{1}\bigcap M_{2}=\overline{M_{1}\bigcup M_{2}}$ утверждение  
для  пересечения  следует  из
утверждений  для  дополнения  и  объединения.  Опишем  машину ${\cal M}$,
распознающую $M_{1}\bigcup M_{2}$, где $M_{1}$ и $M_{2}$ распознаются 
машинами ${\cal M}_{1}$ и ${\cal M}_{2}$.

Сначала ${\cal M}$ действует в соответствии с  программой  машины ${\cal 
M}_{1}$,
модифицированной так, чтобы запомнить  в  разметке  первоначальную
разметку графа и начальную вершину. Если ${\cal M}_{1}$ не допускает  граф, 
${\cal M}$
начинает обходить все вершины графа,  пока  не  найдет  начальную.
После этого ${\cal M}$ действует в сответствии  с  программой ${\cal M}_{2}$.  
Теорема 3
доказана.

Пусть $M$ --- произвольное  множество  графов,  алфавит  разметки
которых есть прямое произведение  алфавитов $A_{1}$  и $A_{2}$.  Проекцией
множества $M$ на $A_{1}$ назовем множество графов, размеченных  
алфавитом
$A_{1}$, для которых можно так  добавить  разметку  алфавитом $A_{2}$,  что
получившийся граф  принадлежит $M$.  Обобщением $M$  на $A_{1}$  назовем
множесто графов, размеченных в $A_{1}$, для которых при любой  разметке
алфавитом $A_{2}$ полученный граф принадлежит $M$.  Будем  рассматривать
иерархию  классов  предикатов   на   графах   наподобие   иерархии
Мейера-Стокмейера. Базовыми  предикатами  являются  распознаваемые
множества. Обозначим этот класс через $\sigma_{0}=\pi_{0}$. Определим по 
индукции
другие классы иерархии. Класс $\sigma_{n+1}$ состоит  из  проекций  множеств
класса $\pi_{n}$.  Класс $\pi_{n+1}$ состоит из обобщений  множеств  класса 
$\sigma_{n}$.
Каждому множеству графов из класса $\sigma_{n}$, размеченному алфавитом 
$A_{1}$,
соответствует формула
$$
\exists {\cal A}_{n+1}\,\forall {\cal A}_{n}\,\exists {\cal A}_{n-1}\ldots (\exists 
/\forall){\cal A}_{2}{\cal M}({\cal A}_{1}\times {\cal A}_{2}\times \ldots \times {\cal 
A}_{n}).
$$
Здесь ${\cal A}_{1},\ldots {\cal A}_{n}$ --- разметки в алфавитах 
$A_{1}$,$A_{2}$,...$A_{n}$, а ${\cal M}$  ---  машина,
работающая  на   графах,   размеченных   алфавитом $A_{1}\times 
A_{2}\times\ldots\times A_{n}$.
Аналогично, каждому множеству класса $\pi_{n}$ соответствует формула
$$
\forall {\cal A}_{n+1}\,\exists {\cal A}_{n}\,\forall {\cal A}_{n-1}\ldots(\exists 
/\forall){\cal A}_{2}{\cal M}({\cal A}_{1}\times\ldots\times {\cal A}_{n}).
$$

ТЕОРЕМА 4. {\it Пусть $M_{1}$ и $M_{2}$ --- два  множества  из  одного  
любого
класса  иерархии,  алфавиты  разметки  которых  совпадают.   Тогда
множества $M_{1}\bigcup M_{2}$ и $M_{1}\bigcap M_{2}$ принадлежат тому же 
классу. Проекция любого
множества из $\sigma_{n}$ лежит в $\sigma_{n}$. Обобщение любого множества 
из $\pi_{n}$ лежит
в $\pi_{n}$.}

ДОКАЗАТЕЛЬСТВО. Пусть множества $M_{1}$ и $M_{2}$ задаются 
формулами $\Phi_{1}$
и $\Phi_{2}$. Опишем формулу $\Phi$,  задающую $M_{1}\bigcup M_{2}$  или 
$M_{1}\bigcap M_{2}$.  Машина ${\cal M}$,
стоящая в ее бескванторной части работает  на  графе,  размеченном
алфавитом,  представляющем  собой  прямое   произведение,   первая
компонента которого --- алфавит разметки множеств $M_{1}$ и $M_{2}$, а  
другие
компоненты  ---  прямые  произведения  двух  алфавитов,  стоящих  на
одинаковых местах в $\Phi_{1}$  и $\Phi_{2}$. ${\cal M}$,  также  как  в  
доказательстве
теоремы~3 последовательно запускает машины из $\Phi_{1}$ и $\Phi_{2}$,  
каждую  на
своей ``половине'' разметки. Алфавиты, соответствующие  кванторам  в
кванторной приставке формулы $\Phi$,  являются  прямыми  произведениями
алфавитов, соответствующих тем же кванторам  в $\Phi_{1}$  и $\Phi_{2}$.  
Вторая
часть теоремы очевидна,  так  как  два  подряд  идущих  одинаковых
квантора  можно   слить   в   один,   беря   прямое   произведение
соответствующих алфавитов. Теорема 4 доказана.

ТЕОРЕМА 5. {\it Семейство графов, обладающих гамильтоновым  циклом
и размеченных в конечном алфавите, принадлежит $\sigma_{1}$.}

ДОКАЗАТЕЛЬСТВО. У графа с выделенным гамильтоновым  циклом  и
направлением обхода по нему каждую вершину разметим номером ребра,
по которому из нее выходит цикл. Машина, пользуясь этой разметкой,
проходит по предполагаемому  циклу,  отмечая  посещенные  вершины,
пока не  придет  в  начальную.  Затем  она  обходит  весь  граф  и
проверяет, что все вершины отмечены. Теорема 5 доказана.

А.О.Слисенко доказал следующую теорему.

ТЕОРЕМА 6. {\it Существует  алгоритм,  который  по  размеченному
связному графу $G$  и  грамматике  выясняет, выводим  ли $G$  в  этой
грамматике, и если выводим, строит его  вывод.  При  фиксированной
грамматике $\Gamma$ время работы этого алгоритма полиномиально зависит от
размера $G$.}

ДОКАЗАТЕЛЬСТВО. В  процессе  вывода   любая   нетерминальная
вершина   промежуточного   графа    соответствует    подграфу    в
окончательном графе, выведенному из  нее.  Число  граничных  ребер
этого подграфа ограничено ветвлением грамматики. Пусть  это  число
$\leq m$. Опишем требуемый алгоритм. Перебираем  в $G$  множества  из $\leq 
m$
предполагаемых граничными ребер с указанием, какой  конец  каждого
ребра внутренний и какой внешний.  Для каждого такого множества $M$
рассмотрим множество $G_{1}$ вершин $G$, соединимых с внутренней 
вершиной
из $M$ путем, не проходящим через внешние вершины,  и  множество $G_{2}$
вершин, соединимых с внешней вершиной путем, не  проходящим  через
внутренние. В  силу  связности $G$, $G_{1}\bigcup G_{2}=G$.  Если 
$G_{1}\bigcap G_{2}=\emptyset$,  то  у
подграфа $G_{1}$ множество граничных ребер есть $M$  и  подграф  с  таким
свойством единственен. Если $G_{1}\bigcap G_{2}\not= \emptyset$ то подграфа с  
этим  свойством
не существует. Таким образом выделим множество $P$ всех подграфов  с
числом граничных ребер $\leq m$. Будем составлять таблицу,  показывающую
какие подграфы из $P$ с  висячими  граничными  ребрами  выводимы  из
каких нетерминалов грамматики $\Gamma$. Будем указывать в  таблице  также
соответствие между  номерами  ребер  при  нетерминале  и  висячими
ребрами выводимого из этого нетерминала графа. Заполнение  таблицы
начинаем с наименьших подграфов,  выводящихся за один  шаг.  Пусть
мы указали в таблице все подграфы, которые могут быть выведены  за
$\leq n$ шагов. Тогда для каждого $p\in P$ и  каждого  правила $\eta 
\longrightarrow B$  из $\Gamma$
естественным образом проверяется, имеется ли вывод $p$ из $\eta$ глубины
$\leq n+1$ с применением правила $\eta \longrightarrow B$ на первом  шаге.  
Таким  образом
добавим в таблицу все подграфы, выводимые за $n+1$ шагов. Так мы  за
полиномиальное от размера $G$ время заполним всю  таблицу  и  узнаем
выводим ли $G$ из начального нетерминала. Теорема 6 доказана.

Существенность   условия   связности   показывает   следующая
теорема.

ТЕОРЕМА 7. {\it Для   несвязных   графов   проблема   выводимости
размеченного графа в некоторой фиксированной  грамматике NP-полна
от размера графа.}

ДОКАЗАТЕЛЬСТВО. Пусть  есть  ленточная   недетерминированная
машина Тьюринга ${\cal M}$, распознающая NP-полный  предикат  и  
работающая
время $p(|x|)$, где $p$ --- полином, $x$ --- входное слово. Можно, очевидно,
считать,  что  для  любого   допускаемого   слова $x$   существует
допускающий протокол  длины  ровно $p(|x|)$. Этот  протокол  будем
представлять в виде матрицы $B$  размера $p(|x|)\times p(|x|)$,  на $i$-той
строке которой записана конфигурация ${\cal M}$  в $i$-ый  момент  времени.
Пусть $L$ --- алфавит записи конфигураций. Опишем некоторую  процедуру
заполнения  матрицы $B$.  Пусть  для  каждой  тройки $(i,j,b)$,  где
$1<i\leq p(|x|)$, $j\leq p(|x|)$, $b\in L$, существует  лампочка,  которую  можно
зажигать. Для каждой тройки $(1,j,b_{j})$,  где $j\leq p(|x|)$, $b_{j}$  --- $j$-ый
элемент начальной конфигурации, тоже есть лампочка. Будем двигаться
по строкам  матрицы $B$,  заполняя  ее  элементами $b_{ij}$  в  порядке
лексикографического возрастания пары $(i,j)$.  На  каждом  шаге  мы
сначала произвольно угадываем значение элемента $b_{ij}$.  Пусть $b$  ---
угаданное значение. Зажигаем лампочку $(i,j,b)$.  Если $i<p(|x|)$  и
$j>1$, угадываем значение $b_{1}$  элемента $b_{i+1,j-1}$  из  тех,  которые
возможны  при  условии,  что ${\cal M}$  совершила  один  шаг   работы   в
соответствии с программой, с учетом четырех  элементов,  угаданных
на двух предыдущих шагах. После этого зажигаем  все $S-1$  лампочек
$(i+1,j-1,b_{2})$, где $S=|L|$, $b_{2}\not= b_{1}$. Если $j=p(|x|)$,  то  после  
этого
угадываем и возможное значение $b_{3}$ элемента $b_{i+1,p(|x|)}$ и  зажигаем
$S-1$ лампочек $(i+1,p(|x|),b_{4})$, $b_{4}\not= b_{3}$. Покажем, что ${\cal M}$  
допускает $x$
тогда и только тогда, когда наша процедура может  отработать  так,
чтобы зажечь каждую   лампочку  ровно  один  раз,  и  в  последней
конфигурации ${\cal M}$  находится  в   заключительном   состоянии.   Если
допускающий протокол существует, то наша процедура угадывает его и
при этом для каждой пары $(i,j)$ зажигает лампочку $(i,j,b)$, где $b$  ---
значение $b_{ij}$, проходя по $i$-ой строке,  а  лампочки $(i,j,c)$, $c\not= b$,
проходя по предыдущей. Обратно, пусть ${\cal M}$ зажигает каждую   лампочку
ровно один раз. Тогда, проходя по $i$-ой строке,  процедура  должна
угадать именно те значения $b_{ij}$, которые были угаданы  при  проходе
по $(i-1)$-ой  строке.  Значит   каждая   последующая   конфигурация
получается  из  предыдущей  совершением  одного  шага  работы ${\cal M}$.
Промоделируем описанную процедуру выводом специального графа $G$  в
некоторой грамматике $\Gamma$.  Опишем  граф $G$.  Он  состоит  из  одной
основной компоненты $K$ и  многих  вспомогательных.  Все  компоненты
представляют собой размеченные цепи. Каждая буква  из $L$  является
терминалом. Занумеруем пары $(i,j)$ в лексикографическом порядке. $K$
отражает весь ход нашей процедуры. Она состоит из $p^{2}(|x|)$  крупных
подотрезков, которые взаимнооднозначно соответствуют парам $(i,j)$ и
располагаются по возрастанию их  номеров.  Номер $(i,j)$  обозначим
через NOM($i,j$).  Каждый  крупный  подотрезок  состоит  из  мелких.
Первый мелкий  подотрезок  представляет  собой  цепь  из  NOM($i,j$)
вершин, помеченных  терминалом $t$,  после  которых  идет  вершина,
помеченная терминалом $r_{1}$. Если $j\not= 1$ и $i\not= p(|x|)$,  то  далее  
следуют
еще $S-1$ мелких подотрезков. Они состоят из NOM($i+1,j-1$) терминалов
$t$, за которыми следует терминал $r_{2}$. Если $j=p(|x|)$, то после  этого
блока подотрезков следует еще $S-1$ мелких подотрезков, состоящих из
NOM($i+1,p(|x|)$) терминалов $t$ и терминала $r_{3}$. В конце $K$ стоит 
стоит
терминал $r_{0}$. Остальные компоненты взаимнооднозначно  соответствуют
лампочкам. Kомпонента, соответствующая  лампочке $(i,j,b)$,  это
цепь,  начинающаяся  с  терминала $b$,  за  которым  идут  NOM($i,j$)
терминалов $d$, а после  них  стоит  терминал $d_{0}$.  Главная  идея  в
грамматике $\Gamma$ состоит в том, чтобы в $\Gamma$ можно было выводить 
основную
компоненту и одновременно ``отслаивать'' от нее лампочки.  Выведение
лампочки  соответствует  ее  зажиганию.  В   процессе   вывода $K$
выведенная часть ее указывает, какой шаг  процедуры  моделируется.
Если выводится крупный подотрезок, соответствуюший $(i,j)$,  то  это
означает, что процедура совершает действия, находясь в точке $b_{ij}$.
Вывод первого мелкого подотрезка соответствует зажиганию  лампочки
в $(i,j)$, а вывод последующих $S-1$ мелких  подотрезков  ---  зажиганию
лампочек в $(i+1,j-1)$. Опишем $\Gamma$ подробнее. Правила  ее  делятся  на
три вида: правила начала отщепления лампочки, продолжения и конца.
Правила начала имеют вид: $\xi\longrightarrow C_{1}$, где $C_{1}$ ---  
двухвершинный  граф,
представляющий собой нетерминал $\eta$, смежный с вершиной,  помеченной
терминалом $b\in L$. Из $\eta$ выходит одно висячее ребро, которое в  выводе
становится ребром основной компоненты, а $b$  это  пометка  первой
вершины лампочки, зависящая от $\xi$. $\eta$ зависит от $\xi$ и от $b$.  Правила
продолжения имеют вид: $\eta\longrightarrow C_{2}$, где $C_{2}$ ---  
трехвершинный  граф.  Он
представляет собой нетерминал $\eta$,  смежный  с  двумя  терминальными
вершинами, помеченными $t$ и $d$. Из них выходит  по  одному  висячему
ребру, которые в выводе становятся ребрами основной  компоненты  и
лампочки соответственно. Правила конца вывода лампочки имеют  вид:
$\eta \longrightarrow C_{3}$, где $C_{3}$ --- трехвершинный граф. Он состоит из  
двух  связных
компонент. Первая компонента это терминальная   вершина $d_{0}$,  из
которой исходит висячее ребро. В процессе вывода $d_{0}$  ---  последняя
вершина отделившейся лампочки. Вторая компонента это  нетерминал
$\xi$, соединенный с терминальной вершиной $r_{i}$,  где $i\in \{1,2,3\}$.  Из 
$r_{i}$
выходит висячее ребро, которое в выводе присоединяется к  основной
компоненте. $\xi$ и $i$ здесь зависят от $\eta$.

Опишем, какую информацию должен ``помнить'' текущий  нетерминал
$\eta$. $\eta$  ``помнит''  элементы,  угаданные  на  текущем  шаге  и   двух
предыдущих шагах по текущей строке, в  частности  отсутствие  этих
элементов,  если  процедура  находится  в   начале   строки,   или
отсутствие следующей строки, если текущая строка  последняя.  В $\eta$
содержится также информация, является ли текущий элемент последним
элементом строки. $\eta$ ``помнит'', зажигает  ли  процедура  лампочку  в
текущей строке или в последующей. Например,  если  в  текущей,  то
элемент $b$ в  правиле  начала  вывода  лампочки  может  быть  любым
(угадывание произвольно), а если в последующей, то $b$  зависит  от
элементов,  угаданных на данном шаге и  двух  предыдущих.  В  этом
случае $\eta$ ``помнит'' какие из $S-1$ лампочек зажигались,  а  какие  еще
предстоит зажечь. Если текущая строка  последняя  и  было  угадано
состояние машины, $\eta$ ``помнит''  заключительное  ли  оно.  Символ $r_{0}$
может появиться только если состояние заключительное. Соответствие
между $\xi$ и $\eta$ в правилах начала и конца обеспечивает  восстановление
всей информации, за исключением той догадки, совершен  ли  переход
на последний элемент строки или на начало последней строки.  Пусть
существует допускающий способ работы процедуры. Тогда существует и
вывод $G$ в $\Gamma$, так  как  единственность  зажигания  каждой  лампочки
позволит вывести соответствующую ей  компоненту  ровно  один  раз.
Пусть, наоборот, существует вывод $G$ в $\Gamma$. Из устройства $\Gamma$  
следует,
что появление символа $r_{i}$ в $K$ может произойти только одновременно с
окончанием   вывода   лампочки,   и   длина   ее    равна    длине
соответствующего  отрезка  в $K$.  Если  бы   в   процессе   вывода
неправильно был бы угадан конец строки, то символ $r_{3}$  появился  бы
не на том  месте,  что  в  основной  компоненте.  Из  всего  этого
следует,  что  если $G$  выведен,  то   порядок   вывода   лампочек
соответствует порядку их зажигания в  процедуре.  То,  что  каждая
лампочка была выведена ровно один  раз,  означает,  что  процедура
допускающая. Теорема 7 доказана.

NP-полнота сохранится и в  случае,  если  потребовать,  чтобы
граф был неразмеченным, а $\Gamma$ представляла  бы  собой  просто  набор
графов с висячими ребрами и начальный граф. При  этом  любой  граф
можно подставить вместо любой вершины, у которой число инцидентных
ребер равно числу висячих ребер графа, соответствие между  ребрами
любое. Дадим набросок доказательства NP-полноты  в  этом  случае.
Смоделируем разметку вершин графа с  помощью  отростков  длины  1.
Каждому нетерминалу  и  терминалу  поставим  в  соответствие  свое
натуральное число, причем любому  терминалу  большее,  чем  любому
нетерминалу. Модифицируем граф $G$, добавив к каждой вершине столько
отростков, чтобы число инцидентных  ей  ребер  было  равно  числу,
соответствующему ее пометке. В $\Gamma$ оставим лишь графы правой  
части,
модифицированные  следующим  образом.   В  нетерминальные   и   те
терминальные вершины, из которых не выходит висячих ребер, добавим
столько отростков, чтобы общее  количество  инцидентных  им  ребер
соответствовало их пометкам. В те терминальные вершины, из которых
выходят  висячие  ребра,  добавим  частично  отростки  и  частично
висячие ребра, так чтобы общее количество висячих ребер было равно
числу, соответствующему нетерминалу в левой части  и  чтобы  число
инцидентных каждой вершине ребер соответствовало ее пометке.

В процессе вывода заменить на граф можно только одну вершину.
Очевидно, что к выводу $G$ может привести  лишь  такая  замена,  при
которой два ребра, которые соответствуют направлению на лампочку и
основную компоненту, отождествляются с  соответствующими  висячими
ребрами графа. Дальнейшее  доказательство  следует  доказательству
теоремы~7.

Скажем, что формула $\Phi$ из иерархии истинна на графе $G$, если $G$
принадлежит задаваемому $\Phi$ множеству.  Следующая  теорема  обобщает
теорему А.О.Слисенко о гамильтоновом цикле, упомянутую во введении.

ТЕОРЕМА 8. {\it Существует  алгоритм,  который  по  графу $G$  и
формуле $\Phi$ из описанной выше иерархии выясняет истинна ли $\Phi$  на 
$G$.
При фиксированной формуле для графов,  выводимых  в  фиксированной
грамматике, время алгоритма полиномиально зависит от размера $G$.}

ДОКАЗАТЕЛЬСТВО. Сначала заметим, что для любой  грамматики $\Gamma$
существует эквивалентная ей  грамматика $\Gamma_{1}$ такая, что  в  правой
части любого правила $\Gamma_{1}$ стоит граф из $\leq 2$  вершин.  Чтобы  
получить
$\Gamma_{1}$,  каждое  правило $\Gamma$  расщепим  на  несколько  
последовательных
правил, отщепляя от графа в  правой  части  по  одной  вершине,  а
оставшуюся  часть  каждый  раз   обозначая   новым   нетерминалом.
Очевидно, что размер $\Gamma_{1}$ полиномиален от размера $\Gamma$.  
Легко  видеть,
что  для  любого $n$  и  любого  конечного  алфавита $A$  существует
грамматика $\Gamma(A,n)$, в которой выводимы все графы, размеченные в 
$A$,
выводимые в какой-либо грамматике с $\leq 2$  вершинами в  правой  части
каждого правила и $\leq n$  ребрами  при  каждой  из  этих  вершин. Эта
грамматика получается объединением всех таких правил с терминалами
из $A$ и одним, кроме начального, нетерминалом.

ЛЕММА. {\it Граф $G$ выводим в $\Gamma(A,n)$ тогда и только тогда, когда  в
ней выводима любая его связная компонента.}

ДОКАЗАТЕЛЬСТВО. Пусть  любая  компонента  выводима,  а  всего
компонент $K$. Тогда  сначала  выведем  граф  из $K$  изолированных
нетерминальных вершин, отщепляя их по одной. Затем из этих  вершин
выведем по компоненте. Пусть, наоборот, $G$  выводим  и  мы  хотим
доказать выводимость компоненты $K$.  Возьмем  вывод $G$.  Начиная  с
начала  вывода,  преобразуем  его  следующим  образом.  Пусть   на
очередном шаге применяется  правило $\eta \longrightarrow B$.  Каждую  
терминальную
вершину  из $B$,  которая  в  конце  не  принадлежит $K$ и  каждую
нетерминальную вершину, из которой в конце выведется  подграф,  не
пересекающийся с $K$, удалим из $B$. Удалим  из $B$  также  все  ребра,
включая  висячие, которые в окончательном графе не принадлежат $K$.
Поскольку по  предположению  индукции  все  ребра  текущего  графа
принадлежат $K$, новое  правило $\eta \longrightarrow B'$  применимо.  
Применим  его.
Очевидно, что продолжая так ограничивать первоначальный  вывод  на
$K$, получим вывод $K$ в $\Gamma(A,n)$. Лемма доказана.

Из доказанной леммы следует, что перебирая грамматики $\Gamma(A,n)$
по возрастанию $n$  мы  найдем,  используя  алгоритм  из  теоремы~6,
грамматику $\Gamma$, в которой выводим $G$,  и  построим  его  вывод. Этот
вывод  мы  будем  представлять  в   виде   бинарного   дерева $D$ с
размеченными вершинами.  Каждая  вершина  дерева $D$  соответствует
вершине промежуточного графа в выводе,  узел ---  нетерминальной,  а
лист  ---  терминальной.  Каждый  узел  помечен  примененным  в  нем
правилом  вывода,  каждой  вершине  правой  части  этого   правила
соответствует вершина дерева, смежная с данным узлом в направлении
от корня. В пометке узла также ставится символ  $u$.  Лист  помечен
той же пометкой,  что  и  соответствующая  ему  вершина  графа $G$,
указывается также  степень  этой  вершины. Формуле $\Phi$  сопоставим
детерминированный автомат $A$,  работающий  на  деревьях. $A$  будет
допускать дерево вывода тогда и только тогда, когда на  выведенном
графе истинна $\Phi$. Пусть ${\cal M}$ - машина, стоящая в  бескванторной  
части
$\Phi$, а $P$ --- подграф графа $G$, имеющий не более $n$ граничных ребер 
($n$ ---
параметр $\Gamma$). Рассмотрим подграф $P$ изолированно от остальной  
части
$G$ вместе с граничными ребрами, которые перенумерованы. Пусть  есть
следующий способ работы ${\cal M}$ на $P$. ${\cal M}$, работая на $P$, может 
выходить из
$P$ и входить в $P$. Входить в $P$ ${\cal M}$  может  по  произвольному  ребру  
в
произвольном состоянии.  Войдя  в  подграф $P$,  разметка  которого
определяется  всей  предыдущей   работой ${\cal M}$,   она   работает   в
соответствии со своей  программой  до  очередного  выхода  или  до
остановки в заключительном состоянии. Выходы и  входы  чередуются.
Если начальная вершина находится в $P$, ${\cal M}$  начинает  работу  в  ней,
иначе входит  в $P$.  Посещаемость  каждой  вершины $P$  ограничена,
поэтому число входов и выходов тоже ограничено. Если ${\cal M}$ заканчивает
работу в $P$, то она должна остановиться в заключительном состоянии,
а если ${\cal M}$ последний раз вышла из $P$ (в любом  состоянии),  то  может
больше не входить, в частности возможна пустая работа ${\cal M}$, когда  она
в $P$ вообще не входила. Каждому такому способу работы соответствует
последовательность $S$ номеров ребер, по которым ${\cal M}$  входила  в $P$  
и
выходила из него, с приписанной каждому номеру  информацией:  вход
или выход совершает ${\cal M}$; состояние, в которое переходит ${\cal M}$.  
Длина $S$
не превышает $2nK$, где $K$ ---  максимальное  число  посещений  одной
вершины. $S$  назовем  реализуемым  следом  машины ${\cal M}$   на $P$,   а
последовательности вида $S$ и длины $\leq 2nK$ --- следами. Таким  образом
подграфу $P$ соответствует множество реализуемых следов, не зависящее
от его внешности. Опишем  детерминированный  автомат $A_{1}$,  который
допускает дерево вывода тогда и только тогда,  когда ${\cal M}$  допускает
выведенный  граф.  Неначальными  состояниями  автомата $A_{1}$   будут
множества следов. $A_{1}$ будет двигаться от листьев к корню дерева.  В
листьях он находится в одном  и  том  же  начальном  состоянии.  В
каждом узле  состоянием $A_{1}$  будет  множество  реализуемых  следов
машины ${\cal M}$ для подграфа, выведенного из данного узла. Состояние 
$A_{1}$ в
очередной вершине $p$ определяется по состояниям в  двух  смежных  с
ней в направлении от корня вершинах $p_{1}$ и $p_{2}$ и  разметке  вершин 
$p$,
$p_{1}$, $p_{2}$.  Покажем  как  это  делается.  Для   всех   одновершинных
подграфов, соответствующих листьям, множество  реализуемых  следов
определяется непосредственно по  пометке  листа.   Пусть  вершинам
$p$,$p_{1}$,$p_{2}$  соответствуют  подграфы $P$,$P_{1}$,$P_{2}$.   Построим   
множество
реализуемых следов для $P$ по множествам реализуемых следов для $P_{1}$ и
$P_{2}$, а также информации о том, какие граничные к $P_{i}$ ребра  ведут  в
$P_{j}$, а какие в $G\setminus P$. Эту  информацию дает  правило  вывода,  
которым
помечена $p$.   Назовем   подробным    следом    для $P$    такую
последовательность $S'$, в которой указаны все переходы между $P_{i}$  и
$G\setminus P$ и между $P_{1}$ и $P_{2}$ с информацией:  направление  
перехода,  номера
ребра относительно $P_{i}$ и $P$ или $P_{1}$ и $P_{2}$, состояние  после  
перехода.
$S'$ реализуем, если существует способ работы ${\cal M}$  на $P$,  такой,  что
последовательность  всех   переходов ${\cal M}$   между $P_{1}$, $P_{2}$, 
$G\setminus P$
соответствует $S'$.  Назовем  проекцией $S'$  на $P_{i}$  след  для $P_{i}$,
получающийся вычленением из $S'$ переходов между $P_{i}$ и $G\setminus 
P_{i}$. Очевидно,
что длина $S'$ не превышает удвоенной длины  обычного  следа  и  что
обычный реализуемый след для $P$ является проекцией на $P$  некоторого
реализуемого подробного следа. Поэтому  достаточно  узнать,  какие
подробные     следы     реализуемы.    Но    очевидно:\\
$(S'\ {\rm реализуем})\Longleftrightarrow ({\rm проекции}\ S'\ {\rm на}\ P_{1}\ {\rm 
и}\ P_{2}\ {\rm реализуемы})$.

$A_{1}$ допускает $D$, если в корне его  состояние  ---  множество  из
одного пустого следа. В [3] доказано, что  проекция  и  дополнение
множества деревьев, распознаваемого  детерминированным  автоматом,
тоже   распознаются   детерминированными   автоматами.    Операция
обобщения выражается через проекцию и дополнение:  это  дополнение
до проекции  дополнения.  Операция  проекции  на  графах  означает
проекцию на деревьях их вывода  по  разметке  в  листьях,  но  это
несущественно, так как в узлах, помеченных символом  $u$,  автомат
может не обращать внимание на ``лишние'' компоненты. Таким  образом,
производя  согласно  формуле $\Phi$  операции  проекции  и  обобщения,
построим искомый автомат $A$. Запустив его на $D$, узнаем  истинна  ли
$\Phi$. Теорема 8 доказана.

\section{Связь с решетками}

В этом разделе мы  попытаемся  оценить  ту  же  проблему  с
другой  стороны.  С.Ф.Сопрунов  доказал  в  [4],  что  для   любой
грамматики существует $n$ такое,  что  граф,  представляющий  собой
плоскую  квадратную  решетку  размера $n\times n$,   невыводим   в   этой
грамматике. Это  следует  также   из   совокупности   результатов
теоремы~8 и следующей теоремы.

ТЕОРЕМА 9. {\it Проблема  истинности  некоторой  фиксированной 
$\sigma_{1}$
формулы на размеченной  квадратной  решетке NP-полна  от  размера
решетки.}

ДОКАЗАТЕЛЬСТВО.  Выше  мы   рассматривали   детерминированную
машину,  работающую  на   графах,   но   можно   рассматривать   и
недетерминированную, программа  которой  не  является  однозначной
функцией. Заметим, что класс $\sigma_{1}$  это  множества,  распознаваемые
такой недетерминированной  машиной  с  ограниченной  посещаемостью
вершины.  Возьмем  обычную  ленточную  недетерминированную  машину
Тьюринга ${\cal M}$,  работающую  полиномиальное  время   и   распознающую
NP-полный    предикат.    Промоделируем    работу ${\cal M}$     работой
недетерминированной машины ${\cal M}_{1}$  на  данной  решетке.  При  этом  
на
каждой горизонтали в разметке будет записана конфигурация ${\cal M}$ в один
момент  времени.   Сначала   на   нижней   горизонтали   размечена
конфигурация ${\cal M}$  в  начальный  момент  времени.   Каждый   шаг ${\cal 
M}$
моделируется следующим образом. ${\cal M}_{1}$ переходит  вверх  на  
следующую
горизонталь  и, проходя с одного края  до  другого,  размечает  ее
вершины. Из каждой вершины ${\cal M}_{1}$  идет  вниз,  определяет  по  
нижней
вершине и двум ее соседям  какая  буква  должна  стоять  в  данной
вершине. Очевидно, что ${\cal M}_{1}$  проходит  по  каждому  ребру  не  более
четырех раз. Теорема 9 доказана.

Некоторые  основания  считать  семейство  решеток  простейшим
семейством, для которого не существует полиномиального  алгоритма,
выясняющего  истинность  формулы  из   иерархии,   дает   теорема,
доказанная Н.Робертсоном и П.Д.Сеймуром в [5]. Из нее следует,  что  для
любого $n$  существует  грамматика такая,  что   если   граф   не имеет 
миноров (см. [5]), изоморфных
решетке размера $n\times n$, то он выводим в этой
грамматике.

\section{Графовые машины: случай неограниченного ветвления}

Очевидно, что графы,  выводимые  в  одной  грамматике,  имеют
ограниченную  степень  ветвления.  В  [7] К. Ю. Горбунов  предложил  понятие
делимости, обобщающее выводимость на графы неограниченной  степени
ветвления. Будем рассматривать процессы деления конечного графа на
подграфы: каждый не одновершинный подграф,  возникший  в  процессе
деления на очередном  шаге  делится  на  два  подграфа,  пока  все
подграфы не станут одновершинными. Скажем, что подграф $B$  графа $G$
отделим от своего дополнения $\leq n$ вершинами, если можно так выделить
$\leq n$ вершин графа $G$, что любое граничное к $B$ ребро  инцидентно  хотя
бы одной  из  выделенных  вершин.  Вершины  из $B$  будем  называть
внутренними, из $G\setminus B$ --- внешними.

ОПРЕДЕЛЕНИЕ. Граф  называется $n$-делимым,  если   существует
процесс его деления, в котором каждый возникающий подграф  отделим
от своего дополнения $\leq n$ вершинами.

Под $n$-делимостью подграфа будем понимать его $n$-делимость  как
графа   с   учетом   граничных   ребер.   Теорема~6,    доказанная
А.О. Слисенко, обобщается, как показал К.Ю. Горбунов, на понятие делимости 
следующей теоремой.

ТЕОРЕМА 10. {\it Существует алгоритм, который по графу $G$ и числу $n$
выясняет, является ли $G$ $n$-делимым, и  если  является, то  строит
процесс его  деления.  При  фиксированном $n$  время  работы  этого
алгоритма полиномиально зависит от размера $G$.}

ДОКАЗАТЕЛЬСТВО. Пусть $B$ ---  подграф  графа $G$,  отделенный  от
своего дополнения $\leq n$ отмеченными вершинами.  Назовем  вершину $g\in 
G$
{\it богатой для} $B$, если ей инцидентно $>n$ граничных к $B$ ребер  (кратные
ребра считаются одним ребром). Деление $B$ на  две  части,  одна  из
которых одновершинная, назовем отделением соответствующей вершины.

ЛЕММА. {\it После отделения любой отмеченной внутренней вершины $g$
подграф $B\setminus \{g\}$ будет отделим от дополнения $\leq n$ вершинами. 
Если $b$  ---
богатая внутренняя вершина и $B$ $n$-делим, то $B\setminus \{b\}$ $n$-делим  
за  не
большее, чем для $B$, число шагов деления. Если $B$ несвязный  подграф, то
($B$ $n$-делим)$\Longleftrightarrow$(любая его связная компонента $n$-
делима).}

ДОКАЗАТЕЛЬСТВО. Первое предложение  леммы  очевидно.  Докажем
второе. Процесс деления $B$  индуцирует  некоторый  процесс  деления
подграфа $B\setminus \{b\}$. Пусть $C$  ---  какой-либо  подграф,  возникший  на
промежуточном этапе второго процесса, а $C'$ ---  соответствующий  ему
подграф процесса деления $B$.  Достаточно  показать,  что  если $C'$
отделим от дополнения $\leq n$ вершинами, то и $C$ тоже. Если $C'=C$  то все
доказано. Пусть $C'=C+\{b\}$. Так как $b$ --- богатая  внутренняя  вершина
для $B$, то она богатая и для $C'$. Поскольку отмеченных для $C'$ вершин
$\leq n$, то все концы граничных к $C'$ ребер, инцидентных $b$ не могут быть
отмечены для $C'$. Поэтому $b$ отмечена для $C'$. Но $C$ получается из $C'$
отделением $b$ и по первому  предложению  леммы  отделим  от  своего
дополнения $\leq n$ вершинами. Последнее предложение  леммы  следует  из
того, что процесс деления $B$ индуцирует процесс  деления  на  любой
его компоненте. Лемма доказана.

Пусть подграф $B$ $n$-делим и отмечены $\leq n$ вершин, отделяющих  его
от  дополнения.  Покажем,  что  можно  так  отделить  от $B$  часть
внутренних  отмеченных  вершин,  чтобы  после  каждого   отделения
оставшаяся часть была бы $n$-делима, а  в  конце  она  не  имела  бы
богатых внутренних вершин. Отделяем от $B$ одну из  его  богатых,  а
значит и отмеченных внутренних вершин. Оставшийся  подграф $B_{1}$  по
лемме $n$-делим. Богатая для $B_{1}$ внутреняя вершина $b_{1}$ могла  не  
быть
богатой для $B$. Но каждое инцидентное ей граничное к $B_{1}$ ребро  либо
граничное и  к $B$,  либо  ведет  в  отмеченную  для $B$  отделенную
внутреннюю вершину. Поэтому $b_{1}$ отмечена для $B$, иначе бы  больше 
$n$
смежных с ней вершин были  бы  отмечены  для $B$,  что  невозможно.
Отделяя $b_{1}$ от $B_{1}$ получим $B_{2}$ и так далее, пока у $B_{i}$  не  
останется
богатых внутренних вершин,  что  произойдет  за $\leq n$  шагов.  Таким
образом, если $G$ $n$-делим, то существует такой процесс его  деления,
при котором для любого возникающего в  этом  процессе  подграфа $B$
сначала отделяются $\leq n$ вершин, а затем оставшийся  подграф $B'$,  не
имеющий богатых внутренних вершин, делится на связные  компоненты.
Очевидно, что для $B'$ число внешних граничных  неотмеченных  вершин
не более $n^{2}$. Будем называть такие вершины  присоединенными  к $B'$.
Будем рассматривать совокупности: множество $M$ из $\leq n$ вершин графа 
$G$
с указанием какие из них внешние, а какие внутренние; множество $P$
из $\leq n^{2}$ присоединенных внешних вершин; связную компоненту  
подграфа
$G\setminus P$, содержащую все внутренние  вершины  и  отделенную  от  
своего
дополнения множеством $M$. Будем по  шагам  составлять  список  всех
таких совокупностей, в которых связная компонента $n$-делима.  После
$m$-го шага в нашем списке  будут  все  совокупности  с  компонентой,
$n$-делимой не  более  чем  за $m$  делений  и,  возможно,  некоторые с 
компонентой,
$n$-делимой более чем за $m$ делений. На $(m+1)$-ом шаге  мы  перебираем
все совокупности и для каждой совокупности $S$, не входящей  в   наш
список, делаем следующее. Угадываем два множества из $\leq n$ вершин 
$M_{1}$ и $M_{2}$
с указанием, какие вершины в каждом из них  внутренние
и какие внешние. Эти  множества  есть  предполагаемые  отделяющие
множества для двух частей $K_{1}$ и $K_{2}$, на  которые  мы  хотим  разбить
компоненту $K$ из $S$ и которые предполагаем $n$-делимыми за $\leq m$ 
делений.
Затем для  каждого $M_{i}$  угадываем  множества $O_{1}\subseteq M_{1}$  и 
$O_{2}\subseteq M_{2}$  тех
внутренних вершин, которые можно отделить и перевести во  внешние,
чтобы подграфы $K_{1}\setminus O_{1}$ и $K_{2}\setminus O_{2}$ остались бы 
$n$-делимыми и не имели  бы
богатых  внутренних  вершин.   Угадываем   множества $P_{1}$   и $P_{2}$
присоединенных для этих подграфов  вершин.  Пусть $V_{i}$ ($i=1,2$)  есть
объединенине множества внешних вершин из $M_{i}$  и  множества 
$O_{i}\bigcup P_{i}$.
Тогда, если все наши угадывания  верны,  подграфы $K_{1}\setminus O_{1}$  и 
$K_{2}\setminus O_{2}$
должны быть объединением  некоторых  связных  компонент  подграфов
$G\setminus V_{1}$ и $G\setminus V_{2}$ соответственно. Назовем  компоненты 
$G\setminus V_{1}$  первыми,  а
$G\setminus V_{2}$ вторыми. Попытаемся разбить подграф $K\setminus 
(O_{1}\bigcup O_{2})$  на  две  части
так, чтобы  одна  часть  была  объединением  некоторых  из  первых
компонент, а вторая --- вторых. Рассматриваем  лишь  те  компоненты,
которые лежат внутри $K\setminus (O_{1}\bigcup O_{2})$. Понятно,  что  к 
$K_{i}$  должны  быть
приписаны $i$-ые компоненты, удовлетворяющие  любому  из  следующих
трех условий.\\
1. Содержащие внутреннюю вершину из $M_{i}$.\\
2. Содержащие вершину из $V_{j}$ при $j\not= i$.\\
3. Имеющие граничное ребро, не инцидентное ни  одной  вершине   из
$M_{j}$ при $j\not= i$.

Легко видеть по условию 2,  что  любая  оставшаяся   неприписанной
$i$-ая компонента либо строго вложена в некоторую $j$-ую  компоненту
($j\not= i$), либо совпадает с  ней.  В  первом  случае $i$-ая  компонента
никуда не приписывается, так как $j$-ая уже приписана по условию  2.
Во втором случае, если $j$-ая компонента уже приписана, то $i$-ая  не
приписывается, а  если  не  приписана,  то  по  условиям  1   и  3
``спорная'' компонента не содержит внутренних вершин из $M_{1}$ и $M_{2}$,  
а
любой внешний конец граничного к ней ребра принадлежит и $M_{1}$ и 
$M_{2}$.
Приписываем ее в произвольную часть. После  этого  проверяем,  что
любая вершина из $K\setminus (O_{1}\bigcup O_{2})$ принадлежит ровно  одной  
части.  Легко
видеть, что истинность этого условия не зависит от того,  куда  мы
приписали ``спорные'' компоненты. То, что множества $M_{1}$ и $M_{2}$ 
являются
отделяющими  для построенных $K_{1}$  и $K_{2}$,  следует  из  проверенного
условия и условия 3. Если $K$ $n$-делим  за $m+1$  шагов  и  все  наши
угадывания были верными, то все выбранные  компоненты  должны  уже
быть в нашем списке. Пусть они там  есть.  Покажем,  что  тогда $K$
$n$-делим, возможно за $>m+1$ шагов. Опишем процесс деления $K$. Делим 
$K$
на $K_{1}$ и $K_{2}$. Отделяем от $K_{i}$ по одной все вершины из $O_{i}$, 
при этом по
лемме  граница  остается $\leq n$.  Подграфы $K_{1}\setminus O_{1}$  и 
$K_{2}\setminus O_{2}$  делим  на
связные компоненты. Эти компоненты, как мы убедились ранее, есть в
списке,  значит  они $n$-делимы.  Их  делением  процесс  кончается.
Поскольку   количество   совокупностей   и   способов   угадывания
ограничено  полиномом  от  размеров $G$  при  фиксированном $n$,  то
описанный алгоритм искомый. Теорема 10 доказана.

Рассмотренные  ранее  детерминированные  машины   на   графах
ограниченной    степени    ветвления    могут    быть     обобщены
недетерминированными    машинами,    работающими     на     графах
неограниченной степени ветвления. Вершины графов,  как  и  прежде,
размечены  буквами  некоторого  алфавита.  Ребра  тоже   размечены
буквами некоторого алфавита, а не перенумерованы, как было раньше.
Разные ребра могут иметь одинаковые пометки. В графе выделена одна
начальная вершина. Опишем недетерминированную  машину,  работающую
на таких графах с числом посещений каждой вершины $\leq K$. Она задается
набором $\langle A,B,Q,q_{0},F\rangle$, компоненты $A$, $Q$, $q_{0}$ которого 
те же, что и
в детерминированном случае. $B$ это алфавит разметки ребер  графа.
Программа $F$ это функция.  Область  ее  определения  ---  множество
наборов $\langle q,a,k\rangle$, где $q\in Q$ --- текущее состояние  машины,  а 
$a\in A$  ---
буква, которой помечена текущая вершина, $k\leq K+1$ ---  число  посещений
текущей  вершины  с   учетом   текущего.   Если $k\leq K$,   а $q$   ---
незаключительное состояние, то  значением $F$  является  множество,
элементы которого  ---  наборы $\langle q',a',(b,b')\rangle$.  Здесь $q'$  ---  новое
состояние машины, $a'\in A$ --- новая  пометка  текущей  вершины, $b\in B$  ---
пометка ребра, по которому машина сдвигается из  текущей  вершины,
$b'\in B$ --- новая пометка этого ребра. Если $k=K+1$,  значением  является
безрезультатная остановка. Если $q$ --- заключительное состояние, $k\leq K$,
то машина допускает граф.  В  начале  работы  машина  находится  в
начальной   вершине   и   в   начальном   состоянии.   Потом   она
недетерминированно действует по своей программе, причем на  каждом
шаге недетерминированно  выбирает  ребро  с  данной  пометкой,  по
которому сдвигается. Каждая машина определяет множество графов, на
которых существует допускающий их  способ  работы.  Назовем  такие
множества распознаваемыми.

ТЕОРЕМА 11. {\it Объединение  и  пересечение  двух  распознаваемых
множеств являются распознаваемыми.}

ДОКАЗАТЕЛЬСТВО. Объединение, очевидно,  допускается  машиной,
которая является формальным объединением машин, где два  начальных
состояния  ``склеены''  в  одно.  Чтобы  доказать  утверждение   для
пересечения, докажем следующую лемму.

ЛЕММА. {\it Для любой  машины ${\cal M}$  существует  машина ${\cal M}'$,  
которая
распознает то же множество графов, что и ${\cal M}$, и заканчивает работу в
начальной вершине.}

ДОКАЗАТЕЛЬСТВО.  Модифицируем ${\cal M}$   так,   чтобы   она   имела
возможность вернуться из текушей вершины в начальную. Это делается
следующим образом. В процессе работы каждой вершине $a$,  посещенной
машиной, присваивается четность противоположная той, которую имеет
вершина, из которой машина впервые пришла в $a$.  Нечетные  вершины
помечаются специальным символом $\alpha_{1}$, а  четные  --- $\alpha_{2}$.  При  
каждом
переходе из вершины $a_{1}$ в $a_{2}$ ребро $l$, по которому совершен 
переход,
помечается кроме основного еще специальным символом $\beta'$.
Если $a_{2}$ уже была  посещена  (в  этом
случае она помечена $\alpha_{1}$ или $\alpha_{2})$, то ${\cal M}'$ за два шага туда  
и  обратно
стирает символ $\beta'$ с $l$ (никакое другое ребро в этот момент символом
$\beta'$ не помечено). Иначе, ${\cal M}'$ за те же два шага заменяет $\beta'$ на 
$\beta_{1}$, если $a_{1}$ четная или на $\beta_{2}$, если нечетная.
Чтобы вернуться в начальную вершину, ${\cal M}'$ должна пройти по  цепи  из
ребер с чередующимися пометками $\beta_{1}$ и $\beta_{2}$. Лемма доказана.

Машина,  распознающая  пересечение  множеств   распознаваемых
машинами ${\cal M}_{1}$ и ${\cal M}_{2}$, строится так. Машина ${\cal M}_{1}$  
переделывается  в ${\cal M}'$,
которая работает  в  соответствии  с  программой ${\cal M}_{1}$  и,  если ${\cal 
M}_{1}$
допускает граф,  возвращается в начальную  вершину.  Информацию  о
первоначальной  разметке ${\cal M}'$ сохраняет.  К ${\cal M}'$   последовательно
подсоединяется ${\cal M}_{2}$. Теорема 11 доказана.

Определим классы $\sigma_{n}$ и $\pi_{n}$ для  случая  неограниченной  степени
ветвления  и $n\geq 1$.  Класс $\sigma_{1}$  это  класс  всех  распознаваемых
множеств. Класс $\pi_{1}$  это  класс  множеств,  дополнение до  которых
является распознаваемым множеством. Класс $\sigma_{n+1}$ состоит из 
проекций
множеств класса $\pi_{n}$.  Класс $\pi_{n+1}$  состоит  из  обобщений  
множеств
класса $\sigma_{n}$. Здесь операции проекции  и  обобщения  производятся  по
разметкам и вершин   и   ребер.   Теорема~4   справедлива   и    в
недетерминированном случае. Отличие ее доказательства лишь в  том,
что в бескванторной части формулы фигурирует (возможно, под знаком
дополнения)  недетерминированная  машина.   Теорема~8   обобщается
следующей теоремой.

ТЕОРЕМА 12. {\it Существует алгоритм, который по графу $G$ и формуле
$\Phi$ из недетерминированной иерархии выясняет истинна ли $\Phi$ на $G$.  
При
фиксированной $\Phi$ и  фиксированном $n$  для $n$-делимых  графов  время
работы этого алгоритма полиномиально зависит от размера $G$.}

ДОКАЗАТЕЛЬСТВО. Перебирая по возрастанию  натуральные  числа,
мы найдем, используя алгоритм из теоремы~10, минимальное $n$  такое,
что $G$ $n$-делим, и построим процесс его деления.  Докажем  следующую
лемму, которую сообщил автору К.Ю. Горбунов.

ЛЕММА 1. {\it Если граф $G$ $n$-делим и есть процесс его  деления,  то
можно  для  каждого  возникающего  подграфа $P$  так  отметить $\leq n$
отделяющих вершин, чтобы при его делении на $P_{1}$  и $P_{2}$  выполнялись
следующие условия:}\\
1. {\it Если вершина $a \notin P$ и $a$ отмечена для $P_{i}$, то $a$ отмечена для 
$P$.}\\
2. {\it Если $a\in P_{i}$ и $a$ отмечена для $P$, то $a$ отмечена для $P_{i}$.}\\
3. {\it Если $a\in P_{i}$ и $a$ отмечена для $P_{j}$ ($j\not= i$), то $a$ отмечена 
для $P_{i}$.}

ДОКАЗАТЕЛЬСТВО. Для каждого $P$ пусть $n_{1}(P)\leq n$ ---  
минимальное число такое, что
существует система из $n_{1}$ вершин, отделяющая $P$ от $G\setminus P$.  
Среди  всех
отделяющих систем мощности $n_{1}$ отметим систему с минимальным числом
внешних вершин.

Докажем утверждение 1. Рассмотрим множество $M$ вершин из $G\setminus 
P$,
отмеченных для $P_{i}$, но не для $P$.  Пусть  вопреки  утверждению $M\not= 
\emptyset$.
Пусть $C$ --- множество вершин из $P_{i}$, соединенных ребром с вершиной из
$M$ и не отмеченных для $P_{i}$. Предположим, что $|C|>|M|$. Очевидно,  все
вершины из $C$  отмечены  для $P$,  а  любое  граничное  к $P$   ребро
инцидентное  вершине  из $C$  ведет  либо  в $M$,  либо  в  вершину,
отмеченную для $P$.  Поэтому,  если  заменить  для $P$  множество $C$
отмеченных вершин на $M$, получится система, отделяющая $P$ от 
$G\setminus P$  и
меньшая по мощности. Это противоречит минимальности первоначальной
системы. Предположим, что $|C|\leq |M|$. Любая вершина из $P_{i}$, смежная  с
вершиной из $M$ либо лежит в $C$, либо отмечена для $P_{i}$. Поэтому,  если
заменить для $P_{i}$ множество $M$  отмеченных  вершин  на $C$,  получится
система,  отделяющая $P_{i}$  от $G\setminus P_{i}$.   Она   будет   не   больше
первоначальной, а внешних к $P_{i}$ вершин будет меньше. Противоречие.

Докажем утверждение 2. Рассмотрим множество $M$ вершин  из $P_{i}$,
отмеченных для $P$, но не для $P_{i}$. Пусть $M\not= \emptyset$.  Пусть $C$  --
-  множество
вершин из $G\setminus P$, соединенных ребром с $M$  и  не  отмеченных  для 
$P$.
Предположим, что $|M|\leq |C|$. Очевидно, $C$ отмечено для $P_{i}$. Заменим 
для
$P_{i}$ $C$ на $M$. Получим систему отделяющих  вершин  для $P_{i}$  с  
меньшим
количеством внешних вершин, что  противоречит   минимальности   системы.
Предположим, что $|M|>|C|$. Заменим для $P$ $M$ на $C$.  Получим  систему
отделяющих  для $P$  вершин,   меньше   предыдущей.   Противоречие.

Доказательство   утверждения~3   получается   из    доказательства
утверждения~2 заменой $G\setminus P$ на $P_{j}$ и $P$  на  $P_{j}$.  Лемма~1
доказана.

Будем считать, что для всех рассматриваемых  далее  подграфов
система отделяющих вершин берется такой,  как  при  доказательстве
леммы~1.

Процесс деления $G$ будем представлять в виде бинарного  дерева
с  размеченными  вершинами.  Каждой   вершине $p$   этого   дерева
соответствует подграф $P$, возникший  в  процессе  деления.  Если $p$
узел, то двум его ``сыновьям'' $p_{1}$ и $p_{2}$ соответствуют два подграфа 
$P_{1}$
и $P_{2}$, на которые делится $P$.  Пусть $V(p)$  ---  множество  вершин $G$,
отмеченных для хотя бы одного  из  подграфов $P,\,P_{1},\,P_{2}$.  Занумеруем
$V(p)$. В разметке $p$ указываются номера элементов множества $V(p)$ и 
для каждого
номера говорится, для какого подграфа  соответствующая  вершина $g$
отмечена, лежит ли она в $P,\,P_{1},\,P_{2}$, принадлежит ли она $V(p_{1})$, 
где $p_{1}$
--- ``отец'' $p$ и, если да, то какой номер она там имеет. Если $g\in V(p)$,
то  для  каждой  буквы $b\in B$  указываается $\min(2K,m)$,  где $K$   ---
максимальное число посещений одной вершины, а $m$ --- число  граничных
к $P$ ребер, помеченных $b$ и инцидентных $g$. Указывается также наличие
всех ребер, оба конца которых являются отмеченными (возможно,  для
разных подграфов) и пометки этих ребер. Будем называть такие ребра
отмеченными. В пометке узла также ставится символ $u$.  В  пометке
листа  указывается  пометка  соответствующей  ему  вершины  и  то,
начальная ли она. Формуле $\Phi$ сопоставим  детерминированный  автомат
$A$, работающий на деревьях. $A$ будет допускать дерево деления  тогда
и только тогда, когда на  первоначальном графе истинна $\Phi$. Пусть ${\cal M}$
--- недетерминированная машина, фигурирующая в  бескванторной  части
$\Phi$, а $P$ --- подграф графа $G$,  отделенный  от  своего  дополнения $\leq 
n$
отмеченными  перенумерованными  вершинами.  Рассмотрим  подграф $P$
изолированно от остальной части $G$ вместе с  граничными  ребрами  и
отмеченными вершинами. Пусть есть следующий способ работы ${\cal M}$ на 
$P$.
${\cal M}$, работая на $P$, может выходить из $P$ и входить в $P$. Перед 
входом в
$P$ $M$  может  находиться  в  произвольном  состоянии  и  входить  по
произвольному   ребру,   пометка   которого   соответствует   шагу
программы. Войдя в подграф $P$, у которого разметка вершин  и  ребер
(в том числе граничных) определяется всей  предыдущей  работой ${\cal M}$,
она недетерминированно работает в соответствии со своей программой
до очередного выхода или до остановки в заключительном  состоянии.
Выходы и входы чередуются. Если начальная вершина находится в $P$, ${\cal 
M}$
начинает работу в ней,  иначе  входит  в $P$.  Посещаемость  каждой
вершины в $P$  ограничена,  поэтому  число  входов  и  выходов  тоже
ограничено.  Если ${\cal M}$  заканчивает  работу  в $P$,  то  она   должна
остановиться в заключительном состоянии, а если ${\cal M}$  последний  раз
вышла из $P$ (в любом состоянии), то  может  больше  не  входить,  в
частности возможна пустая работа ${\cal M}$,  когда  она  в $P$  вообще  не
входила.   Каждому    такому    способу    работы    соответствует
последовательность $S$ номеров отмеченных вершин, которым инцидентны
ребра переходов. Если  ребро,  по  которому ${\cal M}$  вошла  или  вышла,
инцидентно двум отмеченным вершинам, то вместо одного номера  в $S$
указывается пара номеров. Каждому номеру приписывается информация:
вход или выход совершает ${\cal M}$;  состояние,  в  которое  переходит ${\cal 
M}$;
пометки ребра,  по  которому  переходит ${\cal M}$  до  перехода  и  после
перехода.  Длина $S$  ограничена  $2nK$,  где $K$   ---   максимальная
посещаемость вершины. $S$ назовем реализуемым следом машины ${\cal M}$ на 
$P$,
а последовательности вида $S$  и  длины $\leq 2nK$  ---  следами.  Способ
работы ${\cal M}$  будем  называть  реализацией  следа $S$.  Таким  образом
подграфу $P$ соответствует множество реализуемых  следов,  зависящее
только от $P$, его  граничных  ребер  и  отмеченных  вершин.  Опишем
детерминированный автомат $A_{1}$,  который  допускает  дерево  деления
тогда и только  тогда,  когда ${\cal M}$  допускает  первоначальный  граф.
Неначальными состояниями $A_{1}$  будут  множества  следов. $A_{1}$  будет
двигаться от листьев к корню дерева. В  листьях  он   находится  в
одном и том же начальном состоянии. В каждом  узле  состоянием $A_{1}$
будет   множество   реализуемых    следов ${\cal M}$    для    подграфа,
соответствующего этому узлу. Состояние $A_{1}$ в  очередной  вершине $p$
определяется по состояниям в двух ее ``сыновьях'' $p_{1}$ и $p_{2}$ и разметке
вершин $p,\,p_{1},\,p_{2}$. Покажем как это делается. Для  всех  
одновершинных
подграфов,  являющихся  листьями,  множество  реализуемых   следов
определяется непосредственно по разметке. Пусть вершинам $p$, $p_{1}$, 
$p_{2}$
соответствуют подграфы $P$, $P_{1}$, $P_{2}$. Построим  множество  
реализуемых
следов для $P$ по множествам  реализуемых  следов  для $P_{1}$  и $P_{2}$  и
разметке $p$.   Назовем   подробным    следом    для $P$    такую
последовательность $S'$, в которой указаны все переходы между $P_{i}$  и
$G\setminus P$ и между $P_{1}$ и $P_{2}$ с информацией:  направление  
перехода,  номера
отмеченных вершин для $P_{i}$ и $P$ или $P_{1}$ и $P_{2}$, которым 
инцидентно ребро
перехода, пометки этого ребра до и  после  перехода,  состояние ${\cal M}$
после перехода. $S'$ реализуем, если существует способ работы ${\cal M}$  на
$P$ такой, что последовательность всех переходов ${\cal M}$ между $P_{1}$, 
$P_{2}$,
$G\setminus P$  соответствует $S'$.  Очевидно,  что  длина $S'$  не   превышает
удвоенной длины обычного следа и что обычный реализуемый след  для
$P$ является  проекцией  на $P$  некоторого  реализуемого  подробного
следа.  Поэтому   достаточно   узнать,   какие   подробные   следы
реализуемы.  Покажем,  что   для   существования   реализации $S'$
необходимо и достаточно,  чтобы $S'$  удовлетворял  следующим  трем
условиям.

1. Проекции $S'$ на $P_{1}$ и $P_{2}$ реализуемы.

2. Пометка  каждого  отмеченного   ребра $l$   перед   очередным
прохождением по нему  совпадает  с  пометкой $l$  после  последнего
прохождения по нему, а перед первым  прохождением  ---  с  начальной
пометкой.

3. Перед  каждым  переходом  в $S'$  между $P$  и $G\setminus P$  по  ребру,
инцидентному отмеченной для $P$ внутренней вершине $g$, существует $>0$
граничных к $P$ ребер, инцидентных $a$ и имеющих пометку, указанную  в
данном переходе.

Необходимость данных условий очевидна. Докажем достаточность.
Обозначим проекции $S'$ на $P_{1}$ и $P_{2}$ через $S_{1}$ и $S_{2}$. Пусть 
мы построили
начало реализации следа $S'$ и проекции этого  начала  на $P_{1}$  и $P_{2}$
совпадают с началами некоторых реализаций следов $S_{1}$  и $S_{2}$.  Пусть
нам предстоит сделать очередной  переход,  которому  в $S'$  должен
соответствовать  очередной  член $s$.   Продолжим   реализацию $S'$
следующим образом. Возможны следующие два случая.

СЛУЧАЙ 1. Переход из $P_{i}$ в $P_{j}$. Переберем возможные подслучаи.

а) Для $P_{i}$ и $P_{j}$ в $s$  указаны  внутренние  отмеченные  вершины.
Тогда переход совершается по отмеченному ребру $l$, пометка которого
совпадает согласно  условию  2  с  пометкой  в $s$.  Очевидно,  что
дальнейшая реализуемость $S_{i}$ и $S_{j}$ не зависит  от  того,  по  какому
ребру с данной пометкой, инцидентному данной внутренней отмеченной
вершине, машина ${\cal M}$ выйдет или войдет. Поэтому, совершив переход  по
$l$, ${\cal M}$  совершит  выход  из $P_{i}$  и  вход  в $P_{j}$  в  соответствии  с
реализациями $S_{i}$ и $S_{j}$.  Затем ${\cal M}$  проработает  в $P_{j}$  и  
продолжит
реализацию $S_{j}$ до следующего перехода.

б) Для $P_{i}$ отмечена только внутренняя вершина, для $P_{j}$ --- только
внешняя. ${\cal M}$ входит в $P_{j}$,  продолжая  реализацию $S_{j}$  до  
следующего
перехода.

в) Для $P_{i}$ отмечена только внешняя вершина, для $P_{j}$  ---  только
внутренняя.  Машина  входит  в $P_{j}$,  продолжая  реализацию $S_{i}$,  и
работает в $P_{j}$ в соответствии с реализацией $S_{j}$.

г) Для $P_{1}$ и $P_{2}$ в $s$ указаны внешние отмеченные вершины.  Тогда
по утверждению~3 леммы~1 эти вершины отмечены  и  как  внутренние.
Данный случай свелся к случаю а).

СЛУЧАЙ 2. Переход между $P_{i}$ и $G\setminus P$.

а) Для $P_{i}$ отмечена  внутренняя  вершина,  для $P$  ---  внешняя.
Совершаем переход по отмеченному ребру, имеющему в силу условия  2
нужную пометку. Если совершен вход в $P_{i}$, ${\cal M}$  продолжает  работу  
в
соответствии с реализацией $S_{i}$.

б) И для $P_{i}$ и для $P$ отмечена только  внутренняя  вершина.  По
условию 3 существует  граничное  к $P$  ребро,  инцидентное  этой
вершине и имеющее нужную пометку. По нему и совершаем переход.

в) И для $P_{i}$ и для $P$ отмечена только внешняя вершина.  Переход
совершается в соответствии с реализацией $S_{i}$.

г) Для $P_{i}$ отмечена внешняя вершина, для $P$ --- внутренняя. Тогда
по  утверждению~1  леммы~1  внешняя  отмеченная  для $P_{i}$   вершина
отмечена и для $P$.  Внутренняя  для $P$  вершина  по  утверждению~2
леммы~1 отмечена и для $P_{i}$. Данный случай свелся к случаю а).

Таким образом мы продолжим начало реализации $S'$ на один  член
и снова проекции этого начала совпадают с началами реализаций $S_{1}$ и
$S_{2}$. Значит,  мы  можем  по  шагам  реализовать $S'$.  Достаточность
доказана.

Очевидно, что истинность приведенных трех условий проверяется
по $S'$.  Возможность  найти  множество  реализуемых  для $P$  следов
доказана. Автомат $A_{1}$ допускает дерево, если в корне его  состояние ---
непустое множество следов.

Докажем возможность построения искомого автомата $A$.  Выразим
формулой в монадической теории дерева тот факт, что его  разметка,
несущая информацию о реберной разметке  графа,  корректна.  Каждой
вершине $g$ из $G$ поставим в соответствие  множество $M(g)$  вершин $D$
таких, что $g$ отмечена или для  подграфа,  соответствующего  данной
вершине, или для хотя бы одного из двух его сыновей, на  которые
он делится. Таким образом $M(g)=\{p\mid g\in V(p)\}$.

ЛЕММА 2. {\it Для любой вершины $g$ графа $G$ множество $M(g)$ связно  в
$D$. Для любого ребра $(g_{1},g_{2})$ из $G$ $M(g_{1})\bigcap M(g_{2})\not= 
\emptyset$.}

ДОКАЗАТЕЛЬСТВО. Вершине $g$ соответствует  в $D$  путь $l(g)$  от
корня к листу, вдоль которого $g$  ---  внутренняя  вершина.  В  силу
минимальности семейства отмеченных вершин, $g$  отмечена  в  листе.
Следовательно, в силу утверждения~2 леммы~1,  вершины  из $l(g)$, в
которых $g$  отмечена, составляют  непустой  отрезок  от  некоторой
вершины до листа. Пусть $p\in M(g)$ и $g$ ---  внешняя  отмеченная  вершина
для подграфа $p$. Из утверждения~1 леммы~1 следует, что на всем пути
от $p$  до $l(g)$ $g$   остается   внешней   отмеченной   вершиной.
Следовательно,  весь  этот  путь,  включая  его   конец $p_{1}\in l(g)$,
принадлежит $M(g)$. Из утверждения~3 леммы~1 следует, что для сына
подграфа $p_{1}$,  принадлежащего $l(g)$, $g$  ---  внутренняя  отмеченная
вершина. Следовательно, этот сын лежит на вышеупомянутом отрезке
и связность $M(g)$ доказана. Докажем второе утверждение леммы. Пусть
$p_{1}$ --- наиболее удаленная от корня вершина, лежащая и на $l(g_{1})$ и  на
$l(g_{2})$. Очевидно, для любого ее сына отмечена либо $g_{1}$  либо $g_{2}$.
Если и $g_{1}$ и $g_{2}$ отмечены для одного из сыновей, то $p\in 
M(g_{1})\bigcap M(g_{2})$.
Иначе, пусть например $g_{1}$ в сыновьях не отмечена.  Пусть $p_{2}$  ---
наименее удаленная от корня вершина на $l(g_{1})$, для которой отмечена
$g_{1}$. Тогда для отца  вершины $p_{2}$  отмечена $g_{2}$  и  он,  очевидно,
принадлежит $M(g_{1})\bigcap M(g_{2})$. Лемма~2 доказана.

Каждой вершине $g\in G$ сопоставим следующую разметку $R_{g}$ дерева 
$D$.
В каждой вершине дерева указано целое неотрицательное  число.  Оно
отлично от нуля в точности на $M(g)$ и равно в $p\in D$ номеру $g$ в $V(p)$.
Напомним, что основная разметка $D$ задает для каждой  пары  смежных
вершин $p_{1}$,$p_{2}$ из $D$ соответствие между номерами вершин  из 
$V(p_{1})$  и
$V(p_{2})$.

ЛЕММА 3. ({\it Числовая разметка $R$  дерева $D$  с  непустой  связной
ненулевой частью есть $R_{g}$ для  некоторой $g\in 
G$})$\Longleftrightarrow$({\it Для  любых  смежных
$p_{1}$,$p_{2}$ из $D$, номера $R$ в $p_{1}$,$p_{2}$ согласованы с основной 
разметкой $D$}).

ДОКАЗАТЕЛЬСТВО. Утверждение $\Longrightarrow$  очевидно.  Докажем  
обратное.
Возьмем  вершину $p\in D$,  где $R(p)\not= 0$.  Номеру $R(p)$   соответствует
некоторая $g\in G$. Так как $M(g)$ связно в $D$, то в силу  согласованности
$R$ совпадает с $R_{g}$ на $M(g)$, а в силу связности ненулевой части  ---  и
на $D\setminus M(g)$. Лемма 3 доказана.

Таким образом, вершины графа $G$ можно моделировать  разметками
дерева $D$  вышеописанного  вида.  Ребра $G$   можно   по   лемме~2
моделировать парами $(R_{1},R_{2})$ таких разметок,  где $R_{1}$  и $R_{2}$  
имеют
непустое ненулевое пересечение. Связность ненулевой части $R$  можно
выразить так: для любой разметки $R'$ такой, что для любой $p\in D$  если
$R'(p)\not= 0$, то $R'(p)=R(p)$, выполняется:
$$
(\forall(p_{1},p_{2})(R'(p_{1})\not= 0\ \&\ R(p_{2})\not= 0\Rightarrow 
R'(p_{2})\not= 0))\Longrightarrow (R'=R)
$$
Здесь $(p_{1},p_{2})$ --- ребро из $D$.  Понятие ``вершина $p\in D$''  
моделируется
разметкой $D$ единицей в $p$  и  нулями  в $D\setminus p$,  а ``ребро 
$(p_{1},p_{2})$''  -----
разметкой с единицами в $p_{1}$ и $p_{2}$. Корректность разметки  
отмеченных
ребер на $D$ заключается в том, чтобы  одни  и  те  же  ребра  имели
одинаковые пометки. В силу связности $M(g_{1})\bigcap M(g_{2})$, где 
$(g_{1},g_{2})$  ---
ребро, эта корректность выражается в  согласованности  с  числовой
разметкой $D$ и проверяется автоматом очевидным образом.  Корректная
разметка в $D$ отмеченных ребер однозначно определяет разметку ребер
в $G$. Поэтому осталось выразить согласованность  с  ней  той  части
разметки $D$, которая  указывает  число  ребер  с  данной  пометкой,
инцидентных данной отмеченной вершине. Эта  согласованность  имеет
место,  если  для  любой $p\in D$  и   любой   вершины $g$   из $V(p)$
выполняется: $\mathop{\&}\limits_{i=1}^{N}\,\mathop{\&}\limits_{b\in B}$(число  
граничных  ребер   с   пометкой $b$
инцидентных $g$ равно $i$)$\Longleftrightarrow$(в $p$ при номере вершины $g$ 
стоит $i$).
Здесь $N=\min(2K,m)$,  при $i=N$  в  левой   части   эквивалентности
подразумевается ``не меньше $i$''. Принадлежность $g$ к $V(p)$  означает,
что разметка $R_{g}$ не нулевая в $p$,  а  существование $i$  различных
граничных  ребер  инцидентных $g$  с  пометкой $b$   означает,   что
существует $i$ различных вершинных разметок $R$ с непустыми ненулевыми
пересечениями $R\bigcap R_{g}$ и пометкой $b$  в  них  таких,  что  (вершина  с
номером $R(p)$ указана в разметке $D$ как внешняя к 
$p$)$\Longleftrightarrow$(${\it g}$ указана  как
внутренняя  к $p$).

Опишем  порядок  построения  автомата $A$.   В
кванторной приставке формулы $\Phi$ выражаем понятие ``реберная разметка
графа $G$''(это означает корректность разметки на $D$) вышеописанным
способом. Получаем формулу $\Phi'$ на $D$. В силу того,  что  проекция  и
дополнение автоматного множества деревьев являются автоматными,  и
коньюнкция двух автоматных множеств автоматна, можно построить  по
автомату $A_{1}$ искомый автомат $A$, проверяющий истинность $\Phi'$ на 
$D$, что
равносильно истинности $\Phi$ на $G$. Теорема 12 доказана.

Пусть мы  ограничиваем  не  число  посещений  машиной  каждой
вершины, а лишь число прохождений по каждому ребру. Покажем, что в
этом случае существует формула из $\sigma_{1}$, проблема истинности  
которой
на 2-делимых графах NP-полна от  размера  графа.  Возьмем  обычную
ленточную  недетерминированную   машину   Тьюринга ${\cal M}$,   задающую
NP-полный предикат, время работы которой на  отрезке  ленты  равно
$p(|x|)$, где $p$ --- полином, $x$ --- входное  слово. Этот  отрезок  будем
представлять  размеченной  цепью.  Соединим  каждые  две  соседние
вершины этой цепи $p(|x|)$ ребрами. В разметке вершин  укажем  через
одну от края четные и нечетные  вершины.  В  разметке  ребер  тоже
укажем чередующиеся четные и нечетные пучки кратных ребер, а также
каждое ребро пометим числом 0. Смоделируем ${\cal M}$ работой машины ${\cal 
M}'$
на полученном графе с проходом по каждому ребру  не  более  одного
раза. Каждый раз ${\cal M}'$ идет по ребру, помеченному 0, и  меняет  эту
пометку на 1. Если текущая вершина  четная,  то,  например,  при
команде ``направо'' ${\cal M}'$ идет по четному ребру, а  если  нечетная,  то
наоборот.

\section{Гиперграфы}

Напомним,  что  гиперграфом  называется  множество  вершин  и
гиперребер, где гиперребро --- произвольное  подмножество  множества
вершин. Будем рассматривать гиперграфы с размеченными вершинами.

Подгиперграфом $P$ гиперграфа $G$ назовем подмножество вершин $G$ и
те  гиперребра,  которые  целиком  лежат  в   этом   подмножестве.
Гиперребра, которые частично в нем лежат, назовем граничными к $P$.
Под размером гиперграфа будем понимать сумму числа  его  вершин  и
числа гиперребер.  Процесс  деления  множества  вершин  гиперграфа
определяется так же, как для графа.

ОПРЕДЕЛЕНИЕ. Гиперграф называется $n$-делимым, если  существует
такой  процесс  его  деления,  при  котором   каждый   возникающий
подгиперграф имеет не более $n$ граничных гиперребер.

ТЕОРЕМА 13. {\it Существует алгоритм, который по  гиперграфу $G$  и
числу $n$ выясняет, является ли $G$ $n$-делимым и, если является, строит
процесс его  деления.  При  фиксированном $n$  время  работы  этого
алгоритма полиномиально зависит от размера $G$.}

ДОКАЗАТЕЛЬСТВО. Назовем подгиперграф $P$ гиперграфа $G$  связным,
если  для   любых   двух   его   вершин ${\bf p}_{1}$   и ${\bf p}_{2}$   существует
последовательность вершин ${\bf p}_{1},\,{\bf x}_{1},\,{\bf x}_{2},\ldots {\bf 
x}_{k},\,{\bf p}_{2}$  такая,  что  любые
две соседние в ней вершины принадлежат одному гиперребру, лежащему
целиком  внутри $P$.  Очевидно,  если $P$  несвязен,  он  однозначно
разбивается  на  связные  компоненты.  Под $n$-делимостью $P$  будем
понимать $n$-делимость $P$  как  гиперграфа,  но  с  учетом  граничных
гиперребер.

ЛЕММА. {\it ($P$ $n$-делим)$\Longleftrightarrow$(любая его связная 
компонента $n$-делима).}

ДОКАЗАТЕЛЬСТВО. Пусть $P$ $n$-делим, $K$ --- его связная  компонента.
Рассмотрим пересечение подгиперграфа $P'$,  возникшего  в  процессе
деления $P$, с $K$. Так как $K$ --- компонента, не  существует  гиперребра
граничного к $K$ и целиком лежащего в $P'$.  Поэтому,  число  граничных
гиперребер у $P'\bigcap K$ не больше, чем у $P'$. Значит  процесс  деления $P$
индуцирует  процесс  деления $K$.  Обратно,  если   любая   связная
компонента $P$ $n$-делима, то сначала делим $P$ на компоненты,  отщепляя
их по одной. При этом число граничных гиперребер не увеличивается.
Лемма доказана.

Очевидно, число связных  подгиперграфов  гиперграфа $G$  с $\leq n$
граничными  гиперребрами  полиномиально  от   размера $G$.   Будем
составлять список тех из этих  подгиперграфов,  которые $n$-делимы.
Пусть перед очередным  шагом  в  списке  есть  все  подгиперграфы,
$n$-делимые за $\leq m$ делений. На очередном шаге для каждого кандидата $K$
на то, чтобы быть помещенным в список, делаем следующее. Угадываем
множество $R$, $|R|\leq n$ гиперребер, целиком лежащих в $K$ и граничных  к
двум частям $K_{1}$ и $K_{2}$ на которые по предположению можно разделить 
$K$.
Угадаем также разбиение граничных к $K$ гиперребер на три множества:
граничные только к $K_{1}$, только к $K_{2}$ и  к  обеим  частям.  Удалением
множества $R$, $K$ разбивается на связные компоненты, которые  назовем
мелкими  компонентами.  Каждая  мелкая   компонента $K'$   должна,
очевидно, быть компонентой одной из $K_{i}$. Поэтому, если $K$ $n$-делим  и
все наши угадывания верны, то среди граничных к $K'$  гиперребер  не
могут быть одновременно гиперребра граничные только к $K_{1}$ и  только
к $K_{2}$.  Проверим  это  условие.  Пусть  оно  выполняется.  Связные
компоненты подгиперграфов $K_{1}$  и $K_{2}$  должны  быть  среди  мелких.
Поэтому  из  леммы  следует,  что  все  мелкие  компоненты  должны
находиться в  нашем  списке.  Пусть  и  это  условие  выполняется.
Покажем, что тогда $K$ $n$-делим и, следовательно, его можно занести в
список. Определим $K_{1}$ и $K_{2}$ следующим  образом.  Мелкие  
компоненты,
все  граничные  гиперребра  которых  являются   по   предположению
граничными к $K_{i}$,  отнесем  в $K_{i}$ (те,  для  которых  это  условие
выполнено и для $i$=1 и для $i$=2,  отнесем  в  произвольную  часть).
Очевидно, что граничных гиперребер у $K_{i}$ не более $n$. Разделим $K$  на
$K_{1}$ и $K_{2}$. Затем делим $K_{1}$ и $K_{2}$ на компоненты, отщепляя их 
по  одной.
Полученные  мелкие компоненты делим дальше. Таким образом заполним
весь  список. Очевидно: ($G$ $n$-делим)$\Longleftrightarrow$(любая   его   
связная   компонента
$n$-делима). Теорема 13 доказана.

Подобно тому, как для $n$-делимых графов  эффективно  разрешима
проблема допускания их машиной,  для $n$-делимых  гиперграфов  тоже
есть подобная проблема. Пусть каждому гиперребру $l$  гиперграфа $G$
соответствует конечная коммутативная полугруппа $D_{l}$ и  в  ней  есть
подмножество $D'$. Пусть для каждого гиперребра $l$ существует функция
$F_{l}$ из алфавита пометок вершин $A$ в $D_{l}$. Тогда каждой вершине из 
$l$  с
пометкой $a$  соответствует  элемент $F_{l}(a)\in D_{l}$.  Если  для  каждого
гиперребра $l$ сумма элементов, соответствующих  всем  его  вершинам
принадлежит $D'$, то будем говорить, что  есть  допустимая  разметка
гиперграфа $G$.

ТЕОРЕМА 14. {\it Существует алгоритм, который по гиперграфу $G$  и
конечным коммутативным полугруппам $D_{l}$  для  каждого  гиперребра $l$
вместе с функциями $F_{l}$ из алфавита разметки $A$ в $D_{l}$ и 
подмножествами
$D'\subseteq D_{l}$  выясняет,  существует  ли  допустимая  разметка $G$  или  
не
существует. При фиксированном $n$ для $n$-делимых  гиперграфов  время
алгоритма полиномиально зависит от размера $G$ и от $\max|D_{l}|$.}

ДОКАЗАТЕЛЬСТВО. Пользуясь алгоритмом  из  теоремы~13  находим
минимальное $n$ такое, что $G$ $n$-делим, и строим процесс его  деления.
Этот процесс будем представлять в виде дерева деления. Пусть $P$  ---
некоторый подгиперграф, возникший в процессе деления.  Пусть $F$  ---
функция, сопоставляющая каждому граничному к $P$ гиперребру  элемент
из $D_{l}$. Назовем такую функцию граничной. Скажем, что $F$  реализуема
на $P$, если существует разметка вершин $P$ такая, что сумма элементов
$D_{l}$, соответствующих вершинам любого гиперребра $l$, лежащего 
целиком
внутри $P$, принадлежит $D'$, а для любого граничного к $P$ гиперребра $l$
сумма элементов $D_{l}$, соответствующих его  вершинам,  лежащим  в $P$,
есть $F(l)$. Каждому подгиперграфу $P$ в  дереве  деления  поставим  в
соответствие множество реализуемых на  нем  граничных  функций,  а
если у $P$ нет  граничных  гиперребер,  то  также  указание  на  то,
существует ли допустимая разметка $P$.  Идя  по  дереву  деления  от
листьев к корню, будем вычислять эту информацию. Для одновершинных
подгиперрафов в листьях она  определяется  непосредственно.  Пусть  мы
хотим узнать множество реализуемых граничных функций для $P$,  зная
его для $P_{1}$ и $P_{2}$, где $P=P_{1}\bigcup P_{2}$. Перебираем  пары 
$F_{1},F_{2}$  реализуемых
функций для $P_{1}$ и $P_{2}$. Пара $F_{1},F_{2}$ определяет  некоторую  
реализуемую
граничную функцию $F$ для $P$ тогда и только тогда, когда  для  любого
гиперребра $l$, лежащего целиком в $P$, но не лежащего  целиком  ни  в
$P_{1}$, ни в $P_{2}$: $F_{1}(l)+F_{2}(l)\in D'$. В этом случае, для любого  
граничного
к $P$  гиперребра $l$: $F(l)=F_{1}(l)+F_{2}(l)$,    где    слагаемое
$F_{i}(l)$ отсутствует, если $P_{i}$ не пересекается  с $l$.  Обратно,  любой
реализации функции $F$ для $P$ соответствуют  некоторые $F_{1}$,$F_{2}$.  
Таким
образом, дойдя до корня дерева, ответим на вопрос о  существовании
допустимой разметки для $G$. Теорема 14 доказана.

\end{document}


