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

минимум две непересекающиеся полосы. Получим ранее рассмотренный елу. чай. Если М содержит деновскую область D, то для нее обязательно должны выполняться условия: Э£>= у, б, / , 7 i = dD г \ у, 6 i =5DPi8, 3D\y, 5, = /, | / | = 1, либо dD= у’/ 5’, у’ = dD п у, 5’ = dD п 8 , dD \ у, 6 , = /, | / 1= 1. Тогда делящие точки D принадлежат либо у, либо 5, что приводит к вышерассмотренным слу. чаям. И, наконец, пусть М содержит непростые области, пересекающие одно­ временно у и 8 , М не содержит поддиаграмму Г, Тогда в М содержатся области Ей Е2 ........ такие что дЕ, п дЕ,+\ = /„ дЕ, п у = у„ дЕ, п б = б„ i'=l, j -I и поддиаграммы У 0 и Ей либо Et u У’0, где dJ0 Г\ дМ = у 0 50, ЗУ 0 п дЕ\ = Хо>1Хо-|> г\ дМ = у’об’о, а /о п £* = х ’о. Ix’o-I > 1 Тогда поддиаграммы Ус и Е\ и Ек и У '0 - не содержат деновских областей, каждая граничная область в У 0 и Е\ и £* и'У ’о—простая, поэтому они содержат полосы. Теорема доказана. Определение [3J. Пусть М - Л-диаграмма типа С( 6 ). Будем говорить, что последовательность простых областей £>ь D2, ... ,D„,n> 2, образует С-полосув АУ, если: а) V/, 1 <i <п, границы D t, Di+\ пересекаются по ребру; б) ( 3D\ndM) и ... и (dD/^icM) - правильная последовательная часть; в) i(D,) = i(D„) = 3; Vj, 1 <j < n, Щ ) = 4. Лемма 9 [3]. Пусть АУсвязная односвязная приведенная диаграмма типа С( 6 ), каждая область которой является простой, и пусть в АУнет деновских об­ ластей, тогда АУсодержит минимум три непересекающиеся С-полосы. Проведем доказательство теоремы 1 индукцией по числу областей в R - диаграмме М , дМ = уб, с <р(у) = w, ф( 8 ) = v'1, где ср(у), <р( 8 ) е (Т . Пусть АУсодержит одну область D с dD = yi 8 |, где у = у 0 yi у2, 8 = 80 б| §:• Тогда ф(уь Si) е Gab, для некоторых a, beA, ф(уО, ф(5|)'е(Г* аЬ и слова фЫ> ф( 8 |)'’ равны в группе Gab, следовательно по теореме 2 они равны в G*ab и одно 146