Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v3(3-4)/golovanov-193-209.pdf Дата изменения: Fri May 8 16:41:48 2009 Дата индексирования: Tue Oct 2 00:16:03 2012 Кодировка: Windows-1251

Об обходе лабиринтов автоматами, оставляющими след в вершинах лабиринта
А.В. Голованов

1 Введение
Впервые проблему обхода лабиринтов автоматами поставил К. Шеннон в начале шестидесятых годов. Будахом [1] было показано, что не существует автомата, обходящего произвольный лабиринт. Для более узких классов лабиринтов задача обхода автоматами рассмотрена в [2], [3]. Что же касается произвольных лабиринтов, то для решения проблемы обхода необходимо рассматривать автоматы, обладающие дополнительными возможностями. В работе [4] рассмотрен автомат, расставляющий (по своему выбору) в вершинах лабиринта нестираемые отметки. Интерес представляет случай, когда автомат "принудительно"оставляет отметки в посещенных вершинах лабиринта. На содержательном уровне это можно проиллюстрировать как след, оставляемый на поверхности планеты аппаратом или как запах, оставляемый животным. Однако, решение задачи обхода для автоматов, обладающих таким свойством, встречает затруднения, и в данной работе будет рассмотрено естественное обобщение этой задачи.

2 Основные понятия. Формулировка полученного результата
Основные определения, касающиеся автоматов и лабиринтов, взяты из [5]. Пусть X - некоторое индексированное семейство множеств, множество индексов A - конечно. Через будем обозначать отображение проектирования произведения A X на его -й сомножитель X . Пусть L = (V , ) - связный ориентированный граф, V - множество вершин, - множество дуг, эти множества будем обозначать V (L) и (L). Пусть = (u, v ) . Обозначим -1 дугу (v , u). Если в графе L вместе


с дугой (u, v ) содержится дуга (v , u), то эту пару дуг будем называть ребром и обозначать u, v . Граф L называется симметрическим, если (u, v ) u, v . Пусть v V . Обозначим v = { |1 ( ) = v } - множество дуг, "выходящих"из вершины v . Система вращения графа L есть множество {v |v V }, где v циклическая перестановка множества v . Стороной графа называется множество дуг 1 , . . . , n ; i = (ui , vi ) такое, что: 1) ui = vi-1 , i = 2, . . . , n; u1 = vn - 2) i = ui (i-11 ), i = 2, . . . , n; 1 = u1 (n 1 ) - 3) все дуги 1 , . . . , n - различные. Понятие стороны, таким образом, связано с системой вращения графа. Замечание. 1) Каждая дуга симметрического графа (с некоторой системой вращения) принадлежит одной и только одной стороне. 2) У конечного графа число сторон конечно. Пусть M R2 , N R2 , M = N , M N = ai + bj , a, b R, i, j - единичные координатные векторы декартовой системы координат на плоскости. Будем говорить, что uv , u, v V (L) идет в направлении n, если a = 0, b > 0; в направлении e, если a > 0, b = 0; в направлении s, если a = 0, b < 0; в направлении w, если a < 0, b = 0. Обозначим D = {n, e, s, w}. Пусть и - алфавиты букв и , которые берутся в качестве отметок вершин и дуг графа соответственно, = . Лабиринтом назовем связный симметрический граф, не имеющий петель и кратных дуг, такой, что разным дугам, выходящим из одной вершины, приписаны разные отметки. Класс лабиринтов, имеющих в качестве отметок вершин и дуг алфавиты и , обозначим как L(, ). Отметку дуги и вершины v будем обозначать | | и |v |, степень вершины v , то есть количество выходящих из нее дуг, будем обозначать deg(v ). Множество T отрезков на плоскости назовем конфигурацией, если любые два различных отрезка из T могут иметь не более одной общей точки, и, если таковая имеется, то она обязательно является концевой для обоих отрезков. Лабиринт L называется прямоугольным, если 1) = D. 2) u, v V , если (u, v ) , то отрезок uv идет в направлении |(u, v )|. 3) множество отрезков T = {uv |u, v V } является конфигурацией. Прямоугольный лабиринт с выделенной начальной вершиной v0 будем называть инициальным лабиринтом и обозначать Lv0 . 194


