Интегрируемые гамильтоновы системы - Болсинов А.В.
ISBN 5-7029-0352-8
Скачать (прямая ссылка):
Топология слоений, порождаемых функциями Морса
87
Это позволит нам не только указать абстрактный алгоритм перечисления и распознавания, но даже реализовать этот алгоритм на компьютере. Другими словами, мы предъявим эффективную процедуру распознавания.
2.7.2. Алгоритм построения полного списка всех атомов
Ясно, что при построении алгоритма достаточно ограничиться атомами фиксированной сложности. Итак, рассмотрим множество всех атомов с одним и тем же числом вершин га.
Возьмем множество раскрашенных крестов в количестве, равном га. Раскрашенный крест показан на рис. 2.10. Стрелки на его концах направлены из белого цвета в черный. Пометим концы крестов буквами так, чтобы каждая буква встречалась в получившемся наборе ровно два раза. Другими словами, разобьем множество концов на пары и каждую пару пометим одной и той же буквой. Затем склеим концы, помеченные одинаковыми буквами, причем, склеим, уважая их ориентацию, т.е. согласуя стрелки. Каждая такая склейка легко записывается, кодируется дискретной таблицей. Легко видеть, что в результате склейки получится некоторый атом. Черные области крестов дадут положительные кольца атома, а белые области — отрицательные кольца. Перебирая все варианты склеек, строим некоторое множество поверхностей. Отберем из них только связные. В результате, очевидно, получим множество всех атомов данной сложности. Хотя, возможно, с повторами, т.е. список избыточен — две разные таблицы, задающие склейки, могут породить одну и ту же поверхность с графом. Тем не менее, мы алгоритмически получили полный список всех атомов.
2.7.3. Алгоритм распознавания одинаковых атомов
Осталось решить задачу алгоритмического распознавания в этом конечном, при фиксированном га, списке одинаковых, т.е. эквивалентных атомов.
Пусть даны два атома, получившиеся в результате склейки крестов. Удобно сформулировать задачу выяснения их эквивалентности или неэквивалентности так. Рассмотрим один набор крестов: (крест 1), (крест 2), ... , (крест га), и две таблицы, кода, диктующие склейки их концов (рис. 2.30). Требуется выяснить — будут ли гомеоморфны получившиеся атомы, т. е. поверхности с графом.
Задание той или иной склейки крестов очевидно эквивалентно заданию некоторого элемента сг конечной группы перестановок Напомним, что каждый крест имеет по 4 конца, и для задания склейки всех крестов, нужно сказать — какой конец с каким склеивается. Это и дает перестановку из 4га элементов. Впрочем, не любая перестановка сг задает склейку. Нужно выполнение некоторых простых условий.
1) Поскольку концы крестов склеиваются попарно, то перестановка сг очевидно должна быть инволюцией.
2) Так как каждый конец х сам с собой не склеивается, то сг(ж) ф х. То есть каждый конец склеивается обязательно с каким-то другим концом.
88
Глава 2
"жАгГг Sz ^/77/^/77 //77 ^777
dfeCJ ^fccz)
O'- склейка, 6X*) Ф *, 62(*) = *¦
Рис. 2.30
Другими словами, необходимым условием является, что а — это инволюция без неподвижных точек.
Верно и обратное. Любая такая инволюция реализуется в виде некоторой склейки набора крестов. В результате получается некоторый атом.
Обозначим описанное выше подмножество в группе перестановок через Gm.
Возвратимся к вопросу — какие же склейки одного и того же набора крестов дают один и тот же атом?
Предположим, что две склейки дали один и тот же результат. Это означает, что существует гомеоморфизм одного атома на другой. Но каждый атом состоит из крестов с указанными склейками их концов. Возникший гомеоморфизм атомов задает, следовательно, некоторый гомеоморфизм множества еще несклеенных крестов на себя. Этот гомеоморфизм является композицией двух преобразований. Первое — некоторая перестановка крестов. Второе — для каждого креста нужно указать некоторую его симметрию на себя, уважающую его раскраску, т. е. переводящую белое в белое, и черное в черное. Последних симметрий — ровно четыре. Они отвечают элементам группы Z2 + Z2.
Таким образом, на множестве Gm действует некоторая подгруппа Н группы перестановок. Эта подгруппа была только что описана.
Для выяснения эквивалентности двух склеек теперь достаточно проверить — лежат ли две отвечающие им перестановки в одной и той же орбите действия этой группы Н, или же они принадлежат разным орбитам. Так как действующая группа Н конечна, и так как множество Gm тоже конечно, то ответ на этот вопрос дается, например, простым перебором.
Поскольку мы с самого начала фиксировали раскраску крестов на чернобелые области, то в действительности описанный выше алгоритм распознает эквивалентные /-атомы, а не просто атомы. Для этого нужно добавить к описанной выше группе Н еще один класс преобразований — перестановку белого и черного цветов на всех крестах одновременно, т.е. на всем атоме. Это расширяет
Топология слоений, порождаемых функциями Морса
89
группу Н при помощи группы Z2. Образующая этой дополнительной группы Z2 действует так: на всех крестах одновременно выполняется симметрия относительно вертикальной прямой, проходящей через центр креста (рис. 2.30).
