Étiquette : Matrix tree theorem

Formule de Cayley

Exercice La formule de Cayley affirme que pour n>1, le nombre Cn d’arbres qu’on peut construire sur n sommets est nn−2. Le matrix tree theorem ou théorème de Kirchhoff, déjà présenté en exercice, nous permet de calculer directement cette valeur. 1) Prouver la formule de Cayley à l’aide du Matrix Tree Theorem. Une […]

Théorème de Kirchhoff

On présente ici un résultat important de la théorie des graphes pourtant méconnus des étudiants. Le but de cet exercice est de démontrer le théorème de Kirchhoff, aussi appelé matrix tree theorem. Ce théorème donne une formule pour compter le nombre d’arbres couvrants d’un graphe. Cet exercice nécessite une bon maîtrise mathématique de la notion […]