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

и лемма справедлива. 2) Один конец дуги совпадает с некоторой вершиной сети S j , а другой не совпадает. В этом случае ~ ‘/ ( Т у ) = 2 - t . Формула (9) выполняется. Допустим, что •tj* * не имеет общих рёбер с Т„ и что Р - У . Тогда «^Уу входит в некоторую нижнюю дугу у?А- , не совпадая с ней, а значит, определяющее слово if ( X-J U ) входит в определяющее слово У ( У к ) » что противоречит определению полугруппы. Следовательно, в этом случае ^ » у и лемма справедлива. 3] Ни один конец дуги «Т/уу не совпадает с вершинами сети S y . t f Y W " ( ? ; ) = - ? - / • Формула выполняется. Пусть не имеет общих рёбер с Г„ и пусть t = У или ^ =■^ . Если ^ = / , то рассуждаем, как в случае 2, и получаем противоречие. Если t = Z , то Z y r/ - в " , где €■” , С* -н е к о т о ­ рые правая и левад части рёбер с?, , . Ив построения сети видно, что для некоторых нижних дуг У к , yie />к = Слг S~ У е = Г г " • ПУСТЬ ^ ( е " ) = Х , <f ( е- 1 ) = У . Тогда Ч ( У 1 ) =Е Х Н , где /У s /1 или Iе н у 1 . Так как f.(Fy+4) > У ( /ы ) > V (У е ) " определяющие слова, то получаем противоречие с опре­ делением полугруппы П . Следовательно, ^ / Лемма доказана. ТЬОРЬМА 3 . Если в полугруппе /7 И = V , то д ( V ) 6 ( Z д(гс) + - f ) L . , где L = т а х д ( С у ) . Следовательно, /7 - F Е С -представлена. / ДОКАЗАТЕЛЬСТВО. Если U = V , то в П существует п. э . п. веда (В) и можно построить приведённую сет 1 Sm такую, что ^ ( Т в ) ~ U , \ / . Оценим ко­ личество рёбер в пути Т „ . а / ( т -m ) - e f ( T ' ) = ± [ Ы ( Т у ) - с / ( r , , J J = =1 [ с/(те) -с/(Tf.J] *I [ of(ттк) - а/( г,J ]. (и ) Первое слагаемое в правой части (11^ - это сумма по всем таким индексам (. , что в приведённой сети Sm •*-( имеет хотя бы одно общее ребро с . Второе слагаемое - сумма по остальным индексам.