Dénombrer les arbres couvrants

[Subsib]

Bonjour,

j'ai un exercice, et je ne sais pas très bien comment dénombrer les solutions.


Voici l'arbre en exemple : il faut trouver combien d’arbres couvrants possède le graphe.

J'ai pensé que c'était
soit

Mais je ne sais pas justifier ce résultat, et je ne suis pas sûre du tout que ce soit ça.
Quelqu'un aurait-il la gentillesse de m'aider s'il vous plait ?

Merci d'avance.

[Robot]

Ton dessin n'est pas le dessin d'un arbre, mais du graphe complet à 4 sommets. Tu pars du graphe complet à n sommets ?

[Subsib]

Oui, le dessin est celui d'un graphe, et je dois trouver les arbres couvrants contenus dans ce graphe.
Tous. Et je ne sais pas comment m'y prendre.

[Robot]

Ton exercice, c'est spécifiquement pour le graphe complet à 4 sommets, ou de manière générale pour le graphe complet à n sommets ?

[Subsib]

a priori, seulement pour ce graphe-ci.

[Robot]

Pour le problème général, le dénombrement demande un peu de travail, et tu pourras voir des démonstrations en cherchant "Arbres - formule de Cayley".
Pour le cas de 4 sommets :
- tu peux commencer par voir le nombre d'arbres à 4 sommets (à isomorphisme près) ; il y en a deux.
- pour chacun de ces deux arbres, voir le nombre de façons d'étiqueter les sommets avec les n° 1,2,3,4 (à isomorphisme de graphe étiqueté près).
Tu devrais bien trouver 16, nombre donné par la formule de Cayley.

Une autre façon de faire : un arbre à 4 sommet a toujours 3 arêtes. Il faut donc en effacer 3 dans le graphe complet. Tu peux voir les façons de faire, en tenant compte des symétries du carré. Tu trouveras aussi 16, bien sûr.

[Subsib]

Ah !! merci, j'avais donc bien trouvé.
On a bien vu la formule de Cayley, ce qui était difficile pour moi était de faire le lien entre le problème et celle-ci, mais là, j'y vois plus clair, déjà.

Merci.