Документ взят из кэша поисковой машины. Адрес оригинального документа : http://higeom.math.msu.su/elem/knots.pdf Дата изменения: Wed Mar 13 16:30:06 2013 Дата индексирования: Sat Apr 9 23:23:54 2016 Кодировка: Windows-1251

УЗЛЫ: КАК РАЗВЯЗАТЬ ЗАПУТАННУЮ ВЕРЕВКУ?

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

предложен монотонсложность не увелиузла, основанный на диаграммами.

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

Несмотря на доступность формулировок, много вопросов в теории узлов и зацеплений (в частности, алгоритмического характера) до сих пор остается открытыми.