Пусть - циклическая перестановка множества {n, e, s, w}. Определим отображение "поворота по часовой стрелке"в вершине v : (v , r) = (r), где = min{m N | v : | | = r}, r D. i (v , r) = (v , i-1 (v , r)), i 2; -1 (v , r) = r : (v , r ) = r. Дугу, выходящую из вершины v в направлении r D обозначим (v , r). Будем считать в дальнейшем, что множества v упорядочены следующим образом: v = { (v , r), . . . , deg(v) (v , r)}. Тогда с графом связана система вращения "по часовой стрелке". При этом каждая сторона H может быть обойдена по "правилу правой руки то есть, если переходить, начиная с некоторой дуги i = (ui , vi ), i H к дуге (vi , (vi , |i-1 |)), и так далее, то все дуги данной стороны будут обойдены. Множество R2 \ L является открытым и, в общем случае несвязным. Если L - прямоугольный лабиринт, то число компонент связности R2 \ L равняется числу сторон. Если это число равно k , то лабиринт называют k -связным. Пусть Aq0 = (A, Q, B , , , q0 ) - инициальный автомат. Aq0 будем называть допустимым для лабиринтов из L(, ), если его входной алфавит состоит из букв a вида ( , {1 , .., n }), где и {1 , .., n } , и выходной алфавит есть Ч ( {}), , при этом всегда 2 ( (an , qn )) / 2 (an ) {}. Всюду в дальнейшем будем рассматривать только допустимые для того или иного класса лабиринтов автоматы. Будем считать, что в качестве алфавитов, которыми могут быть нагружены вершины некоторого лабиринта L, взяты конечные отрезки натурального ряда: EM = {0, 1, . . . , M -1}, т.е. L L(EM , D). Пусть KM = {1, 2, . . . , M - 1}, D = { = d D}. В дальнейшем, для краткости будем писать i (at , qt ) вместо i ( (at , qt )), i = 1, 2. Функционирование Aq0 в Lv0 понимаем следующим образом: в начальный момент отметки всех вершин лабиринта равны 0 (не окрашены) и автомат, находящийся в состоянии q0 , помещается в начальную вершину v0 . Если в некоторый момент времени t автомат находится в вершине vt , то входной буквой at является пара, состоящая из отметки вершины и множества отметок дуг, выходящих из данной вершины. В следующий момент, если 2 (at , qt ) = , автомат остается в вершине vt , иначе перемещается в вершину 2 ( (vt , 2 (at , qt ))), заменяя при этом отметку вершины vt на 1 (at , qt ), и в любом случае переходя в состояние (at , qt ). 195


Автоматом, оставляющим след, будем называть инициальный автомат Aq0 = (A, Q, B , , , q0 ) такой, что A = E2 Ч D , B = 1 Ч {D }. Таким образом, автомат Aq0 окрашивает в "отметку 1"каждую вершину, в которой он побывал в процессе функционирования. Будем называть отметку 1 следом. Рассмотрим следующее обобщение этого автомата. Автоматом с M красками будем называть инициальный автомат Aq0 = (A, Q, B , , , q0 ) такой, что A = EM +1 Ч D , B = KM +1 Ч {D }, причем выполнены условия: чn чn+1 M n N, 2 (an , qn ) 2 (an ), чn - номер краски в момент времени n, ч0 = 1, чn+1 =чn + 1 (an , qn ). В силу определения автомата Aq0 , чn M n N (номер краски не убывает и не превосходит максимального номера краски из множества KM ). Aq0 является допустимым для лабиринтов из класса L(EM +1 , D). Класс таких автоматов будем обозначать AM . Класс автоматов, оставляющих след, таким образом, будет совпадать с A1 . Поведением Aq0 в Lv0 называется последовательность пар = i (Aq0 , Lv0 ), i (Aq0 , Lv0 ) = (qi , vi ), i N0 . Если для v V (L) n N0 : v = 2 (n (Aq0 , Lv0 )), то говорим, что Aq0 обходит вершину v . Обозначим Int(Aq0 , Lv0 ) - множество вершин лабиринта, которые обходятся автоматом. Если Int(Aq0 , Lv0 ) = V (L), то говорим, что Aq0 обходит лабиринт Lv0 , если Aq0 обходит лабиринт Lv v V (L), то говорим, что Aq0 сильно обходит лабиринт L. Пусть Lk - класс k -связных лабиринтов, для которых допустимы автоматы из рассматриваемого класса.

обходит L, причем M 198k .

Теорема 1 k N Aq0 A

M

: L Lk , M = M (k ), Aq0 сильно

