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

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

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

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

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

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