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

v, ’= 8 , n уя то есть концы у, - делящие вершины. Что требовалось доказать. Лемма 8. Пусть дМ = у 8 , где ф(у), <p( 6 )', eGrfI*) каждая область D с Мяв- I : м.г.«{V,- И ляется граничной, М = y j Д , и пусть Vi, 1 < i < п, область Д не является про- Ы стой, тогда слова ф(у), ф( 8 )'' равны в Доказательство. Рассмотрим случай, когда М - однокомпонентпач диа­ грамма. Согласно предыдущей лемме существует область Д , у которой деля­ щими точками являются, например, концы пути у,. Тогда слово <р(/,.| 5, и в силу леммы 4 от слова ф(у,) к слову ф(//.| 8 , в G*^ можно перейти, ис­ пользуя определяющие соотношения (Г*,*. Сотрем в М путь у,; в результате М разобьется на две поддиаграммы М\, М2 связанные путем 8/. дМ, = 8, 82 ... 8 м /,.Г' у,., ... уь где ф( 8 ,)'| еС*а», ф(/м' 1 )е(7\*, ф(у,)е(Д,4; дМ2 = 8 ,+t ... 8 „ у„ ... у,чI /,+Г1, где ф( . Покажем, что каждая из поддиа­ грамм Mit i = 1 , 2 , содержит область D с делящими точками, принадлежащими границе (дМ,\ 8 ). Действительно, если делящие точки области Д .| являются концами 8 ,.\, то нетрудно убедиться, что у Д , делящими точками являются концы yf. Анало­ гичные соображения имеют место и для М2. М состоит из нескольких компо­ нент, а именно, М\, М2, ... , М„, каждая из которых удовлетворяет условиям ; Ю • __ леммы, и граничные циклы каждой компоненты Mh i = 1 , п, дМ, = у ’ 5 , то на­ личие в какой-то из компонент М] области D с делящими точками, являющими­ ся концами дГ>глуи\ позволяет, используя вышеизложенные рассуждения, пока­ зать, что на каждом шаге после удаления подобных областей в каждой компо­ ненте, в частности, и во вновь образованных после удаления D, будут содер­ жаться аналогичные области. Что и требовалось доказать. Продолжим доказательство теоремы 2. ;t ,| 144 1 !