Notation de Neveu

En théorie des graphes, un arbre planaire enraciné peut être décrit de manière non ambigüe par la liste de ses sommets, chacun désigné par une suite finie d'entiers, qui sont les positions, au sein de leur fratrie, des ancêtres du sommet : c'est la notation de Neveu^[1].

On utilise ici l'arbre généalogique comme métaphore pour l'arbre planaire  : le sommet 2|4|3 désigne le 3^e fils du 4^e fils du 2^e fils de l'ancêtre (l'ancêtre étant lui-même désigné par la suite vide, notée ${\displaystyle \scriptstyle \emptyset \ }$). Par convention, l'ancêtre est le sommet initial de l'arête racine, et le sommet final de l'arête racine est le fils ainé de l'ancêtre : en tant que tel, il est noté 1. La longueur de la suite associée à un sommet est la hauteur (ou la profondeur) du sommet, i.e. la distance entre ce sommet et le début de la racine, qui représente l'ancêtre : en filant la métaphore, un sommet de hauteur n représente un individu appartenant à la n-ème génération de la population fondée par l'ancêtre.