Satz von Frucht

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 ${\displaystyle G=(V,E)}$, wobei ${\displaystyle V}$ die Knotenmenge und ${\displaystyle E}$ die Kantenmenge ist, ist eine bijektive Abbildung ${\displaystyle \varphi :V\rightarrow V}$ mit der Eigenschaft, dass zwei Knoten ${\displaystyle v_{1},v_{2}\in V}$ genau dann durch eine Kante verbunden sind, wenn ${\displaystyle \varphi (v_{1})}$ und ${\displaystyle \varphi (v_{2})}$ durch eine Kante verbunden sind. Die Menge ${\displaystyle \mathrm {Aut} (G)}$ aller Automorphismen von ${\displaystyle G}$ ist offenbar eine Gruppe und heißt die Automorphismengruppe von ${\displaystyle G}$.

Für einen kantenlosen Graphen ${\displaystyle G=(V,\emptyset )}$ oder für einen vollständigen Graphen ist ${\displaystyle \mathrm {Aut} (G)}$ offenbar gleich der symmetrischen Gruppe von ${\displaystyle \mathrm {Sym} (V)}$ von ${\displaystyle V}$. Für alle anderen Graphen ist ${\displaystyle \mathrm {Aut} (G)}$ eine echte Untergruppe von ${\displaystyle \mathrm {Sym} (V)}$. Im Extremfall ist ${\displaystyle \mathrm {Sym} (V)=\{\mathrm {id} _{V}\}}$, 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.

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 ${\displaystyle G}$ mit einer Ordnung größer als 2 und den Elementen ${\displaystyle S_{1},S_{2},\ldots ,S_{n}}$, wobei ${\displaystyle S_{1}}$ das neutrale Element der Gruppe ist, muss zunächst der zugehörige Cayleygraph zum Erzeugendensystem ${\displaystyle G\setminus \{S_{1}\}}$ konstruiert werden.

Nachdem den Elementen ${\displaystyle S_{i}}$ eindeutige Knoten ${\displaystyle P_{i}}$ zugeordnet wurden, werden gerichtete Kanten von ${\displaystyle P_{i}}$ nach ${\displaystyle P_{j}}$ und umgekehrt gezogen, wenn ${\displaystyle i}$ und ${\displaystyle j}$ unterschiedliche Indizes sind. Gilt ${\displaystyle S_{\alpha }=S_{j}S_{i}^{-1}}$, so erhält die gerichtete Kante von ${\displaystyle P_{i}}$ nach ${\displaystyle P_{j}}$ die Farbe ${\displaystyle \alpha \in \{2,3,\ldots ,n\}}$.

Aus dem gerichteten Cayleygraphen muss nun ein ungerichteter Graph konstruiert werden. Hierzu wird eine gerichtete Kante von ${\displaystyle P_{i}}$ nach ${\displaystyle P_{j}}$durch das Einfügen zweier Knoten ${\displaystyle Q_{ij1}}$ und ${\displaystyle R_{ij1}}$ ersetzt. Dabei werden drei ungerichtete Kanten hinzugefügt, welche von ${\displaystyle P_{i}}$ nach ${\displaystyle Q_{ij1}}$, von ${\displaystyle Q_{ij1}}$nach ${\displaystyle R_{ij1}}$ und von ${\displaystyle R_{ij1}}$ nach ${\displaystyle P_{j}}$ verlaufen.

An die neuen Knoten ${\displaystyle Q_{ij1}}$ und ${\displaystyle R_{ij1}}$ werden nun weitere Knoten in Form einer Kette angehängt: insgesamt ${\displaystyle 2\alpha -3}$ Knoten an ${\displaystyle Q_{ij1}}$ und ${\displaystyle 2\alpha -2}$ Knoten an ${\displaystyle R_{ij1}}$.

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 ${\displaystyle Q_{ij1}}$ und ${\displaystyle R_{ij1}}$ verhindert.

Ein auf diese Weise konstruierter Graph besitzt ${\displaystyle 2\cdot n^{3}-n^{2}}$ Knoten, wobei ${\displaystyle n}$ die Ordnung der zugrundeliegenden Gruppe ist. Es existieren in der Regel auch andere, teils sogar kleinere Graphen, deren Automorphismengruppe die Anforderungen erfüllt.^[1]

Aus einem Graphen ${\displaystyle G}$ mit ${\displaystyle m}$ Knoten kann stets auch ein Graph ${\displaystyle G'}$ mit ${\displaystyle 2m}$ 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 ${\displaystyle G}$ angebracht werden.

Da die Nachbarschaft von Knoten innerhalb von Automorphismengruppen erhalten bleibt, verändern die zusätzlichen Knoten die Automorphismengruppe von ${\displaystyle G}$ nicht, denn sie bleiben stets Nachbarn ihres Ursprungspunktes, sie werden unter einer Permutation aus der Automorphismengruppe von ${\displaystyle G}$ 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.^[1]

• 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

1. ↑ ^{a b} R. Frucht: Herstellung von Graphen mit vorgegebener abstrakter Gruppe. In: Compositio Mathematica. Band 6, 1938, S. 239–250.