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

Структура графа, изучаемая в теории групп

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle (\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 -сторонний многоугольник с элементами в вершинах:

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

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

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

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

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

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

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

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

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

Смотрите также

• Список малых групп
• График Кэли

Ссылки

1. Сара Перкинс (2000). "Коммутирующие инволюционные графы для A˜n, раздел 2.2, стр. 3, первый рисунок" (PDF) . Birkbeck College, Malet Street, London, WC1E 7HX: School of Economics, Mathematics and Statistics . Получено 31 января 2016 г.{{cite web}}: CS1 maint: местоположение ( ссылка )
2. Стэнфорд, Кейлеб; Веррет, Габриэль. «Является ли граф-цикл группы уникальным?». Mathematics Stack Exchange .
3. Шэнкс 1978, стр. 246.
4. Шэнкс 1978, стр. xii.
5. Шэнкс 1978, стр. 83–98, 206–208.
6. Шэнкс 1978, стр. 225.
7. Картер, Натан (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). Cambridge University Press.

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

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