УДК 512.54
Гамильтоновость графов Кэли простой группа порядка 168
КемГУ математический факультет кафедра алгебры и геометрии
89505973267
*****@***ru
Пусть G − некоторая группа, S − симметричное порождающее множество группы G, не содержащее единицы G. Вершинами неориентированного графа Кэли Cay(G, S) являются элементы множества G, пара {x, y}, x, y € G, является ребром тогда и только тогда, когда x = ys или x = ys-1 для некоторого элемента s € S. Более сорока лет назад было высказано предположение о том, что каждый граф Кэли конечной группы гамильтонов. Это предположение до сих пор не доказано и не опровергнуто. Имеется много работ, в которых это предположение доказывается для тех или иных конкретных групп.
В этой работе мы доказываем, что каждый граф Кэли простой группы G порядка 168 является гамильтоновым. Простая группа порядка 168 может быть реализована как группа всех невырожденных матриц GL3(F2) порядка три над полем из двух элементов F2. Известно также, что эта группа изоморфна проективной группе матриц PGL3(F7) второго порядка над полем F7 из семи элементов. Пусть V — векторное пространство над полем F2. Так как каждый линейный оператор V действует как перестановка на семи ненулевых векторах V, то имеет место инъективный гомоморфизм GL3(F2)®A7. Таким образом, элементы нашей группы можно представлять как четные перестановки на семи символах.
На первом шаге строятся все графы Кэли группы G с точностью до эквивалентности относительно группы автоморфизмов группы G. При этом два графа Кэли Cay(G, S) и Cay(G, T) эквивалентны в указанном смысле, если T = Sσ для некоторого автоморфизма σ группы G.
На втором шаге для каждого графа Кэли построенного на первом шаге строится гамильтонов цикл.
Для вычисления гамильтоновых циклов используется следующий алгоритм:
1. Берем произвольную цепь длины 1 (ребро) одну из вершин цепи будем называть начальной (она не изменяется на протяжении работы всего алгоритма), другую — концевой.
2. Берем вершину смежную с концевой вершиной, не являющуюся предыдущей вершиной этой цепи.
3. Если вершина не принадлежит цепи, то к цепи добавляем ребро, связывающее концевую вершину и вершину которую мы выбрали. Получаем новую цепь и переходим к пункту 2.
4. Если вершина принадлежит цепи, то добавляем ребро.
5. Если после пункта 4 получился гамильтонов цикл, алгоритм закончен.
6. Удаляем ребро смежное с добавленным ребром такое, чтобы получилась цепь, и переходим к пункту 2.
Алгоритмы первого и второго шагов реализованы в системе компьютерной алгебры GAP4. GAP - свободно распространяемый, открытый и расширяемый программный комплекс для применения в области вычислительной дискретной математики, в частности, теории групп. GAP запускается практически в любой версии Unix/Linux, MacOS и Windows.
С помощью GAP вычислены 53 графов Кэли, которым эквивалентны все остальные графы этой группы. Среди них: 8 графов 3степени, 26 графов 4 степени, 14 графов 5 степени, 5 графов 6 степени.
Для каждого из этих 53 графов Кэли найдены гамильтоновы циклы. Например для графа Кэли с порождающим множеством
[ (2,4,6)(3,5,7), (1,2,3)(4,6,5), (1,3,4)(2,7,5) ]
добавим обратные элементы в список
[ (2,4,6)(3,5,7), (1,2,3)(4,6,5), (1,3,4)(2,7,5), (2,6,4)(3,7,5), (1,3,2)(4,5,6), (1,4,3)(2,5,7) ]
гамильтонов цикл выглядит так:
[ 5, 4, 4, 5, 5, 3, 1, 5, 5, 1, 3, 2, 2, 1, 6, 6, 2, 3, 1, 5, 1, 3, 2, 3, 1,
2, 3, 1, 2, 6, 6, 4, 6, 1, 3, 3, 5, 5, 3, 3, 4, 3, 3, 5, 4, 4, 5, 3, 5, 5,
4, 2, 3, 2, 1, 3, 3, 1, 3, 4, 2, 2, 1, 3, 3, 1, 2, 2, 6, 2, 1, 3, 5, 3, 5,
3, 1, 6, 1, 2, 4, 5, 5, 3, 2, 6, 4, 3, 2, 2, 1, 1, 6, 4, 6, 6, 2, 6, 4, 4,
6, 5, 6, 5, 1, 5, 3, 2, 1, 6, 5, 5, 1, 5, 3, 3, 1, 1, 5, 6, 5, 5, 1, 3, 5,
1, 3, 2, 1, 1, 5, 1, 3, 4, 2, 3, 2, 4, 4, 6, 6, 2, 6, 2, 4, 3, 1, 5, 5, 6,
4, 2, 2, 3, 2, 4, 6, 2, 6, 6, 4, 2, 3, 3, 2, 6, 6, 5 ]
Здесь цифрами 1, 2, 3, 4, 5, 6 обозначены порождающие, а сам цикл представляет собой не последовательность вершин, а последовательность меток, с помощью которых каждая вершина соединяется с последующей.
Данная работа является продолжением курсовой работы проделанной мной ранее.
Литература:
1. http://www. gap-system. org/ukrgap/gapbook/chap0.html
2. «Конкретная теория групп»
3. «Введение в теорию групп»
4. Timothy L. «The existence and uniqueness of a simple group of order 168»
Научный руководитель – кандидат физ.-мат. наук, доцент
