Article : Arbres gracieux - Collège Alain Fournier (Orsay)

Article
Résumé de la production
Un arbre à n arêtes est gracieux si l'on peut étiqueter ses sommets de 0 à n sans doublon, ses arêtes de 1 à n sans doublon, et de telle sorte que la valeur d'une arête soit la différence (en valeur absolue) des valeurs des sommets situés à ses extrémités.
Une conjecture encore ouverte aujourd'hui est que tout arbre est gracieux. Ici, les élèves explorent la validité de cette conjecture sur les étoiles, les chemins et les chenilles, où des algorithmes de coloration gracieuse sont exhibés. Le cas des homards et des araignées est également considéré, mais aucun algorithme générique n'est proposé pour ces familles de graphes.
Mots clés
arbre
coloration
algorithme