АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП 1986 г.

что противоречит условию леммы. Если & /= , то области ^ образуют специальную /? - диаграмму * , что невозможно, так как W ay и VYг у удовлетворяют условию S . Пусть и ,я г е G удовлетворяют условиям леммы. Рассмотрим циклические слова и , гг , Окружность, являющуюся границей циклического слова и (гг) , обозначим через в - Ст) . Разобьем эту окружность точками на ребра так, чтобы каждому ребру соответствовала буква слова и (и). Построим алгоритм, с помощью которого можно будет выяснить, су­ ществует ли слово ^P (st)£ <г такое, что - гг* (ГдВ и * , V * - некоторые циклические перестановки соответственно и , гг , Ч(ое.) - метка пути , соединяющего некоторые граничные вершины из 6 “ и . Если T a n o r q W *e) не существует, то олова и , гг не являются метками никакой кольцевой R - диаг­ раммы М вида 3°. Разбиваем циклическое слово и (гг) на подсло- ва и , . . . и т (гг, ... vn ) , где каждое u t e ^ JS ( г( * & { ) )) • Подсло­ ва / ( л ) занумерованы в направлении обходи 6 ~ (Т ) по часовой стрелке. Данному разбиению соответствует разбиение гра­ ницы 6 ~ ( Т ) на простые пути S '/,..,, ®>п ( Ц , . - . , Т п ) , W s lJ= , i - f, пъ ('Щ ) - . Соединим конец 6~7 отрезком f e с кон­ цом какого- 1 Шбудь пути _ , например с Т, , и разобьем ■>£ на два ребра 6 , , -йд, в направлении от Т, к 6 ~, . Укажем спо­ соб нахождения меток Lpt'et ) , У (?*.) . Для этого к каждому пути /п пристраиваем области ( $ 1 , , X>t) > удовлетворяющие следующим условиям: Пх~е^ пересокаютоя по ребру: // ^ ( d ^ i \ д л , / 7 еу ц = 4 > если ' У * \ / 7 в ) / 1 , з (ИПЪЬ'ьХйЦпт =3). Причем процесс построения последовательности областей % ( ( f y ) начинается со случая, когда /г= 2 ( t ~ Z ) . Алгоритм построения об- ле тег %с ( % J) аналогичен указанному в леглле 29, за тем исклю­ чением, что вси&ий раз он начинается с нахождения области \ (% t) ■ Если для ценного разбиения циклических слов и. , гг и фиксиро­ ванного соединения концов и Г, можно построить интересующие нас последовательности областей { fc; i =ф для не­ которых к it t , 2 *-k<.m, 2 < t<n. , то тем самым будет определена метка V’/’ae ) , для которой проворном выполнимость равенства ffae) (и * У/э*) ** гГ * , где и * , гг*~ циклические перестановки соот­ ветственно v , тг , оиредоляошо конечными вершинами -С, , Tr . ft противном случае определяем мотку пути jz , сч здш т- "о ко»'. ■ о", с концом Тй>п т .д . >