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

них совпадают). Коли , O i S f k , то утверждение леммы следует из леммы 1 9 ; если w не принадлежит ни одной из ассоци­ ированных подгрупп 1/цу( , O t t * к , то утверждение л ё ш ы очевид­ но, Пусть w e Ц ц а , , s * 0 , и пусть существует такое и Ч , что , где г - - к а н о н и ч е с к а я ёорма представления элемента 2 . Разбиваем слово 2 на подслова Ду , j - ^ 1 , где t*/V , 9>t . K / ^ r - K t .......... * t , . Г Д < p t 4 .......... h , * O fit fiJ i заметим, что <}io может не принадлежать r y j . Так же, как в лемме 19 , каждому слову 2, поставим в соответствие связный подграф Г( с.Г, которому соо тветствует подгруппа &Г{ cQ , Qr . _ древесное произ­ ведение групп F q о объединением по f/y, л,-е <?/-,•. Каждый подграф Г( содержит Берлину &(а , из которой в Г{ выходит только одно ребро. Обозначим ч е р е з п о д г р у п п у , соо т­ ветствующую ребру из Г( , выходящему из вершины &са . Пусть 2 . Wf+, , где W=W„ , w ,ff « к , w a . * 4 * ъ * 0 ы * ............... ..... ....... < t y * ............ Для того чтобы Vi , 6 < < * t , необходимо, чтобы элемент бьш бы сопряжен в F(0 с некоторым элементом из №^а, * Пусть у, « Fia такой элемент, что у,- им/ , где < « Тогда 2,- запишем следугацим образом-. 2,- > где % • $ * » ,* < " # > 9'< W Таким образом, W , t , * j * j = М/ц, где №/, , а поэтому , V fi, no лемме 19 сопряжены в подгруппе Ui^jX; * то е с т ь 5 элементы (A cjio тоже сопряжены в U g x ,, Jb 0* U i ^ : w„ ну =w,. Рассмотрим слово ...M r ,у е^ 0 , для которого УИЬjT '« * К Лем^а доказана. Д оказательства теорем I и 2 проводятся методом математиче­ ской индукции по числу сомножителей F в группе <?. f Для это?о представляем группу в в виде произведения о объеди­ нением групп (?г >и F , где F е ст ь сомножитель группы <?г , например, F „0 , Oo<rt , соответствующий вершине ^/?0 граев Г , являющейся конечной вершиной Г . Пусть ьершина &п0 соединена ребром с &s , &s соо тветствует сомножитель F j из , а реб­ ру W 4 J - подгруппы ^sne < Fi , объединяемые о помощью изомор$мзма % Пв :*^Пс1(U i.s)*ty„o ; группа С?г< е сть древесное про- 37