3 Обход лабиринтов с использованием одного алгоритма обхода
Рассмотрим алгоритм A обхода графов, являющихся прямоугольными лабиринтами. У таких графов 1 deg(v ) 4 v V (L). Пусть лабиринт L - k -связный (следовательно, L имеет k сторон), ni - число дуг в стороне Hi . Пусть nmax = max{ni }. Алгоритм A работает в дискретном времени и, просматривая вершину vt в момент времени t, формирует две таблицы: основную W (L) размера nmax Ч k и вспомогательную Z (L) размера 2 Ч (k - 1).

196


1) инициализация: v0 - начальная вершина, |0 | - начальное направление (где 0 = min(v0 )). Дуга 0 принадлежит некоторой стороне, которую мы назовем первой. Записываем в первую строку первым элементом вершину v0 , переходим к п.2. Обозначения (см. рис. 1): пусть в вершину v мы пришли из вершины u. Обозначим направления, а также вершины, в которые из v ведут дуги в этих направлениях, как C -1 (v ) = |(v , u)|, C i (v ) = i (v , |(v , u)|), i = 1, 2, . . . , deg(v ).

C 2 (vn , r
6

n-1

)

C 1 (vn , r

n-1

) vn s

6

C 3 (vn , r -1

n-1

)

rn C
-1

vt .

(vn , rn-1 ) Рис. 1. Пусть совершается обход i-й стороны, текущую вершину будем обозначать

?

2) 1-обход: совершаем обход стороны по правилу правой руки, т.е., пока обход не закончен, переходим от вершины vt к вершине vt+1 = C 1 (vt ), вершину vt+1 записываем очередным элементом в i-ю строку, снова выполняем п.2. Обход стороны будет завершен, если vt = wi0 и C 1 (vt ) = wi1 , в этом случае переходим к п.3. Замечание. В i-й строке к этому моменту записаны все вершины, принадлежащие i-й стороне. 3) 2-обход: двигаемся по вершинам i-й стороны в порядке их записи в таблицу W . Для вершин степени больше двух проверяем по порядку вершины C 2 (vt ) и C 3 (vt ), записаны они в таблицу W или нет. 3.1) Пусть проверяем j -й элемент i-й строки и одна из вершин C 2 (vt ), C 3 (vt ), например C 2 (vt ), отсутствует в таблице. Это означает, что C 2 (vt ) находится на новой стороне, отличной от всех сторон, записанных в таблицу W ранее. Пусть на этот момент в таблицу записаны m строк, тогда новую сторону назовем (m+1)-й, запишем в m-ю строку вспомогательной таблицы Z два натуральных числа: номер строки i (т.е. номер стороны) и номер элемента строки j , в которых была обнаружена новая не обойденная вершина. Обнаруженная вершина объявляется первой вершиной (m + 1)й стороны, записывается первым элементом в новую, (m + 1)-ю строку 197


таблицы W . Направление |(wij , C 2 (wij ))| считаем начальным для (m + 1)й стороны. Будем говорить при этом, что из j -й вершины i-й стороны произошло углубление в (m + 1)-ю сторону. 3.2) Если при проверке wij все вершины множества {C 2 (wij ), . . . , C n (wij )}, n = deg(wij ) записаны в таблицу и вершина wij не последняя в i-й строке (т.е. j < ni ), переходим к следующей вершине строки и выполняем п.3. Если вершина wj - последняя, и вершины {C 2 (wij ), . . . , C n (wij )} записаны в таблицу, то 2-обход i-й стороны закончен. Если i = 1, то в (i - 1)-й строке вспомогательной таблицы записаны номер строки и вершины этой строки, из которых произошло углубление в i-ю сторону. 1 Переходим к продолжению 2-обхода h-й стороны, h = zi-1,1 , т.е. к п.3, начиная с g -го элемента, g = zi-1,2 . При этом говорим, что произошло возвращение из i-й стороны в h-ю. Алгоритм заканчивает работу, когда завершается 2-обход первой стороны. Пример графа L с занумерованными вершинами и матриц W (L) и Z (L), полученных в результате работы алгоритма A, показан на рис. 2 и 3, здесь начальная вершина - 1, начальное направление |(1, 2)|.

Рис. 2.

Рис. 3. Будем говорить, что алгоритм обходит вершину v лабиринта, если она заносится в таблицу. Алгоритм обходит лабиринт, если он обходит все его вершины. 198


