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

Теорема о площади. [1] Пусть М - односвязная приведенная диаграмма с условием С(б). Тогда число областей диаграммы М удовлетворяет неравенст­ ву: Здесь точка над знаком суммы означает, что суммирование распространя­ ется только на граничные области. Докажем сформулированное свойство диаграмм Н ,. Оценим сверху количество Я, граничных областей в диаграмме Я,. А'( < a(z') + nl max jw,j + |m!jvj. Из лемм 1. 6 , 2.1 следует, что в кольцевых диа­ граммах Т[,Т'г на внешней и на внутренних границах - одинаковое число гра­ ничных областей (в любой приведенной кольцевой диаграмме, удовлетворяю­ щей условию С( 6 ), с циклическими Л, Л-несократимыми метками, число об­ ластей с ребрами на внутренней границе равно числу областей с ребрами на внешней границе). Указанные числа равны р ,р . Поэтому верно неравенство: .V, < а, + 2|л|р. Обозначим через р' число областей в основании любого элемента из K(v), а через р0- наибольшее из чисел р ,р '. Тогда число областей диаграммы Я, с ребрами на путях А,,А 2 не превышает £(4/ + 2)+ р 0 (4/ + 2)=p(f). Таким образом, имеет место неравенство Я, <, р(/)+ 2 |и|р„. Пусть Я, - самый длинный диск первого типа в диаграмме 7]. Обозначим через Я, число областей в К ,, имеющих ребра на границе диаграммы Г, с мет- м>... e~i 63