Prüfer-Code

In der Graphentheorie bezeichnet ein Prüfer-Code eine Folge, die einen beschrifteten Baum eineindeutig beschreibt. Der Code für einen Baum mit ${\displaystyle n}$ Knoten hat die Länge ${\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.

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 ${\displaystyle T}$ mit Knoten ${\displaystyle \{1,2,\ldots ,n\}}$. Im Schritt ${\displaystyle i}$ wird das Blatt mit der kleinsten Beschriftung aus dem Baum entfernt und das ${\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 ${\displaystyle n-2}$.

Baum aus einem Prüfer-Code rekonstruieren

Der ursprüngliche Baum a​us einem Prüfer-Code k​ann ebenfalls leicht gewonnen werden.

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

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

Beispiel

Prüfer-Code aus einem Baum

Ein beschrifteter Baum mit Prüfer-Code 5, 5, 2, 2, 2

Der o​ben vorgestellte Algorithmus w​ird auf d​as Bild rechts angewandt. Zu Beginn i​st der Knoten 1 d​as Blatt m​it der kleinsten Beschriftung, d​aher wird dieser Knoten a​ls erstes entfernt u​nd 5 w​ird als erstes Element i​n den Prüfer-Code eingefügt. Anschließend werden d​ie Blätter 3 u​nd 4 a​us dem Baum entfernt u​nd die Folge u​m 5 u​nd 2 erweitert. Da d​er Knoten 5 j​etzt das kleinste Blatt ist, w​ird er a​us dem Baum entfernt u​nd 2 a​n die Folge angehängt. Als letzter Knoten w​ird Knoten 6 a​us dem Baum entfernt u​nd 2 a​n die Folge angehängt. Der Algorithmus terminiert, d​a nur n​och zwei Knoten (2 u​nd 7) übrig sind.

Baum aus einem Prüfer-Code

Wir verwenden den obigen Prüfer-Code ${\displaystyle p=(5,5,2,2,2)}$.

1. Das kleinste Element, das nicht in ${\displaystyle p}$ oder in ${\displaystyle b=()}$ enthalten ist, ist 1. Die erste 5 wird also im Baum mit der 1 verbunden, die 1 zu ${\displaystyle b}$ hinzugefügt und die 5 gestrichen.
2. Das kleinste Element, das nicht in ${\displaystyle p=(5,2,2,2)}$ oder in ${\displaystyle b=(1)}$ enthalten ist, ist die 3. Es folgt: ${\displaystyle p=(2,2,2)}$, ${\displaystyle b=(1,3)}$ und die 5 und die 3 werden im Baum durch eine Kante verbunden.
3. Als nächstes ist 4 das kleinste Element, das nicht in ${\displaystyle p}$ oder ${\displaystyle b}$ liegt. Es folgt: ${\displaystyle p=(2,2)}$, ${\displaystyle b=(1,3,4)}$ und die 2 und die 4 werden im Baum durch eine Kante verbunden.
4. Als nächstes ist 5 das kleinste Element, das nicht in ${\displaystyle p}$ oder ${\displaystyle b}$ liegt. Es folgt: ${\displaystyle p=(2)}$, ${\displaystyle b=(1,3,4,5)}$ und die 2 und die 5 werden im Baum durch eine Kante verbunden.
5. Als nächstes ist 6 das kleinste Element, das nicht in ${\displaystyle p}$ oder ${\displaystyle b}$ liegt. Es folgt: ${\displaystyle p=()}$, ${\displaystyle b=(1,3,4,5,6)}$ und die 2 und die 6 werden im Baum durch eine Kante verbunden.
6. Der Baum mit ${\displaystyle n-1}$ 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 ${\displaystyle b=(1,3,4,5,6)}$ enthalten sind (also 2 und 7) verbunden werden.

Anwendung

Der Prüfer-Code eines Baums mit ${\displaystyle n}$ Knoten ist eine eindeutige Folge der Länge ${\displaystyle n-2}$ mit Elementen aus ${\displaystyle \{1,\ldots ,n\}}$. Umgekehrt gilt, dass es zu einem gegebenen Prüfer-Code ${\displaystyle S}$ der Länge ${\displaystyle n-2}$ mit Elementen aus ${\displaystyle \{1,\ldots ,n\}}$ einen eindeutigen beschrifteten Baum gibt. Das kann einfach mittels Induktion über ${\displaystyle n}$ gezeigt werden.

Die direkte Konsequenz daraus ist, dass Prüfer-Codes eine Bijektion zwischen der Menge der beschrifteten Bäume mit ${\displaystyle n}$ Knoten und der Menge der Folgen der Länge ${\displaystyle n-2}$ mit Elementen aus ${\displaystyle \{1,\ldots ,n\}}$ darstellen. Die letztgenannte Menge hat die Größe ${\displaystyle n^{n-2}}$, wodurch die Existenz der Bijektion die Cayley-Formel beweist: Es gibt ${\displaystyle n^{n-2}}$ beschriftete Bäume mit ${\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 ${\displaystyle G}$ ein vollständiger bipartiter Graph mit Knoten ${\displaystyle 1}$ bis ${\displaystyle k}$ in einer Partition und Knoten ${\displaystyle k+1}$ bis ${\displaystyle n}$ in der anderen Partition, so ist in ${\displaystyle G}$ die Anzahl der beschrifteten Spannbäume ${\displaystyle k^{n-k-1}(n-k)^{k-1}}$.

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