Русская Википедия:Граф циклов (алгебра)
Граф циклов группы иллюстрирует различные циклы в группе и, в частности, используется для визуализации структуры малых конечных групп.
Цикл — это множество степеней элемента a группы, где an, n-ая степень элемента a, определяется как произведение a на себя n раз. Говорят, что элемент a генерирует цикл. В конечной группе некоторая ненулевая степень элемента a должна быть равна нейтральному (единичному) элементу e . Наименьшая такая степень называется порядком цикла и она равна числу различных элементов в цикле. В графе циклов цикл представляется многоугольником, в котором вершины отражают элементы группы, а соединяющие вершины рёбра указывают, что вершины многоугольника являются членами одного цикла.
Циклы
Циклы могут накладываться или не иметь общих элементов, кроме единичного. Граф циклов показывает каждый цикл в виде многоугольника.
Если a генерирует цикл порядка 6 (или, более коротко, имеет порядок 6), то a6 = e. В этом случае степени квадрата элемента a2, {a2, a4, e} образуют цикл, но в реальности этот факт не даёт никакой дополнительной информации. Аналогично, a5 генерирует тот же самый цикл, что и сам a.
Таким образом, нужно рассматривать только простые циклы, а именно те, которые не являются подмножествами других циклов. Каждый из этих циклов генерируется некоторым простым элементом a. Возьмём одну вершину для каждого элемента исходной группы. Для каждого простого элемента соединим ребром e с a, a с a2, ..., an−1 с an, и т.д., пока не получим опять e. Результатом будет граф циклов.
Если a2 = e, a имеет порядок 2 (является инволюцией) и соединено с единичным элементом e двумя рёбрами. Кроме случаев, когда хотят подчеркнуть два ребра цикла, обычно рисуется[1] только одно ребро.
Свойства
| Файл:Dihedral group4 example.png Dih4 калейдоскоп с красным зеркалом и 4-кратными генераторами вращения |
Файл:Dih4 cycle graph.svg Граф циклов диэдральной группы Dih4. |
В качестве примера графа циклов группы рассмотрим диэдральную группу Dih4. Таблица умножения этой группы показана ниже, а граф циклов показан на рисунке справа (e показывает единичный элемент).
| o | e | b | a | a2 | a3 | ab | a2b | a3b |
|---|---|---|---|---|---|---|---|---|
| e | e | b | a | a2 | a3 | ab | a2b | a3b |
| b | b | e | a3b | a2b | ab | a3 | a2 | a |
| a | a | ab | a2 | a3 | e | a2b | a3b | b |
| a2 | a2 | a2b | a3 | e | a | a3b | b | ab |
| a3 | a3 | a3b | e | a | a2 | b | ab | a2b |
| ab | ab | a | b | a3b | a2b | e | a3 | a2 |
| a2b | a2b | a2 | ab | b | a3b | a | e | a3 |
| a3b | a3b | a3 | a2b | ab | b | a2 | a | e |
Обратим внимание на цикл e, a, a2, a3. Его можно видеть в таблице как последовательные степени a. Обратный проход тоже подходит. Другими словами, (Шаблон:Nowrap, Шаблон:Nowrap и Шаблон:Nowrap. Это поведение остаётся верным в любом цикле любой группы — цикл можно проходить в любом направлении.
Циклы, содержащие непростые значения элементов, неявно содержат циклы, не показанные в графе. Для группы Dih4 выше мы можем нарисовать ребро между a2 и e, поскольку Шаблон:Nowrap, но a2 является частью большего цикла, так что ребро не проведено.
Может существовать неопределённость, если два цикла содержат элемент, не являющийся единичным элементом. Рассмотрим, например, группу кватернионов, граф циклов которой показан справа. Каждый элемент в среднем ряду, умноженный на себя, даёт −1. В этом случае мы можем использовать различные цвета для отражения циклов, хотя просто соглашение о симметрии будет работать так же хорошо.
Как упоминалось ранее, два ребра цикла из двух элементов обычно изображаются единственным ребром.
Обратный элемент можно найти в графе циклов следующим образом: это элемент, находящийся на том же расстоянии от единицы, но в обратном направлении.
История
Графы циклов рассматривал специалист по теории чисел Дэниел Шенкс в начале 1950-х как средство изучения мультипликативных групп колец вычетовШаблон:Sfn. Шенкс первым опубликовал идею в первом издании (1962) его книги «Solved and Unsolved Problems in Number Theory» («Решённые и нерешённые проблемы теории чисел»)Шаблон:Sfn. В книге Шенкс исследует, какие группы имеют изоморфные графы циклов и когда граф циклов планаренШаблон:Sfn. Во втором издании (1978) Шенкс рассуждает о своих исследованиях групп классов идеалов и разработке алгоритма больших и малых шаговШаблон:Sfn:
| « |
Графы циклов оказались полезными при работе с абелевыми группами и я использовал их часто для понимания их сложной структуры [77, стр. 852], для получения множественных связей [78, стр. 426] или выделения некоторых подгрупп [79]. | » |
| — Анонимус | ||
Графы циклов используются в качестве учебного средства во вводном учебнике Натана Картера (Nathan Carter, 2009) «Visual Group Theory» («Наглядная теория групп»)Шаблон:Sfn.
Графы циклов некоторых семейств групп
Некоторые виды групп имеют типичные графы:
Циклические группы Zn порядка n имеют единственный цикл, который можно нарисовать как многоугольник с n сторонами:
| Файл:GroupDiagramMiniC1.svg | Файл:GroupDiagramMiniC2.svg | Файл:GroupDiagramMiniC3.svg | Файл:GroupDiagramMiniC4.svg | Файл:GroupDiagramMiniC5.svg | Файл:GroupDiagramMiniC6.svg | Файл:GroupDiagramMiniC7.svg | Файл:GroupDiagramMiniC8.svg |
| Z1 | Z2 = Dih1 | Z3 | Z4 | Z5 | Z6=Z3×Z2 | Z7 | Z8 |
|---|---|---|---|---|---|---|---|
| Файл:GroupDiagramMiniC9.svg | Файл:GroupDiagramMiniC10.svg | Файл:GroupDiagramMiniC11.svg | Файл:GroupDiagramMiniC12.svg | Файл:GroupDiagramMiniC13.svg | Файл:GroupDiagramMiniC14.svg | Файл:GroupDiagramMiniC15.svg | Файл:GroupDiagramMiniC16.svg |
| Z9 | Z10=Z5×Z2 | Z11 | Z12=Z4×Z3 | Z13 | Z14=Z7×Z2 | Z15=Z5×Z3 | Z16 |
| Файл:GroupDiagramMiniC17.svg | Файл:GroupDiagramMiniC18.svg | Файл:GroupDiagramMiniC19.svg | Файл:GroupDiagramMiniC20.svg | Файл:GroupDiagramMiniC21.svg | Файл:GroupDiagramMiniC22.svg | Файл:GroupDiagramMiniC23.svg | Файл:GroupDiagramMiniC24.svg |
| Z17 | Z18=Z9×Z2 | Z19 | Z20=Z5×Z4 | Z21=Z7×Z3 | Z22=Z11×Z2 | Z23 | Z24=Z8×Z3 |
| Файл:GroupDiagramMiniC2.svg | Файл:GroupDiagramMiniD4.svg | Файл:GroupDiagramMiniC2x3.svg | Файл:GroupDiagramMiniC2x4.svg |
| Z2 | Z22 = Dih2 | Z23 = Dih2×Dih1 | Z24 = Dih22 |
|---|
Если n является простым числом, группы вида (Zn)m имеют Шаблон:Nowrap циклов длины n с общим единичным элементом:
| Файл:GroupDiagramMiniD4.svg | Файл:GroupDiagramMiniC2x3.svg | Файл:GroupDiagramMiniC2x4.svg | Файл:GroupDiagramMiniC3x2.svg |
| Z22 = Dih2 | Z23 = Dih2×Dih1 | Z24 = Dih22 | Z32 |
|---|
Диэдральные группы Dihn имеют порядок 2n и состоят из цикла длины n и n 2-элементных циклов:
| Файл:GroupDiagramMiniC2.svg | Файл:GroupDiagramMiniD4.svg | Файл:GroupDiagramMiniD6.svg | Файл:GroupDiagramMiniD8.svg | Файл:GroupDiagramMiniD10.svg | Файл:GroupDiagramMiniD12.svg | Файл:GroupDiagramMiniD14.svg | Файл:GroupDiagramMiniD16.svg | Файл:GroupDiagramMiniD18.png | Файл:GroupDiagramMiniD20.png |
| Dih1 = Z2 | Dih2 = Z22 | Dih3 | Dih4 | Dih5 | Dih6=Dih3×Z2 | Dih7 | Dih8 | Dih9 | Dih10=Dih5×Z2 |
|---|
Дициклические группы, Dicn = Q4n имеют порядок 4n:
| Файл:GroupDiagramMiniQ8.svg | Файл:GroupDiagramMiniX12.svg | Файл:GroupDiagramMiniQ16.svg | Файл:GroupDiagramMiniQ20.png | Файл:GroupDiagramMiniQ24.png |
| Dic2 = Q8 | Dic3 = Q12 | Dic4 = Q16 | Dic5 = Q20 | Dic6 = Q24 |
|---|
Другие прямые произведения:
| Файл:GroupDiagramMiniC2C4.svg | Файл:GroupDiagramMiniC2x2C4.svg | Файл:GroupDiagramMiniC2C6.svg | Файл:GroupDiagramMiniC2C8.svg | Файл:GroupDiagramMiniC4x2.svg |
| Z4×Z2 | Z4×Z22 | Z6×Z2 | Z8×Z2 | Z42 |
|---|
Симметрическая группа Sn для любой группы порядка n содержит подгруппу, изоморфную этой группе, так что граф циклов любой группы порядка n можно найти в качестве подграфа графа циклов Sn.
Смотрите пример: Подгруппы группы S4.
Пример: Подгруппы полной октаэдральной группы
| Файл:GroupDiagramMiniS4xC2.svg | Файл:GroupDiagramMiniA4xC2.svg | Файл:GroupDiagramMiniC2D8.svg | Файл:GroupDiagramMiniD12.svg |
| S4 × Z2 | A4 × Z2 | Dih4 × Z2 | S3 × Z2 |
Шаблон:Не переведено 5 является прямым произведением симметрической группы S4 и циклической группы Z2.
Группа имеет порядок 48 и содержит подгруппы любого порядка, делящего 48.
В примерах ниже вершины, связанные друг с другом, расположены рядом,
Так что представленные графы циклов не являются наиболее простыми графами этих групп (сравните с графами циклов тех же групп в начале раздела).
| Файл:Full octahedral group; cycle graph.svg | Файл:Subgroup of Oh; A4xC2; cycle graph.svg | Файл:Subgroup of Oh; Dih4xC2 07; cycle graph.svg | Файл:Subgroup of Oh; Dih6 03; cycle graph.svg |
| S4 × Z2 (order 48) | A4 × Z2 (order 24) | Dih4 × Z2 (order 16) | S3 × Z2 = Dih6 (order 12) |
|---|---|---|---|
| Файл:Subgroup of Oh; S4 green orange; cycle graph.svg | Файл:Subgroup of Oh; A4; cycle graph.svg | Файл:Subgroup of Oh; Dih4 green orange 07; cycle graph.svg | Файл:Subgroup of Oh; S3 green 03; cycle graph.svg |
| S4 (order 24) | A4 (order 12) | Dih4 (order 8) | S3 =Dih3 (order 6) |
Подобно всем другим графам графы циклов можно представить различными способами, чтобы подчеркнуть различные свойства. Два представления графа циклов группы S4 являются примером этого.
| Файл:Subgroup of Oh; Dih4 green orange 07; cycle graph.svg | Файл:Subgroup of Oh; Dih4 green orange 16; cycle graph.svg | Файл:Subgroup of Oh; Dih4 green orange 23; cycle graph.svg |
| Граф циклов группы S4, приведённый выше, подчёркивает наличие трёх Dih4 подгрупп. | ||
| Файл:Symmetric group 4; cycle graph.svg | Файл:Symmetric group 4; cycle graph; inversions.svg | |
| Эти два представления подчёркивают симметрию, которую можно видеть в перевёртывании множеств справа. | ||
См. также
Примечания
Литература
Ссылки
