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

кой w " . Площадь диаграммы Н t удовлетворяет неравенству: \H.\>ATUib 2 ~ с А -= » =А 2С, (здесь мы применили следствие из леммы 2 . 8 ). Заметим, что Ц р - число областей в слое из А'(н'), наклеенном на диа­ грамму 7; по границе с меткой w", так, что полученная диаграмма является приведенной. Часть из этих областей имеет ребра на простых путях, соеди­ няющих диски в диаграмме Т,. Таких областей не больше, чем С2. Значит, чис­ ло областей, имеющих ребра на границе с меткой w ", и содержащихся в дисках диаграммы 7], не меньше, чем |и|р - С,2. Так как число дисков в Г, не превыша­ ет С,, то ]Л^| |> (п р -С , 2 )/С | . Итак, ' ' Ц р - С ' ' 1 С, - с : г с Г г М - S ! ■ Теперь ограничим сверху правую часть неравенства (* *) из теоремы о площади. Так как пути sl,s1- кратчайшие, то выражение (б-/(£>)) ограничено числом 4. Поэтому 1*4,* ‘ й { | ‘)’ ' й ( р Й * ^ ^ (О + З Р оН У s у (4;(£ + д0)+ 2(£ + )+ 2р0|п|)г < при [и! > 2 {Е + рс) продолжаем цепочку неравенств: ^ *Ы Е + Рй)+ п (2р 0 + OF = с ■ Введем обозначения: А - 4(£ + р ь\ В = (2р0 + 1). При таких обозначениях запишем неравенство : 12 64