Étudier les arbres - Collège Charles Lebrun (Montmorency) Collège L’Ardillière de Nézant (St Brice)

Un graphe se compose de deux types d'éléments, des "sommets" (aussi appelés "nœuds") et des "arêtes", chaque arête pouvant être vue comme une paire de sommets, appelés les extrémités de l'arête. On représente souvent une arête comme une liaison qui joint ses deux extrémités. Un arbre (avec racine) est un type particulier de graphe qui peut être construit de proche en proche de la manière suivante : on choisit au début un sommet particulier comme "racine" (sommet de base); puis, à chaque étape on ajoute de nouveaux sommets que l'on joint par de nouvelles arêtes à un sommet choisi déjà construit.
Le problème consiste à construire tous les arbres possibles ayant un nombre donné de sommets et à les compter.