Для доказательства некоторых утверждений об алгоритме A рассмотрим вспомогательный граф R(L), который будем строить по ходу выполнения алгоритма. Вершины графа R соответствуют сторонам лабиринта L, а из вершины r1 в вершину r2 ведет дуга в том и только в том случае, когда из стороны r1 происходит углубление в сторону r2 , причем дуги, выходящие из одной вершины, упорядочены по времени углубления. Существование цикла в графе R невозможно, так как если из вершины r1 на некотором шаге выходит дуга, то сторона r1 лабиринта уже полностью 1-обойдена, следовательно, все ее вершины записаны в таблицу W и углубления в r1 -ю сторону не происходит. Таким образом, поскольку число вершин R конечно, R является деревом, корнем которого является первая сторона, при углублении алгоритм переходит в вершину-потомок, при возвращении - в вершину-родитель. Нетрудно видеть, что при выполнении алгоритма происходит обход дерева R в глубину, следовательно, из каждой вершины R, не являющейся корнем произойдет возвращение, значит, будет закончен ее 2-обход (пример R-дерева для рассмотренного графа показан на рис. 4).

Рис. 4. Но после того, как будут 2-обойдены все вершины, в которые ведут дуги, выходящие из корня, будет закончен и 2-обход корневой вершины, таким образом, справедливо

Утверждение 1 Если был начат 2-обход некоторой стороны, то он
будет закончен за конечное время.
Таким образом, алгоритм заканчивает работу за конечное время. Назовем моментом времени T = T(L) момент, когда заканчивается 2-обход первой стороны. Будем иногда употреблять для вершин лабиринта термин "окрашена"вместо термина "обойдена поскольку для определенных выше автоматов с красками эти понятия совпадают. На момент T справедливы следующие утверждения.

199


Утверждение 2 Если вершина v V (L) 1-обойдена, то она и 2-обойдена
(Очевидно из алгоритма).
Другими словами, если вершина окрашена, то она была 2-обойдена в некоторый момент времени.

Утверждение 3 Не (u, v ) (L) : (|u| = 0) (|v | = 0). Доказательство. Пусть такая дуга существует. Тогда, по Утверждению
2, происходил 2-обход вершины u. Сразу заметим, что степень вершины u не менее трех, иначе вершина v была бы обойдена как соседняя для вершины u уже при 1-обходе u. Пусть deg(u) = 3, и при выполнении 2-обхода в вершину u мы пришли из вершины C -1 (u). Тогда вершины C -1 (u) и C 1 (u) были 1-обойдены, следовательно, неокрашенной может быть только вершина C 2 (u), но ее мы в этом случае обнаружим следующим же шагом 2-обхода, углубимся в нее и окрасим. Аналогично, если степень u равна четырем, доказываем, что v не может быть вершиной C 2 (u) и вершиной C 3 (u) при окрашенной C 2 (u). Остается рассмотреть случай, когда и C 2 (u), и C 3 (u) не окрашены. Тогда происходит углубление в сторону, которой принадлежит C 2 (u). Пусть номер этой стороны равен m. Если C 3 (u) также принадлежит стороне m, то C 3 (u) будет обойдена при 1-обходе, если не принадлежит, то C 3 (u) может остаться не окрашенной только до момента 2-обхода вершины C 2 (u), стороны m. В этот момент, если C 3 (u) осталась не окрашенной, алгоритм произведет углубление в сторону, которой принадлежит C 3 (u), и окрасит ее. Таким образом, оказываются окрашенными все соседние вершины для u, и мы приходим к противоречию.

Утверждение 4 Алгоритм обходит любой лабиринт за время T.
обходит, |v0 | = 0. Пусть существует не обойденная при t = T вершина w, |w| = 0. Тогда, в силу связности лабиринта, существует путь S , соединяющий вершины v0 и w. Но тогда существует дуга (u, v ) S : (|u| = 0) (|v | = 0), что противоречит Утверждению 3.

Доказательство. По крайней мере одну вершину (начальную) алгоритм

Доказательство теоремы 1
Нам нужно построить автомат с красками, реализующий алгоритм A, без использования таблиц W и Z , совершающий 1- и 2-обходы, углубление 200


