In der Graphentheorie bezeichnet ein Prüfer-Code eine Folge, die einen beschrifteten Baum eineindeutig beschreibt. Der Code für einen Baum mit n {\displaystyle n} Knoten hat die Länge n − 2 {\displaystyle n-2} und kann mit einem einfachen iterativen Algorithmus erstellt werden. Prüfer-Codes wurden 1918 von Heinz Prüfer eingeführt, um die Cayley-Formel zu beweisen.
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 T {\displaystyle T} mit Knoten { 1 , 2 , … , n } {\displaystyle \{1,2,\ldots ,n\}} . Im Schritt i {\displaystyle i} wird das Blatt mit der kleinsten Beschriftung aus dem Baum entfernt und das i {\displaystyle i} -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 n − 2 {\displaystyle n-2} .
Der ursprüngliche Baum aus einem Prüfer-Code kann ebenfalls leicht gewonnen werden.
Dazu geht man den Prüfer-Code p {\displaystyle p} von links nach rechts durch und schreibt (in eine Liste b {\displaystyle b} ) die jeweils kleinste Zahl darunter, die weder in p {\displaystyle p} , noch in b {\displaystyle b} enthalten ist. Diese wird mit der aktuellen Zahl in p {\displaystyle p} verbunden. Die aktuelle Zahl in p {\displaystyle p} wird anschließend gestrichen. Diese Schritte werden wiederholt, bis keine Elemente mehr in p {\displaystyle p} vorhanden sind. Das i {\displaystyle i} -te Element in p {\displaystyle p} ist dann jeweils mit dem i {\displaystyle i} -ten Element in b {\displaystyle b} durch eine Kante verbunden.
Man erhält so allerdings einen Baum mit nur n − 1 {\displaystyle n-1} Knoten. Um den n {\displaystyle n} -ten Knoten zu erhalten, verbindet man nun die zwei Zahlen, die nicht in b {\displaystyle b} enthalten sind, durch eine weitere Kante.
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.
Wir verwenden den obigen Prüfer-Code p = ( 5 , 5 , 2 , 2 , 2 ) {\displaystyle p=(5,5,2,2,2)} .
Der Prüfer-Code eines Baums mit n {\displaystyle n} Knoten ist eine eindeutige Folge der Länge n − 2 {\displaystyle n-2} mit Elementen aus { 1 , … , n } {\displaystyle \{1,\ldots ,n\}} . Umgekehrt gilt, dass es zu einem gegebenen Prüfer-Code S {\displaystyle S} der Länge n − 2 {\displaystyle n-2} mit Elementen aus { 1 , … , n } {\displaystyle \{1,\ldots ,n\}} einen eindeutigen beschrifteten Baum gibt. Das kann einfach mittels Induktion über n {\displaystyle n} gezeigt werden.
Die direkte Konsequenz daraus ist, dass Prüfer-Codes eine Bijektion zwischen der Menge der beschrifteten Bäume mit n {\displaystyle n} Knoten und der Menge der Folgen der Länge n − 2 {\displaystyle n-2} mit Elementen aus { 1 , … , n } {\displaystyle \{1,\ldots ,n\}} darstellen. Die letztgenannte Menge hat die Größe n n − 2 {\displaystyle n^{n-2}} , wodurch die Existenz der Bijektion die Cayley-Formel beweist: Es gibt n n − 2 {\displaystyle n^{n-2}} beschriftete Bäume mit n {\displaystyle n} Knoten.
Die Ergebnisse können verallgemeinert werden: Ein beschrifteter Baum ist ein Spannbaum eines beschrifteten 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 G {\displaystyle G} ein vollständiger bipartiter Graph mit Knoten 1 {\displaystyle 1} bis k {\displaystyle k} in einer Partition und Knoten k + 1 {\displaystyle k+1} bis n {\displaystyle n} in der anderen Partition, so ist in G {\displaystyle G} die Anzahl der beschrifteten Spannbäume k n − k − 1 ( n − k ) k − 1 {\displaystyle k^{n-k-1}(n-k)^{k-1}} .