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

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 $p$ von links nach rechts durch und schreibt (in eine Liste $b$) die jeweils kleinste Zahl darunter, die weder in $p$, noch in $b$ enthalten ist. Diese wird mit der aktuellen Zahl in $p$ verbunden. Die aktuelle Zahl in $p$ wird anschließend gestrichen. Diese Schritte werden wiederholt, bis keine Elemente mehr in $p$ vorhanden sind. Das $i$-te Element in $p$ ist dann jeweils mit dem $i$-ten Element in $b$ durch eine Kante verbunden.

Man erhält so allerdings einen Baum mit nur $n-1$ Knoten. Um den $n$-ten Knoten zu erhalten, verbindet man nun die zwei Zahlen, die nicht in $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 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 $p=(5,5,2,2,2)$.

1. Das kleinste Element, das nicht in $p$ oder in $b=()$ enthalten ist, ist 1. Die erste 5 wird also im Baum mit der 1 verbunden, die 1 zu $b$ hinzugefügt und die 5 gestrichen.
2. Das kleinste Element, das nicht in $p=(5,2,2,2)$ oder in $b=(1)$ enthalten ist, ist die 3. Es folgt: $p=(2,2,2)$, $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 $p$ oder $b$ liegt. Es folgt: $p=(2,2)$, $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 $p$ oder $b$ liegt. Es folgt: $p=(2)$, $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 $p$ oder $b$ liegt. Es folgt: $p=()$, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b = (1, 3, 4, 5, 6)} und die 2 und die 6 werden im Baum durch eine Kante verbunden.
6. Der Baum mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b = (1, 3, 4, 5, 6)} enthalten sind (also 2 und 7) verbunden werden.

Anwendung

Der Prüfer-Code eines Baums mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Knoten ist eine eindeutige Folge der Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n-2} mit Elementen aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{ 1, \ldots , n \}} . Umgekehrt gilt, dass es zu einem gegebenen Prüfer-Code Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S} der Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n-2} mit Elementen aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{ 1, \ldots , n \}} einen eindeutigen beschrifteten Baum gibt. Das kann einfach mittels Induktion über Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} gezeigt werden.

Die direkte Konsequenz daraus ist, dass Prüfer-Codes eine Bijektion zwischen der Menge der beschrifteten Bäume mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Knoten und der Menge der Folgen der Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n-2} mit Elementen aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{ 1, \ldots, n \}} darstellen. Die letztgenannte Menge hat die Größe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n^{n-2}} , wodurch die Existenz der Bijektion die Cayley-Formel beweist: Es gibt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n^{n-2}} beschriftete Bäume mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} ein vollständiger bipartiter Graph mit Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} bis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} in einer Partition und Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k+1} bis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} in der anderen Partition, so ist in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} die Anzahl der beschrifteten Spannbäume Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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

Commons: Prüfer-Code – Sammlung von Bildern, Videos und Audiodateien