и возвращение. Для этой цели будем расставлять в вершинах лабиринта метки т.е. краски, по которым автомат будет определять, в какой ситуации он находится. Будем считать пока, что число красок сколь угодно велико. В начале 1-обхода ставится метка, соответствующая направлению |(C -1 (vt ), vt )|, то есть направлению, в котором мы пришли в vt . Автомат определяет, что 1-обход закончен, если он попадает в вершину с меткой начала обхода, и направление |(C -1 (vt ), vt )| соответствует направлению, закодированному меткой. Аналогично автомат определяет окончание 2обхода. В течение 2-обхода алгоритм проверяет, обойдены ли вершины множества 2 {C (vt ), . . . , C deg(vt ) (vt )}, в соответствии с этим автомат, находясь в вершине vt , совершает "вылазки"в вершины C 2 (vt ), . . . , C n (vt ), возвращаясь, если вершина окрашена, и совершая углубление, если вершина не окрашена. При углублении, в соответствии с алгоритмом, начинается 1-обход новой стороны (с той вершины, которая была обнаружена неокрашенной при вылазке), при этом начальным направлением обхода считается направление |(vt , C 1 (vt ))|. Будем различать случаи углубления в вершины C 2 (vt ) и C 3 (vt ), поскольку при окончании 2-обхода (при возвращении в предыдущую сторону) необходимо вернутся именно к тому направлению 2-обхода предшествующей стороны, в котором он производился до углубления. Если 2-обход закончен в направлении r D, то для того, чтобы вернуться из C 2 -углубления в предшествующую сторону, переходим в нее в направлении -1 (r-1 ), в случае C 3 -углубления (которое возможно только в вершине степени 4) - в направлении -2 (r-1 ). Замечание 1. Метка начала 2-обхода каждой стороны будет "затирать"метку начала 1-обхода этой стороны и находиться в той же вершине. Замечание 2. Метки начал 2-обходов разных сторон находятся в разных вершинах и поэтому не затирают друг друга (поскольку новую метку мы всегда ставим в неокрашенную вершину). Таким образом, для реализации алгоритма необходимо 9 типов красок: метки, соответствующие 4-м направлениям начала обхода в случае 2 C -углубления, метки, соответствующие 4-м направлениям начала обхода в случае 3 C -углубления, один тип краски, закрашивающий все остальные вершины, в которых не стоит меток ("непомеченные"). Заметим, что по определению автомата с красками, при попадании на некоторую вершину автомат закрашивает ее своей текущей краской (обязательно оставляет отметку). Поэтому, для того, чтобы сохранять информацию об отметке начала обхода, будем поступать следующим образом. 201


