Comptez rapidement le nombre d'arbres couvrant

19

Soit le nombre d'arbres couvrant un graphe à sommets. Il existe un algorithme qui calcule dans les opérations arithmétiques . Cet algorithme consiste à calculer , où Q est le laplacien de G et J est la matrice constituée uniquement de 1 . Pour plus d'informations sur cet algorithme, voir Biggs - Théorie des graphes algébriques ou cette question Math SE .t(G)Gnt(G)O(n3)1n2det(J+Q)QGJ1

Je me demande s'il existe un moyen de calculer t(G) plus rapidement. (Oui, il existe des algorithmes plus rapides que O(n3) pour calculer le déterminant, mais je suis intéressé par une nouvelle approche.)

Il est également intéressé à considérer des familles spéciales de graphes (planaires, peut-être?).

Par exemple, pour les graphes circulants, t(G) peut être calculé dans les opérations arithmétiques O(nlgn) via l'identité t(G)=1nλ1λn1 , où λi sont des valeurs propres non nulles de la matrice laplacienne de G , qui peuvent être calculées rapidement pour les graphes circulants. (Représentez la première ligne comme un polynôme, puis calculez-la sur les n ième racines de l'unité - cette étape utilise la transformation de Fourier discrète et peut être effectuée dans les opérations arithmétiques O(nlgn) .)

Merci beaucoup!

Finsky
la source
Sergey, j'ai essayé de modifier votre question pour améliorer la clarté. Veuillez vérifier que j'ai bien compris votre question et que je n'ai introduit aucune erreur.
Tyson Williams
1
Voici un exemple plus général des familles graphique où trouver la complexité peut être fait plus rapidement: Cayley graphiques pour les groupes abéliens avec des générateurs mis , tels que . Nous savons que les valeurs propres d'une telle matrice sont , où sont différents caractères du groupe. Tous les caractères sont faciles à trouver (pour plus d'informations, consultez cet article ), le calcul de ces caractères est une FFT à dimensions (voir le chapitre de Cormen et al sur la FFT), c'est-à-dire peut être fait en . GSS1=ShSχ(h)χnO(nlgn)
Finsky
Pour plus d'informations sur les graphiques Cayley, consultez ce livre .
Finsky
1
Faire de l'algèbre linéaire avec le laplacien plutôt qu'avec une matrice générale est souvent plus facile. Je me demande si cela peut être pertinent.
Gil Kalai
Pourriez-vous, s'il vous plaît, être plus précis, si possible, fournir quelques exemples, même si ce n'est pas directement lié au sujet en discussion. Je vous remercie.
Finsky

Réponses:

12

On sait que, pour de largeur d'arbre bornée, le polynôme Tutte peut être évalué à n'importe quel utilisant des opérations arithmétiques . Si est connecté, alors .T ( G ; x , y ) ( x , y ) O ( n ) G t ( G ) = T ( G ; 1 , 1 )GT(G;x,y)(x,y)O(n)Gt(G)=T(G;1,1)

Radu Curticapean
la source