Les graphes 119
maître et de sous-répertoires qui s’en écartent. Parce qu’il n’y a pas de cycle, il n’y
a aucun moyen de traverser d’une branche à l’autre autrement qu’en passant par le
répertoire maître, manœuvre familière pour les utilisateurs d’ordinateurs.
Compter les arbres Combien d’arbres différents peut-on construire à partir
d’un nombre spécifique de sommets ? Le problème de l’énumération des structures arborescentes a été traité par Arthur Cayley, grand mathématicien anglais du
xix
e siècle. Il existe par exemple exactement trois types différents d’arbres comportant cinq points :
Cayley réussit à énumérer les structures arborescentes pour un nombre inférieur de
points. Il s’arrêta aux arbres contenant moins de 14 points avant que la complexité
du calcul ne soit trop grande pour un homme travaillant sans ordinateur. Depuis
lors, les calculs ont progressé et nous en sommes maintenant à des arbres de 22
points. Il existe des millions de structures possibles dans ce cas.
Les recherches de Cayley avaient déjà des applications pratiques à son époque.
Énumérer les arbres est utile en chimie, où le caractère distinctif de certains composés dépend de la manière dont les atomes sont arrangés dans leurs molécules. Les
composés comportant le même nombre d’atomes arrangés différemment ont des
propriétés chimiques différentes. L’utilisation de cette analyse permit de prédire
« crayon en main » la présence de produits chimiques que des études en laboratoire
pouvaient ensuite confirmer.
l’idée clé
Par les ponts
et par les arbres
maître et de sous-répertoires qui s’en écartent. Parce qu’il n’y a pas de cycle, il n’y
a aucun moyen de traverser d’une branche à l’autre autrement qu’en passant par le
répertoire maître, manœuvre familière pour les utilisateurs d’ordinateurs.
Compter les arbres Combien d’arbres différents peut-on construire à partir
d’un nombre spécifique de sommets ? Le problème de l’énumération des structures arborescentes a été traité par Arthur Cayley, grand mathématicien anglais du
xix
e siècle. Il existe par exemple exactement trois types différents d’arbres comportant cinq points :
Cayley réussit à énumérer les structures arborescentes pour un nombre inférieur de
points. Il s’arrêta aux arbres contenant moins de 14 points avant que la complexité
du calcul ne soit trop grande pour un homme travaillant sans ordinateur. Depuis
lors, les calculs ont progressé et nous en sommes maintenant à des arbres de 22
points. Il existe des millions de structures possibles dans ce cas.
Les recherches de Cayley avaient déjà des applications pratiques à son époque.
Énumérer les arbres est utile en chimie, où le caractère distinctif de certains composés dépend de la manière dont les atomes sont arrangés dans leurs molécules. Les
composés comportant le même nombre d’atomes arrangés différemment ont des
propriétés chimiques différentes. L’utilisation de cette analyse permit de prédire
« crayon en main » la présence de produits chimiques que des études en laboratoire
pouvaient ensuite confirmer.
l’idée clé
Par les ponts
et par les arbres