Разобьем множество красок Km автомата Aq0 на отрезки длины 9 и не будем различать краски множества Km , номера которых равны по модулю 9. На каждом отрезке естественным образом вводится нумерация, также по модулю 9: 1,2,3,4 - метки начал обходов, соответствующие направлениям n,e,s,w, случай C 2 -углубления. 5,6,7,8 - метки начал обходов, соответствующие направлениям n,e,s,w, случай C 3 -углубления. 0 - основная краска (натуральное число, кратное 9). Таким образом, с точки зрения автомата Aq0 каждая вершина лабиринта либо не окрашена, либо в ней стоит одна из 8-ми меток, либо она окрашена основной краской. Теперь, если автомат попадает в вершину, отметка которой отличается по модулю 9 от номера текущей краски, причем эту отметку необходимо сохранить, автомат подбирает наименьший номер n, превосходящий номер текущей краски, такой, чтобы n совпадал по модулю 9 с отметкой вершины, и двигается дальше. Тогда отметка вершины будет нести ту же информацию, что и раньше. Если лабиринт L - k -связный, то в его вершинах автоматом Aq0 расставляется не более k меток, следовательно, главным образом вершины окрашиваются основной краской (поскольку вершин у лабиринта значительно больше, чем сторон). Поэтому типичным является случай, когда основная краска является текущей и метка окружена вершинами неокрашенными или окрашенными основной краской. В этом случае при прохождении через помеченную вершину, отметку которой необходимо сохранить, автомат "затрачивает"9 красок: если отметка равна n d 9), (mo то к номеру текущей краски прибавляется n, автомат окрашивает данную вершину, сохраняя отметку, затем требуется еще (9 - n) красок, чтобы текущая краска снова стала основной. В каждый момент времени t и в каждом состоянии q Q(Aq0 ), кроме начального, требуется знать направление |(C -1 (vt ), vt )|. Поэтому состояний qi , соответствующих каждому шагу алгоритма - четыре, по одному на каждое направление. В соответствии с этим закодируем состояния как qi , r , r D. Будем считать, что на входе Aq0 имеется также остаток от деления текущего цвета на 9, то есть автомат каким-то образом знает, какое число нужно прибавлять к текущему номеру краски, чтобы сохранить отметку помеченной вершины. Это сделано для упрощения изложения, но, в принципе, без этой входной информации можно было бы обойтись, храня информацию о текущей краске в состояниях автомата. Пусть n - отметка вершины vn ; (n) = 1, (e) = 2, (s) = 3, (w) = 4. чn+1 = чn + 1 (an , qn ) - наименьшее из возможных, равное по модулю 9 202


указанному в таблице. Задаем автомат функциями и (см. таблицу 1). Таким образом, построенный автомат реализует алгоритм A. Определим момент времени T как момент, в который будет 2-обойдена автоматом Aq0 первая сторона лабиринта L (сохраняя терминологию, относящуюся к алгоритму A). Замечание. К моменту времени T лабиринт L, согласно Утверждению 4, будет обойден, и нам не важно, как поведет себя автомат при t > T .

Лемма 1 Если лабиринт L - k -связный, то к моменту времени T автомат
Aq0 затратит не более 198k красок.

Доказательство. Каждой стороне соответствует одна метка начала обхода
этой стороны, таким образом, в вершинах лабиринта ставится не более k меток.
Состояние q0 q1 , rn-1 (n = (rn-1 )) (n = (rn-1 ) + 4) иначе q2 , rn-1 (n = (rn-1 )) (n = (rn-1 ) + 4) deg(vn ) 2 deg(vn ) > 2 n = (rn-1 ) n = (rn-1 ) + 4 q3 , rn-1 n = 0 n = 0 q4 , rn-1 deg(vn ) = 3 deg(vn ) = 4 q5 , rn-1 n = 0 n = 0 q6 , rn-1

rn = 2 (an , qn ) чn+1 mod 9 первое из v0 0 C 1 ( vn , r ) n n

(an , qn ) q1 , r0 q1 , r n q2 , rn-1

Примечание начальное 1-обход

n-1

2-обход

C 1 ( vn , C 2 ( vn , C -1 (vn C -1 (vn

rn-1 ) rn-1 ) , rn-1 ) , rn-1 )

n n 0 0 (rn-1 ) n n n

q2 , r n q3 , rn-1 q7 , -1 (vn , r q7 , -2 (vn , r q1 , r n q4 , rn-1 q2 , r q5 , r
n n

n-1 n-1

) )
вылазка в C 2 -вершину возврат из C 3 -вылазки вылазка в C 3 -вершину переход к следующей вершине при 2-обходе возвращение к соответствующей стороне

C 1 (vn , rn-1 ) C -1 (vn , rn-1 ) C 1 ( vn , r C 3 ( vn , r
n-1 n-1

) )

C 1 (vn , rn-1 ) (rn-1 ) + 4 C -1 (vn , rn-1 ) n C 1 (vn , rn-1 ) n

q1 , r n q6 , rn-1

q7 , r

n-1

C 1 ( vn , r

n-1

)

n

q2 , r

n-1

Таблица 1. 203


Пусть v - одна из помеченных вершин. При t T Aq0 может побывать в этой вершине самое большое: 3 раза при 1-обходах сторон, 12 раз при 2-обходах сторон, которым v принадлежит (если степень v равна 4), 7 раз при 2-обходах вершин, соседних с v (если все эти вершины степени 4). Четвертое попадание при 1-обходе нами не учтено, так как при этом сразу начинается 2-обход и это попадание по сути совпадает с первым для 2-обхода, которое мы и учитываем. Таким образом, на метку уходит не более (3 + 12 + 7) Ч 9 = 198 красок, всего на лабиринт - не более 198k красок.

Следствие 1 (Теорема 1) k N Aq0 AM : L Lk , M = M (k ), Aq0 сильно обходит L, причем M 198k . Замечание. Количество красок, затраченных на данную вершину, зависит
от ее расположения, степени и степеней ее соседей, наибольшее количество красок для данного алгоритма равно 198. Можно показать, что в самом лучшем случае на помеченную вершину затрачивается не менее двух красок, так что 2k M 198k .

4 Дополнение
Назовем двусвязным лабиринт, у которого число сторон k равно двум (см. рис. 5).

Рис. 5.

Предложение 1 В случае k = 2 Aq0 A1 такой, что L L2 Aq0
сильно обходит L.

204


Автомат с одной краской обязательно окрашивает вершину, из которой выходит (в краску 1), таким образом, каждая вершина лабиринта либо окрашена в 0 (при этом автомат в ней не был, вершину будем называть неокрашенной), либо окрашена в 1 (будем называть ее просто окрашенной). Пусть H1 - одна сторона двусвязного лабиринта L, H2 - его вторая сторона. Пусть Vi = {v V (L)| Hi : 1 ( ) = v }, i = 1, 2 - множество вершин стороны. Непустое множество вершин, общих для обеих сторон Vc = V1 V2 назовем циклом лабиринта L, а множество Vi0 = Vi \ Vc , i = 1, 2 внутренними точками стороны Hi . Если множество Vi0 несвязно, то, очевидно, каждая из компонент связности Vi0 , которые мы будем называть отростками, является деревом. Корнем отростка назовем вершину цикла, соседнюю с данным отростком. Пусть в вершину u мы пришли из v . Введем обозначения (см. рис. 6): L(u) = C 1 (u), R(u) = C deg(u)-1 (u), B (u) = C -1 (u) = v , LL(u) = L(L(u)), RR(u) = R(R(u)).
s 6 6 s ?

LL ) L() (u u s s

us

R(su) RR(u) -s

B (u)
Рис. 6. Пусть v0 - начальная вершина, r D - начальное направление, т.е. то направление, по которому производится переход в соседнюю с начальной вершину. Сторону, которой принадлежит дуга (v0 , r), назовем первой, без ограничения общности считаем, что это H1 . Оставшуюся сторону назовем второй. Если начальная вершина принадлежит некоторому отростку, назовем его первым. Ситуацией 1 2 в вершине u назовем положение, когда |u| = 1, |L(u)| = 1, |R(u)| = 0.

L(u)u

uu
6

e

R(u)

Рис. 7. Ситуацией 2 3 - положение, когда |u| = 1, |L(u)| = 1, |LL(u)| = 1, |R(u)| = 0 или когда |u| = 1, |L(u)| = 1, |LL(u)| = 1, |R(u)| = 1, |RR(u)| = 0. 205


u

u

LL(u) L(u)

u e 6 R(u) u

или

u u e 6 R(u) RR(u) LL(u) L(u) u

u

u

Рис. 8. Рассмотрим алгоритм A обхода двусвязного лабиринта L: 1) 1-й этап обхода первой стороны: если ситуация 1 2, то переход в вершину L(u) и ко 2-му этапу. Иначе, обход по правилу правой руки. 2) 2-й этап: если ситуация 2 3, то переход в неокрашенную в ситуации 2 3 вершину и к 3-му этапу. Иначе, обход по правилу правой руки. 3) 3-й этап: обход второй стороны по правилу правой руки.

