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

называть связным KCTi - слоем дискам. В случае 2 диаграмма Ка{ является объединением нескольких дисков: (К \Г *В этом К 1 случае;'бу- дем называть несвязным К ° х- слоем диска К. В обоих случаях К а> является объединением всех областей из К \ К а<>, граничащих с К ст° . Аналогично определяются слои К Сг ,К ° Ъ, . . . диска К. Они тоже могут быть связными и несвязными, после удаления из дисков K \,...,K S областей из несвязного Ка' - слоя каждый из них в свою очередь может распасться в объе­ динение дисков и связывающих их простых путей. Несвязный К а г - слой дис­ ка К в этом случае, очевидно, является объединением всех областей из диа­ граммы ( К \К а° ) \ К а' , фаничащих с областями из К а' . Точно также опре­ деляются К т' - слои диска К. Вернемся к диафамме Щ сопряженности слов wjj , v2m. Наша цель - ог­ раничить числа п, т, поэтому далее будем считать, что в нашей диафамме есть диск Кх такой, что ЗА, = a ]0r \r l0, а'0 а . сг0, т'0 с r0, | р(оо)| > 2| и>|, I^з(го)| > 2| v|. Диски из М0, удовлетворяющие этим неравенствам будем назы­ вать длинными, а остальные диски из М<>- короткими. Замечание. Очевидно, что если в нашей диафамме все диски короткие, а число их мы уже можем офаничить (лемма 2), то числа и, m можно Офаничить. Считаем далее, что в нашей диафамме есть длинные диски. Пусть К г дликный диск. Из основания его К °° - слоя можно склеить кольцевую диа- фамму N, одна из меток которой равна wq , а вторая wj ". Из строения слоя К°° следует, что в N есть области с двумя и четырьмя внутренними (в диа­ грамме М0) ребрами, причем любые две области с двумя внутренними ребрами разделены областью с четырьмя внутренними ребрами (не считая областей с тремя внутренними ребрами). Склеим диаграммы N, Мо по фанице с меткой . Для любого диска Kj нашей диафаммы, применяя рассуждения из доказательства леммы 1, легко ai проверить, что либо все области из К1 0 сокращаются с областями из N, либо диафамма К, и N— приведённая. Все диски диафаммы М0, области из которых сокращаются с областями из N назовем дисками первого типа. Лемма 6. Пусть в простой диафамме М0с фаничными метками и $ , v2m есть .длинный диск К\ первого типа и любой длинный диск - диск первого типа. 5 (1 v | - | w 0l ) 2 + | v M w 0|-2 max(| v | , | w 0l ) = C. Тогда Ti к[° Доказательство. Рассмофим построенную выше диафамму N, 131