Prüfer-Code

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der Graphentheorie bezeichnet ein Prüfer-Code eine Folge, die einen beschrifteten Baum eineindeutig beschreibt. Der Code für einen Baum mit Knoten hat die Länge 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[Bearbeiten | Quelltext bearbeiten]

Prüfer-Code aus einem Baum[Bearbeiten | Quelltext bearbeiten]

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 mit Knoten . Im Schritt wird das Blatt mit der kleinsten Beschriftung aus dem Baum entfernt und das -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 .

Baum aus einem Prüfer-Code rekonstruieren[Bearbeiten | Quelltext bearbeiten]

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

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

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

Beispiel[Bearbeiten | Quelltext bearbeiten]

Prüfer-Code aus einem Baum[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Wir verwenden den obigen Prüfer-Code .

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

Anwendung[Bearbeiten | Quelltext bearbeiten]

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

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

Literatur[Bearbeiten | Quelltext bearbeiten]

  • Heinz Prüfer: Neuer Beweis eines Satzes über Permutationen. Arch. Math. Phys. 27: 742-744. 1918

Weblinks[Bearbeiten | Quelltext bearbeiten]

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