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

граммы ГL и Г L, i - 1,2, Г ^ u Г ^ считаем приведенными, так как в противном случае в некотором слове из R есть свободное сокращение. Будем считать, что Д область с минимальным номером в / \ , имеющая одно ребро на о,. Тогда существует единственная область Д среди областей Д ^ .Д .,, имеющая три ребра на а г В Г ^ есть область Д 2 с тремя ребрами на т,, имеющая общее ребро с Д . Среди областей Д 2 ,...,Д 2 , в Д_ есть область Д 2 с одним ребром на т,. 1) предположим, что /, = 1. Тогда г, = 1. Легко проверить, что область Д 1 имеет на у, два ребра, так как область £>] с Г ^ с одним ребром на у, должна иметь общее ребро с областью Д . При этом либо Д 2 имеет два ребра на у,, откуда либо нарушено условие С(б), либо в слове Ф(?д,,) есть свободное со­ кращение; либо Д 2 имеет два ребра на dDB , откуда в слове ф(а0) есть свобод­ ное сокращение. 2) пусть /, > 1. Тогда i 3 > 1, и Д 2 имеет три ребра на у ,. Существует об­ ласть Д 1 с одним ребром на у ,, имеющая общее ребро с Д . В Д среди областей Д'.-.^Д1,, либо все имеют по два ребра на у,, либо одна из них (ближайшая к Д ), если не обращать внимания на области с двумя ребрами на у,) имеет три ребра на у ,. В обоих случаях два ребра из Д 2 при­ надлежат границе некоторой области из Д , откуда либо нарушается условие С( 6 ), либо Д является копией Д , что противоречит сделанному в начале разбора третьего случая предположению. Итак, все рассмотренные случаи невозможны. Тем самым лемма доказа­ на. Замечание. Поскольку в решаемой проблеме степенной сопряженности слова w,v равноправны, то из доказанной леммы следует, что из совпадения 59