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

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

Цикл — это множество степеней элемента a группы, где a ⁿ , n -ая степень элемента a , определяется как произведение a на себя n раз. Говорят, что элемент a генерирует цикл. В конечной группе некоторая ненулевая степень элемента a должна быть равна нейтральному (единичному) элементу e . Наименьшая такая степень называется порядком цикла и она равна числу различных элементов в цикле. В графе циклов цикл представляется многоугольником, в котором вершины отражают элементы группы, а соединяющие вершины рёбра указывают, что вершины многоугольника являются членами одного цикла.

Циклы

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

Если a генерирует цикл порядка 6 (или, более коротко, имеет порядок 6), то a ⁶ = e . В этом случае степени квадрата элемента a ² , { a ² , a ⁴ , e } образуют цикл, но в реальности этот факт не даёт никакой дополнительной информации. Аналогично, a ⁵ генерирует тот же самый цикл, что и сам a .

Таким образом, нужно рассматривать только простые циклы, а именно те, которые не являются подмножествами других циклов. Каждый из этих циклов генерируется некоторым простым элементом a . Возьмём одну вершину для каждого элемента исходной группы. Для каждого простого элемента соединим ребром e с a , a с a ² , ..., a ^{n

−1} с a ⁿ , и т.д., пока не получим опять e . Результатом будет граф циклов.

Если a ² = e , a имеет порядок 2 (является инволюцией ) и соединено с единичным элементом e двумя рёбрами. Кроме случаев, когда хотят подчеркнуть два ребра цикла, обычно рисуется только одно ребро.

Свойства

Dih ₄ калейдоскоп с красным зеркалом и 4-кратными генераторами вращения	Граф циклов диэдральной группы Dih ₄ .

В качестве примера графа циклов группы рассмотрим диэдральную группу Dih ₄ . Таблица умножения этой группы показана ниже, а граф циклов показан на рисунке справа ( e показывает единичный элемент).

^o	e	b	a	a ²	a ³	ab	a ² b	a ³ b
e	e	b	a	a ²	a ³	ab	a ² b	a ³ b
b	b	e	a ³ b	a ² b	ab	a ³	a ²	a
a	a	ab	a ²	a ³	e	a ² b	a ³ b	b
a ²	a ²	a ² b	a ³	e	a	a ³ b	b	ab
a ³	a ³	a ³ b	e	a	a ²	b	ab	a ² b
ab	ab	a	b	a ³ b	a ² b	e	a ³	a ²
a ² b	a ² b	a ²	ab	b	a ³ b	a	e	a ³
a ³ b	a ³ b	a ³	a ² b	ab	b	a ²	a	e

Обратим внимание на цикл e , a , a ² , a ³ . Его можно видеть в таблице как последовательные степени a . Обратный проход тоже подходит. Другими словами, ( a ³ ) ² = a ² , ( a ³ ) ³ = a и ( a ³ ) ⁴ = e . Это поведение остаётся верным в любом цикле любой группы — цикл можно проходить в любом направлении.

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

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

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

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

История

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

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

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

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

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

Циклические группы Z _n порядка n имеют единственный цикл, который можно нарисовать как многоугольник с n сторонами:

Z ₁	Z ₂ = Dih ₁	Z ₃	Z ₄	Z ₅	Z ₆ =Z ₃ ×Z ₂	Z ₇	Z ₈


Z ₉	Z ₁₀ =Z ₅ ×Z ₂	Z ₁₁	Z ₁₂ =Z ₄ ×Z ₃	Z ₁₃	Z ₁₄ =Z ₇ ×Z ₂	Z ₁₅ =Z ₅ ×Z ₃	Z ₁₆

Z ₁₇	Z ₁₈ =Z ₉ ×Z ₂	Z ₁₉	Z ₂₀ =Z ₅ ×Z ₄	Z ₂₁ =Z ₇ ×Z ₃	Z ₂₂ =Z ₁₁ ×Z ₂	Z ₂₃	Z ₂₄ =Z ₈ ×Z ₃

Z ₂	Z ₂ ² = Dih ₂	Z ₂ ³ = Dih ₂ ×Dih ₁	Z ₂ ⁴ = Dih ₂ ²

Если n является простым числом , группы вида (Z _n ) ^m имеют ( n ^m − 1)/( n − 1) циклов длины n с общим единичным элементом:

Z ₂ ² = Dih ₂	Z ₂ ³ = Dih ₂ ×Dih ₁	Z ₂ ⁴ = Dih ₂ ²	Z ₃ ²

Диэдральные группы Dih _n имеют порядок 2 n и состоят из цикла длины n и n 2-элементных циклов:

Dih ₁ = Z ₂	Dih ₂ = Z ₂ ²	Dih ₃	Dih ₄	Dih ₅	Dih ₆ =Dih ₃ ×Z ₂	Dih ₇	Dih ₈	Dih ₉	Dih ₁₀ =Dih ₅ ×Z ₂

Дициклические группы , Dic _n = Q _4n имеют порядок 4 n :

Dic ₂ = Q ₈	Dic ₃ = Q ₁₂	Dic ₄ = Q ₁₆	Dic ₅ = Q ₂₀	Dic ₆ = Q ₂₄

Другие прямые произведения :

Z ₄ ×Z ₂	Z ₄ ×Z ₂ ²	Z ₆ ×Z ₂	Z ₈ ×Z ₂	Z ₄ ²

Симметрическая группа S _n для любой группы порядка n содержит подгруппу, изоморфную этой группе, так что граф циклов любой группы порядка n можно найти в качестве подграфа графа циклов S _n .
Смотрите пример: .

Пример: Подгруппы полной октаэдральной группы


S ₄ × Z ₂	A ₄ × Z ₂	Dih ₄ × Z ₂	S ₃ × Z ₂

является прямым произведением симметрической группы S ₄ и циклической группы Z ₂ .
Группа имеет порядок 48 и содержит подгруппы любого порядка, делящего 48.

В примерах ниже вершины, связанные друг с другом, расположены рядом,
Так что представленные графы циклов не являются наиболее простыми графами этих групп (сравните с графами циклов тех же групп в начале раздела).

S ₄ × Z ₂ (order 48)	A ₄ × Z ₂ (order 24)	Dih ₄ × Z ₂ (order 16)	S ₃ × Z ₂ = Dih ₆ (order 12)


S ₄ (order 24)	A ₄ (order 12)	Dih ₄ (order 8)	S ₃ =Dih ₃ (order 6)

Подобно всем другим графам графы циклов можно представить различными способами, чтобы подчеркнуть различные свойства. Два представления графа циклов группы S ₄ являются примером этого.


Граф циклов группы S ₄ , приведённый выше, подчёркивает наличие трёх Dih ₄ подгрупп.


Эти два представления подчёркивают симметрию, которую можно видеть в перевёртывании множеств справа.

См. также

Примечания

Sarah Perkins. . Birkbeck College, Malet Street, London, WC1E 7HX: School of Economics, Mathematics and Statistics (2000). Дата обращения: 31 января 2016. 31 января 2016 года.
, p. 246.
, с. xii.
, с. 83–98, 206–208.
, p. 225.
.

Литература

Steven Skiena. §4.2.3 Cycles, Stars, and Wheels // . — Addison-Wesley, 1990. — С. -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 // . — 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 .