Cтраница 1
Квазилабиринт, у которого каждое приписанное ребру слово есть слово над В, назовем ЭД - квазилабиринтом. Очевидно, подобные слова р к. Если 21-квазилабиринт L получен из 9 ( - квазилабиринта LI заменой отметок ребер на подобные им отметки, то скажем, что L и L2 подобны. Очевидно, что поведения ЭД в L и в L2 одинаковы. [1]
Квазилабиринт L назовем плоским, если лабиринт Ф ( Ь) плоский. L назовем планарным, если существует подобный ему плоский квазилабиринт. [2]
Квазилабиринт L назовем деревом, если граф, получающийся из него при замене каждой пары противоположных ребер одним неориентированным ребром, есть дерево. [3]
Рассмотрим произвольный квазилабиринт L, у которого от вершины и к вершине v ведет ребро с отметкой рт. В лабиринте L ( L) от и к v будет вести коридор вида, изображенного на рис. 4.4. В силу вышесказанного, мышь 5 (, находящаяся в вершине u ( v), для любого m li либо не заходит в коридор, либо заходит в него и, не дойдя до конца, возвращается к ( и), либо остается в коридоре сколь угодно долго, либо, наконец, проходит до конца коридора и оказывается в состоянии s ( s), не зависящем от i. [4]
Построение правильного квазилабиринта, не обходимого мышьк 31, во всех этих подслучаях осуществляется следующим образом. Полученный квазилабиринт обозначим L. [5]
L возьмем квазилабиринт, изображенный на рис. 4.22. Как и в случае 3.2.2, для получения планарного квазилабиринта L преобразуем слово q ( q) K - l qi к такому слову q, чтобы соответствующий q цикл был планарным. [6]
Лемма 4.13. Пусть L - планарный 9t - квазилабиринт и v - вершина L. Тогда 31 -квазилабиринт, получающийся из L и L % склеиванием вершин и и и, планарен. [7]
L возьмем квазилабиринт, изображенный на рис. 4.22. Как и в случае 3.2.2, для получения планарного квазилабиринта L преобразуем слово q ( q) K - l qi к такому слову q, чтобы соответствующий q цикл был планарным. [8]
Квазилабиринт, у которого каждое приписанное ребру слово есть слово над В, назовем ЭД - квазилабиринтом. Очевидно, подобные слова р к. Если 21-квазилабиринт L получен из 9 ( - квазилабиринта LI заменой отметок ребер на подобные им отметки, то скажем, что L и L2 подобны. Очевидно, что поведения ЭД в L и в L2 одинаковы. [9]
Построение правильного квазилабиринта, не обходимого мышьк 31, во всех этих подслучаях осуществляется следующим образом. Полученный квазилабиринт обозначим L. [10]
В качестве L возьмем квазилабиринт, изображенный на рис. 4.14. Покажем, как преобразовать слова q и qz при помощи соотношений () в слова qi и q % так, чтобы полученный при этом квазилабиринт U был пленарным. [11]
Очевидно, достаточно показать, что если 31-квазилабиринт обладает некоторой укладкой на плоскости, то он также обладает укладкой, у которой вершины расположены в узлах подрешетки целочисленной решетки с шагом I, а ломаные ведут по ребрам этой решетки. Пусть дана плоская укладка 3 ( - квазилабиринта L. [12]
Квазилабиринт L назовем плоским, если лабиринт Ф ( Ь) плоский. L назовем планарным, если существует подобный ему плоский квазилабиринт. [13]
Произвольная укладка разбивает плоскость на одну внешнюю область и конечное число внутренних областей. При помощи рассуждения, аналогичного рассуждению при доказательстве леммы 4.10, нетрудно убедиться, что для правильного 31-квазилабиринта существует такой подобный ему 9t - квазилабиринт L, что лабиринт Ф ( Ь) правильный. Поэтому для доказательства теоремы достаточно показать, что для любой мыши существует правильный 91 -квазилабиринт, не обходимый этой мышью. [14]
В качестве L возьмем квазилабиринт, изображенный на рис. 4.14. Покажем, как преобразовать слова q и qz при помощи соотношений () в слова qi и q % так, чтобы полученный при этом квазилабиринт U был пленарным. [15]