Утверждение 5 Ситуации 1 2 на 1-м этапе и 2 3 на 2-м этапе
не могут произойти в вершине отростка.

Доказательство. Пусть на 1-м этапе алгоритма ситуация 1 2 произошла в некоторой вершине u отростка, т.е. n момент времени, |u| = 1, |L(u)| = 1, |R(u)| = 0, vn = u, vn-1 = B (u). Пусть L(u) = uL , R(u) = uR , B (u) = uB - фиксированные вершины лабиринта. u Vi0 {(u, L(u)), (L(u), u), (u, R(u)), (B (u), u)} H1 . Поскольку окрашены вершины u и uL , то существует момент времени k < n такой, что либо алгоритм перешел от вершины uL к вершине u, либо наоборот. И в том, и в другом случае, поскольку в момент времени n - 1 алгоритм находился в вершине uB , существует момент m, k < m < n, в который алгоритм перешел из u в uB . Но так как на первом этапе происходит обход по правилу правой руки, то в момент времени m - 1 алгоритм перешел из uR в u, следовательно, uR окрашена. Противоречие. Аналогично доказывается, что на втором этапе алгоритма не может произойти ситуация 2 3. Утверждение 6 1) На 1-м этапе происходит обход всей первой стороны,
за исключением, быть может, некоторой части первого отростка. 1-й этап заканчивается, когда: 1. Окрашен весь цикл. 2. Окрашена одна вершина отростка второй стороны, соседняя с корнем этого отростка. 2) На 2-м этапе заканчивается обход первой стороны, 2-й этап заканчивается, когда найден отросток второй стороны, по крайней мере одна вершина которого не окрашена. 3) На 3-м этапе обходим вторую сторону.
206


