Extracto
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
f¨
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.
F¨
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.
F¨
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.
F¨
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
f¨
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
f¨
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
f¨
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
)
f¨
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
Final del extracto de 35 páginas
- Citar trabajo
- Christin Zabelt (Autor), 2014, Symmetriegruppen der 1-Faktorisierungen vollständiger Graphen, Múnich, GRIN Verlag, https://www.grin.com/document/283093
Textos similares
Así es como funciona
✕
Extracto de
35
Páginas
Comentarios