Loading AI tools
mathematischer Satz Aus Wikipedia, der freien Enzyklopädie
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:
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:
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.[1]
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.[1]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.