In der Gruppentheorie, einem Teilgebiet der abstrakten Algebra, stellt der Zykel-Graph die verschiedenen Zykel einer Gruppe dar. Er ist besonders zur Visualisierung der Struktur kleiner, endlicher Gruppen nützlich, spielt aber in der Gruppentheorie keine wichtige Rolle.

Ein Zykel einer Gruppe ist die Menge der Potenzen eines gegebenen Gruppenelements  , wobei die n-te Potenz   eines Elements   als das n-fache Produkt von   mit sich selbst definiert ist. In einer endlichen Gruppe muss eine positive Potenz von   das neutrale Element   ergeben, die kleinste Potenz, für die das eintritt, ist die Anzahl der verschiedenen Elemente des Zykels und heißt dessen Ordnung. In einem Zykel-Graphen werden die Zykel als Polygone dargestellt, die Ecken des Graphen stehen für die Gruppenelemente und Kanten deuten an, dass die durch sie verbundenen Ecken des Polygons zum selben Zykel gehören.

Zykel können sich überlappen oder mit Ausnahme des neutralen Elementes kein Element gemeinsam haben. Der Zykel-Graph zeigt jeden interessierenden Zykel als Polygon.

Wenn   einen Zykel der Ordnung 6 erzeugt (oder kurz: die Ordnung 6 hat), dann ist  . Die Menge der Potenzen von   ist der Zykel  , stellt aber keine neue Information dar, da er im von   erzeugten Zykel enthalten ist.   erzeugt denselben Zykel wie  .

Daher müssen nur sogenannte primitive Zykel betrachtet werden, das heißt solche, die nicht Teilmenge eines anderen sind. Jeder dieser Zykel wird von einem oder mehreren primitiven Elementen erzeugt. Der Zykel-Graph entsteht nun dadurch, dass man die Gruppenelemente als Ecken nimmt, zu jedem primitiven Zykel von   eine Kante zu einem primitiven Element   zieht und dann   mit  ,   mit  , … verbindet, bis man wieder beim neutralen Element angekommen ist.

Falls  , das heißt   die Ordnung 2 hat, also eine Involution ist, so ist dieses Element über zwei Kanten mit   verbunden. Wenn dies nicht besonders herausgestellt werden soll, so wird typischerweise nur eine Kante gezeichnet.[1]

Beispiele

Bearbeiten
 
Zykel-Graph der Diedergruppe  

Als Beispiel für einen Zykel-Graphen betrachten wir die Diedergruppe  . Die Verknüpfungstafel findet sich auf der linken Seite, rechts ist der Zykel-Graph mit dem neutralen Element   abgebildet:

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

Betrachte den Zykel  . Der Verknüpfungstafel können die aufeinanderfolgenden Potenzen von   entnommen werden. Die umgekehrte Reihenfolge ist auch möglich, das heißt, es gilt   und schließlich  . Das gilt für alle Zykel jeder Gruppe, ein Zykel kann in jeder Richtung durchlaufen werden.

 
Zykel-Graph der Quaternionengruppe  

Zykel mit einer nicht primen Anzahl von Elementen haben immer Unter-Zykel, die im Zykel-Graph nicht gezeigt werden. Man könnte versucht sein, im Zykel-Graph der Gruppe D4 eine Kante zwischen   und   zu ziehen, aber das geschieht nicht, da der von   erzeugte Zykel der Ordnung 2 Teil des größeren von   erzeugten Zykels der Ordnung 4 ist.

Wie bereits oben festgestellt werden zweielementige Zykel in der Regel nur durch eine Kante dargestellt.

Wenn zwei Zykel eine von   verschiedene Ecke gemeinsam haben, kann es zu Mehrdeutigkeiten über den Zykelverlauf kommen. Betrachte dazu die Quaternionengruppe  , deren Zykel-Graph nebenstehend zu sehen ist. Das Quadrat des Elements der mittleren Zeile ergibt −1, wobei 1 für das neutrale Element in   steht. Hier kann man, wie in der Zeichnung geschehen, Zykel durch unterschiedliche Farben kennzeichnen.

