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

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

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

Определение

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

Предположим, что элемент группы a порождает цикл порядка 6 (имеет порядок 6), так что узлы a , a ², а ³, а ⁴, а ⁵и ⁶ = e — вершины шестиугольника в графе циклов. Элемент а ² тогда имеет порядок 3; узлы но сделать ², а ⁴, а e — вершины треугольника в графе, не добавят новой информации. только примитивные Таким образом, необходимо учитывать циклы, те, которые не являются подмножествами другого цикла. Кроме того, узел a ⁵, который также имеет порядок 6, генерирует тот же цикл, что и сам a ; поэтому у нас есть как минимум два варианта, какой элемент использовать при создании цикла, а часто и больше.

Чтобы построить граф цикла для группы, мы начинаем с узла для каждого элемента группы. Затем для каждого примитивного цикла мы выбираем некоторый элемент a , который генерирует этот цикл, и соединяем узел для e с узлом для a , a с a. ², ..., а ^{к -1} к ^ки т. д., пока не вернемся к e . Результатом является график цикла для группы.

Когда элемент группы a имеет порядок 2 (так что умножение на a является инволюцией ), приведенное выше правило соединит e с a двумя ребрами, одно выходящее, а другое возвращающееся. За исключением случаев, когда целью является подчеркнуть два края такого цикла, его обычно рисуют ^[1] как одна линия между двумя элементами.

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

Пример и свойства

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

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

^тот	и	б	а	а ²	а ³	аб	а ²б	а ³б
и	и	б	а	а ²	а ³	аб	а ²б	а ³б
б	б	и	а ³б	а ²б	аб	а ³	а ²	а
а	а	аб	а ²	а ³	и	а ²б	а ³б	б
а ²	а ²	а ²б	а ³	и	а	а ³б	б	аб
а ³	а ³	а ³б	и	а	а ²	б	аб	а ²б
аб	аб	а	б	а ³б	а ²б	и	а ³	а ²
а ²б	а ²б	а ²	аб	б	а ³б	а	и	а ³
а ³б	а ³б	а ³	а ²б	аб	б	а ²	а	и

Обратите внимание на цикл { e , a , a ², а ³} в таблице умножения с помощью ⁴ = е . Обратное а ⁻¹ = а ³ также является генератором этого цикла: ( a ³) ² = а ², ( а ³) ³ = а и ( а ³) ⁴ = е . Точно так же любой цикл в любой группе имеет как минимум две образующие и может проходиться в любом направлении. В более общем смысле, количество генераторов цикла с n элементами определяется функцией Эйлера φ от n , и любой из этих генераторов может быть записан как первый узел в цикле (рядом с единицей e ); или, чаще, узлы остаются немаркированными. Два различных цикла не могут пересекаться в генераторе.

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

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

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

Инверсией элемента является узел, симметричный ему в его цикле относительно отражения, которое фиксирует идентичность.

Неуникальность

Граф циклов группы не определен однозначно с точностью до изоморфизма графов ; он также не определяет группу однозначно с точностью до группового изоморфизма . То есть полученный граф зависит от выбранного набора генераторов, и две разные группы (с выбранными наборами генераторов) могут генерировать один и тот же граф циклов. ^[2]

Одна группа может иметь разные графики циклов.

Для некоторых групп выбор разных элементов для создания различных примитивных циклов этой группы может привести к созданию разных графов циклов. Это пример для абелевой группы. $C_{5}\times C_{2}\times C_{2}$ , который имеет порядок 20. ^[2] Обозначим элемент этой группы как тройку чисел $(i;j,k)$ , где $0\leq i<5$ и каждый из $j$ и $k$ равно либо 0, либо 1. Тройка $(0;0,0)$ является элементом идентичности. На рисунках ниже, $i$ показано выше $j$ и $k$ .

Эта группа имеет три примитивных цикла, каждый порядка 10. В первом графе циклов мы выбираем в качестве генераторов этих трех циклов узлы $(1;1,0)$ , $(1;0,1)$ , и $(1;1,1)$ . Во втором мы генерируем третий из этих циклов (синий), начав вместо этого с $(2;1,1)$ .

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

Разные группы могут иметь один и тот же график циклов.

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

Пример этого уже есть для групп порядка 16, причем эти две группы $C_{8}\times C_{2}$ и $C_{8}\rtimes _{5}C_{2}$ . Абелева группа $C_{8}\times C_{2}$ является прямым произведением циклических групп порядков 8 и 2. Неабелева группа $C_{8}\rtimes _{5}C_{2}$ это полупрямой продукт $C_{8}$ и $C_{2}$ в котором неидентичный элемент $C_{2}$ умножения на отображается в автоморфизм 5 $C_{8}$ .

Рисуя графики циклов этих двух групп, мы берем $C_{8}\times C_{2}$ быть порождено элементами s и t с

s^{8}=t^{2}=1\quad {\text{and}}\quad ts=st,

где это последнее соотношение делает $C_{8}\times C_{2}$ абелев. И мы берем $C_{8}\rtimes _{5}C_{2}$ быть сгенерировано элементами 𝜎 и 𝜏 с

\sigma ^{8}=\tau ^{2}=1\quad {\text{and}}\quad \tau \sigma =\sigma ^{5}\tau .

Вот графики циклов для тех двух групп, где мы выбираем $st$ для создания зеленого цикла слева и $\sigma \tau$ чтобы сгенерировать этот цикл справа:

