К вопросу об алгоритмической сложности задачи Рейдемейстера | Статья в журнале «Молодой ученый»

Авторы: ,

Рубрика: Математика

Опубликовано в Молодой учёный №28 (162) июль 2017 г.

Дата публикации: 16.07.2017

Статья просмотрена: 109 раз

Библиографическое описание:

Шмаль С. Н., Павлова Е. Ю. К вопросу об алгоритмической сложности задачи Рейдемейстера // Молодой ученый. — 2017. — №28. — С. 1-3. — URL https://moluch.ru/archive/162/45150/ (дата обращения: 17.07.2018).



Ключевые слова: теория узлов, движения Рейдемейстера, пара Перко, инвариант

Теория узлов — одна из наиболее красивых областей математики. Прародителем ее является К. Ф. Гаусс, который дал формулу для вычисления числа оборотов одной замкнутой кривой в трехмерном евклидовом пространстве вокруг другой.

Узлом называется гладкая замкнутая несамопересекающаяся кривая в пространстве, которую можно представить диаграммой, т. е. гладкой кривой на плоскости, не имеющей других особых точек, кроме конечного числа простых двойных точек (там, где происходит трансверсальное самопересечение), и снабженную в каждой двойной точке одним битом дополнительной информации, указывающим, какая из двух ветвей в этой точке является проходом (т. е. лежит снизу), а какая — переходом (т. е. лежит сверху). [1]

Автором первой книги, посвященной целиком теории узлов, был К. Рейдемейстер (1932), который доказал следующую теорему: две диаграммы узлов задают один и тот же узел тогда и только тогда, когда от одной из них можно перейти к другой посредством плоских изотопий диаграммы и перестроек Рейдемейстера.

Напомним, что в теории узлов, движением (преобразованием) Рейдемейстера называют одно из трех локальных движений на диаграмме узла или зацепления. В 1927 году Д. Александер и Бриггс, а также независимо К. Рейдемейстер, показали, что две диаграммы, относящиеся к одному и тому же узлу, с точностью до плоской изотопии могут быть преобразованы одна в другую с помощью последовательного применения одного из трех движений Рейдемейстера.

Каждое движение действует в небольшой области диаграммы и бывает одного из трех типов (рис. 1):

Тип I. Скручивание и раскручивание в любом направлении.

Тип II. Перемещение одной петли целиком через другую.

Тип III. Перемещение нити целиком над или под пересечением.

Заметим, что другие части диаграммы не отображены на схеме движения, а также, что плоская изотопия может исказить рисунок. Нумерация типов движений соответствует числу нитей, вовлеченных в него, к примеру, движение типа II действует на двух нитях диаграммы.

Один из важных случаев, когда требуется движение Рейдемейстера — это определение инвариантов узлов. Инвариант определяют, как свойство диаграммы узла, которое не меняется при любых движениях Рейдемейстера. Множество важных инвариантов можно определить таким образом, включая полином Джонса.

Только движения типа I изменяют число закрученности узла или зацепления. Движение типа III — единственное, которое не изменяет число пересечений на диаграмме.

Рис. 1. Типы движений (преобразований) Рейдемейстера

Учитывая теорию особенностей (известную как теория катастроф) теорема Рейдемейстера вполне очевидна. Ясно, что любую гладкую изотопию узла в пространстве можно немного пошевелить так, что она сведется к последовательности элементарных перестроек указанных трех типов (преобразования Рейдемейстера). Однако актуальным является вопрос: каково минимальное число и какую последовательность перестроек Рейдемейстера необходимо совершить, чтобы преобразовать одну диаграмму узла в другую, если известно, что эти две диаграммы принадлежат одному классу эквивалентности.

Такова же задача актуальна и для кос. Существует множество алгоритмов, которые по двум математическим косам, записанным в образующих Артина, отвечают на вопрос, эквивалентны эти косы или нет (один из самых быстрых принадлежит И. А. Дынникову). Это стандартная постановка вопроса, которая известна, как проблема равенства (word problem) и может применяться не только к группе кос, но и к любой группе, заданной образующими и соотношениями.

