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

3) пункт 2 ) повторяется с заменой Г^ на Г ^ , А2 - на 5 ,, 5,- на . В соответствии с тремя указанными пунктами необходимо разобрать не­ сколько возможных случаев. Введем обозначения: Г ь - {JD,,r, =U ,7 =1>2 - области пронумерованы М ' /»| в порядке следования вдоль у, от Л2 к В, . Через j u (р) мы обозначаем число граничных ребер области D в диаграмме М . Через 7] обозначим диаграмму Первый случай: Д (Д ) =3, Д (Д)= 2 ,i =2,..., I . a) при всех / Д (д2)= 2 . Рассмотрим области D{,D lt . Они имеют по два ребра на у,. Значит, либо ||ф(ЭО,)||< 6 , либо ||ф(30,2)| < 6 , либо области 0 ,,Ц 2- взаимно обратные в диаграмме Т2, и отсюда следует, что в слове ф ^О ^) - сво­ бодное сокращение при вершине Л2, что невозможно; b ) предположим, что Д ,(д ')-3 . Тогда д ( д 2 )= 1 , Д (д 2 )=2 при I= 2 »..,/2 -1 . Если Д (д')=2, то рассмотрим области D,2, D \. Они имеют по два ребра на у,, поэтому либо в слове ф( 0 Ов[) - свободное сокращение при вершине Я,, либо в одном из слов ф(зо2) ф(3£>') меньше шести кусков (если область Ц 2 имеет два ребра на dDB, то в слове ф(ст0) при вершине В, - свободное сокра­ щение). Если же Д (д')= 3, то обязательно д (д ')= 1 . Для областей D^,D, получа- •V ,..^ ‘/4 и ем: либо |ф(дО,‘) !< 6 , либо ;)ф(ЗЦ |[ < 6 , либо (если область D't имеет два ребра на Э£Д) в слове ф(а0) есть свободное сокращение при вершине Л2, либо (если область £)' имеет два ребра на 8D , ) в слове ф(ЭЕД ) в слове ф(<ЗДя ) есть сво­ бодное сокращение, так как области в TL и в /Д будут образовывать сократи­ мые пары: ф(ЭД) = ф(30,!) ф(ЭО/1)= ф(30('_,), и т.д., ф(30,)* ф(эЦ'). 57