Établissement
Université de Bordeaux (Talence)
Année
2014-2015
Résumé
On appelle "arbre" une structure obtenue en reliant n points (appelés sommets) par n - 1 lignes (appelées arêtes), chacune reliant deux points, de façon telle que la structure ne contient aucun cycle. On cherche à numéroter de 1 à n les sommets d'un arbre à n sommets de façon telle que, si on inscrit sur chaque arête la différence entre les valeurs de ses extrémités, toues les n-1 arêtes ont des valeurs distinctes. Tous les arbres admettent-ils une bonne numérotation ? Quelles formes particulières d'arbres admettent une bonne numérotation ?