Der Satz von Frucht (nach Roberto Frucht) ist ein Satz aus dem mathematischen Teilgebiet der Graphentheorie. Er besagt, dass bis auf Isomorphie jede Gruppe als Automorphismengruppe eines Graphen auftritt.
Ein Automorphismus eines ungerichteten Graphen , wobei die Knotenmenge und die Kantenmenge ist, ist eine bijektive Abbildung mit der Eigenschaft, dass zwei Knoten genau dann durch eine Kante verbunden sind, wenn und durch eine Kante verbunden sind. Die Menge aller Automorphismen von ist offenbar eine Gruppe und heißt die Automorphismengruppe von .
Für einen kantenlosen Graphen oder für einen vollständigen Graphen ist offenbar gleich der symmetrischen Gruppe von von . Für alle anderen Graphen ist eine echte Untergruppe von . Im Extremfall ist , solche Graphen nennt man asymmetrisch. Die kleinste Knotenzahl eines asymmetrischen Graphen ist 6.
Da nach dem Satz von Cayley jede Gruppe isomorph zu einer Untergruppe einer symmetrischen Gruppe ist, stellt sich die Frage, ob jede Gruppe als Automorphismengruppe eines Graphen auftritt. Diese Frage wird durch den Satz von Frucht positiv beantwortet:
- Satz von Frucht: Zu jeder Gruppe gibt es einen Graphen, dessen Automorphismengruppe isomorph zu dieser Gruppe ist.
Dieser Satz wurde 1938 von Roberto Frucht für endliche Gruppen formuliert und bewiesen. Der Fall unendlicher Gruppen wurde unabhängig voneinander von J. de Groot (1959) und G. Sabidussi (1960) bewiesen.
Konstruktionsidee Bearbeiten
Der Satz von Frucht wird konstruktiv bewiesen, d. h. es wird ein explizites, aber universelles Vorgehen zur Konstruktion eines Graphen angegeben. Im Nachhinein wird dann die Eignung dieser Graphen bewiesen. Zunächst gilt:
- Ein Graph, welcher lediglich einen Knoten enthält, ist isomorph zu endlichen Gruppen der Ordnung 1, denn die Automorphismengruppe besteht nur aus der identischen Abbildung.
- Gruppen der Ordnung zwei sind isomorph zum Graphen mit zwei miteinander verbundenen Knoten, denn dessen Automorphismengruppe besteht aus der identischen Abbildung sowie der Permutation der beiden Knoten.
Für endliche Gruppen mit einer Ordnung größer als 2 und den Elementen , wobei das neutrale Element der Gruppe ist, muss zunächst der zugehörige Cayleygraph zum Erzeugendensystem konstruiert werden.
Nachdem den Elementen eindeutige Knoten zugeordnet wurden, werden gerichtete Kanten von nach und umgekehrt gezogen, wenn und unterschiedliche Indizes sind. Gilt , so erhält die gerichtete Kante von nach die Farbe .
Aus dem gerichteten Cayleygraphen muss nun ein ungerichteter Graph konstruiert werden. Hierzu wird eine gerichtete Kante von nach durch das Einfügen zweier Knoten und ersetzt. Dabei werden drei ungerichtete Kanten hinzugefügt, welche von nach , von nach und von nach verlaufen.
An die neuen Knoten und werden nun weitere Knoten in Form einer Kette angehängt: insgesamt Knoten an und Knoten an .
Wiederholt man diese Schritte an allen gerichteten Kanten des Cayleygraphen, so erhält man einen ungerichteten Graphen. Mögliche Symmetrien in diesem Graphen, welche weitere Elemente in der Automorphismengruppe zufolge hätten, werden durch die unterschiedliche Länge der Ketten an den Knoten und verhindert.
Ein auf diese Weise konstruierter Graph besitzt Knoten, wobei die Ordnung der zugrundeliegenden Gruppe ist. Es existieren in der Regel auch andere, teils sogar kleinere Graphen, deren Automorphismengruppe die Anforderungen erfüllt.
Existenz unendlich vieler Graphen Bearbeiten
Aus einem Graphen mit Knoten kann stets auch ein Graph mit Knoten konstruiert werden, sodass die beiden Graphen isomorphe Automorphismengruppen besitzen. Hierfür muss lediglich eine Kette der Länge 1 an jeden bereits vorhandenen Punkt des Graphen angebracht werden.
Da die Nachbarschaft von Knoten innerhalb von Automorphismengruppen erhalten bleibt, verändern die zusätzlichen Knoten die Automorphismengruppe von nicht, denn sie bleiben stets Nachbarn ihres Ursprungspunktes, sie werden unter einer Permutation aus der Automorphismengruppe von also gewissermaßen einfach mitgetragen. Diese Konstruktion kann beliebig oft durchgeführt werden.
Da nach dem Satz von Frucht zu jeder endlichen Gruppe ein Graph mit einer zur Gruppe isomorphen Automorphismengruppe existiert, kann nun geschlussfolgert werden, dass sogar unendliche viele solcher Graphen zu einer beliebigen endlichen Gruppe existieren.
Literatur Bearbeiten
- J. de Groot: Groups represented by homeomorphism groups, Mathematische Annalen (1959), Band 138, Seiten 80–102
- R. Frucht: Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Compositio Mathematica (1938), Band 6, Seiten 239–250
- G. Sabidussi: Graphs with given infinite group Monatshefte für Mathematik (1960), Band 64, Seiten 64–67
- K. Wagner: Graphentheorie, Bibliographisches Institut AG, Mannheim (1970), ISBN 3-411-00248-4
Einzelnachweise Bearbeiten
- ↑ R. Frucht: Herstellung von Graphen mit vorgegebener abstrakter Gruppe. In: Compositio Mathematica. Band 6, 1938, S. 239–250.