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

определяющее соотношение полугруппы. Дуги ^ -i , ограничи­ вают часть плоскости '<Di , гомеоморфную открытому кругу и на зываемую гранью. назовём верхней, a A i - нижней дугами грани . После склеивания в полученном графе удалим все вершины сте­ пени 2 (кроме Р и Q ) . Если при этом рёбра и P-z объединяются в одно ребро Р , то ¥ (& ) ~ <f (&<) ¥(*->-)• Полученный плоский граф вместе с функцией метки ¥ назовём приведённой сетью Ту для равных слов 7 ~0 , Ту над по­ лугруппой П (эта сеть является S -диаграммой в смысле [ 8 ] ) . Вершину Р назовём источником, Q - стоком. Границу'сети составляют два пути от источника к стоку: Тс (верхний, или исходный) и Ту (нижний), причём ¥ ( Т в ) = & ; 1р(Ту) = Ту Всего в Sy имеется J +Y различных путей от источника к стоку (по каждому ребру можно проходить только в направлении его ориентации). Для То нижний и верхний пути совпадают и состоят из одного ребра. S. >у+/ заключается в приклеивании 2 > грани 2 >V+Y с границей (верхняя '/> / отождествляется с соответствующей Переход от сети к нижнему пути сети дуга Ау*< грани частью нижнего пути . Ту ) . Рассмотрим подробнее, как происхо­ дит этот переход. • Пусть у - путь в приведённой сети. Обозначь через d ( у ) число рёбер в этом пути. Далее под с / ( Г , ) , i > 0 } понимается число рёбер в £(• - нижнем пути сети Т( , а не в проме­ жуточном пути некоторой сети S m . ЛЕША 2 . Пусть Т у - нижний путь для сети Ту ; Т у * , дуга Г * V +/ Ту Тогда, если верхняя имеет общие рёбра с исходным путём d ( Т у ) + 1 ; (9 ) (ю) - нижний путь для сети 1/*< грани £>у+< то d ( Т у Т а если не имеет, то d ( Т у . , ) Т ДОКАВАТЕЛЬСТЬО. t Ъ / , так как из определения полугруппы следует определяющие слова непусты, d ( Ау*< ) - / в сети Рассмотрим три возможных случая. l) Концы дуги Ayt< совпадают с некоторыми вершинами се­ ти Ту ( т . е . при переходе от Ту к Не появляет ся новых вершин). Тогда с / у ы ) - с / ( Т у ) - / - t ( О d ( Т у ) . , Пусть d ( Лу+Г) г t что все •Ту** 83