Циклічний граф (алгебра)

В теорії груп, яка є розділом абстрактної алгебри, циклічний граф групи ілюструє різні цикли групи і особливо корисний при візуалізації структури малих скінченних груп.

Цикл — це множина ступенів даного елемента групи a, де aⁿ, n-та ступень елементу a визначається як добуток, помножений на себе n раз. Елемент a називається генератором циклу. У скінченній групі деяка ненульова ступінь повинна бути нейтральним елементом e; така найменша ступінь є порядком циклу, тобто кількістю різних елементів циклу. У циклічному графі, цикл зображується у вигляді багатокутника, з вершинами, що представляють елементи групи, і сполучними лініями, що вказують, на те що всі елементи в цьому багатокутнику є членами одного і того ж циклу.

Цикли

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

Якщо a породжує цикл 6-го порядку (або, більш коротко, має порядок 6), то a⁶ = e. Тоді множина ступенів a², {a², a⁴, e} є циклом, але це очевидно. Аналогічно, a⁵ генерує той самий цикл, що і a.

Таким чином, потрібно розглядати тільки первісні цикли, а саме ті, що не є підмножинами іншого циклу. Кожен з них породжується деяким первісним елементом, a. Візьмемо вершину для кожного елемента вихідної групи. Для кожного первісного елемента, треба поєднати е і a, a вже з a², …, aⁿ⁻¹ з aⁿ і т. д., поки е не буде досягнуто. В результаті отримуємо циклічний граф.

Коли a² = e, a має порядок 2 (це інволюція), і з'єднана з e двома ребрами. За винятком випадків, коли мета полягає в тому, щоб підкреслити, що маємо два ребра циклу, то граф, як правило, малюється^[1] у вигляді однієї лінії між цими двома елементами.

Властивості

Dih4 калейдоскоп з червоним дзеркалом і 4-кратним генератором обертання

Циклічний граф для діедральної групи 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, a², a³. З таблиці множення можна побачити, що послідовні ступені поводяться так і у прямому, і у зворотньому порядку. Іншими словами: (a³)²=a², (a³)³=a, і (a³)⁴=e. Така поведінка справедлива для будь-якого циклу в будь-якій групі — цикл може бути пройдений в будь-якому напрямку.

Циклічний граф групи кватерніона Q₈.

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

Існує поняття неоднозначності, коли два цикли мають спільний, не одиничний елемент. Розглянемо, наприклад, просту групу кватерніона, чий циклічний граф показаний праворуч. Кожен з елементів в середньому рядку при множенні на себе дає -1 (де 1 — це одиничний елемент). У цьому випадку ми можемо використовувати різні кольори для відстеження циклів. Як зазначалося раніше, два ребра 2-елементного циклу, як правило, представлені у вигляді одного рядка.

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

Історія

Циклічні графи досліджував числовий теоретик Даніель Шенкс^[en] на початку 1950-х років, як інструмент для вивчення мультиплікативних груп кільця лишків за модулем n.^[2] Шенкс вперше опублікував цю ідею в 1962 у першому виданні своєї книги «Вирішені та невирішені проблеми в теорії чисел». ^[3] У книзі, Шенкс досліджує, які групи мають ізоморфні циклічні графи і, коли цикл є планарним графом.^[4] У другому виданні 1978 року, Шенкс розмірковує про своє дослідження класових груп і розвиток алгоритму великих і малих кроків^[ru]:^[5]

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

Графи циклу використовуються як педагогічний інструмент у підручнику Теорія візуальних груп Натана Картера.^[6]

Графи циклів деяких сімейств групи

Певні типи груп дають типові графи:

Циклічні групи Z_n, порядку n, являють собою один цикл графу простого n-кутника з вершинами елементів.

Z1	Z2 = Dih1	Z3	Z4	Z5	Z6=Z3×Z2	Z7	Z8
Z9	Z10=Z5×Z2	Z11	Z12=Z4×Z3	Z13	Z14=Z7×Z2	Z15=Z5×Z3	Z16
Z17	Z18=Z9×Z2	Z19	Z20=Z5×Z4	Z21=Z7×Z3	Z22=Z11×Z2	Z23	Z24=Z8×Z3

Z2	Z22 = Dih2	Z23 = Dih2×Dih1	Z24 = Dih22

При простому числі n, групи виду (Z_n)^m матимуть (n^m − 1)/(n − 1) n-цикли, що ділять окремий елемент.

Z22 = Dih2	Z23 = Dih2×Dih1	Z24 = Dih22	Z32

Діедральні групи Dih_n, порядку 2n складаються з циклу n-елементу і n циклів 2-елементу.

Dih1 = Z2	Dih2 = Z22	Dih3	Dih4	Dih5	Dih6=Dih3×Z2	Dih7	Dih8	Dih9	Dih10=Dih5×Z2

Біциклічні групи^[en], Dic_n = Q_4n, порядку 4n.

Dic2 = Q8	Dic3 = Q12	Dic4 = Q16	Dic5 = Q20	Dic6 = Q24

Інші прямі добутки:

Z4×Z2	Z4×Z22	Z6×Z2	Z8×Z2	Z42

Симетрична група — симетрична група S_n містить для будь-якої групи порядку n, підгрупу, ізоморфну цій групі. Таким чином, циклічний граф кожної групи порядку n можна знайти в циклічному графі S_n.

A4×Z2

S3 = Dih3

S4

Один з трьох Dih4, що знаходиться в S4 Те ж саме, що й

Див. також

• Граф Келі

Посилання

• Weisstein, Eric W. Cycle Graph(англ.) на сайті Wolfram MathWorld.
• R. J. Mathar (2014). Plots of cycle graphs of the finite groups up to order 36.