Calcul du nombre total d'arbres de recouvrement contenant un ensemble particulier d'arêtes

Question

Je l'ai essayé l'approche suivante:

D'abord, je fais la contraction de bord pour tous les bords dans l'ensemble donné des bords pour former un graphique modifié.

Alors je calcule le nombre total d'arbres couvrants, en utilisant le théorème de l'arbre de la matrice, à partir du graphique modifié.

Je veux savoir si cette méthode est correcte et s'il y a d'autres méthodes mieux.

Answer 1

Soit G un graphe, soit e un bord, et G / E le même graphique avec e contrat. Ensuite,

Proposition: Il y a une bijection entre les arbres de G couvrant contenant e, et les

arbres de G / e couvrant.

Cette proposition n'est pas difficile à prouver; vous êtes mieux comprendre la preuve vous-même au lieu de simplement demander à d'autres que ce qui est vrai. Il est évident que si vous avez un arbre couvrant T de G qui contient e, T / e est un arbre couvrant de G / e. La chose à réfléchir est que vous pouvez revenir en arrière.

Et, comme Adam souligne, il faut faire attention à gérer correctement des graphiques avec des bords parallèles et des graphiques avec des bords d'un sommet lui-même.

Answer 2

Je ne sais pas s'il est correct ou non, mais vous devrez faire attention au fait que la contraction de bord peut entraîner des bords parallèles. Vous devez vous assurer que les arbres ne diffèrent que par lequel bord parallèle est utilisé sont comptés comme étant distincts.