Neffen-Notation
In der Graphentheorie kann ein verwurzelter planarer Baum eindeutig durch die Liste seiner Scheitelpunkte beschrieben werden, die jeweils durch eine endliche Reihe von ganzen Zahlen bezeichnet werden, die die Positionen der Vorfahren des Scheitelpunkts innerhalb ihrer Geschwister darstellen: c 'ist Neveus Notation .
Der Stammbaum wird hier als Metapher für die planare Baum: Scheitel 2 | 4 | 3 das bezeichnet 3 rd Sohn des 4 - ten Sohn des 2 nd Sohn des Vorfahren (Vorfahr sich durch die leere Suite bezeichnet wird, notiert ). Konventionell ist der Vorfahr der anfängliche Scheitelpunkt der Wurzelkante, und der letzte Scheitelpunkt der Wurzelkante ist das älteste Kind des Vorfahren. Als solches wird er mit 1 bezeichnet. Die Länge der zugehörigen Sequenz an einem Scheitelpunkt ist die Höhe (oder Tiefe ) des Scheitelpunkts, dh der Abstand zwischen diesem Scheitelpunkt und dem Beginn der Wurzel, der den Vorfahren darstellt: Wenn man der Metapher folgt, repräsentiert ein Scheitelpunkt der Höhe n ein Individuum, das zur n- ten Generation der gegründeten Bevölkerung gehört vom Vorfahren.
Beispiel
Beispiel:Die 5 3-kantigen Bäume oben werden daher durch die 5 folgenden Sätze von Wörtern beschrieben:
Bemerkungen
Die Route der Eckpunkte in lexikografischer Reihenfolge ist dann die vorangestellte Tiefenroute (oder Präfixroute) eines Baums, die in der Informatik als Datenstruktur angesehen wird . Eine andere Anwendung: Mit dieser Notation codiert ein planarer Baum bequemerweise eine Realisierung des Galton-Watson-Prozesses mit Extinktion. Nichts ist dagegen, einen unendlichen planaren Baum mit der Neveu-Notation zu definieren, die es ermöglicht, die Realisierungen von Galton-Watson-Prozessen zu codieren, bei denen die Population nicht erlischt.
Bewertung und Referenz
- J. Neveu , „ Bäume und Galton-Watson-Prozesse “, Ann. von der IHP , vol. 22, n o 21986( online lesen ) (Sektion 2).