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

чающиеся разбиением дМ на минимальное возможное число рёбер, метки кото­ рых являются кусками граничных областей. Вершины, полученные в результа­ те такого разбиения называются вторичными. Первичные и вторичные верши­ ны определяют разбиение дМ на рёбра. Замечание 3. Пусть в Л/есть полоса П=ДиОзи . . . и Д . Тогда в соответ­ ствии с обозначениями, введёнными в определении 4, вершины ребер с метка­ ми г*2 , h е { 1 , . . . ,к - 1 } (то есть граничные вершины внутренних ребер поло­ сы) будут первичными. Предположим, что вершина ребра с меткой г} будет вторичной. Она рас­ полагается между двумя первичными вершинами, содержащими кусок Ь неко­ торого определяющего соотношения г. Наклеив на дМ по участку Ь область D такую что <р(dD) = г получим либо противоречие с условием Т(4), либо слова из R сократимы. Лемма 3. Пусть группа G задана своим представлением (X;R). Пусть w- циклически приведенное слово в образующих группы G, порядок слова w равен п> 1 и |Н | =1. Тогда теорема 1 справедлива. Доказательство. Т.к. к ' =1 в группе G, то существует приведённая диа­ грамма М такая, что <р(дМ) =w " . Если в М всего одна область, то утверждение леммы имеет место. Поэтому далее считаем, что в М более одной области. I. Случай деновской области. 1.1. Пусть в М есть деновская область D е D" ,т> 4. Тогда либо \\(р (3£>)|| < 4, либо по лемме 1 <p(dD) - требуемое в теореме соотношение. 1-2. D е £>,3. Пусть w = vv.,H>n= wx'w„' и w„ s ip(dD n dM) = w .w / . »/v. ■ 1.2.1. |w„ | > |w„'|. Наклеим на диаграмму M по границе дМ экземпляры об­ ласти D в тех местах дМ, где читаем метку <р(dD п дМ). Полученную диаграм­ му обозначим М\, <р(дМ\) s [<pD(dD \ ёЩ пД )'']1" = v" где v ~ (w*)2. Тогда или \М\\ = 1 , или по лемме 2 в диаграмме М, есть деновская область либо полоса. 1.2.1.1. Если в М\ есть деновская область, то либо появляются вершины 100