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

ма Nj с метками w " , v 2m, в которой все диски границе aj одного - 1 -го типа При этом при построении Nj используются элементы из (w) с последователь, но убывающими номерами. Проделаем теперь подобные преобразования словом v2m. Как и выше на некотором шаге мы получим диаграмму в которой будут длинные диски, слои которых по границам а/ и tj одного типа. Пусть у нас есть диаграмма Т, и Г) с длинными дисками 1 -го и Н-го типов соответственно. Пусть дТ, = a l u , дТ2= <Jj и т\ . Наклеим на границы диаграмм Г, иГ; с метками w” и w" соответственно S, и S2 слоев (5, +S2<Ew) из I» , ана границы с метками v™ и v" соответственно S]' и S2 слоев (5,' + S2 < £„) из (v) так, чтобы метки в полученных диаграммах Т{ и Т2 совпадали. Таким об­ разом, <р( дТ{') s /р( 8Т{) = Wf и v” . Очевидно, что если склеить диаграммы ТУ и 7У по границам с метками wj! или v” , то в обоих случаях получим приве­ денные диаграммы. Приклеим к диаграмме Т,' диаграмму Т2 по границе с меткой w%. Полу- . hrt 1 - о-:. A i- ■./it-: . -v ченную диаграмму обозначим Q2, <р( д Q2) = v” . Приклеим к Q2 по гра­ ничным меткам диаграмму Т \, получим диаграмму Q2. К ней приклеим Т2, по­ лучим диаграмму QA. Продолжая этот процесс, на некотором шаге получаем диаграмму Qin i- Сделаем разрез по кратчайшему пути. Обозначим полученную диаграмму через Я2,». Пусть Е =max{£w, £„}. Поскольку разрез сделан по крат­ чайшему пути, то «толщина» диаграммы H2i+\ в месте разреза не превышает 2 Е. Оценим сверху количество граничных областей Я, в диаграмме Я2,*|. N, < 2(2 Е -1 г 01-(2/ + 1)) + «(max |w(|) + m(max |v;|) < 2(2E-\r0\ (2/ + ])) + np +mq £ 2(2£-1 r0\-(2i + 1)) + 2np0, где pn= max(p,<y}, aq - число областей в основаниях для слова v и учитываем тот. факт, что на верхнюю и нижнюю границу диаграмм 7У и ТУ выходит одинаковое число областей. Пусть К\ - самый длинный диск в диаграмме Т\ или в Т2 (для определен­ ности в Т{), N - число областей этого диска с ребрами на границе диаграммы. Мы получили, что в этом случае IAT 1 1>— — = С. Таким образом, площадь самой 2С ,2 диаграммы Я2,+ 1 удовлетворяет неравенству IЯ2„ 1 1>(2i+l )• I К, I£ (2/ + 1)• j v i 2C\ Оценим N. Пусть np - число областей в кольцевой диаграмме из (и>), ко­ торую можно наклеить на диаграмму Т\ по границе с меткой w” . Часть из этих областей будут иметь ребра на простых путях, соединяющих диски в диаграм­ ме Т\. Но таких областей не больше чем С2. Значит, на долю областей, имею­ щих ребра на границе диаграммы Т и содержащихся в дисках этой диаграммы 136