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

Т е о р е м а 2 [ 3 ] . Пусть УК -нормальная подгруппа из F , порожденная симметризованным множеством R . Тогда цикличес­ ки несократимое слово и г из Г принадлежит УК , если и только если существует связная односвязяэя R -диаграмма М такая,что для некоторой выделенной вершины О на дМ граница е,...еп кар­ ты М о началом в точке 0 имеет метку tfe ,). . Ч‘(€а ) = и Г . Дусть r , t rx e R , rt =6 c f , гл =6сл . В этом случае элемент Ь называется куском относительно множест­ ва R . Будем говорить, что симметризованное множество R удов­ летворяет условию С (/г ) , если никакой элемент из R не является произведением менее чем /г. кусков, т’ условию Т(ф) , если для любых Г ,... Г ^ из R , 3 * h < t y , таких, что любые после­ довательные элементы Г^г Г , 1 < б < /г , не являются взаимно­ обратными, то по крайнем мере одно из произведений r/i~ irh , rh rf приведено. Если 2) -область из М с данной ориентацией, то любой цикл минимальной длины Frt) включающий в себя ребра границы д-& области Д 5 ,. в котором все ребра ориентированы в соответствии с ориентацией области 2) , называется граничным циклом этой области. Граничной вершиной или граничным ребром И будем называть вершину или ребро из диаграммы М . Если V -вершина диаграм­ мы Л7 , то d(v) -степень вершины V - есть число ребер, инци­ дентных вершине V . Если 2 -область из /V , то d (Я>) - степень области % - есть число ребер в граничном цикле для -Э . Симво­ лом i(X>) будем обозначать число внутренних ребер из 2 . Гранич­ ной областью диаграммы М называется такая область 2 из М ,что v д Ъ П д П * Я* . R - диаграмму М назовем приведенной, если для любых её областей Ъ , , , пересекающихся по ребру & и имеющих гра­ ничные циклы соответственно e.S~t и <S'jLe.~t , имеем: 1 . Т е о ' р е т а З [ 3 ] _ . Допустим, что R удовлетворяет ус­ ловиям C(fi) и TCty) и И - приведенная R - диаграмма. Тогда, если 2 - внутренняя область М ,, то d d > ) » jx , и если 1 Г - внутренняя вершина Л/ , то d C V ) z q , R - диаграмму Л? , удовлетворяющую теореме 3, будем называть диаграммой типа CCfi) . Пусть 2) - область из М . Будем говорить, что д Ъ П д П есть последовательная часть карты М , если дЪПд ! ^ \ >-об"еди­ нение последовательности ^ замкнутых оебер, и ребра _ 27 _