Если в постановке задачи уже известно, что косы изотопны, то теоретически найти преобразование одной в другую минимальным числом движений Рейдемейстера можно простым перебором: для каждого перебирать все косы, которые получаются из первой косы применением движений Рейдемейстера, и проверять, нет ли среди них второй данной косы.

Такой перебор, конечно, будет огромен, так что этот подход дает только ответ на вопрос, можно ли найти минимальную последовательность движений Рейдемейстера. Теоретически — да, можно. Но вряд ли за разумное время.

За разумное время довольно просто решается другая задача — найти какую-то последовательность движений Рейдемейстера от одной косы к другой, но без претензий на то, что она будет кратчайшей. Из конструкции некоторых алгоритмов для решения проблемы равенства такая последовательность легко извлекается. Например, для этой цели подойдет алгоритм У. Тёрстона (W. Thurston) приведения к жадной нормальной форме (greedy normal form) или два алгоритма П. Деорнуа (P. Dehornoy) — сокращение ручек (handle reduction) и обращение слов (word reversing). Все эти алгоритмы достаточно быстрые, хотя для сокращения ручек хорошая оценка до сих пор не доказана.

Что касается узлов, то задача преобразования одного изотопного узла в другой решается намного сложнее. Чтобы оценить, насколько, достаточно ознакомиться с историей пары Перко (Perko pair): двумя эквивалентными друг другу узлами, которые в течение 75 лет, начиная с 1899 года, считались различными. Является очевидным, что быстрых алгоритмов, применимых на практике, для сравнения двух узлов на сегодняшний момент нет. Однако, существует достаточно надежный эфристический метод, реализованный в программе SnapPea Д. Викса (J. Weeks), которая умеет распознавать узлы с умеренным числом пересечений на диаграмме, но осуществляет это вне всякой связи с движениями Рейдемейстера. Однако, из процедуры, которую она выполняет, последовательность движений Рейдемейстера извлечь можно, но для этого программу придется усовершенствовать. Однако, для решения задачи вычисления минимальной последовательности преобразования одного изотопного узла в другой остается только снова полный перебор всех возможных вариантов.

Авторы благодарят доктора физ.-матем. наук, ведущего научного сотрудника МИАН И. А. Дынникова за полезные рекомендации и помощь в работе над статьей.

Литература:

  1. Дужин С. В., Чмутов С. В. Узлы и их инварианты // Математическое просвещение. — 1999. — № 3. — С. 59–93.
Основные термины (генерируются автоматически): III, теория узлов, движение типа, движение, коса, диаграмма узла, изотопный узел, плоская изотопия, разумное время, сокращение ручек.


Похожие статьи

Определение топологических компонентов диаграмм узловых...

Рис. 2. Графическое представление третьего движения Рейдемейстера. Определение. Ориентированным узлом называется узел, на котором задано направление обхода, или же отображения ориентированной окружности в . При этом при изотопии узлов требуется...

Лагранжевы методы моделирования потоков со свободной...

Подход Лагранжа в описании движения относится к типу отсчётных.

Метод основан на использовании сетки, узлы которой движутся вместе с жидкостью, так что граница раздела автоматически отслеживается узлами расчетной сетки [1]. Метод LINC применим только для...

Распознавание английского текста сверточной нейронной сетью

Каждая вершина графа соответствовала одному из полученных ранее разрезов, а ребро – фрагменту изображения, расположенному между разрезами на узлах. Ребро графа строилось только в том случае, если полученный фрагмент мог быть распознан в качестве буквы.

Графы в Scilab | Статья в сборнике международной научной...

Длительное время задачи теории графов решались вручную.

