Осталось решить задачу алгоритмического распознавания в этом конечном, при фиксированном $m$, списке одинаковых, т. е. эквивалентных атомов.
Пусть даны два атома, получившиеся в результате склейки крестов. Удобно сформулировать задачу выяснения их эквивалентности или неэквивалентности так. Рассмотрим один набор крестов: (крест 1), (крест 2),.., (крест $m$ ), и две таблицы, кода, диктующие склейки их концов (рис. 2.30). Требуется выяснить будут ли гомеоморфны получившиеся атомы, т. е. поверхности с графом.
Задание той или иной склейки крестов очевидно эквивалентно заданию некоторого элемента $\sigma$ конечной группы перестановок $S_{4 m}$. Напомним, что каждый крест имеет по 4 конца, и для задания склейки всех крестов, нужно сказать какой конец с каким склеивается. Это и дает перестановку из $4 m$ элементов. Впрочем, не любая перестановка $\sigma$ задает склейку. Нужно выполнение некоторых простых условий.
1) Поскольку концы крестов склеиваются попарно, то перестановка $\sigma$ очевидно должна быть инволюцией.
2) Так как каждый конец $x$ сам с собой не склеивается, то $\sigma(x)
eq x$. То есть каждый конец склеивается обязательно с каким-то другим концом.
Другими словами, необходимым условием является, что $\sigma$ – это инволюция без неподвижных точек.
Верно и обратное. Любая такая инволюция реализуется в виде некоторой склейки набора крестов. В результате получается некоторый атом.
Обозначим описанное выше подмножество в группе перестановок через $G_{m}$.
Возвратимся к вопросу – какие же склейки одного и того же набора крестов дают один и тот же атом?
Предположим, что две склейки дали один и тот же результат. Это означает, что существует гомеоморфизм одного атома на другой. Но каждый атом состоит из крестов с указанными склейками их концов. Возникший гомеоморфизм атомов задает, следовательно, некоторый гомеоморфизм множества еще несклеенных крестов на себя. Этот гомеоморфизм является композицией двух преобразований. Первое – некоторая перестановка крестов. Второе – для каждого креста нужно указать некоторую его симметрию на себя, уважающую его раскраску, т.е. переводящую белое в белое, и черное в черное. Последних симметрий – ровно четыре. Они отвечают элементам группы $\mathbb{Z}_{2}+\mathbb{Z}_{2}$.
Таким образом, на множестве $G_{m}$ действует некоторая подгруппа $H$ группы перестановок. Эта подгруппа была только что описана.
Для выяснения эквивалентности двух склеек теперь достаточно проверить – лежат ли две отвечающие им перестановки в одной и той же орбите действия этой группы $H$, или же они принадлежат разным орбитам. Так как действующая группа $H$ конечна, и так как множество $G_{m}$ тоже конечно, то ответ на этот вопрос дается, например, простым перебором.
Поскольку мы с самого начала фиксировали раскраску крестов на чернобелые области, то в действительности описанный выше алгоритм распознает эквивалентные $f$-атомы, а не просто атомы. Для этого нужно добавить к описанной выше группе $H$ еще один класс преобразований – перестановку белого и черного цветов на всех крестах одновременно, т.е. на всем атоме. Это расширяет
группу $H$ при помощи группы $\mathbb{Z}_{2}$. Образующая этой дополнительной группы $\mathbb{Z}_{2}$ действует так: на всех крестах одновременно выполняется симметрия относительно вертикальной прямой, проходящей через центр креста (рис. 2.30).
Описанный алгоритм, конечно, достаточно прост и естественен, однако ввиду требующегося здесь большого перебора, он недостаточно эффективен. И причина этого ясна. Мы опирались здесь на задание атома в виде склейки крестов. Этот способ хотя и нагляден, но, как было только что показано, ведет к большому перебору при решении задач распознавания. Поэтому остается актуальной задача построения более эффективного алгоритма. Это можно сделать, и в следующем пункте мы его опишем.
