Comptez rapidement le nombre d'arbres couvrant

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ù est le laplacien de et est la matrice constituée uniquement de . Pour plus d'informations sur cet algorithme, voir Biggs - Théorie des graphes algébriques ou cette question Math SE . $t(G)$ $G$ $n$ $t(G)$ $O(n^3)$ $\frac{1}{n^2} \det(J + Q)$ $Q$ $G$ $J$ $1$

Je me demande s'il existe un moyen de calculer $t(G)$ plus rapidement. (Oui, il existe des algorithmes plus rapides que $O(n^3)$ 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(n \lg n)$ via l'identité $t(G) = \frac{1}{n} \lambda_1 \dotsm \lambda_{n-1}$ , où $\lambda_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(n \lg n)$ .)

Merci beaucoup!

graph-theory graph-algorithms counting-complexity spectral-graph-theory 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

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 .

G

$G$

S

$S$

S^{- 1} = S

$S^{-1} = S$

\sum_{h \in S} χ (h)

$\sum_{h \in S} \chi (h)$

χ

$\chi$

n

$n$

O (n \lg n)

$O(n \lg n)$

Finsky

Pour plus d'informations sur les graphiques Cayley, consultez ce livre .

Finsky

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

Comptez rapidement le nombre d'arbres couvrant

Réponses: