Symmetriegruppen der 1-Faktorisierungen vollständiger Graphen


Bachelorarbeit, 2014

35 Seiten, Note: 1,3


Leseprobe

Technische Universit¨at Dresden
· Fachrichtung Mathematik
Symmetriegruppen der
1-Faktorisierungen vollst¨
andiger
Graphen
Bachelorarbeit
zur Erlangung des ersten Hochschulgrades
Bachelor of Science (B.Sc.)
vorgelegt von
Christin
ZABELT
Tag der Einreichung: 20. 06. 2014

KURZFASSUNG
Kurzfassung
Zyklische Gruppen der Ordnung n bilden genau dann Automorphismengruppen auf einer
1-Faktorisierung des vollst¨
andigen Graphen K
n
, wenn n = 2
t
ur t
3. Im Falle n = 2
t
mit t
3 wird bewiesen, dass es keine zyklische 1-Faktorisierung von K
n
gibt, f¨
ur die
anderen F¨
alle wird die Aussage durch Konstruktion der 1-Faktoren bewiesen. Eine analoge
Aussage f¨
ur abelsche Gruppen ist m¨
oglich, wird aber nicht vollst¨
andig bewiesen.
Seite I

INHALTSVERZEICHNIS
Inhaltsverzeichnis
1 Einleitung
1
2 Einf¨
uhrung in die Graphentheorie
2
2.1
Grundlagen und Definitionen
. . . . . . . . . . . . . . . . . . . . . . . . .
2
2.2
Cayley-Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.3
Faktorisierungen
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
3 Zyklische 1-Faktorisierungen vollst¨
andiger Graphen
11
3.1
Struktur zyklischer 1-Faktorisierungen
. . . . . . . . . . . . . . . . . . . .
16
3.2
Konstruktion einer zyklischen 1-Faktorisierung . . . . . . . . . . . . . . . .
18
3.3
Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
4 Abelsche Automorphismengruppen auf 1-Faktorisierungen vollst¨
andiger
Graphen
26
4.1
Gruppen der Ordnung 2m (f¨
ur m ungerade Primzahlpotenz) . . . . . . . .
26
4.2
Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
4.3
Beispiel
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
4.4
Verallgemeinerung
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
5 Zusammenfassung und Ausblick
31
6 Quellenverzeichnis
32
Seite II

Kapitel 1
Einleitung
1 Einleitung
Aufgabe der Graphentheorie als Teilgebiet der diskreten Mathematik ist die Modellierung
netzartiger Strukturen in Natur und Technik (vgl. z.B. [Tit11]). Sie besch¨
aftigt sich mit
der Struktur und Eigenschaften von Graphen und insbesondere auch mit algorithmischen
Problemen, so zum Beispiel mit dem Finden k¨
urzester Wege und anderen Optimierungs-
aufgaben.
ur einige dieser Aufgaben spielen Zerlegungen von Graphen eine Rolle, so z.B. bei
Matching-Problemen oder beim Finden von Hamilton-Kreisen (vgl. Diestel [R.D06]).
Zahlreiche mathematische Schriften besch¨
aftigen sich seit einigen Jahrzehnten mit be-
stimmten Zerlegungen, sogenannten 1-Faktorisierungen. Dabei liegt das Augenmerk oft
auf sehr spezifischen Fragestellungen bez¨
uglich der Existenz von Automorphismengruppen
auf 1-Faktorisierungen.
In dieser Arbeit wollen wir uns vor allem der Fragestellung widmen, welche zyklischen
Gruppen Automorphismengruppen auf 1-Faktorisierungen vollst¨
andiger Graphen sind.
Wir orientieren uns dabei an einer Arbeit von Hartman und Rosa [HR85], welche als
Grundlage f¨
ur zahlreiche weitere Arbeiten dient. Der dort angef¨
uhrte Beweis soll hier
detailliert nachvollzogen werden.
Dazu werden wir zun¨
achst einige wichtige Grundlagen der Graphentheorie kennenlernen
und wesentliche Begriffe einf¨
uhren. Im Speziellen soll es dabei auch um eine bestimmte
Art von Graphen, die sogenannten Cayley-Graphen, gehen, die f¨
ur die Konstruktion der
1-Faktorisierungen ein anschauliches Hilfsmittel sein werden.
Wir werden Faktorisierungen von Graphen kennenlernen, um uns anschließend in Kapi-
tel 3 speziell den zyklische Faktorisierungen vollst¨
andiger Graphen zuzuwenden. Dieses
Kapitel wird im Kern der Arbeit von Hartman und Rosa [HR85] folgen und den dort
gef¨
uhrten Beweis in allen Details wiedergeben.
Wir wollen uns anschließend ¨
uberlegen, inwiefern die Erkenntnisse auf abelsche Gruppen
¨
ubertragbar sind. Dazu betrachten wir im 4. Kapitel allerdings lediglich einen Spezi-
alfall und verweisen f¨
ur allgemeine Aussagen auf die Literatur, da die entsprechenden
¨
Uberlegungen den Rahmen dieser Arbeit ¨
ubersteigen.
Seite 1

