imported>Horst Gräbner: siehe den verlinkten Artikel

2021-07-05T08:19:03Z

siehe den verlinkten Artikel

Neue Seite

In der [[Graphentheorie]] bezeichnet ein '''Prüfer-Code''' eine [[Folge (Mathematik)|Folge]], die einen beschrifteten [[Baum (Graphentheorie)|Baum]] [[Bijektive Funktion|eineindeutig]] beschreibt. Der Code für einen Baum mit <math>n</math> [[Knoten (Graphentheorie)|Knoten]] hat die Länge <math>n-2</math> und kann mit einem einfachen [[Iteration|iterativen]] [[Algorithmus]] erstellt werden. Prüfer-Codes wurden 1918 von [[Heinz Prüfer (Mathematiker)|Heinz Prüfer]] eingeführt, um die [[Cayley-Formel]] zu beweisen.

== Algorithmus ==
=== Prüfer-Code aus einem Baum ===
Erstellt werden kann ein Prüfer-Code aus einem Baum durch das iterative Entfernen von Knoten, bis nur noch zwei Knoten übrig sind. Gegeben sei ein Baum <math>T</math> mit Knoten <math>\{ 1, 2, \ldots , n \}</math>. Im Schritt <math>i</math> wird das [[Blatt (Graphentheorie)|Blatt]] mit der kleinsten Beschriftung aus dem Baum entfernt und das <math>i</math>-te Element des Prüfer-Codes auf die Beschriftung des einzigen Nachbarn des entfernten Blattes gesetzt.

Der Code eines Baums ist offensichtlich eindeutig und hat die Länge <math>n-2</math>.

=== Baum aus einem Prüfer-Code rekonstruieren ===
Der ursprüngliche Baum aus einem Prüfer-Code kann ebenfalls leicht gewonnen werden.

Dazu geht man den Prüfer-Code <math>p</math> von links nach rechts durch und schreibt (in eine Liste <math>b</math>) die jeweils kleinste Zahl darunter, die weder in <math>p</math>, noch in <math>b</math> enthalten ist. Diese wird mit der aktuellen Zahl in <math>p</math> verbunden. Die aktuelle Zahl in <math>p</math> wird anschließend gestrichen. Diese Schritte werden wiederholt, bis keine Elemente mehr in <math>p</math> vorhanden sind. Das <math>i</math>-te Element in <math>p</math> ist dann jeweils mit dem <math>i</math>-ten Element in <math>b</math> durch eine Kante verbunden.

Man erhält so allerdings einen Baum mit nur <math>n-1</math> Knoten. Um den <math>n</math>-ten Knoten zu erhalten, verbindet man nun die zwei Zahlen, die nicht in <math>b</math> enthalten sind, durch eine weitere Kante.

== Beispiel ==
=== Prüfer-Code aus einem Baum ===
[[Datei:Arbre a sept sommets.svg|mini|Ein beschrifteter Baum mit Prüfer-Code 5, 5, 2, 2, 2]]

Der oben vorgestellte Algorithmus wird auf das Bild rechts angewandt. Zu Beginn ist der Knoten 1 das Blatt mit der kleinsten Beschriftung, daher wird dieser Knoten als erstes entfernt und 5 wird als erstes Element in den Prüfer-Code eingefügt. Anschließend werden die Blätter 3 und 4 aus dem Baum entfernt und die Folge um 5 und 2 erweitert. Da der Knoten 5 jetzt das kleinste Blatt ist, wird er aus dem Baum entfernt und 2 an die Folge angehängt. Als letzter Knoten wird Knoten 6 aus dem Baum entfernt und 2 an die Folge angehängt. Der Algorithmus terminiert, da nur noch zwei Knoten (2 und 7) übrig sind.

