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

слов U , V над П , опять понимая под с /( Т - ) число рёбер в ниадем пути сети 5 - ЛЕ йл Л 4 . Пусть Г, ( 'Гд. J ) - нижний путь для мини­ мальной сети Sj ( S/ r / ) . Тогда, если верхняя дуга грани fy'+ s имеет общие рёбра с Т с , то выполняется формула ( 9 ) , а если не имеет, то s ( V + , ) - S ( V ) < м - l сУ (Т у) - с /(т д , ) 1 • ДОКАЗАТЕЛЬСТВО . Ясно, что (9 ) выполняется всегда, так как при приклеивании в Т у вносится не более двух новых вершин. Пусть не имеет общих рёбер с Т„ . Обозначим V* f Z y t , ) ~ С > Поскольку С = В определяющее соотношение, то из определения функции длины сле- W » » '•* ( ТЛ / ) - s ( Ту) = S ( А ) - S ( с) . По-определению полугруппы существует М > О такое, что С удовлетворяет условию К ( т ) , где m > £ [ s(e) - sf c) ] +Z . Тогда достаточно доказать, что m 4 с / ( Т у ) - +Л. Пусть < / ( Zy+<) = t > -t, = e , . . . e* ; c/(e-c) =Q( . Поскольку рёбра, составляющие -yV/ в бд ./ , будут внут­ ренними и мы рассматриваем минимальную сеть над полугруппой без циклов, то,по лемме 3, <f(Zy 1 .J= С = Q t - произведе­ ние непустых кусков. Рассуждаем, как в лемме 2. 1 ) Концы дуги совпадают с некоторыми вершинами се­ ти Sy . Тогда с ( ( Т у ) - с / ( т г у + , ) + г = t + s - Предположим, что . Тогда m >2 , t >4 f n - y , С = Q i ... Q t , поэтому из определения полугруппы следует, что произведение Q-t - не плоское, то есть сущест­ вует индекс i i t - ( такой, что * € i ... ^ ^ - ^ 5 -А- = с Y<e i f r > /><.' Уъе 1 ч К ’ гДе /* * , _ А - некоторые нижние дуги сети S, , а / г , / ) - непустые пути. Но из построения сети ясно, что такого быть не может, иначе произош­ ло бы наложение граней и Z>s Следовательно, в этом случае т g t г / и лемма справедлива. 2) Один конец дуги / д , ( для определённости будем счи­ тать, что левый,) совпадает с некоторой вершиной сети , а другой нет. Тогда с / ( Т у) ~ { Tyyf ) + 2 = t . 88