Главная > ИHTEГPИPУEMЫE ГAMИЛЬTOHOBЫ СИСТЕМЫ(А. В. Болсинов, А. Т. Фоменко)
<< Предыдущий параграф Следующий параграф >>
Пред.
След.
Макеты страниц

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

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

Ясно, что при построении алгоритма достаточно ограничиться атомами фиксированной сложности. Итак, рассмотрим множество всех атомов с одним и тем же числом вершин $m$.
Возьмем множество раскрашенных крестов в количестве, равном $m$. Раскрашенный крест показан на рис. 2.10. Стрелки на его концах направлены из белого цвета в черный. Пометим концы крестов буквами так, чтобы каждая буква встречалась в получившемся наборе ровно два раза. Другими словами, разобьем множество концов на пары и каждую пару пометим одной и той же буквой. Затем склеим концы, помеченные одинаковыми буквами, причем, склеим, уважая их ориентацию, т.е. согласуя стрелки. Каждая такая склейка легко записывается, кодируется дискретной таблицей. Легко видеть, что в результате склейки получится некоторый атом. Черные области крестов дадут положительные кольца атома, а белье области – отрицательные кольца. Перебирая все варианты склеек, строим некоторое множество поверхностей. Отберем из них только связные. В результате, очевидно, получим множество всех атомов данной сложности. Хотя, возможно, с повторами, т.е. список избыточен – две разные таблицы, задающие склейки, могут породить одну и ту же поверхность с графом. Тем не менее, мы алгоритмически получили полный список всех атомов.

Categories

1
Оглавление
email@scask.ru