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

dQ, =s.q's~'t ' , где q‘ ,t" - пути, полученные разрезанием замкнутых путей ?,,/,.* = U . Имеют место следующие графические равенства: ф(<?,’ )= v j'v '^ 'v ;1, где v е v,v„; ф(л ) s где w* — Ф(^)*ф('Г 1 ) * г 1; у-!" 'у ;',г д е v = v'v,; Ф (?2 )= , где wt = yv^w^,; Ф( 0 = Ф к 'Г a z 2 - Заметим, что из построения диаграмм £? i >(?2 следует, что|<ф,)|£ £|г0| , где 1 = 1 , 2 , г0- самое длинное слово в R , так как пути st,s2, являясь кратчайшими, содержат ребра не более, чем из Е областей диаграмм Г, ,Г2’, соответственно. Склеим диаграммы Q, ,Q2 по подпутям максимальной длины путей tt,t2. Получим приведенную диаграмму F s. Приклеим к Е\ по подпути максималь­ ной длины пути q2 диаграмму Q ,. Получим приведенную диаграмму F2. Так строятся диаграммы Fi для любого / > 2. Рассмотрим диаграмму F 2M. Ее граничный цикл разбит на четыре участ­ ка: й,,А;, где q\,t \ - пути из 8Q, , a ht,h2- «боковые» пути в F 1M, длины ко­ торых ограничены числом (Е г 0 (2 + 4/))+ max i(M,!w/l )}(2 + 4/)= оф), где первым слагаемым оценивается сумма длин путей с метками zv z2,z ^ ,z 2' . Обозначим диафаммы ^ 2+1 через Н-. Полученное семейство диафамм F = {Я2|+|, /> l}= Я = {Я,, i'> 1} обладает следующим свойством: площади диа­ фамм Я, растут быстрее квадратов длин их фаниц, что позволяет получить при больших ml,И противоречие со следующей теоремой о площади. 62