Kapitel 2
Einf¨
uhrung in die Graphentheorie
2 Einf¨
uhrung in die Graphentheorie
In diesem Kapitel soll ein ¨
Uberblick ¨
uber die Grundlagen der Graphentheorie gegeben
werden. Es werden die wichtigsten Begriffe definiert, die im weiteren Verlauf eine Rolle
spielen werden. Im Speziellen soll es dabei um Cayley-Graphen gehen. Wir orientieren
uns bei der Definition grundlegender Begriffe an der Literatur zum Thema, vgl. bspw.
[R.D06], [GR01] oder [Bol98].
2.1 Grundlagen und Definitionen
Definition 2.1. Ein Graph ist ein Paar G = (V, E) bestehend aus einer endlichen,
nichtleeren Menge V und einer Menge E
V
2
=
{{u, v} | u, v V, u = v}. Die
Elemente der Menge V werden als Knoten (oder Ecken) bezeichnet, Elemente von E
nennen wir Kanten.
Ein Knoten v
V inzidiert mit einer Kante e E, wenn v e gilt, v und e heißen dann
inzident. Zwei Knoten v
1
, v
2
V heißen adjazent, wenn es eine Kante e E gibt mit
v
1
e und v
2
e.
ur die Kante
{v
1
, v
2
} schreiben wir, sofern die Eindeutigkeit der Notation es zul¨asst,
im Folgenden kurz auch v
1
v
2
bzw. v
2
v
1
. Dementsprechend sind zwei Knoten v
1
, v
2
V
adjazent, wenn v
1
v
2
E gilt.
Zur besseren Veranschaulichung werden wir in den folgenden Beispielen Graphen jeweils
in Form sogenannter Graphendiagramme darstellen.
Beispiel 2.2. Diagramm eines Graphen (V, E) mit V =
{1, 2, 3, 4, 5, 6, 7} und E =
{12, 14, 24, 27, 36}
1
2
3
4
5
6
7
Abbildung 1: Beispiel Graph
Seite 2

Kapitel 2
Einf¨
uhrung in die Graphentheorie
Definition 2.3. Sei G = (V, E) ein Graph. Der Grad d
G
(v) eines Knotens v
V ist die
Anzahl der mit diesem Knoten inzidenten Kanten:
d
G
(v) =
|{w V | vw E}|.
Definition 2.4. Als regul¨
ar bezeichnen wir einen Graphen G = (V, E), wenn jeder Kno-
ten v
V den gleichen Grad hat. Insbesondere wird G als k-regul¨ar bezeichnet, wenn
d
G
(v) = k f¨
ur alle v
V f¨ur ein k N.
Beispiel 2.5. Diagramm eines 3-regul¨
aren Graphen G = (V, E) mit
|V | = 6.
1
2
3
4
5
6
Abbildung 2: 3-regul¨
arer Graph
Definition 2.6. Ein Graph G = (V, E) heißt vollst¨
andig, wenn je zwei Knoten aus V
adjazent sind.
ur
|V | = n gilt dann |E| =
n
2
und wir schreiben G = (V, E) = K
n
. Sofern nicht anders
angegeben, gilt im Folgenden V = Z
n
=
{0, 1, ..., n - 1}.
Beispiel 2.7. Diagramm des vollst¨
andigen Graphen K
5
. Dieser Graph hat
5
2
= 10 Kan-
ten.
0
1
2
3
4
Abbildung 3: Vollst¨
andiger Graph K
5
Seite 3

Kapitel 2
Einf¨
uhrung in die Graphentheorie
Definition 2.8. Ein Graph G = (V , E ) heißt Teilgraph von G = (V, E), wenn V
V
und E
E gilt.
Wir schreiben dann auch G
G.
Beispiel 2.9. Diagramm eines Graphen G = (V, E) mit V =
{1, 2, 3, 4, 5} und E =
{12, 15, 23, 24, 34} sowie eines Teilgraphen G = (V , E ) G mit V = {1, 2, 3, 4} V
und E =
{12, 23, 24} E
1
2
3
4
5
1
2
3
4
Abbildung 4: Graph G und Teilgraph G
G
Definition 2.10. Zwei Graphen G
1
= (V
1
, E
1
) und G
2
= (V
2
, E
2
) heißen isomorph, wenn
es eine bijektive Abbildung : V
1
V
2
gibt, so dass f¨
ur alle v, w
V
1
gilt:
{v, w} E
1
{(v), (w)} E
2
.
heißt Isomorphismus. Im Spezialfall G
1
= G
2
sprechen wir von einem Automorphismus.
Bemerkung: Da wir nur endliche Knotenmengen V
1
, V
2
betrachten, gen¨
ugt die Implikation
{v, w} E
1
{(v), (w)} E
2
ur alle v, w
V
1
als Bedingungen f¨
ur die Isomorphie der Graphen G
1
und G
2
.
Sind zwei Graphen G
1
, G
2
isomorph zueinander, so schreiben wir G
1
G
2
.
Seite 4

