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

этого вычислим разность Мг ~ 8 = 2 Ь ~ 8 ~ 1 6 ■ Найдем конец третьего ребра: M3 - i 6 = a o ~ f g = * / > Все остальное несложно; надо только смотреть в какой стороне от линии стыка я /я находится верпшна. Если слева, то отражаем ее от д ,1 , если же справа, то от - х , ( От х 3 * отражение идет независимо от т о г о , в какой сторона лежит верпшна. Кроме то го , надо следить з а тем , не закончился ли про­ ц есс, т . е . , не получилось ли у нас число М 2 , МЪ или К 3. Запишем теперь очевидные формулы: L 2 = L 1 + k ( 4 .1 ) L 3 ~ L 1 + L 2 К 1 - 1 1 (4.2) (4.3) К2 - 2 L U L 2 КЗ = L 3 ~г 2 1 = 2 К -1-2 K 2 = 2 L 1 К З = У 2 +2 М 1 ~ 2 К 1 М 2 = 2 К 2 М3*2 КЗ (4.4) (4.5) (4.6) (4.7) ( 4 . 0 ) ' (4.9) (4.10) ( 4 . I I ) Будем исследовать, существует ли решение для наших троек ( h i , L 2 , L 3 ) длин слов , А 3 , А3 . Исследовав очередную тройку, добавляем к L 1 и L 2 число 2 , т . е . исследуем следующую тройку ( L l + 2 , L 2 t 2 , L 3 * ^ ) с учетом периода, поскольку при добавлении периода I к длинам L 1 и L 2 картина повторяется. Значит, если ( / . / , L 2 , L 3 ) - решение, то ( i i t l , ^ 2 + Г , L 3 + 2 T ) тоже решение и , наобо­ ро т, если первая тройка не является решеюг 1 , то и вторая тройка не является решением. Итак, будем рассматривать - 67 -