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

Из определения ленты ясно, что в случае, когда в М есть лента L, то ее внутренние ребра должны удовлетворять условию замечания 3, но в этом слу­ чае на внутренней границе происходит уменьшение числа кусков, так как мож­ но выделить точную полосу, значит применимо индуктивное предположение. Полоса является лентой. Короткие и длинные ленты определяются анало­ гично полосам, а так же диаграммы M l , M l , где лента L удовлетворяет усло­ вию \<p(dLndM)\ < | w| определяются аналогично диаграммам Мъ Mjy . Определение 14. Пусть S - поддиаграмма диаграммы М (возможно не­ связная), состоящая из полос и деновских областей диаграммы М, удовлетво­ ряющая условию аь: множество (возможно несвязное) dS п дМ содержится в некотором связном подмножестве К границы дМ таком, что | <р(К%i |и>|. Тогда диаграммы Ms, Ms определяются аналогично диаграммам Мп, М ц . Определение 15. Если S - дизъюнктное объединение полос и деновских областей в диаграмме М с меткой <р(дМ) = w‘\ удовлетворяющее условию аь, то деновская область D в диаграмме Ms называется изолированной от множества S в Ms, если D является деновской областью в Ms , и (dD Г\ dS) \8M S = 0 . Анало­ гичное определение вводится для полос. Пусть в М есть короткая полоса П| и в карте М п, есть короткая полоса П2, причём П 2 изолирована от П| в Л/П |. Рассмотрим S2 = П| и П2, для неко­ торого /, где П'| - тот из п экземпляров полос П*, . . . , П" карты М щ , при объ­ единении с которым полосы П2, S2 удовлетворяет условию аь. Пусть с помощью полосы П 2 построена карта (МП] )n j , которую будем обозначать МП) П2. До­ пустим, что в ней есть изолированная короткая полоса Пэ. Существование та­ кой полосы следует из изолированности полосы П2от П| в диаграмме Л/П[. В качестве поддиаграммы S} возьмём диаграмму S} = n j 1 и П '2 и П -j, где n j ',n 2 - экземпляры полос Пу, . . . , П" карты Л/П) , при объединении с .жом эн : \лд хк ‘л,.- 109