Kapitel 2
Einf¨
uhrung in die Graphentheorie
Beispiel 2.11. Diagramme zweier isomorpher Graphen G
1
und G
2
.
1
2
3
4
5
6
7
8
9
10
A
B
C
D
E
F
G
H
I
J
Abbildung 5: Isomorphe Graphen
Bisher haben wir nur Graphen mit ungerichteten Kanten u, v betrachtet. Obwohl dies
ur die Betrachtung von 1-Faktorisierungen v¨
ollig ausreichend ist, werden wir zu deren
Konstruktion auf das Prinzip der Cayley-Graphen (vgl. Kapitel 2.2) zur¨
uckgreifen, so dass
wir uns auch mit Graphen besch¨
aftigen werden, deren Kanten eine Richtung haben.
Definition 2.12. Ein gerichteter Graph G = (V, E) ist ein Paar bestehend aus einer
endlichen, nichtleeren Menge V und einer Menge E
V × V , dessen Kantenmenge aus
geordneten Paaren von Elementen aus V besteht, wir schreiben dann (u, v)
E .
Die Kanten (u, v) gerichteter Graphen k¨
onnen als Pfeile mit Anfang u und Ende v inter-
pretiert werden.
Beispiel 2.13. Diagramm eines gerichteten Graphen mit Knotenmenge V =
{1, 2, 3, 4, 5}
und E =
{(1, 2), (1, 4), (2, 3), (2, 4), (4, 1), (5, 4)}.
1
2
3
4
5
Abbildung 6: Gerichteter Graph
Seite 5

Kapitel 2
Einf¨
uhrung in die Graphentheorie
2.2 Cayley-Graphen
Wie bereits im vorigen Abschnitt erw¨
ahnt, werden wir den Begriff des Cayley-Graphen
ur die Konstruktion von 1-Faktorisierungen vollst¨
andiger Graphen verwenden. Dazu
zun¨
achst einige kurze Erl¨
auterungen. Die folgende Definition orientiert sich an [Bog02].
Definition 2.14. Sei G eine Gruppe und ein Erzeugendensystem. Wir bezeichnen mit
Cay(G, ) = (V, E) den Cayley-Graphen von G unter , wobei V = G und
E =
{(g, g) | g G, }.
Wir interpretieren den Cayley-Graphen als gef¨
arberten Graphen, d.h. wir ordnen jedem
eine Farbe col() zu. F¨ur alle g G und wird dann die gerichtete Kante
(g, g) mit der Farbe col() versehen.
Beispiel 2.15. Der Cayley-Graph Cay(Z
5
,
{1}) hat Knotenmenge Z
5
und Kantenmenge
{(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)}.
0
1
2
3
4
Abbildung 7: CayleyGraph Cay(Z
5
,
{1})
Beispiel 2.16. Der Cayley-Graph Cay(Z
5
,
{1, 3}) hat Knotenmenge Z
5
. Die Kanten wer-
den in zwei verschiedenen Farben dargestellt, in der Grafik sind Kanten (g, g) (g
Z
5
)
ur = 1 rot und f¨
ur = 3 blau dargestellt.
0
1
2
3
4
Abbildung 8: Cayley-Graph Cay(Z
5
,
{1, 3})
Seite 6
Ende der Leseprobe aus 35 Seiten

Details

Titel
Symmetriegruppen der 1-Faktorisierungen vollständiger Graphen
Hochschule
Technische Universität Dresden  (Algebra)
Note
1,3
Autor
Jahr
2014
Seiten
35
Katalognummer
V283093
ISBN (eBook)
9783656847496
ISBN (Buch)
9783656847502
Dateigröße
540 KB
Sprache
Deutsch
Schlagworte
symmetriegruppen, graphen
Arbeit zitieren
Christin Zabelt (Autor), 2014, Symmetriegruppen der 1-Faktorisierungen vollständiger Graphen, München, GRIN Verlag, https://www.grin.com/document/283093

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Symmetriegruppen der 1-Faktorisierungen vollständiger Graphen



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden