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

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

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

Цикли

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

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

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

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

Властивості


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

Циклічний граф для діедральної групи Dih4.

Як приклад циклічного графу групи, розглянемо діедральну групу Dih4. Таблиця множення для цієї групи показана ліворуч, а цикл графу показано праворуч із зазначенням одиничного елементу e.

oebaa2a3aba2ba3b
e ebaa2a3aba2ba3b
b bea3ba2baba3a2a
a aaba2a3ea2ba3bb
a2 a2a2ba3eaa3bbab
a3 a3a3beaa2baba2b
ab ababa3ba2bea3a2
a2b a2ba2abba3baea3
a3b a3ba3a2babba2ae

Зверніть увагу на цикл e, a, a2, a3. З таблиці множення можна побачити, що послідовні ступені поводяться так і у прямому, і у зворотньому порядку. Іншими словами: (a3)2=a2, (a3)3=a, і (a3)4=e. Така поведінка справедлива для будь-якого циклу в будь-якій групі — цикл може бути пройдений в будь-якому напрямку.

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

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

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

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

Історія

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

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

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

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

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

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

Z1Z2 = Dih1Z3Z4Z5Z6=Z3×Z2Z7Z8
Z9Z10=Z5×Z2Z11Z12=Z4×Z3Z13Z14=Z7×Z2Z15=Z5×Z3Z16
Z17Z18=Z9×Z2Z19Z20=Z5×Z4Z21=Z7×Z3Z22=Z11×Z2Z23Z24=Z8×Z3
Z2 Z22 = Dih2 Z23 = Dih2×Dih1 Z24 = Dih22

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

Z22 = Dih2Z23 = Dih2×Dih1Z24 = Dih22Z32

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

Dih1 = Z2Dih2 = Z22Dih3Dih4Dih5Dih6=Dih3×Z2Dih7Dih8Dih9Dih10=Dih5×Z2

Біциклічні групи, Dicn = Q4n, порядку 4n.

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

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

Z4×Z2Z4×Z22Z6×Z2Z8×Z2Z42

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


A4×Z2

S3 = Dih3

S4

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

Див. також

Посилання

Посилання

  1. Sarah Perkins (2000). 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. Процитовано 31 січня 2016.
  2. Shanks, 1978, с. 246.
  3. Shanks, 1978, с. xii.
  4. Shanks, 1978, с. 83–98, 206–208.
  5. Shanks, 1978, с. 225.
  6. Carter, Nathan (2009). Visual Group Theory. Classroom Resource Materials. Mathematical Association of America. ISBN 978-0-88385-757-1.
  • Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica 1990, § 4.2.3 Cycles, Stars, and Wheels, pp. 144—147
  • Shanks, Daniel (1978) [1962]. Solved and Unsolved Problems in Number Theory (вид. 2nd). New York: Chelsea Publishing Company. ISBN 0-8284-0297-3.
  • Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematics Cambridge, England: Cambridge University Press, 2003, § 6.2.4 Cycles, Stars, and Wheels pp. 248—249
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.