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

меткой минимальной связной односвязной R - диаграммы t^i . со­ держащей более одной области, тогда, если и г циклически R -при­ ведено, то в R - диаграмме М можно выделить полосу. Д о к а з а т е л ь с т в о . Рассмотрим случай, когда ft - диаграмма М является экстремальным Kpyroi.i [3 ] . Будем называть граничную область 5) простой, если дЗ)Г)&М~ связное множество и ЭЯП&М - последовательная часть карты Л 7 . Предположим, что каждая граничная область я - диаграммы М простая. Используем формулу кривизны для карт с условием ССб) : 2 * (4 -i(S> )) ^ в , где суммирование проводится по граничным об­ ластям £> , у которых д З Ь П дМ последовательная часть карты М . Так как метка и / гран:пщ /V является циклически R - приведенным словом, то наименьшая внутренняя степень граничных областей равна i &>) - 3 . Возьмем любую граничную область %>с c\SJ*j и обозначим её через %>, . Качнем переме'щат? тя 0т неё против часовой стрелки по границе карты М . Присоединяем к 5), следую­ щую область , подсчитывая ,для 5), и Х>^_ слагаемые (4-i(X>j')) суммы 21* ( 4 -с (Я )) , Если =3 , то лемма для данного случая доказана. Пусть i Сto*.)* 3 . Если I (3>л ) > ^ , то сла- гаемые (4 - i (Я х ))<. С . Поэтому вклад в общую суд у (4~i (4)) по областям # , , либо пулевой, либо отрицательный и дан­ ные слагаемые выбросим из общей суммы, начиная подсчет её от новой области Ъ с i ( t o ) =3. Если L , то переходим к еле,дующей области 5 )3 . Если i С5>3 )= 4 , щ переходим к следующей области 2 >у ; если l ^ , то предыдущие слага­ емые отбрасываем и начинаем подсчет суммы от новой области ЗЬ с * ( X » - 3 . Если с (% з )~ 3 , то последовательность облас­ тей 5>лг X> j образует полосу. Продолжая указанный выше про - цесс, через конечное число шагов построим полосу. Заметим, что в данном случае может быть построено минимум три полосы. Теперь предположим, е>то карта М содержит область $ , которая явля- атся неправильной, то есть д& /1 д М - несвязное множество. Выб росив область & , разобьем карту на две подкарты J, 3 г . Рассмотрим карты М {~3t П Ь и М4 = П fe , каждая из которых содэриит более одной области и является экстремальным кругом, D каждой из карт M L , L=<Л , Допустим, что все граничные области карты М; , L - l t2 , являются простыми. Поэтому в карте M L , ~ 1 } £> , может быть выделено минимум д в о ’полосы^ ВН 01 ШШЯ граница каждой из которых может быть вклю­ чена в некоторый граничный цикл карты f“7 . Допустим, что /"-f