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

лежат смежным углам Д , Dj+t и не являются концами общего ребра двух облас­ тей. Делящие точки в областях могут располагаться следующими двумя спосо­ бами: (а) в Д одна точка v, есть | П а, другая v = /,•п т , i = 1 , в . ( б ) в Д одна точка v, = /,.| п т, v = /, п а. В случае (а) существует путь у, соединяющий точку О 6 о с точкой О’ 6 т, такой что ф(х )'1 еСГа|>и ср(ст) ф(х )'1 = Ф<х)'' 4>W'- Во втором случае в М содержится подпуть %, также соединяющий точки Ои О’, такой что ф(х)еСг''.А, ф(х) ф(сг) = ф(т )'1 ф(х)- В случае, когда М содержит Д с |ф(ст,)| = 0 либо |ф(т,)| = 0, учитывая, что делящие точки Д будут концами т„ если |ф(а,)| = 0 и сг(, если |ф(т,)| = 0 , непо- • Oil - ■ средственно убеждаемся в существовании пути х : ф(х)еи аЬ и Ф(х) ф(ст) = ф(т) ф(х). .. м , » tv , ' ( . ;• , <) f v ;У V M ' 1 • • 1 •’ ^ 7> Допустим, что M - я-слойная кольцевая диаграмма. Обозначим через Ка . н а д н ; . ■ ■ ' / , . я . : " V. > ■'■ : граничный слой диаграммы М с граничными циклами о, о*1’. И также как для однослойной карты области D\, Д ,..., Dm из К„ расположены в порядке их по­ явления при движении по часовой стрелке вдоль границы ст. Вначале покажем, что ф(ст< 1 ))‘| еС*„ь. Если области Д- таковы, что |{р(о;)| * 0 и |ф(ЗД п о(|))| * 0, i - ], п, то, учитывая расположение делящих точек и тот факт, что ф(а,)еС*в*, i = 1 , и, можно легко убедиться в том, что ф(а 11 ))''еС^(,. Тогда ф(/, ot. Для того чтобы область Д +i имела с Д об­ щее ребро /, необходимо, чтобы метка пути ф((ЗД +1 п a) и /,) принадлежала бы С*о*, но это возможно, если делящие точки Д+, будут концами пути (дД» п ст) и /,, но в этом случае одна из делящих точек Д будет совпадать с одной из делящих точек Дн , что невозможно. Если делящие точки Д +| явля­ ются концами отрезка о/+| = <ЭДц п о, то это невозможно, так как метки ребра /, в Д и в Д +| должны быть взаимно обратные элементы. Получили противоре­ чие. 151