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

1) Области образуют сократимую пару. Тогда область А '*1 можно “развернуть” на границу ст0, что влечёт наличие в слое диаграммы М об­ ласти со свободно сократимой граничной меткой, что невозможно. 2) Никакие две из областей O 0 ,S/*',O/ не образуют сократимую пару. То­ гда для одной из областей нарушается условие С( 6 ). 3) Сократимую пару образуют области D0,S{". Тогда, во-первых, область D, имеет с областью Si" одну общую вершину. Во-вторых, £>„ имеет ровно одно общее ребро с областью £>/. Таким образом, ||SD 0 n r , ||=4 (Рис. 1). На­ клеим на все пары областей Dj,S/"(J = 1... и-1),£>",5,' копии области D„ . Тем самым мы выполним п копий одного и того же А-сокращения, о которых упоминалось в условии леммы. Полученную диаграмму назовём Mt . Легко убедиться в том, что её граничные метки циклически R, R - несократимы, что и утверждалось в лемме. Таким образом, единственная возможность А-сокращения рассмотрена. Пусть в слове « 1 (г4) есть А- сокращение. Наклеим на внутреннюю гра­ ницу диаграммы Mi соответствующую полосу П 0 (Рис. 2). Повторим эту про­ цедуру п раз. Получим диаграмму А/,. Легко проверить, что на внутреннюю границу диаграммы М , нельзя наклеить ни деновскую область, ни полосу, ни слой из областей с двумя рёбрами на границе слоя. Тем самым доказательство леммы заканчивается. Рис. 2 68