Aller au contenu
Omnikalc

Calculateur du nombre d’arbres couvrants

Saisissez le nombre de sommets d’un graphe complet, les tailles des deux parties d’un graphe biparti complet et le nombre de rayons d’une roue pour obtenir le nombre d’arbres couvrants de chacun.

Mis à jour le
Vos paramètres

Valeur hors limites

Valeur hors limites

Valeur hors limites

Valeur hors limites

Résultats

Arbres couvrants du graphe complet

1 296

Arbres couvrants du graphe biparti complet

432

Arbres couvrants de la roue

320

Arbres couvrants du cycle de la même jante
6
Longueur du code de Prüfer du graphe complet
4
Arêtes de chaque arbre couvrant du graphe complet
5
Arbres couvrants en part de tous les sous-ensembles d’arêtes de même taille
43,1568 %

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.

Questions fréquentes

Qu’est-ce que la formule de Cayley ?

La formule de Cayley dit que le graphe complet à n sommets étiquetés a exactement n^(n−2) arbres couvrants. Pour n = 4, il y a 16 arbres étiquetés, pour n = 5 il y en a 125 et pour n = 6 il y en a 1 296. Elle a été énoncée par Cayley en 1889, et Prüfer en a donné une preuve avec une bijection entre arbres et suites de longueur n − 2.

Comment compte-t-on les arbres couvrants d’un graphe biparti ?

Pour le graphe biparti complet K(m, n), le nombre d’arbres couvrants est m^(n−1) × n^(m−1). Pour K(3, 4), c’est 3³ × 4² = 432. Pour m = 1, c’est une étoile avec un seul arbre couvrant, qui est le graphe lui-même.

Et la roue ?

Une roue à w rayons a w + 1 sommets : un moyeu relié à tous les sommets d’un cycle de w sommets. Son nombre d’arbres couvrants est L(2w) − 2, où L est le nombre de Lucas. Pour w = 6, c’est L(12) − 2 = 322 − 2 = 320. La suite pour w ≥ 3 commence par 16, 45, 121, 320.

Pourquoi compte-t-on les arbres couvrants ?

Les arbres couvrants décrivent les façons de relier tous les nœuds d’un réseau avec le moins de liens. Le nombre mesure la robustesse d’une conception de réseau, il entre dans les calculs de fiabilité et l’analyse des réseaux électriques, et le théorème de l’arbre matriciel de Kirchhoff les compte pour tout graphe à partir du déterminant du laplacien.

Ce calculateur vous a-t-il été utile ?

Merci pour votre avis !

Résultats indicatifs fournis à titre d'information. Ils ne remplacent pas l'avis d'un professionnel.