Enumaration of the number of spanning trees in some special planar maps

Abstract

Le nombre d’arbres couvrants dans une carte planaire - graphe plongé dans une surface sans croisement d’arêtes - (réseau) est un important bien étudié la quantité et invariant du graphe (réseau); de plus c’est aussi une mesure importante de la fiabilité d’un réseau qui joue un rôle central dans la théorie classique de Kirchhoff des réseaux électriques. Dans un graphe (réseau) qui contient plusieurs cycles, il faut supprimer les redondances dans ce réseau, i.e., on obtient un arbre couvrant. Un arbre couvrant dans une carte C est un arbre qui a le même ensemble de sommets en tant que C (arbre qui passe par tous les sommets de la carte C). Notre thème de recherche dans cette thèse se concentre sur le calcul du nombre d’arbres couvrants dans les cartes planaires connexes, un sujet dans la théorie des graphes combinatoire; ainsi que, pour trouver de nouvelles méthodes pour calculer le nombre d’arbres couvrants dans une carte planaire (réseau). Arbres couvrants sont pertinents pour les différents aspects de graphes (réseaux). En général, le nombre d’arbres couvrants dans un réseau peut être obtenu par le calcul le déterminant de la matrice laplacien liée ou le calcul du spectre de Laplace du réseau. Cependant, pour une grande carte (réseau), l’évaluation du déterminant pertinent est calcul intraitable. Dans ce travail, nous fournissons de nouvelles méthodes pour faciliter le calcul du nombre d’arbres couvrants dans les cartes planaires et de prouver de nouveaux résultats simplifiée et généralisée. Enfin, nous appliquons ces méthodes sur certaines cartes planaires de dériver plusieurs formules explicites pour calculer le nombre d’arbres couvrants dans certaines familles particulières des cartes planaires.