Das Inverse eines Elements kann im Zykel-Graph dadurch gefunden werden, dass man im Zykel, dem dieses Element angehört, dasjenige Element ausfindig macht, das bei umgekehrt durchlaufenem Zykel genauso weit vom neutralen Element entfernt ist.

Geschichte

Bearbeiten

Zykel-Graphen wurden in den frühen 1950ern vom Zahlentheoretiker Daniel Shanks als Mittel zum Studium von primen Restklassengruppen untersucht.[2] Shanks hat diese Idee erstmals 1962 in der ersten Ausgabe seines Buches Solved and Unsolved Problems in Number Theory veröffentlicht.[3] In diesem Buch untersucht Shanks, welche Gruppen isomorphe Zykel-Graphen haben und welche Zykel-Graphen planar sind.[4] In der 1978 erschienenen zweiten Auflage schreibt Shanks über seine Untersuchung von Idealklassengruppen und der Entwicklung der Babystep-Giantstep-Methode:

The cycle graphs have proved to be useful when working with finite Abelian groups; and I have used them frequently in finding my way around an intricate structure, in obtaining a wanted multiplicative relation, or in isolating some wanted subgroup.
deutsch: Die Zykel-Graphen haben sich bei der Arbeit mit abelschen Gruppen als nützlich erwiesen; und ich habe sie häufig verwendet, mich in verwickelten Strukturen zurechtzufinden, gesuchte multiplikative Beziehungen zu erhalten oder einige gesuchte Untergruppen zu isolieren.

In Nathan Carters 2009 erschienenem, einführenden Lehrbuch Visual Group Theory haben Zykel-Gruppen als pädagogisches Hilfsmittel Verwendung gefunden.[5]

Grapheigenschaften bestimmter Gruppenfamilien

Bearbeiten

Gewisse Typen von Gruppen haben typische Zykel-Graphen:

Die Zykel-Graphen der zyklischen Gruppen   der Ordnung   sind  -seitige regelmäßige Polygone, jede Ecke steht für ein Gruppenelement.

               
Z1 Z2 = D1 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

Direkte Produkte von  :

       
Z2 Z22 = D2 Z23 = D2×D1 Z24 = D22

Ist   eine Primzahl, so bestehen die Zykel-Graphen der Gruppen   aus   Zykel der Ordnung  , die das neutrale Element gemeinsam haben:

       
Z22 = D2 Z23 = D2×D1 Z24 = D22 Z32

Die Zykel-Graphen der Diedergruppen   der Ordnung   haben einen n-elementigen Zykel und n 2-elementige:

                   
D1 = Z2 D2 = Z22 D3 D4 D5 D6=D3×Z2 D7 D8 D9 D10=D5×Z2

Die dizyklischen Gruppen   der Ordnung   haben folgende Zykel-Graphen:

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

Zykel-Graphen anderer direkter Produkte:

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

Jede Gruppe der Ordnung   ist isomorph zu einer Untergruppe der symmetrischen Gruppe  , ihr Zykel-Graph kann daher im Zykel-Graph der   gefunden werden, siehe folgende Beispiele für die  .

 
A4×Z2
 
S3 = D3
 
S4
 
Eine der drei D4 in S4
identisch zu  

Siehe auch

Bearbeiten

Literatur

Bearbeiten
  • S. Skiena: Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica 1990, §4.2.3 Cycles, Stars, and Wheels, Seiten 144–147
  • Daniel Shanks: Solved and Unsolved Problems in Number Theory, Chelsea Publishing Company (1978), ISBN 0-8284-0297-3
  • S. Pemmaraju, S. Skiena: Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematics Cambridge, England: Cambridge University Press, 2003, §6.2.4 Cycles, Stars, and Wheels Seiten 248–249
Bearbeiten

Einzelnachweise

Bearbeiten
  1. Sarah Perkins: Commuting Involution Graphs for A˜n, Section 2.2, Seite 3, erste Abbildung. School of Economics, Mathematics and Statistics, 2000, abgerufen am 31. Januar 2016.
  2. Shanks 1978, Seite 246
  3. Shanks 1978, Seite xii
  4. Shanks 1978, Seiten 83–98, 206–208
  5. Nathan Carter (2009): Visual Group Theory, Mathematical Association of America, Classroom Resource Materials ISBN 978-0-88385-757-1