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

Пусть а - |J Д ; р = ( j Dj - все области диаграммы М, кроме Д и Д , <•-•1 к ' м граничащие с у, 8 соответственно, s ,t e N . Определение 18. Назовем а, Р - поясами карты М. у\ = 3<А(уиЭДиЭД), 8\ = dp\(5udDAudDB) - будем называть внутренними границами поясов а, Р Лемма 14. (ру\), <р$\) - R, R - несократимы. Доказательство очевидно. Пусть Му = М\ D a u a u D j и р - диаграмма, полученная из М удалением её граничного слоя. дМу -yy'oSy. Считаем, что в Му все области правильные. Следствие 14.1. Если диаграмма Му не однослойная, то она имеет такую же структуру, что и диаграмма М из следствия 13.1. Доказательство очевидно. Причем, если Му однослойная, то рассуждения приводимые ниже проходят и в этом случае. Пусть, далее М'= М Д и а и DB. Следствие 14.2. Диаграмма М' имеет такую же структуру, что и диа­ грамма М из следствия 13.1. Доказательство. В Му вместо области Д появляется область Д , т.е. ЭД- п ЭД - вершина, З Д п у\ - ребро, dDc п 8у - ребро. Аналогично вводится об­ ласть Д для Му, как DB для М. (мСД ) = 3. Действительно, ДХД ) т 4, как вытекает из следствия 13.1. Предположим, что <м(Д ) = 2. Пусть а ь Ру - пояса карты Му. Согласно следствию 14.1. в поясе Ру бли­ жайшей областью к Д (если не учитывать области с тремя внутренними (в Му) ребрами) должна быть область с двумя внутренними (в М^) ребрами. Пусть это область Д . Тогда, чтобы избежать противоречия с условием Т(4) в поясе Дей должна соответствовать область Д : i(Dk ) = 2. Причем V/ е { 2 , . . . , k-l) i(Dj)= 3. Но в этом случае получаем, что области Д и . . . и Д образуют полосу, что противоречит R - несократимости слова (р{8). Следствие доказано. Вернемся к диаграмме М , дМ - у'О &, а - Д и . . . и Д , Р = Д и .. . и Д . yi, <5, - внутренние границы поясов а и Р соответственно. Пусть <?'- внешняя граница Д т.е. <У'= £ \ (ЭД vj ЗД ) или в ' = др п 8, а у'- внешняя граница пояса а, т.е. у'= у\ (ЭД и ЭД) или у '= Э а п у. Пусть ЭМ'= A|Uy иЯ 2 и<?', где А, = ЭД пЭ Д , Я 2 = ЭД пЭД , т.е. др= 2,yu8y u A qu 8', A|Uyi и Aj = у>, 5 " = 5 '\ (3Д и 3D,). 117