www.wikidata.de-de.nina.az

Prüfer Code In der Graphentheorie bezeichnet ein eine Folge die einen beschrifteten Baum eineindeutig beschreibt Der Cod

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 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

Prüfer-Code aus einem Baum 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

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

Prüfer-Code aus einem Baum 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

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

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

Weblinks Bearbeiten

Commons: Prüfer-Code – Sammlung von Bildern, Videos und Audiodateien
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der Graphentheorie bezeichnet ein Prufer Code eine Folge die einen beschrifteten Baum eineindeutig beschreibt Der Code fur einen Baum mit n displaystyle n Knoten hat die Lange n 2 displaystyle n 2 und kann mit einem einfachen iterativen Algorithmus erstellt werden Prufer Codes wurden 1918 von Heinz Prufer eingefuhrt um die Cayley Formel zu beweisen Inhaltsverzeichnis 1 Algorithmus 1 1 Prufer Code aus einem Baum 1 2 Baum aus einem Prufer Code rekonstruieren 2 Beispiel 2 1 Prufer Code aus einem Baum 2 2 Baum aus einem Prufer Code 3 Anwendung 4 Literatur 5 WeblinksAlgorithmus BearbeitenPrufer Code aus einem Baum Bearbeiten Erstellt werden kann ein Prufer Code aus einem Baum durch das iterative Entfernen von Knoten bis nur noch zwei Knoten ubrig sind Gegeben sei ein Baum T displaystyle T nbsp mit Knoten 1 2 n displaystyle 1 2 ldots n nbsp Im Schritt i displaystyle i nbsp wird das Blatt mit der kleinsten Beschriftung aus dem Baum entfernt und das i displaystyle i nbsp te Element des Prufer Codes auf die Beschriftung des einzigen Nachbarn des entfernten Blattes gesetzt Der Code eines Baums ist offensichtlich eindeutig und hat die Lange n 2 displaystyle n 2 nbsp Baum aus einem Prufer Code rekonstruieren Bearbeiten Der ursprungliche Baum aus einem Prufer Code kann ebenfalls leicht gewonnen werden Dazu geht man den Prufer Code p displaystyle p nbsp von links nach rechts durch und schreibt in eine Liste b displaystyle b nbsp die jeweils kleinste Zahl darunter die weder in p displaystyle p nbsp noch in b displaystyle b nbsp enthalten ist Diese wird mit der aktuellen Zahl in p displaystyle p nbsp verbunden Die aktuelle Zahl in p displaystyle p nbsp wird anschliessend gestrichen Diese Schritte werden wiederholt bis keine Elemente mehr in p displaystyle p nbsp vorhanden sind Das i displaystyle i nbsp te Element in p displaystyle p nbsp ist dann jeweils mit dem i displaystyle i nbsp ten Element in b displaystyle b nbsp durch eine Kante verbunden Man erhalt so allerdings einen Baum mit nur n 1 displaystyle n 1 nbsp Knoten Um den n displaystyle n nbsp ten Knoten zu erhalten verbindet man nun die zwei Zahlen die nicht in b displaystyle b nbsp enthalten sind durch eine weitere Kante Beispiel BearbeitenPrufer Code aus einem Baum Bearbeiten nbsp Ein beschrifteter Baum mit Prufer Code 5 5 2 2 2Der 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 Prufer Code eingefugt Anschliessend werden die Blatter 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 angehangt Als letzter Knoten wird Knoten 6 aus dem Baum entfernt und 2 an die Folge angehangt Der Algorithmus terminiert da nur noch zwei Knoten 2 und 7 ubrig sind Baum aus einem Prufer Code Bearbeiten Wir verwenden den obigen Prufer Code p 5 5 2 2 2 displaystyle p 5 5 2 2 2 nbsp Das kleinste Element das nicht in p displaystyle p nbsp oder in b displaystyle b nbsp enthalten ist ist 1 Die erste 5 wird also im Baum mit der 1 verbunden die 1 zu b displaystyle b nbsp hinzugefugt und die 5 gestrichen Das kleinste Element das nicht in p 5 2 2 2 displaystyle p 5 2 2 2 nbsp oder in b 1 displaystyle b 1 nbsp enthalten ist ist die 3 Es folgt p 2 2 2 displaystyle p 2 2 2 nbsp b 1 3 displaystyle b 1 3 nbsp und die 5 und die 3 werden im Baum durch eine Kante verbunden Als nachstes ist 4 das kleinste Element das nicht in p displaystyle p nbsp oder b displaystyle b nbsp liegt Es folgt p 2 2 displaystyle p 2 2 nbsp b 1 3 4 displaystyle b 1 3 4 nbsp und die 2 und die 4 werden im Baum durch eine Kante verbunden Als nachstes ist 5 das kleinste Element das nicht in p displaystyle p nbsp oder b displaystyle b nbsp liegt Es folgt p 2 displaystyle p 2 nbsp b 1 3 4 5 displaystyle b 1 3 4 5 nbsp und die 2 und die 5 werden im Baum durch eine Kante verbunden Als nachstes ist 6 das kleinste Element das nicht in p displaystyle p nbsp oder b displaystyle b nbsp liegt Es folgt p displaystyle p nbsp b 1 3 4 5 6 displaystyle b 1 3 4 5 6 nbsp und die 2 und die 6 werden im Baum durch eine Kante verbunden Der Baum mit n 1 displaystyle n 1 nbsp Knoten ist nun fertiggestellt Da der Prufer Code funfstellig ist fehlt noch ein Knoten Dieser ergibt sich indem die beiden Zahlen die jetzt nicht in b 1 3 4 5 6 displaystyle b 1 3 4 5 6 nbsp enthalten sind also 2 und 7 verbunden werden Anwendung BearbeitenDer Prufer Code eines Baums mit n displaystyle n nbsp Knoten ist eine eindeutige Folge der Lange n 2 displaystyle n 2 nbsp mit Elementen aus 1 n displaystyle 1 ldots n nbsp Umgekehrt gilt dass es zu einem gegebenen Prufer Code S displaystyle S nbsp der Lange n 2 displaystyle n 2 nbsp mit Elementen aus 1 n displaystyle 1 ldots n nbsp einen eindeutigen beschrifteten Baum gibt Das kann einfach mittels Induktion uber n displaystyle n nbsp gezeigt werden Die direkte Konsequenz daraus ist dass Prufer Codes eine Bijektion zwischen der Menge der beschrifteten Baume mit n displaystyle n nbsp Knoten und der Menge der Folgen der Lange n 2 displaystyle n 2 nbsp mit Elementen aus 1 n displaystyle 1 ldots n nbsp darstellen Die letztgenannte Menge hat die Grosse n n 2 displaystyle n n 2 nbsp wodurch die Existenz der Bijektion die Cayley Formel beweist Es gibt n n 2 displaystyle n n 2 nbsp beschriftete Baume mit n displaystyle n nbsp Knoten Die Ergebnisse konnen verallgemeinert werden Ein beschrifteter Baum ist ein Spannbaum eines beschrifteten vollstandigen Graphen Werden geeignete Einschrankungen an den Prufer Code gestellt kann mit ahnlichen Methoden die Anzahl von Spannbaumen fur vollstandige bipartite Graphen ermittelt werden Ist G displaystyle G nbsp ein vollstandiger bipartiter Graph mit Knoten 1 displaystyle 1 nbsp bis k displaystyle k nbsp in einer Partition und Knoten k 1 displaystyle k 1 nbsp bis n displaystyle n nbsp in der anderen Partition so ist in G displaystyle G nbsp die Anzahl der beschrifteten Spannbaume k n k 1 n k k 1 displaystyle k n k 1 n k k 1 nbsp Literatur BearbeitenHeinz Prufer Neuer Beweis eines Satzes uber Permutationen In Archiv der Mathematik und Physik Reihe 3 Bd 27 1918 S 742 744 Weblinks Bearbeiten nbsp Commons Prufer Code Sammlung von Bildern Videos und Audiodateien Abgerufen von https de wikipedia org w index php title Prufer Code amp oldid 213573032