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

которыми в S 3 полоса П}образует множество, удовлетворяющее условию а*,. Процесс построения карт Ms„ и множеств Sm = П { 'и П ^ и . . . иГ 1 ^ > удовлетворяющих условию при помощи изолированных коротких полос ко­ нечен. Значит, при некотором и 0 > 0 в диаграмме нет изолированных от S„0 коротких полос. Обозначим через Л /0 диаграмму =МП|.....>а че­ рез Мо - диаграмму с меткой <р(дМ 0) = w'n. Заметим, что <р(дМ0) = w0n, где и>о ~ w. Считаем, что ||wo Ц- ||w||, т.е. полосы П |,. . . не были точными. Покажем, что в результате любых дальнейших преобразований диаграммы М 0 приходим либо к слову w о~ w0, причем ||w о || < ||w0|| и к w оприменимо индук­ тивное предположение, либо к противоречию с условием Т(4). Итак, на данном шаге в диаграмме нет длинных полос, нет изолирован­ ных деновских областей и нет изолированных коротких полос. В качестве воз­ можных преобразований рассмотрим следующие: В диаграмме М0 появляются неизолированные деновские области. Тогда либо получаем противоречия с условием Т(4), либо переходим к слову w о~ Wo, такому, что ||wi || < ||w0||. Пусть в диаграмме Л /0 существуют неизолированные короткие полосы. Будем говорить, что полоса П накрыла полосу П ,, если ЗП п дМ0 з ЗП* п ЭП. Полоса П примкнула к полосе П„ если одно из множеств ЗП п 3£>/ или 3D*' к п ЗП содержит ребро, где П, = (J £>j . >1 Неизолированная короткая полоса П может: 1) накрыть одну или не­ сколько полос полностью; 2 ) примкнуть к одной или 2 -м полосам; 3) накрыть полосы П|, П* частично, а полосы Пз, . . . , Пц - полностью. Процесс, рассмот­ ренный в случае 1 конечен, поскольку число областей в накрывающей полосе должно быть больше числа областей в накрываемой полосе, очевидно, что меньше их быть не может, если же эти полосы имеют равное число областей, то ПО