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

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

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

Атомы бывают двух сортов: атомы типа $A$ и седловые атомы. Атомы первого типа изоморфны между собой. Если мы сразу рассматриваем атом как класс эквивалентности, то лучше сказать, что атом $A$ – только один. Поэтому проблема классификации атомов актуальна, в действительности, для седловых атомов. Начиная с этого момента мы будем говорить лишь о седловых атомах, называя их просто атомами, если не оговорено противное.

Как мы сейчас покажем, атомы допускают довольно красивую классификацию. Мы предъявим алгоритм, выписывающий полный список всех атомов. Затем мы укажем алгоритм, позволяющий сравнивать любые два атома и отвечать на вопрос: эквивалентны они или нет. Отметим, что классификация атомов задача не вполне тривиальная. В самом деле, атом – это пара: поверхность с вложенным в нее графом. Рассмотрим сначала более общую задачу, когда на граф $L$ вложенный в поверхность, никаких ограничений не наложено. Пусть даны две такие пары: $\left(P^{2}, L\right)$ и $\left(P^{\prime 2}, L^{\prime}\right)$. Как выяснить – существует ли гомеоморфизм, переводящий $P$ в $P^{\prime}$ и $L$ в $L^{\prime}$ ? Эта более общая задача алгоритмически разрешима. Хотя выяснение вопроса: существует ли искомый гомеоморфизм или нет, для каждой конкретной пары поверхностей с графами может быть весьма громоздкой процедурой. В нашем же случае есть облегчающее обстоятельство, состоящее в том, что граф $K$, вложенный в поверхность $\mathrm{P}$, обладает дополнительными свойствами. В частности, нам известно, что дополнение к графу $L$ в поверхности $P$ состоит из колец.
Это позволит нам не только указать абстрактный алгоритм перечисления и распознавания, но даже реализовать этот алгоритм на компьютере. Другими словами, мы предъявим эффективную процедуру распознавания.

Categories

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