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

Лемма 5. Пусть М - приведенная кольцевая диаграмма сопряженности слов w q и v 0. Тогда в Мнет островов. Доказательство. Предположим, что в М есть остров М2. Тогда $дМ 2) - подслово в W q или V o , а значит это слово R, R - несократимо. Если в диаграмме М2 нет деновских областей, то по лемме 2 в Мг есть 2 не пересекающиеся полосы, что противоречит выбору слов wj , v0. Пусть в диаграмме М 2 есть область D такая, что i(D) - 0, тогда в (ДдМ2) есть R сокращение, что противоречит выбору слов Wg , vg. Предположим, что в диаграмме М 2 есть область D такая, что i(D) = 1, из свойств слов w” , Voследует, что В (вершина из определения 3)е 8 D. Это озна­ чает, что некоторая область D', имеющая с D общее внутреннее ребро - непра­ вильная, но тогда dD 'n у - несвязное множество, что противоречит только что доказанной лемме 5. Итак, в М 2 нет ни полос, ни деновских областей, следовательно, \М2\ = 1и в <Ду) есть R сокращение - противоречие. Лемма 5 доказана. Лемма 6 . Пусть М - приведенная кольцевая диаграмма сопряженности слов wg и v0. Тогда в Мнет полуостровов. Доказательство аналогично доказательству леммы 5. Вновь рассматри­ ваем М>, <р(дМ2). В М2 не может быть двух не пересекающихся полос. Тогда ли­ бо в М2 одна область, что противоречит R -несократимости подслова <р(дМ2), либо в М 2 есть деновские области, что опять-таки приводит к противоречию либо с леммой 5, либо с R -несократимости подслова <р(дМ2). Лемма 6 доказана. Пусть М - кольцевая приведенная связная диаграмма, дМ - y<j& Обозна­ чим через М ' диаграмму, полученную из М удалением внешнего граничного слоя Ку,, а через М " - диаграмму, полученную из Мудалением внутреннего гра­ ничного слоя К$ Определение б [1]. Пусть М- кольцевая связная приведенная Л-диаграмма типа С(4)&Т(4) с граничными циклами у и б, нс содержащая полосы. Внешний /^(внутренний Ks) - слой назовем специальным, если составляющие его облас­ ти D) , . . . ,D„ удовлетворяют, условиям: (1) для любого j е {1, п - 1} Д , Z)y +1 и D], D„ пересекаются по ребру; (2) i(D\) = 2, i(D2) = . . . i{D„) = 3. Лемма 7 [1], Пусть М - кольцевая специальная Л-диаграмма типа С(4)&Т(4). Тогда диаграмма М ' {М") не содержит ни островов, ни полуостро­ вов. 182