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

Если 1(% з) =2, то области Щ , \ , %з обра­ зуют полосу согласно определению. Если с/^ ) > 3 , то области Я / , Я д , отбрасываем, так как суммирование по ним дает от­ рицательную величину в сумме ( 2 Уд - ^ (%)) Если ¿ (& з ) = 3 , то область 2 >3 присоединяем к X),, и рассма­ триваем граничную область , пересекающуюся с ^ по ребру. Допустим, что мы выделили следующую последовательность об­ ластей : Я , , Яя ..........Д , где Д - , Д><, , пересекаются по ребру ‘ ( 3 / ) тс(Яя)= 2 , ¿('%)=с('Як)=. ..= (СЯр+,)=3, 2 ^ + 1 <к^ 1(Х>*)^(<Я6) = .. .= 1 ,( 3 >ц) = 2, . Пусть к =2/- Рассмотрим следующую граничную область ' пересекающуюся с Д , по ребру. Если ¿ ( \ , / ) = 2, то последовательность областей Д , . . . . . . , Я>к н образует полосу. Если ¿ (Я /# ,) =3, то присоединив 2 )^ к областям Я , , ^ , . . . , % , переходим к следующей граничной области, пересекающейся с Ду/ по ребру. Если ¿ (Я ^ 1 ) > 3 , то области Д , Де . . . . . Д - у у отбрасываем и приступаем к построе­ нию новой последовательности граничных областей. Если то получаем случай, когда к = Я к + 1 - Пусть \i~2j-t-1 и пусть следующая граничная область переоекагацаяся с \ По ребру, имеет тогда области Я , отбрасываем. Допустим, что ¡-(Як-н) = 2, то­ гда Я к и присоединяем к областям Д , . ••, %к , получаем пре­ дыдущий случай, когда к = 2 /■ Так как сумма в результате суммирования по граничным областям диаграммы Я) должна Принять значение не меньше тр ех, то мы обязательно должны выделить полосу, причем минимум д в е . В случ ае, когда М содержит граничные области , не являющие­ ся простыми, или состоит из нескольких экстремальных кругов, рассуждения аналогичны рассуждениям в пункте I . Лемма доказана. Пусть '^■=£/ 6 г ...€ л ~ некоторый путь диаграммы М, тогда символом |Г| , равным П , обозначим длину пути . Пусть М связная /2 -диаграмма типа С (р )& Т (^ ) и С - полоса диаграммы М. Тогда д С П д М - внешняя граница С, а дС\(дСпсЯ1) (дС \ (дС п дМ) - рассматриваем как замкнутое множество) - о с ­ нование С. Из определения С-полосы следует ЛЕММА 4 . Пусть М - связная й -диаграмма типа С (р)&Т(<0 и С -полоса М. Тогда |с?С\(с?с, ^дЛ1)| < \дСП дМ \ .