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

справедливо для всех связных односвязннх минимальных R - диаг­ рамм М ,' содержащих к областей, к < ц , , и имеющих в качестве граничной метки слова u v , u ^G g , v s (?■ и г/ содержит буквы из алфавита Ад . Рассмотрим случай, когда М содержит п облас­ тей. Так как число областей в карте М больше I , то для М вы­ полняется формула кривизны: (Ц откуда следует, что М содержит дэновскую область k , ‘ (*>)*3 . Пусть д2нТ)М-&, 6 "е а . Если то слово V является R -приводимым. До- Луотим, что i ( » ) * 3 , с , УСдЭ) где £ ~ , £ , /г - метки внутренних ребер области й . Сотрем в карте М простой путь б" , получим карту М ' , имеющую граничную метку и г = ~и„Щ к ч / ^ £ ^ 1 г^ил , где и= и л , c ~ k ^ F ~ fE ' / и г получено из слова w '^u^iT fCVxU * , 1 Гкчг,с.г£, заменой <7 на k ~ f F ~ fE ~ r Пусть zrr jtS L , 2 £ = л » где А . - пустое слово. Тогда предположе­ ние, что подслово гг, к ~*F~'E\ свободно сократимо, приводит к Р - приводимости слова гг . действительно, так как и сокращение возможно только в словах V) к ~ ' 3 Е ~ 'г ^ , то,пред­ положив, например, что в слове vf /^''км еет место свободное сок­ ращение, выполнив его, получим Щ к где ^5 = ^ / ^ , К K ~ f ~ A • Отсюда следует, что в слове г г можно вы­ летать подслово С , ’удовлетворяющее соотношению lKn cl> \}(^£yF f^ где KnC=-K^/-,E~f, то есть слово Z f является /? - приводи:,пил. Предположим, что г/^=Л, 2 £ * л и в слове UT=Un имеет мес­ то свободное сокращение. Допустим, что оно происходит в подслове Un к ' . Случаи, когда сокращение имеет место в £ ~ ггт^} анало­ гичен вышерассмотренному. Так как l4 ’(6'J]»lk~,F~ 1 E il и в слове У ~ V -х '- ^^подйлова F ~13 г/д, содержат буквы из алфавита A j } k ~ t является степенью некоторого образующего из А д , то слово гг можно заменить более^коротким, что противоречит нашему предполо­ жению. Случаи, когда в олове Ua V ,K fF 1 £~ гт&ил имеют место сокра­ щения при услЬвии, что =Л , либо 2^* гг^ = а . , также невоз­ можны. ОтсщДа следует, что слово иА=.ип ц к г,Р ^ г}дд /свободно несокра­ тимо, и так как карта М ' , граничной меткой которой является иг , содержит ( а -{ ) _ область, то на основании индуктивного предположения слово vi K ',F ,£ ,irjL записано на образующих Ад , то тогда и слово гг в силу того, что Il'M&JHz 3 и Ц£,р~1£~*Ц = 3 . токе записано на образующих Ад . Если S' с ы , то, рассуждая анало­ гично, получаем, что гг удовлетворяет заключению лемм . Поэтому предположим, что 6 "= е / ,..e je ,.. ek содержит ребра как из ос , так _ 5 7 _