Zyklische Gruppen der Ordnung n bilden genau dann Automorphismengruppen auf einer 1-Faktorisierung des vollständigen Graphen K_n, wenn n ̸= 2^t für t ≥ 3. Im Falle n = 2^t mit t ≥ 3 wird bewiesen, dass es keine zyklische 1-Faktorisierung von K_n gibt, für die anderen Fälle wird die Aussage durch Konstruktion der 1-Faktoren bewiesen. Eine analoge Aussage für abelsche Gruppen ist möglich, wird aber nicht vollständig bewiesen.
Inhaltsverzeichnis
1 Einleitung
2 Einführung in die Graphentheorie
2.1 Grundlagen und Definitionen
2.2 Cayley-Graphen
2.3 Faktorisierungen
3 Zyklische 1-Faktorisierungen vollständiger Graphen
3.1 Struktur zyklischer 1-Faktorisierungen
3.2 Konstruktion einer zyklischen 1-Faktorisierung
3.3 Fazit
4 Abelsche Automorphismengruppen auf 1-Faktorisierungen vollständiger Graphen
4.1 Gruppen der Ordnung 2m (für m ungerade Primzahlpotenz)
4.2 Zusammenfassung
4.3 Beispiel
4.4 Verallgemeinerung
5 Zusammenfassung und Ausblick
Zielsetzung & Themen
Das primäre Ziel dieser Bachelorarbeit ist die detaillierte Untersuchung und der rechnerische Nachweis der Existenz zyklischer Automorphismengruppen auf 1-Faktorisierungen vollständiger Graphen. Dabei steht die Beantwortung der Frage im Fokus, für welche Gruppenordnungen solche Strukturen mathematisch konstruierbar sind und unter welchen Bedingungen die Existenz zyklischer 1-Faktorisierungen ausgeschlossen werden kann.
- Grundlagen der Graphentheorie und Cayley-Graphen
- Strukturanalyse von 1-Faktorisierungen vollständiger Graphen
- Konstruktiver Beweis zyklischer 1-Faktorisierungen
- Untersuchung abelscher Automorphismengruppen
- Fallstudien zu speziellen Gruppenordnungen
Auszug aus dem Buch
3.1 Struktur zyklischer 1-Faktorisierungen
Wir betrachten wie schon im vorigen Kapitel eine (endliche) zyklische Gruppe (G, +) der Ordnung n und g wie zuvor.
Lemma 3.4. Sei {Fi}i∈{1,...,n−1} eine zyklische 1-Faktorisierung von Kn. Gemäß der Definition zyklischer Faktorisierungen unterteilt g ∈ G die 1-Faktoren in Bahnen. Die Zahl der 1-Faktoren in derselben Bahn teilt n.
Beweis. Da die 1-Faktorisierung zyklisch ist, gilt gn(Fi) = Fi (i ∈ {1, ..., n − 1}). Sei m die Anzahl der 1-Faktoren in einer Bahn, wobei offensichtlich m Offensichtlich besteht jede Bahn von 1-Faktoren aus einer Vereinigung von Bahnen von Kanten. Lemma 3.5. Enthält die Bahn eines 1-Faktors genau ein Element, so handelt es sich um En/2. Enthält die Bahn eines 1-Faktors genau zwei Elemente, so handelt es sich um die 1-Faktoren F1 und F2, die eine Zerlegung einer ungeraden Bahn von Kanten E2i+1, wie am Anfang dieses Kapitels angegeben, darstellen. Beweis. Die Bahn eines 1-Faktors F enthalte genau ein Element, d.h. g(F) = F. Wie wir in Kapitel 3 gesehen haben, bleibt genau ein 1-Faktor unter der Wirkung von g unverändert, nämlich En/2. Enthält die Bahn eines 1-Faktors F genau zwei Elemente, sagen wir F1 und F2, d.h. g(F1) = F2 und g2(F1) = F1, so haben wir ebenfalls eher in diesem Kapitel gesehen, dass dies gerade für die Zerlegung der ungeraden Bahn E2i+1 gilt.
Zusammenfassung der Kapitel
1 Einleitung: Diese Einleitung führt in die graphentheoretischen Grundlagen ein und definiert das Ziel, die Existenz zyklischer Automorphismengruppen auf 1-Faktorisierungen vollständiger Graphen zu untersuchen.
2 Einführung in die Graphentheorie: In diesem Kapitel werden die mathematischen Grundlagen, wie Cayley-Graphen und die Definition von 1-Faktorisierungen als Zerlegungen der Kantenmenge, erarbeitet.
3 Zyklische 1-Faktorisierungen vollständiger Graphen: Das Kernkapitel analysiert die Struktur dieser Graphen und liefert durch eine detaillierte Konstruktion den Beweis für die Existenzbedingungen zyklischer Faktorisierungen.
4 Abelsche Automorphismengruppen auf 1-Faktorisierungen vollständiger Graphen: Hier wird die Untersuchung auf allgemeinere abelsche Gruppen ausgeweitet, wobei ein spezieller Fall detailliert konstruiert und beispielhaft erläutert wird.
5 Zusammenfassung und Ausblick: Dieses Kapitel fasst die gewonnenen Erkenntnisse zur Konstruktion von 1-Faktorisierungen zusammen und gibt einen Ausblick auf die Komplexität bei allgemeineren abelschen Gruppen.
Schlüsselwörter
Graphentheorie, 1-Faktorisierung, vollständiger Graph, Automorphismengruppe, zyklische Gruppe, Cayley-Graph, Kantenzerlegung, diskrete Mathematik, Symmetrie, Permutationsgruppe, Graphenisomorphie, abelsche Gruppe, Knotenzahl, Kantenmenge, Beweiskonstruktion.
Häufig gestellte Fragen
Worum geht es in dieser Bachelorarbeit grundsätzlich?
Die Arbeit befasst sich mit der mathematischen Untersuchung von 1-Faktorisierungen vollständiger Graphen unter dem speziellen Aspekt der Existenz von Automorphismengruppen.
Was sind die zentralen Themenfelder?
Die zentralen Felder umfassen die Graphentheorie, insbesondere Faktorisierungen und deren Symmetrieeigenschaften, sowie die Gruppentheorie im Kontext von Automorphismen.
Was ist das primäre Ziel oder die Forschungsfrage?
Das Hauptziel ist zu bestimmen, für welche n der vollständige Graph Kn eine zyklische 1-Faktorisierung besitzt und wie diese strukturell konstruiert werden können.
Welche wissenschaftliche Methode wird verwendet?
Die Arbeit verwendet primär konstruktive mathematische Beweismethoden und führt eine fundierte strukturelle Analyse der Graphenbahnen unter Gruppenwirkung durch.
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in die theoretischen Grundlagen, die detaillierte Konstruktion zyklischer Faktorisierungen sowie die Erweiterung auf spezielle abelsche Gruppen.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit wird durch Begriffe wie 1-Faktorisierung, vollständiger Graph, Automorphismengruppe, zyklische Gruppe und Cayley-Graph charakterisiert.
Warum existiert für n = 2^t (mit t >= 3) keine zyklische 1-Faktorisierung?
Dies wird im dritten Kapitel mittels einer Analyse der Bahnen von 1-Faktoren und Kanten bewiesen, die zeigt, dass für diese spezifische Knotenzahl die notwendigen Symmetriebedingungen nicht erfüllt werden können.
Wie wird die 1-Faktorisierung für allgemeine Knotenzahlen konstruiert?
Die Konstruktion erfolgt, indem man den Graphen in Kantenbahnen unter der Wirkung der zyklischen Gruppe zerlegt und diese Bahnen zu 1-Faktoren zusammenfügt, wobei für verschiedene n unterschiedliche Zerlegungsschemata angewendet werden.
Welche Bedeutung haben Cayley-Graphen für diese Arbeit?
Cayley-Graphen dienen als anschauliches Hilfsmittel, um die Wirkung der zyklischen Gruppe auf die Kanten des vollständigen Graphen zu visualisieren und die Zerlegung in 1-Faktoren zu erleichtern.
- Quote paper
- Christin Zabelt (Author), 2014, Symmetriegruppen der 1-Faktorisierungen vollständiger Graphen, Munich, GRIN Verlag, https://www.grin.com/document/283093