Доказательство. 1) Из Утверждения 5 следует, что ситуация 1 2

может произойти только на цикле лабиринта. Пусть цикл не окрашен полностью и мы обходим вершину v цикла. Возможны три случая: 1. v обходится впервые 2. v является корнем отростка, который тогда должен обходиться впервые, при этом 2.1. вершина C 1 (v ) принадлежит циклу, тогда она не обойдена. 2.2. вершина C 1 (v ) принадлежит второму отростку, корнем которого является v , тогда C 1 (v ) не была еще обойдена. Во всех случаях ситуация 1 2 невозможна по определению. Таким образом, на этапе 1 производится обход цикла и всех отростков, за исключением, может быть части первого отростка, причем это произойдет только если корень первого отростка является одновременно корнем некоторого отростка второй стороны. Ту вершину, принадлежащую отростку второй стороны, которая была не окрашена при ситуации 1 2, обозначим v .

207


Состояние q0 q1 , rn-1 n = 0 n = 1 q2 , rn-1 n = 0 n = 1 q3 , rn-1 q4 , rn-1 n = 0 n = 1 q5 , rn-1 q6 , rn-1 q7 , rn-1 n = 0 n = 1 q8 , rn-1 n = 0 n = 1 q9 , rn-1 n = 0 n = 1 q10 , rn-1 q11 , rn-1 q12 , rn-1 n = 0 n = 1 q13 , rn-1 n = 0 n = 1 q14 , rn-1 q15 , rn-1 q16 , rn-1

rn = 2 (an , qn ) L L L L B R2 B B L2 L2 L L L L L B R R2 L R L B L L2 L

(an , qn ) q, rn q1 , r q2 , r q1 , r q3 , r q4 , r q q q q
5 6 1 7 n n n n n n n n n

Примечание начальное 1-й этап

, , , ,

r r r r

q7 , r q8 , r q7 , r q9 , r

2-й этап
n n n n

q7 , r n q10 , rn q11 , rn q12 , rn q16 , rn q13 , rn q16 , rn q14 , rn q15 , rn q7 , r n q16 , rn

Таблица 2.

3-й этап

2) Как было сказано при доказательстве п.1), первый отросток не обходится полностью на первом этапе алгоритма, только если вершина v - соседняя с корнем первого отростка, а значит, в этом случае мы переходим к выполнению этапа 2 в корне первого отростка. Из алгоритма следует, что следующим шагом мы переходим в первый отросток, следовательно, он будет обойден до возникновения ситуации 2 3. 3) Поскольку начальным для этапа 3 является направление из цикла внутрь отростка, то соответствующая этому направлению дуга принадлежит второй стороне. Поэтому обход по правилу правой руки будет обходом именно второй стороны. Утверждение 7 Алгоритм A сильно обходит любой двусвязный лабиринт. 208


пусто, тем самым, лабиринт будет обойден на первом этапе. Если алгоритм перейдет ко второму, но не перейдет к третьему этапу, то V20 состоит из одной вершины v , которая была окрашена во время ситуации 1 2, и лабиринт также будет обойден. Наконец, если переход к третьему этапу осуществился, то очевидно, лабиринт будет обойден. Построение автомата с одной краской. Будем называть направлениями L, L2 , R, R2 , B направления C 1 (vn ), C 2 (vn ), C deg(vn )-1 (vn ), C deg(vn )-2 (vn ), C -1 (vn ). В таблице 2 заданы функции и автомата, n - отметка текущей (на момент n) вершины.

Доказательство. Если алгоритм не перейдет ко второму этапу, то V20

Список литературы
[1] Budach L. Automata and Labyrinths, Math. Nachrichten 86, 1978, p. 195-282. [2] Зыричев А.Н. О синтезе автомата, обходящего плоские лабиринты с ограниченными дырами. Дискретная математика, 1991, т. 3, вып. 1, с. 105-113. [3] Золотых А.А. Обход лабиринтов с ограниченными в фиксированном направлении дырами. Дискретная математика, 1993, т. 5, вып. 1, с. 59-69. [4] Насыров А.З. Об обходе лабиринтов автоматами, оставляющими нестираемые отметки. Дискретная математика, 1997, т. 9, вып. 1. [5] Кудрявцев В.Б., Ушчумлич Ш., Килибарда Г. О поведении автоматов в лабиринтах. Дискретная математика, 1992, т. 4, вып. 3, с. 3-28.

209