Граф циклов (алгебра)

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Граф циклов группы иллюстрирует различные циклы в группе и, в частности, используется для визуализации структуры малых конечных групп.

Цикл — это множество степеней элемента 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. Обратный проход тоже подходит. Другими словами, (a3)2 = a2, (a3)3 = a и (a3)4 = e. Это поведение остаётся верным в любом цикле любой группы — цикл можно проходить в любом направлении.

Граф циклов группы кватернионов Q8.

Циклы, содержащие непростые значения элементов, неявно содержат циклы, не показанные в графе. Для группы Dih4 выше мы можем нарисовать ребро между a2 и e, поскольку (a2)2 = e, но a2 является частью большего цикла, так что ребро не проведено.

Может существовать неопределённость, если два цикла содержат элемент, не являющийся единичным элементом. Рассмотрим, например, группу кватернионов, граф циклов которой показан справа. Каждый элемент в среднем ряду, умноженный на себя, даёт −1. В этом случае мы можем использовать различные цвета для отражения циклов, хотя просто соглашение о симметрии будет работать так же хорошо.

Как упоминалось ранее, два ребра цикла из двух элементов обычно изображаются единственным ребром.

Обратный элемент можно найти в графе циклов следующим образом: это элемент, находящийся на том же расстоянии от единицы, но в обратном направлении.

История[править | править код]

Графы циклов рассматривал специалист по теории чисел Дэниел Шенкс в начале 1950-х как средство изучения мультипликативных групп колец вычетов[2]. Шенкс первым опубликовал идею в первом издании (1962) его книги «Solved and Unsolved Problems in Number Theory» («Решённые и нерешённые проблемы теории чисел»)[3]. В книге Шенкс исследует, какие группы имеют изоморфные графы циклов и когда граф циклов планарен[4]. Во втором издании (1978) Шенкс рассуждает о своих исследованиях групп классов идеалов и разработке алгоритма больших и малых шагов[5]:

«Графы циклов оказались полезными при работе с абелевыми группами и я использовал их часто для понимания их сложной структуры [77, стр. 852], для получения множественных связей [78, стр. 426] или выделения некоторых подгрупп [79].»

Графы циклов используются в качестве учебного средства во вводном учебнике Натана Картера (Nathan Carter, 2009) «Visual Group Theory» («Наглядная теория групп»)[6].

Графы циклов некоторых семейств групп[править | править код]

Некоторые виды групп имеют типичные графы:

Циклические группы 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 имеют (nm − 1)/(n − 1) циклов длины 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

Полная октаэдральная группа[en] является прямым произведением симметрической группы 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
Эти два представления подчёркивают симметрию, которую можно видеть в перевёртывании множеств справа.

См. также[править | править код]

Примечания[править | править код]

  1. Sarah Perkins. Commuting Involution Graphs for A˜n, Section 2.2, p.3, first figure. Birkbeck College, Malet Street, London, WC1E 7HX: School of Economics, Mathematics and Statistics (2000). Дата обращения 31 января 2016.
  2. Shanks, 1978, p. 246.
  3. Shanks, 1978, с. xii.
  4. Shanks, 1978, с. 83–98, 206–208.
  5. Shanks, 1978, p. 225.
  6. Carter, 2009.

Литература[править | править код]

  • Steven Skiena. §4.2.3 Cycles, Stars, and Wheels // Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. — Addison-Wesley, 1990. — С. 144-147. — ISBN 0201509431.
  • Daniel Shanks. Solved and Unsolved Problems in Number Theory. — 2nd. — New York: Chelsea Publishing Company, 1978. — ISBN 0-8284-0297-3.
  • Sriram Pemmaraju, Steven S. Skiena. §6.2.4 Cycles, Stars, and Wheels // Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematics. — Cambridge, England: Cambridge University Press, 2003. — С. pp. 248-249. — ISBN 0-521-80686-0.
  • Nathan Carter. Visual Group Theory. — Mathematical Association of America, 2009. — (Classroom Resource Materials). — ISBN 978-0-88385-757-1.

Ссылки[править | править код]