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

<p(dN) = wq u w ” . Склеим N и M0 как это было сделано выше. Области из N со- кращаются с областями из AY На простые пути соединяющие диски К, в Л/си на короткие диски наклеиваются области из N. В результате получается приве­ денная диаграмма М0 сопряженности слов и>” и v2m. Сравним числа ! а /01 и \ М 0 \ . В результате сокращения областей из К\ из диаграммы Мй удалено областей. На короткие диски было наклеено не более | у М ич *2| и ,| областей. (Число коротких дисков <1vl •Ivv|, а «длина» короткого диска < 2 | w |). На про­ стые пути наклеено не более чем ( Iv I Iи>0!)J. Таким образом, добавилось С об­ ластей. Но, если добавилось меньше, чем сократилось, то I М 01> I Л/0 | , что про­ тиворечит выбору диаграммы Мп. Следовательно, К , 0 й С и аналогичные рас- #1 суждения проводим и для АГ,0. Лемма доказана. Таким образом, если в нашей диаграмме длинные диски только одного (J* г' типа (например, если основание слоев АГ, °или АТ,-0 типа ), то числа п, т можно ограничить, поскольку само число дисков также ограничено. Теперь ясно, что замечание 1 было правомерным. Считаем далее, что в М0 есть длинные диски К, и К2, такие, что оба ст1 а1 длинные, и области из АТ, 0 (соответственно из К2 ° ) не сокращаются с облас- а г тями кольцевой диаграммы N2 (N\), склеенной из п оснований слоя К 2 0(слоя A'i<T°) и представляющий элемент из (w). Учитывая, что диаграммы N\ и N2, склеенные по границе с меткой wfi дают приведенную диаграмму, получаем, что для любого диска Kt с М0 слой К°° полностью сокращается либо с областями из /V), либо из N2 при соответст­ вующей склейке диаграмм Nt и N2 с диаграммой М0. Далее всем дискам К,, таким, что их граничный слой К°° полностью со­ кращается с областями из N\ присвоим тип I, если же диск таков, что его гра­ ничный слой K j° полностью сокращается с областями из N2, то таким дискам присвоим тип II. Дадим другое определение разбиения множества дисков на два типа. Рассмотрим диаграмму Мй и диски АГ, и АГ)- I-го и Н-го типов соответст­ венно. Все элементы из (w) пронумерованы. Пусть основание /с, слоя , 132