Алгоритмические проблемы теории групп и полугрупп. 1994 г.

(ь ) К/ * ® пересекаются по ребру; (б ) (¿ 2 ^Ос>М)и , с/ С< 22 )п П дМ ) _ правильная последователь­ ная часть; (в) при /Т.*3 I (%,) = I (%л) = I ( ^ з) =2 ; (г) при М > 3 т (Я ,)*= с(Я г ) = с ( Я п - 1 ) = ¿(Х>п) - 2 ; Ч 2 Ы , 2 < к к + « п Ч , Щ к н ) ^ У 2 к ,2 < 2 к < п > ¿С»Л к> 2 . В дальнейшем под диаграммами типа С (р )& Т (а ) будем по­ нимать диаграммы С (6)1Т(2) , либо С(к)%1(4) , либо С(3)&Т( 6 ) ЛВММА 3 . Пусть М ^ связная односвязная приведенная, не содержащая деновских областей к -диаграмма типа С(р)Ь ТО?-) с граничным циклом 'г . Тогда М содержит минимум три непере- секающихоя полосы, если М типа 0 ( 6)1 Т ( 3 ) , и минимум д в е , если М - типа С(РМТСР) либо С (3) Т ( 6 ) . ДОКАЗАТЕЛЬСТВО. I , Рассмотрим случай, когда М Й -ди а­ грамма типа С ( 6 )АТ( 3 ) . Допустим, что И - экстремальный кр .у гЩ . Ьудем предполагать, что каждая граничная область 0 сМ является простои. Используем формулу кривизны для диаграмм типа С( 8 Ж Т ( 3 ): Ъ * ( 4 -'■(%>)) $6 где суммирование проводится по простым областям. Возьмем про­ извольную граничную область 2 ) с ¿ГЯ ) = 3 , обозначив её через ¿V . начнем перемещаться по граничному циклу Т против ч а со - ляи ' ]Несоединим к Ъ , следующую граничн.ую область 2 )л ' ^ ~ общее ребро. Если 1 С$л) =3, то лемма доказана. Пусть 3 . Если <('#г,)>.4, то слш’аемое 4 - ¿(2>л ) , вхо­ дящее в сумму (к~< ( £ ) ) , принимает отрицательное значе­ ни е, поэтому вклад в общую суш у ^ * ( 4 - с ( Я ) ) по областям либо Нулевой,.либо отрицательный. В этом случае отбрасы-^ ваем области 2 , , и начинаем строить полису с новой об­ ласти Х> с <-(%) = 3 , первой встретившейся после Я , , 2 ^ при движении вдоль Т в выбранном направлении. Пусть на некотором шаге выделена последовательность прос- тых областей Л , . , , , ^ таки х , что 4 - (Щ , ) ^ > = н ) - 4 ; , пересекаются по ребру. Рассмотрит/! следующую граничную область , Если (ф Ы то области ^ , . . . , 2 к н образ.уют полосу, если же 1 (ЗЬк *).Ч) то область %)ы присоединяем к данной последовательности об­ л а ст ей ; если 1 (Я к н ) > 4 то полученную последовательность об ­ ластей Я ,, \ ........... 2 к ч оторасынаем и начинаем строить со следующей первой области Я о ¿ (Л )-3 новую последовательность. 7