В теории групп , подпол абстрактной алгебры , группа цикл график иллюстрирует различные циклы из в группе , и особенно полезно при визуализации структуры малых конечных групп .
Цикл - это набор степеней данного элемента группы a , где a n , n-я степень элемента a определяется как произведение a, умноженного на себя n раз. Говорят, что элемент a генерирует цикл. В конечной группе, некоторая ненулевая сила должна быть единичной группа , е ; самая низкая такая мощность - это порядокцикла, количество отдельных элементов в нем. В графе циклов цикл представлен в виде многоугольника, вершины которого представляют элементы группы, а соединительные линии указывают, что все элементы в этом многоугольнике являются членами одного цикла.
Циклы
Циклы могут перекрываться, или у них не может быть ничего общего, кроме идентичности. График цикла отображает каждый интересующий цикл в виде многоугольника.
Если a порождает цикл порядка 6 (или, короче, имеет порядок 6), то a 6 = e . Тогда набор степеней a 2 , { a 2 , a 4 , e } представляет собой цикл, но это действительно не новая информация. Аналогичным образом , 5 генерирует тот же цикл , как в себе.
Таким образом, необходимо рассматривать только примитивные циклы, а именно те, которые не являются подмножествами другого цикла. Каждый из них порождается некоторым примитивным элементом , . Возьмите по одному очку за каждый элемент исходной группы. Для каждого примитивного элемента, подключают е к , в виде 2 , ..., в п -1 к в п и т.д., пока е не будет достигнута. Результатом является график цикла.
Когда a 2 = e , a имеет порядок 2 (является инволюцией ) и соединяется с e двумя ребрами. За исключением случаев, когда цель состоит в том, чтобы выделить два края цикла, его обычно рисуют [1] как одну линию между двумя элементами.
Характеристики
Калейдоскоп Dih 4 с красным зеркалом и 4-кратными генераторами вращения | Граф циклов для диэдральной группы Dih 4 . |
В качестве примера графа групповых циклов рассмотрим группу диэдра Dih 4 . Таблица умножения для этой группы показана слева, а график цикла показан справа, где e указывает единичный элемент.
о | е | б | а | а 2 | а 3 | ab | а 2 б | а 3 б |
---|---|---|---|---|---|---|---|---|
е | е | б | а | а 2 | а 3 | ab | а 2 б | а 3 б |
б | б | е | а 3 б | а 2 б | ab | а 3 | а 2 | а |
а | а | ab | а 2 | а 3 | е | а 2 б | а 3 б | б |
а 2 | а 2 | а 2 б | а 3 | е | а | а 3 б | б | ab |
а 3 | а 3 | а 3 б | е | а | а 2 | б | ab | а 2 б |
ab | ab | а | б | а 3 б | а 2 б | е | а 3 | а 2 |
а 2 б | а 2 б | а 2 | ab | б | а 3 б | а | е | а 3 |
а 3 б | а 3 б | а 3 | а 2 б | ab | б | а 2 | а | е |
Обратите внимание на цикл { e , a , a 2 , a 3 } в таблице умножения, где a 4 = e . Обратный элемент a −1 = a 3 также является генератором этого цикла: ( a 3 ) 2 = a 2 , ( a 3 ) 3 = a и ( a 3 ) 4 = e . Точно так же любой цикл в любой группе имеет не менее двух образующих и может проходить в любом направлении. В более общем смысле, количество генераторов цикла с n элементами задается функцией Эйлера φ от n , и любой из этих генераторов может быть записан как первый узел в цикле (рядом с тождеством e ); или чаще узлы остаются немаркированными. Два различных цикла не могут пересекаться в образующей.
Циклы, содержащие непростое число элементов, имеют циклические подгруппы, не показанные на графике. Для группы DIH 4 выше, мы могли бы провести линию между более 2 и е поскольку ( в 2 ) 2 = е , но так как 2 является частью более крупного цикла, это не ребро графа цикла.
Может возникнуть двусмысленность, когда два цикла разделяют неидентификационный элемент. Например, группа кватернионов из 8 элементов имеет график цикла, показанный справа. Каждый из элементов в средней строке при умножении на себя дает -1 (где 1 - это единичный элемент). В этом случае мы можем использовать разные цвета для отслеживания циклов, хотя соображения симметрии также будут работать.
Как отмечалось ранее, два края двухэлементного цикла обычно представлены как одна линия.
Обратным элементом элемента является узел, симметричный ему в его цикле относительно отражения, которое фиксирует идентичность.
История
Графы циклов были исследованы теоретиком чисел Дэниелом Шэнксом в начале 1950-х годов как инструмент для изучения мультипликативных групп классов вычетов . [2] Шанкс впервые опубликовал эту идею в 1962 году в первом издании своей книги « Решенные и нерешенные проблемы теории чисел» . [3] В книге Шанкс исследует, какие группы имеют изоморфные графы циклов, а когда граф циклов является плоским . [4] Во втором издании 1978 года Шанкс размышляет о своих исследованиях групп классов и развитии метода гигантских шагов « бэби-шаг» : [5]
Графы циклов оказались полезными при работе с конечными абелевыми группами; и я часто использовал их, чтобы обойти замысловатую структуру [77, с. 852], при получении желаемого мультипликативного отношения [78, с. 426], или в изоляции некоторой разыскиваемой подгруппы [79].
Графики цикла используются в качестве педагогического инструмента во вводном учебнике Натана Картера 2009 года « Visual Group Theory» . [6]
Графические характеристики отдельных групповых семейств
Некоторые типы групп дают типичные графики:
Циклические группы Z n , порядок n , представляют собой единственный цикл, изображенный на графике просто как n- сторонний многоугольник с элементами в вершинах:
Z 1 | Z 2 = Dih 1 | Z 3 | Z 4 | Z 5 | Z 6 = Z 3 × Z 2 | Z 7 | Z 8 |
---|---|---|---|---|---|---|---|
Z 9 | Z 10 = Z 5 × Z 2 | Z 11 | Z 12 = Z 4 × Z 3 | Z 13 | Z 14 = Z 7 × Z 2 | Z 15 = Z 5 × Z 3 | Z 16 |
Z 17 | Z 18 = Z 9 × Z 2 | Z 19 | Z 20 = Z 5 × Z 4 | Z 21 = Z 7 × Z 3 | Z 22 = Z 11 × Z 2 | Z 23 | Z 24 = Z 8 × Z 3 |
Z 2 | Z 2 2 = Dih 2 | Z 2 3 = Dih 2 × Dih 1 | Z 2 4 = Dih 2 2 |
---|
Когда n - простое число , группы формы (Z n ) m будут иметь ( n m - 1) / ( n - 1) n -элементных циклов, разделяющих единичный элемент:
Z 2 2 = Dih 2 | Z 2 3 = Dih 2 × Dih 1 | Z 2 4 = Dih 2 2 | Я 3 2 |
---|
Группы диэдра Dih n порядка 2 n состоят из n -элементного цикла и n 2-элементных циклов:
Dih 1 = Z 2 | Dih 2 = Z 2 2 | Dih 3 = S 3 | Dih 4 | Dih 5 | Dih 6 = Dih 3 × Z 2 | Dih 7 | Dih 8 | Dih 9 | Dih 10 = Dih 5 × Z 2 |
---|
Дициклические группы , Dic n = Q 4 n , порядок 4 n :
Dic 2 = Q 8 | Dic 3 = Q 12 | Dic 4 = Q 16 | Dic 5 = Q 20 | Dic 6 = Q 24 |
---|
Другие прямые продукты :
Z 4 × Z 2 | Z 4 × Z 2 2 | Z 6 × Z 2 | Z 8 × Z 2 | Я 4 2 |
---|
Симметричные группы - Симметрическая группа S n содержит для любой группы порядка n подгруппу, изоморфную этой группе. Таким образом, граф циклов каждой группы порядка n будет найден в графе циклов группы S n .
См. Пример: Подгруппы S 4
Пример: подгруппы полной октаэдрической группы
Полная октаэдрической группа представляет собой перекрестное произведение симметрической группы S 4 и циклической группы Z 2 .
Его порядок равен 48, и в нем есть подгруппы любого порядка, который делит 48.
В приведенных ниже примерах связанные друг с другом узлы расположены рядом друг с другом,
поэтому это не самые простые возможные графы циклов для этих групп (как те, что справа).
S 4 × Z 2 (заказ 48) | A 4 × Z 2 (заказ 24) | Dih 4 × Z 2 (заказ 16) | S 3 × Z 2 = Dih 6 (порядок 12) |
---|---|---|---|
S 4 (заказ 24) | A 4 (заказ 12) | Dih 4 (заказ 8) | S 3 = Dih 3 (порядок 6) |
Как и все графы, циклический граф может быть представлен по-разному, чтобы подчеркнуть разные свойства. Два представления графа циклов S 4 являются примером этого.
Смотрите также
Внешние ссылки
Рекомендации
- ^ Сара Перкинс (2000). «Коммутирующие инволюционные графы для A˜n, раздел 2.2, стр.3, первый рисунок» (PDF) . Биркбек-колледж, Малет-стрит, Лондон, WC1E 7HX: Школа экономики, математики и статистики . Проверено 31 января 2016 .CS1 maint: location ( ссылка )
- ^ Шанкс 1978 , стр. 246.
- ^ Шанкс 1978 , стр. xii.
- ↑ Шанкс, 1978 , стр. 83–98, 206–208.
- ^ Шанкс 1978 , стр. 225.
- ^ Картер, Натан (2009), Теория визуальных групп , учебные материалы для учебных заведений, Математическая ассоциация Америки, ISBN 978-0-88385-757-1
- Скиена, С. (1990). Циклы, звезды и колеса. Реализация дискретной математики: комбинаторика и теория графов с помощью Mathematica (стр. 144-147).
- Шанкс, Дэниел (1978) [1962], Решенные и нерешенные проблемы в теории чисел (2-е изд.), Нью-Йорк: Chelsea Publishing Company, ISBN 0-8284-0297-3
- Пеммараджу, С., & Скиена, С. (2003). Циклы, звезды и колеса. Вычислительная дискретная математика: комбинаторика и теория графов с Mathematica (стр. 248-249). Издательство Кембриджского университета.