На правом графике зеленый цикл после перехода от 1 к $\sigma \tau$ , перемещается рядом с $\sigma ^{6},$ потому что

(\sigma \tau )(\sigma \tau )=\sigma (\tau \sigma )\tau =\sigma (\sigma ^{5}\tau )\tau =\sigma ^{6}.

История

Графы циклов были исследованы теоретиком чисел Дэниелом Шэнксом в начале 1950-х годов как инструмент для изучения мультипликативных групп классов вычетов . ^[3] Шэнкс впервые опубликовал эту идею в первом издании своей книги « Решенные и нерешенные проблемы теории чисел» в 1962 году . ^[4] В книге Шэнкс исследует, какие группы имеют изоморфные графы циклов и когда граф циклов является плоским . ^[5] Во втором издании 1978 года Шанкс размышляет о своих исследованиях классовых групп и разработке метода «маленький шаг — гигантский шаг» : ^[6]

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

Циклические графики используются в качестве педагогического инструмента во вводном учебнике Натана Картера « Теория визуальных групп» 2009 года . ^[7]

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

Определенные типы групп дают типичные графики:

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

З ₁	Z ₂ = Дих ₁	З ₃	З ₄	Z_Z5	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 ₂×Dih ₁	З ₂⁴ = Дих ₂²

Когда n — простое число , группы вида (Z _n ) ^м будет иметь ( н ^м − 1)/( n − 1) n -элементных циклов, разделяющих единичный элемент:

З ₂² = Дих ₂	З ₂³ = Dih ₂×Dih ₁	З ₂⁴ = Дих ₂²	З ₃²

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

Дих ₁ = Z ₂	Dih2 = _Z2²	Dih3 = _S3	Это ₄	Дих ₅	Дих ₆ = Дих ₃ ×Z ₂	Дих ₇	это ₈	День ₉	Дих ₁₀ = Дих ₅ ×Z ₂

Дициклические группы , Dic _n = Q _{4 n} , порядок 4 n :

Дик ₂ = Вопрос ₈	Дикс ₃ = Вопрос ₁₂	Дикс ₄ = Вопрос ₁₆	декабря ₅ = _{20 квартал}	Дикс ₆ = Вопрос ₂₄

Другие прямые продукты :

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

Симметричные группы . Симметричная группа Sn _{содержит} для любой группы порядка n подгруппу, изоморфную этой группе. Таким образом, граф циклов каждой группы порядка n будет найден в графе циклов группы _Sn .
См. пример: Подгруппы S ₄

Расширенный пример: подгруппы полной октаэдрической группы.

С ₄ × З ₂

А ₄ × З ₂

Дих ₄ × Z ₂

С ₃ × З ₂

Полная октаэдрическая группа является прямым произведением $S_{4}\times Z_{2}$ симметрической группы S ₄ и циклической группы Z ₂ .
Его порядок равен 48, и у него есть подгруппы каждого порядка, делящего 48.

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

S ₄ × Z ₂ (заказ 48)	А ₄ × Z ₂ (порядок 24)	Дих ₄ ×Z ₂ (порядок 16)	S ₃ × Z ₂ = Dih ₆ (порядок 12)


С ₄ (заказ 24)	А ₄ (заказ 12)	Дих ₄ (заказ 8)	S ₃ = Dih ₃ (порядок 6)

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

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

Это другое представление подчеркивает симметрию, наблюдаемую в наборах инверсий справа.

См. также

Ссылки

^ Сара Перкинс (2000). «Коммутирующие инволюционные графы для A˜n, раздел 2.2, стр.3, первый рисунок» (PDF) . Колледж Биркбек, Малет-стрит, Лондон, WC1E 7HX: Школа экономики, математики и статистики . Проверено 31 января 2016 г. {{cite web}}: CS1 maint: местоположение ( ссылка )
^ Jump up to: ^а ^б Стэнфорд, Калеб; Верре, Габриэль. «Уникален ли граф цикла группы?» . Математический обмен стеками .
^ Шанкс 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). Издательство Кембриджского университета.

Внешние ссылки

Вайсштейн, Эрик В. «График группового цикла» . Математический мир .

[1] Сара Перкинс (2000). «Коммутирующие инволюционные графы для A˜n, раздел 2.2, стр.3, первый рисунок» (PDF) . Колледж Биркбек, Малет-стрит, Лондон, WC1E 7HX: Школа экономики, математики и статистики . Проверено 31 января 2016 г. {{cite web}}: CS1 maint: местоположение ( ссылка )

[MathSENotUnique-2] Jump up to: ^а ^б Стэнфорд, Калеб; Верре, Габриэль. «Уникален ли граф цикла группы?» . Математический обмен стеками .

[FOOTNOTEShanks1978246-3] Шанкс 1978 , с. 246.

[FOOTNOTEShanks1978xii-4] Шанкс 1978 , с. xii.

[FOOTNOTEShanks197883–98,_206–208-5] Шанкс 1978 , стр. 83–98, 206–208.

[FOOTNOTEShanks1978225-6] Шанкс 1978 , с. 225.

[7] Картер, Натан (2009), Теория визуальных групп , Учебные материалы, Математическая ассоциация Америки, ISBN 978-0-88385-757-1

[1]

[2]

[3]

[4]

[5]

[6]

[7]