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

кой области, содержащей слог а’, будет а‘ b а А '1 аА Ьл либо a b a 1 Ь'] аА Ь~’. До­ пустим, что меткой будет первой соотношение, тогда <р(ст 0 п 3D) = a* b, q>(3D.| гг 3D) = а, ф(3D n 0 |) = А '1 а '\ ф(3D n 3Di) = А'1, где области D .ь D |6 , граничат с D соответственно слева и справа. Область D' из , пересекающаяся с D по ребру с меткой Ь‘ имеет граничной метко соотношение b’ с Ь с* ЬА сА. В слое ^ с,г область D ”, пересекающаяся по ребру сО 'с меткой с , будет иметь граничной Меткой соотношение cs d с d s с 1 d ' и так далее. Легко видно, что каждая из этих областей содержи?; по два положи­ тельно направленных ребра. Поэтому существует путь у, соединяющий точку О е По с О' е т0, проходящий в каждом случае через одно из положительно на­ правленных ребер в каждом слое Ка. исф (у)еС+. Если меткой области De является соотношение а Ь а‘ ЬА аА А'*, то в этом случае ф(ЭDn 3D,) = а, ф(30 г\ сто) = b d , ф(3D., n 3D) = bA, q>(3Dn Oi) = аАЬ". Область D ’e , пересекающаяся с D по ребру с меткой Ь 1 имеет гра­ ничной метко соотношение Ас A 1 сА bA c s и так далее, причем ребра 3D.| n 3D, 3Dп 3D, являются отрицательно направленными, такими же свойствами обла­ дают и аналогичные ребра области D ’e , где D ’- область, пересекающаяся с D по ребру с меткой b 1 и так далее. В этом случае в диаграмме М содержится путь у, соединяющий О еа 0 с О' ето, содержащий по одному из указанных ребер в каждом слое Ка и с ф(у)''е(7*. В каждом из рассмотренных случаев в силу теоремы 1 получаем, что сло­ ва и, v сопряжены в G*. Теперь рассмотрим случай, когда граничная метка ф(Оо) не содержит сло­ гов вида d ,s > 1. Используя структуру диаграммы и структуру граничных ме­ 1S9