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

*/>■■■•>** ’ яля К 010! 151311 ^2 )/ Пъ> pf ( д \ / ) Т 'Ф 0 ) , L - ^ к , 9 Л / О ^ = 4 ^ й^ вг' = ? ' ^ перес0каетоя с 2>‘ ’1' по РебРУ* г = ^ Г' . И с ( К ) = 3 . Е с л и / , = **, , то в * 1 путь д имеет вид: [I, - е,е^ . Разрезав М по д , получим карту м , , присоединив к которой область / , идентичную й', , получаем связную односвязную приведенную карту МА =М, О £ ' , Ъ Ь 'П д М ,~ р , . Рассуждая аналогично предыдущее случаю, можно показать, что в А/Л вдоль & (Т ; от ое; , в направлении по часовой стрелке, мож­ но выделить последовательность областей Д > / , , для которых 0)1 ( } £ * < ) } , ёЗ^'Пэе, = ех. Г Э Я /П м , = е , ) , пересекается с T»[+t по ребру, , и tY * /J = ■■ =4 , L (3)^ , Используя данное свойство, покажем, что в кольцевых связных минимальных R - диаграммах Л? вида 3° нет граничных областей 2 > , для которых д 2 ьП дМ - несвязное множество и 055/16“ либо д% О Т , либо и то, и другое являются вершинами соответственно б" , Г . Допустим противное, то есть существу­ ет область 3> , которая пересекается с граничными циклами б” , карты М соответственно в вершинах гг , тг' : М П в - ^ г г , д%/1£ = у ' . Тогда в граничном цикле /9зе области 3> простые пути р , эе , соединяющие вершины гг , гг' , будут иметь вид: /3 = р , , « * # / • • ет . где либо п , либо гп. больше двух. Однако, как показано выше, этот случай невозможен. Допустим, что дан области 2 > =°tt где <* - простой путь, a = гг' , V ' - вершина Г . Тогда в гран: шом цикле ы-р»*- области А пути (1 , ек. .^соединяющие вершину гг' соответственно с кон- Ь)м ск и с немалом Ы , будут иметь •вид: /з =е , . .. е„ , .. £'п , где К / г к Ц . Случай, когда n * m ~ < , невозможен ввиду специальной ,«f? - приведенности '?(&) , ^ C V ) , Пусть n - i , т = Я . Тогда iC &)=3 , и согласно вш е доказанному, справа от 2 >’ вдоль границы ? можно выделить последовательность граничных областей , образующих с Я полосу, что про­ тиворечит условию лести. " Если n = z , m =Z , то, как и в предыдущем случае, справа от вдоль границы б" можно выделить области и, из тех же соображений, слева вдоль б" - граничные области Первое множество областей нумеруется в направлении по часовой стрелке вдоль 6 " от ■£ , второе против часовой стрелки,’ i (Я ,') = i f » l ) = . . . • i ( » /V a ...= Если , т с области %s", образуют полосу,