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

крайней мере одну область. Выберем На <оПГ вершину О такую, что она принадле­ жит границе некоторой области JD и при разрезании диаграммы А в вершине О о последующим зашиванием границы получим связную односвязную диаграмму й' , граничный цикл которой имеет метку W S (Я & )п такую, что ГТшт- {(Д|,| 6|5 - минимальный. Тогда по крайней мэре одно из слов А и & является циклически свободно приведённым. Заметим, ч то , согласно лемме 2 , в рассматриваемом случае <&= . . . 0 , , т =-/, Л . . . Д с началом в О для некоторого целого к и рёбер и У, для 1 * i &к и либо = (ФЧА)) 1 , либо €>‘ ^ - у У . Д * является граничным циклом некоторой области D , из Д , где - внутренние рёбр а, возможно пустые, и Lf( k 0 ) s r 4 . Обозначив <г< = е ч e i - * . . . е * , т< «•/,Л . . . У ; , имеем, что путь Со,- т<- У , 7 является замкнутым. Покажем, что /?£, и <f Действительно, если < Д е *)а = Л В е ,/?£> , где £ = / 8 , && и f i f e * i , то в силу т о г о , что ц > (^ ) т>(1/4) Я , имеем ( j j ) ) —3 P & i R i так как иначе по условию (4(1/ 4 ) имели бы невозможное в - 4 .Кроме т о го , ^ i f так как в про тивном сл у ч а е,в силу В 2 /7 & с , по условию Т (4 > по­ лучается свободная приводимость мэтки области 35, или смежной с ней области Х>« .Приведенность граничных циклов С и "t" впечёт l y H e , ) / - I L p(-fi)l .Поэтому, имея P & z ftlb и & fl~ 1 8 "*Р , получим & у£ Ё ^7 р ", Q " i . в силу по условию С(1 / 4 ) имеем, что & < ( ( / 4 ) € .Однако, с другой стороны, в силу Ь ¥ 1 , по условию (Й 1 / 4 ) получаем, что ■<( 1 /4 ) Р , а значит Е±> (1/4 ) Р. .Полученное про тиворечие показывает, что I f ( 0 , ) о . ^ g .Аналогично имеем (f(i-r) s fl * • Если для некоторого с if(G r( T t ) s Д & Д ' 1& 1 ( то II ф(<3,)|- I ф (Т ,)| I |Ц’ (к ,')| .Действительно, положим 4 4 « i . ) a S i , Ф ( т , ) ^ Г с , 1?(кл) * Н с И / 7 6 - G S , Тогда, вставляя в вершине О ^ шип с меткой в и з а д н я я Я на H . V > получим слово Л ’ е (Q/-/, T t' ’ )п В (G Н i T " 1)-''- 1 из множества М .Поэтому I Q U i T C ' l > I Q S i l влечёт нера­ венство |ф (< з 1')1 - п р С т ,-) | < |(р (к,)| 48