Каждый узел и каждая дуга имеет свой номер. При представлении графа обязательными являются 5 элементов структуры: имя графа (тип: строка); флаг, показывающий тип графа (1 — ориентированный, 0...

Математическое моделирование движения плоского...

Математическое моделирование движения плоского шестизвенного внутритрубного робота.

Результаты математического моделирования представлены в виде временных диаграмм (рис. 3–5). Рис. 3. Параметры перемещения 3-го звеньев робота.

Проблемы развития железнодорожных узлов на современном этапе

В настоящее время развития инфраструктуры железнодорожных узлов фактически не происходит, в то время как они во многом определяют

В случаях, когда хотя бы одна станция узла перестает справляться с работой, нарушается движение поездов на прилегающих...

Программирование разностного метода решения одной задачи для...

Результат программы для приведенного выше тестового примера представлен на рисунке 2. Решение волнового уравнения при заданных начальных и краевых условиях представлено в виде таблицы значений в узлах построенной сетки.

Объемные FinFET-транзисторы: конструирование на 14 нм узле...

В сравнении с традиционным двумерным MOSFET-транзистором (МДП-транзистор основанный на эффекте поля, далее — MOSFET), FinFET-транзистор (полевой транзистор с вертикальным каналом, напоминающим по форме рыбий плавник(fin), далее — FinFET)...

Определение топологических компонентов диаграмм узловых...

Рис. 2. Графическое представление третьего движения Рейдемейстера. Определение. Ориентированным узлом называется узел, на котором задано направление обхода, или же отображения ориентированной окружности в . При этом при изотопии узлов требуется...

Лагранжевы методы моделирования потоков со свободной...

Подход Лагранжа в описании движения относится к типу отсчётных.

Метод основан на использовании сетки, узлы которой движутся вместе с жидкостью, так что граница раздела автоматически отслеживается узлами расчетной сетки [1]. Метод LINC применим только для...

Распознавание английского текста сверточной нейронной сетью

Каждая вершина графа соответствовала одному из полученных ранее разрезов, а ребро – фрагменту изображения, расположенному между разрезами на узлах. Ребро графа строилось только в том случае, если полученный фрагмент мог быть распознан в качестве буквы.

Графы в Scilab | Статья в сборнике международной научной...

Длительное время задачи теории графов решались вручную.

Каждый узел и каждая дуга имеет свой номер. При представлении графа обязательными являются 5 элементов структуры: имя графа (тип: строка); флаг, показывающий тип графа (1 — ориентированный, 0...

Математическое моделирование движения плоского...

Математическое моделирование движения плоского шестизвенного внутритрубного робота.

Результаты математического моделирования представлены в виде временных диаграмм (рис. 3–5). Рис. 3. Параметры перемещения 3-го звеньев робота.

Проблемы развития железнодорожных узлов на современном этапе

В настоящее время развития инфраструктуры железнодорожных узлов фактически не происходит, в то время как они во многом определяют

В случаях, когда хотя бы одна станция узла перестает справляться с работой, нарушается движение поездов на прилегающих...

Программирование разностного метода решения одной задачи для...

Результат программы для приведенного выше тестового примера представлен на рисунке 2. Решение волнового уравнения при заданных начальных и краевых условиях представлено в виде таблицы значений в узлах построенной сетки.

Объемные FinFET-транзисторы: конструирование на 14 нм узле...

В сравнении с традиционным двумерным MOSFET-транзистором (МДП-транзистор основанный на эффекте поля, далее — MOSFET), FinFET-транзистор (полевой транзистор с вертикальным каналом, напоминающим по форме рыбий плавник(fin), далее — FinFET)...

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Определение топологических компонентов диаграмм узловых...

Рис. 2. Графическое представление третьего движения Рейдемейстера. Определение. Ориентированным узлом называется узел, на котором задано направление обхода, или же отображения ориентированной окружности в . При этом при изотопии узлов требуется...

Лагранжевы методы моделирования потоков со свободной...

Подход Лагранжа в описании движения относится к типу отсчётных.

Метод основан на использовании сетки, узлы которой движутся вместе с жидкостью, так что граница раздела автоматически отслеживается узлами расчетной сетки [1]. Метод LINC применим только для...

Распознавание английского текста сверточной нейронной сетью

Каждая вершина графа соответствовала одному из полученных ранее разрезов, а ребро – фрагменту изображения, расположенному между разрезами на узлах. Ребро графа строилось только в том случае, если полученный фрагмент мог быть распознан в качестве буквы.

Графы в Scilab | Статья в сборнике международной научной...

Длительное время задачи теории графов решались вручную.

Каждый узел и каждая дуга имеет свой номер. При представлении графа обязательными являются 5 элементов структуры: имя графа (тип: строка); флаг, показывающий тип графа (1 — ориентированный, 0...

Математическое моделирование движения плоского...

Математическое моделирование движения плоского шестизвенного внутритрубного робота.

Результаты математического моделирования представлены в виде временных диаграмм (рис. 3–5). Рис. 3. Параметры перемещения 3-го звеньев робота.

Проблемы развития железнодорожных узлов на современном этапе

В настоящее время развития инфраструктуры железнодорожных узлов фактически не происходит, в то время как они во многом определяют

В случаях, когда хотя бы одна станция узла перестает справляться с работой, нарушается движение поездов на прилегающих...

Программирование разностного метода решения одной задачи для...

Результат программы для приведенного выше тестового примера представлен на рисунке 2. Решение волнового уравнения при заданных начальных и краевых условиях представлено в виде таблицы значений в узлах построенной сетки.

Объемные FinFET-транзисторы: конструирование на 14 нм узле...

В сравнении с традиционным двумерным MOSFET-транзистором (МДП-транзистор основанный на эффекте поля, далее — MOSFET), FinFET-транзистор (полевой транзистор с вертикальным каналом, напоминающим по форме рыбий плавник(fin), далее — FinFET)...

Определение топологических компонентов диаграмм узловых...

Рис. 2. Графическое представление третьего движения Рейдемейстера. Определение. Ориентированным узлом называется узел, на котором задано направление обхода, или же отображения ориентированной окружности в . При этом при изотопии узлов требуется...

Лагранжевы методы моделирования потоков со свободной...

Подход Лагранжа в описании движения относится к типу отсчётных.

Метод основан на использовании сетки, узлы которой движутся вместе с жидкостью, так что граница раздела автоматически отслеживается узлами расчетной сетки [1]. Метод LINC применим только для...

Распознавание английского текста сверточной нейронной сетью

Каждая вершина графа соответствовала одному из полученных ранее разрезов, а ребро – фрагменту изображения, расположенному между разрезами на узлах. Ребро графа строилось только в том случае, если полученный фрагмент мог быть распознан в качестве буквы.

Графы в Scilab | Статья в сборнике международной научной...

Длительное время задачи теории графов решались вручную.

Каждый узел и каждая дуга имеет свой номер. При представлении графа обязательными являются 5 элементов структуры: имя графа (тип: строка); флаг, показывающий тип графа (1 — ориентированный, 0...

Математическое моделирование движения плоского...

Математическое моделирование движения плоского шестизвенного внутритрубного робота.

Результаты математического моделирования представлены в виде временных диаграмм (рис. 3–5). Рис. 3. Параметры перемещения 3-го звеньев робота.

Проблемы развития железнодорожных узлов на современном этапе

В настоящее время развития инфраструктуры железнодорожных узлов фактически не происходит, в то время как они во многом определяют

В случаях, когда хотя бы одна станция узла перестает справляться с работой, нарушается движение поездов на прилегающих...

Программирование разностного метода решения одной задачи для...

Результат программы для приведенного выше тестового примера представлен на рисунке 2. Решение волнового уравнения при заданных начальных и краевых условиях представлено в виде таблицы значений в узлах построенной сетки.

Объемные FinFET-транзисторы: конструирование на 14 нм узле...

В сравнении с традиционным двумерным MOSFET-транзистором (МДП-транзистор основанный на эффекте поля, далее — MOSFET), FinFET-транзистор (полевой транзистор с вертикальным каналом, напоминающим по форме рыбий плавник(fin), далее — FinFET)...

Задать вопрос