RUS  ENG
Полная версия
ЖУРНАЛЫ // Математическое просвещение // Архив

Матем. просв., сер. 3, 2021, выпуск 28, страницы 150–158 (Mi mp1021)

Алгебра и смежные области

Реализуемость дисков с ленточками на ленте Мёбиуса

А. И. Бикеев

Московский физико-технический институт

Аннотация: Назовём иероглифом циклическое слово длины $2n$ из $n$ букв, в котором каждая буква встречается дважды (стандартный термин: мультиграф с вращениями, имеющий одну вершину). Возьмём выпуклый многоугольник на плоскости. Отметим на ограничивающей его ломаной $2n$ непересекающихся отрезков и обозначим их буквами из слова в том порядке, в каком эти буквы следуют в слове. Для каждой буквы соединим соответствующие два отрезка ленточкой так, чтобы различные ленточки не пересекались. Любой полученный таким образом объект будем называть диском с ленточками, соответствующим данному иероглифу. Назовём иероглиф слабо реализуемым на ленте Мёбиуса, если из неё можно вырезать некоторый диск с ленточками, соответствующий данному иероглифу. В работе приводится критерий слабой реализуемости, дающий квадратичный (по количеству букв) алгоритм. Известные критерии, основанные на формуле Эйлера и теореме Мохара, дают экспоненциальные алгоритмы. Приведённый критерий также основан на критерии Мохара реализуемости диска с ленточками на ленте Мёбиуса.



© МИАН, 2024