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

■ Определение [3]. Пусть M -R - диаграмма типа С(4)&Т(4). Будем говори^ что последовательность простых областей D\, Di ........ D„, п > 2, образует q , полосу в М, если: а) Vi, 1 < i< п, границы А„ А,_| пересекаются по ребру; б) (дВ\ПдМ) kj ... и {дО„глдМ) - правильная последовательная часть [4]; в) i(A) = i(A) = 2; V/, 1< / < и, /(А) = 3. В [3] доказывается лемма 5. Лемма 5. Пусть М - связная односвязная приведенная, не содержащая де- новских областей Д-диаграмма типа С(4)&Т(4), тогда она содержит минимум две непересекающиеся С-полосы. Лемма 6. Пусть М - связная односвязная приведенная однокомпонентна (экспериментальный круг [5]) Л-диаграмма типа С(4)&Т(4) над группой G* Пусть метка (р(ЭМ) свободно приведенное слово. Тогда (р(ЗМ) содержит непере­ секающие подслова ф(у|), ф(у2), такие, что <р(у,), ф'(у2) принадлежат С*„ь и 11<Р(г011- т аь, ||ф(у2)|| 2; т аЬ. Доказательство. Доказательство проводится индукцией по числу облас­ тей. . Доказательство теоремы 2 будем вести индукцией по числу областей в R- диаграмме М. Если А/ содержит одну область, то так как дМ= у 8 , где ф(у) = tv, ф(5) = V1, то заключение теоремы очевидно. Пусть М содержит s областей. До­ пустим, что каждая область А, с; Мне является простой. Тогда для каждого /, 1 <,i<s, dD, г> у = yf, 8D, п 6 = 5,-. Допустим, что в М выделено максимально возможное подмножество об­ ластей: А . А» , Dp, для которых ЗА, n 3A,+i = /» /, - ребро, 1 < i < р. Для про­ стоты можно считать, что p~s. Таким образом получаем, что у = yi у 2 ... у3, 8 = 5| 62 ... 8 ,. Делящие вершины области А, будем обозначать v„ v,’. Так как ф(у) - слово в положительном алфавите, а ф( 8 ) - в отрицательном и подслова a V , Ьга*, где е = ±1, не являются кусками, то вершины v„ v,’ являются конце­ выми вершинами 142