=== Baum aus einem Prüfer-Code ===
Wir verwenden den obigen Prüfer-Code <math>p = (5, 5, 2, 2, 2)</math>.
# Das kleinste Element, das nicht in <math>p</math> oder in <math>b = ()</math> enthalten ist, ist 1. Die erste 5 wird also im Baum mit der 1 verbunden, die 1 zu <math>b</math> hinzugefügt und die 5 gestrichen.
# Das kleinste Element, das nicht in <math>p = (5, 2, 2, 2)</math> oder in <math>b = (1)</math> enthalten ist, ist die 3. Es folgt: <math>p = (2, 2, 2)</math>, <math>b = (1, 3)</math> und die 5 und die 3 werden im Baum durch eine Kante verbunden.
# Als nächstes ist 4 das kleinste Element, das nicht in <math>p</math> oder <math>b</math> liegt. Es folgt: <math>p = (2, 2)</math>, <math>b = (1, 3, 4)</math> und die 2 und die 4 werden im Baum durch eine Kante verbunden.
# Als nächstes ist 5 das kleinste Element, das nicht in <math>p</math> oder <math>b</math> liegt. Es folgt: <math>p = (2)</math>, <math>b = (1, 3, 4, 5)</math> und die 2 und die 5 werden im Baum durch eine Kante verbunden.
# Als nächstes ist 6 das kleinste Element, das nicht in <math>p</math> oder <math>b</math> liegt. Es folgt: <math>p = ()</math>, <math>b = (1, 3, 4, 5, 6)</math> und die 2 und die 6 werden im Baum durch eine Kante verbunden.
# Der Baum mit <math>n-1</math> Knoten ist nun fertiggestellt. Da der Prüfer-Code fünfstellig ist, fehlt noch ein Knoten. Dieser ergibt sich, indem die beiden Zahlen, die jetzt nicht in <math>b = (1, 3, 4, 5, 6)</math> enthalten sind (also 2 und 7) verbunden werden.

== Anwendung ==
Der Prüfer-Code eines Baums mit <math>n</math> Knoten ist eine eindeutige Folge der Länge <math>n-2</math> mit Elementen aus <math>\{ 1, \ldots , n \}</math>. Umgekehrt gilt, dass es zu einem gegebenen Prüfer-Code <math>S</math> der Länge <math>n-2</math> mit Elementen aus <math>\{ 1, \ldots , n \}</math> einen eindeutigen beschrifteten Baum gibt. Das kann einfach mittels [[Vollständige Induktion|Induktion]] über <math>n</math> gezeigt werden.

Die direkte Konsequenz daraus ist, dass Prüfer-Codes eine [[Bijektion]] zwischen der Menge der beschrifteten Bäume mit <math>n</math> Knoten und der Menge der Folgen der Länge <math>n-2</math> mit Elementen aus <math>\{ 1, \ldots, n \}</math> darstellen. Die letztgenannte Menge hat die Größe <math>n^{n-2}</math>, wodurch die Existenz der Bijektion die [[Cayley-Formel]] beweist: Es gibt <math>n^{n-2}</math> beschriftete Bäume mit <math>n</math> Knoten.

Die Ergebnisse können verallgemeinert werden: Ein beschrifteter Baum ist ein [[Spannbaum]] eines beschrifteten [[Vollständiger Graph|vollständigen Graphen]]. Werden geeignete Einschränkungen an den Prüfer-Code gestellt, kann mit ähnlichen Methoden die Anzahl von Spannbäumen für vollständige bipartite Graphen ermittelt werden. Ist <math>G</math> ein vollständiger [[bipartiter Graph]] mit Knoten <math>1</math> bis <math>k</math> in einer Partition und Knoten <math>k+1</math> bis <math>n</math> in der anderen Partition, so ist in <math>G</math> die Anzahl der beschrifteten Spannbäume <math>k^{n-k-1}(n-k)^{k-1}</math>.

== Literatur ==
* Heinz Prüfer: ''Neuer Beweis eines Satzes über Permutationen.'' In: ''[[Archiv der Mathematik und Physik]].'' Reihe 3, Bd. 27, 1918, S. 742–744.

== Weblinks ==
{{Commonscat|Prüfer sequences|Prüfer-Code}}

{{DEFAULTSORT:Prufercode}}

[[Kategorie:Graphentheorie]]

Prüfer-Code - Versionsgeschichte

imported>Horst Gräbner: siehe den verlinkten Artikel