Le calculateur du nombre d’arbres couvrants donne le nombre d’arbres couvrants d’un graphe complet avec la formule de Cayley, d’un graphe biparti complet, d’une roue et d’un cycle, avec la longueur du code de Prüfer et le nombre d’arêtes d’un arbre.
Comment se fait le calcul
- Saisissez les sommets du graphe complet.
- Saisissez les tailles des deux parties du graphe biparti et les rayons de la roue.
- Lisez le nombre d’arbres couvrants de chaque graphe.
Exemple
Le graphe complet à 6 sommets a 1 296 arbres couvrants, chacun avec 5 arêtes et un code de Prüfer de longueur 4. Le graphe biparti complet K(3, 4) en a 432. Une roue à 6 rayons en a 320, et son cycle de jante en a 6.
Pourquoi c’est utile
Le calculateur aide les étudiants en théorie des graphes et mathématiques discrètes, concepteurs de réseaux et amateurs de casse-têtes qui veulent compter les façons de relier un ensemble de nœuds avec le minimum de liens, vérifier la formule de Cayley sur de petits cas, ou comparer la richesse de différentes formes de réseaux.
À savoir
Les décomptes concernent des sommets étiquetés, donc deux arbres qui ne diffèrent que par le nom des sommets sont comptés séparément. Les nombres croissent vite avec le nombre de sommets, donc le calculateur limite les tailles. Utilisez le théorème de Kirchhoff pour les graphes qui ne sont pas dans ces familles. La formule de la roue utilise le nombre de Lucas arrondi à partir du nombre d’or, ce qui est exact pour les tailles permises. La part affichée se compare à tous les sous-ensembles d’arêtes de la bonne taille. Pour une vérification rapide, un graphe complet à 3 sommets a 3 arbres couvrants, et un chemin ou une étoile sur un nombre quelconque de sommets en a exactement un.
Outils liés
Le calculateur du graphe de Turán traite les graphes extrémaux, celui des combinaisons compte les sous-ensembles, celui du binôme donne les coefficients et celui de Fibonacci renvoie aux nombres de Lucas.