imported>FerdiBf: Tippfehler

2023-07-20T14:53:01Z

Tippfehler

Neue Seite

Der '''Satz von Frucht''' (nach [[Roberto Frucht]]) ist ein Satz aus dem [[Teilgebiet der Mathematik|mathematischen Teilgebiet]] der [[Graphentheorie]]. Er besagt, dass bis auf Isomorphie jede [[Gruppe (Mathematik)|Gruppe]] als [[Automorphismengruppe]] eines [[Graph (Graphentheorie)|Graphen]] auftritt.

[[Datei:Kleinster asymmetrischer Graph.svg|mini|Ein kleinster asymmetrischer Graph]]
Ein Automorphismus eines ungerichteten Graphen <math>G=(V,E)</math>, wobei <math>V</math> die Knotenmenge und <math>E</math> die Kantenmenge ist, ist eine [[Bijektivität|bijektive]] [[Abbildung (Mathematik)|Abbildung]] <math>\varphi:V\rightarrow V</math> mit der Eigenschaft, dass zwei Knoten <math>v_1,v_2 \in V</math> genau dann durch eine Kante verbunden sind, wenn <math>\varphi(v_1)</math> und <math>\varphi(v_2)</math> durch eine Kante verbunden sind.
Die Menge <math>\mathrm{Aut}(G)</math> aller Automorphismen von <math>G</math> ist offenbar eine Gruppe und heißt die Automorphismengruppe von <math>G</math>.

Für einen kantenlosen Graphen <math>G=(V,\emptyset)</math> oder für einen [[vollständiger Graph|vollständigen Graphen]] ist <math>\mathrm{Aut}(G)</math> offenbar gleich der [[Symmetrische Gruppe|symmetrischen Gruppe]] von <math>\mathrm{Sym}(V)</math> von <math>V</math>. Für alle anderen Graphen ist <math>\mathrm{Aut}(G)</math> eine echte [[Untergruppe]] von <math>\mathrm{Sym}(V)</math>. Im Extremfall ist <math>\mathrm{Sym}(V) = \{\mathrm{id}_V\}</math>, 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 [[Johannes de Groot|J. de Groot]] (1959) und [[Gert Sabidussi|G. Sabidussi]] (1960) bewiesen.

== Konstruktionsidee ==
Der Satz von Frucht wird konstruktiv bewiesen, d. h. es wird ein explizites, aber universelles Vorgehen zur Konstruktion eines [[Graph (Graphentheorie)|Graphen]] angegeben. Im Nachhinein wird dann die Eignung dieser Graphen bewiesen. Zunächst gilt:

* Ein [[Graph (Graphentheorie)|Graph]], welcher lediglich einen [[Knoten (Graphentheorie)|Knoten]] enthält, ist [[Isomorphie von Graphen|isomorph]] zu endlichen Gruppen der [[Ordnung einer Gruppe|Ordnung]] 1, denn die [[Automorphismengruppe]] besteht nur aus der [[Identische Abbildung|identischen Abbildung]].

* [[Gruppe (Mathematik)|Gruppen]] der [[Gruppe (Mathematik)#Gruppenordnung|Ordnung]] zwei sind [[Isomorphismus|isomorph]] zum Graphen mit zwei miteinander verbundenen [[Knoten (Graphentheorie)|Knoten]], denn dessen [[Automorphismengruppe]] besteht aus der [[Identische Abbildung|identischen Abbildung]] sowie der [[Permutation]] der beiden Knoten.

Für endliche Gruppen <math>G</math> mit einer [[Gruppe (Mathematik)#Gruppenordnung|Ordnung]] größer als 2 und den Elementen <math>S_1, S_2, \ldots, S_n</math>, wobei <math>S_1</math> das [[Neutrales Element|neutrale Element]] der Gruppe ist, muss zunächst der zugehörige [[Cayleygraph]] zum [[Erzeugendensystem]] <math>G \setminus \{S_1\}</math> konstruiert werden.

Nachdem den Elementen <math>S_i</math> eindeutige [[Knoten (Graphentheorie)|Knoten]] <math>P_i</math> zugeordnet wurden, werden gerichtete [[Kante (Graphentheorie)|Kanten]] von <math>P_i</math> nach <math>P_j</math> und umgekehrt gezogen, wenn <math>i</math> und <math>j</math> unterschiedliche Indizes sind. Gilt <math>S_{\alpha} = S_{j}S_{i}^{-1}</math>, so erhält die gerichtete Kante von <math>P_i</math> nach <math>P_j</math> die Farbe <math>\alpha \in \{2, 3, \ldots, n\}</math>.

Aus dem gerichteten [[Cayleygraph]]en muss nun ein [[ungerichteter Graph]] konstruiert werden. Hierzu wird eine gerichtete [[Kante (Graphentheorie)|Kante]] von <math>P_i</math> nach <math>P_j</math>durch das Einfügen zweier Knoten <math>Q_{ij1}</math> und <math>R_{ij1}</math> ersetzt. Dabei werden drei ungerichtete Kanten hinzugefügt, welche von <math>P_i</math> nach <math>Q_{ij1}</math>, von <math>Q_{ij1}</math>nach <math>R_{ij1}</math> und von <math>R_{ij1}</math> nach <math>P_j</math> verlaufen.

An die neuen [[Knoten (Graphentheorie)|Knoten]] <math>Q_{ij1}</math> und <math>R_{ij1}</math> werden nun weitere Knoten in Form einer Kette angehängt: insgesamt <math>2\alpha-3</math> Knoten an <math>Q_{ij1}</math> und <math>2\alpha-2</math> Knoten an <math>R_{ij1}</math>.

Wiederholt man diese Schritte an allen gerichteten Kanten des [[Cayleygraph]]en, so erhält man einen [[Ungerichteter Graph|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 <math>Q_{ij1}</math> und <math>R_{ij1}</math> verhindert.

Ein auf diese Weise konstruierter [[Graph (Graphentheorie)|Graph]] besitzt <math>2 \cdot n^3 - n^2</math> [[Knoten (Graphentheorie)|Knoten]], wobei <math>n</math> die [[Gruppe (Mathematik)#Gruppenordnung|Ordnung]] der zugrundeliegenden [[Gruppe (Mathematik)|Gruppe]] ist.
Es existieren in der Regel auch andere, teils sogar kleinere Graphen, deren [[Automorphismengruppe]] die Anforderungen erfüllt.<ref name=":0">{{Literatur |Autor=R. Frucht |Titel=Herstellung von Graphen mit vorgegebener abstrakter Gruppe |Sammelwerk=Compositio Mathematica |Band=6 |Datum=1938 |Seiten=239-250}}</ref>

== Existenz unendlich vieler Graphen ==
Aus einem Graphen <math>G</math> mit <math>m</math> Knoten kann stets auch ein Graph <math>G'</math> mit <math>2m</math> 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 <math>G</math> angebracht werden.

Da die Nachbarschaft von Knoten innerhalb von Automorphismengruppen erhalten bleibt, verändern die zusätzlichen Knoten die Automorphismengruppe von <math>G</math> nicht, denn sie bleiben stets Nachbarn ihres Ursprungspunktes, sie werden unter einer Permutation aus der Automorphismengruppe von <math>G</math> 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.<ref name=":0" />

== Literatur ==
* 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 ==
<references />

[[Kategorie:Satz (Graphentheorie)|Frucht, Satz von]]

Satz von Frucht - Versionsgeschichte

imported>FerdiBf: Tippfehler