Formule exacte du nombre d'arbres couvrant un rectangle

10

Ce blog parle de générer des "petits labyrinthes sinueux" à l'aide d'un ordinateur et de les énumérer. L'énumération peut être effectuée en utilisant l'algorithme de Wilson pour obtenir l' UST , mais je ne me souviens pas de la formule du nombre.

http://strangelyconsistent.org/blog/youre-in-a-space-of-twisty-little-mazes-all-alike

En principe, le théorème de l'arbre matriciel indique que le nombre d'arbres couvrant un graphe est égal au déterminant de la matrice laplacienne du graphe. Soit le graphe et la matrice d'adjacence, la matrice des degrés, alors avec les valeurs propres , puis: $G= (E,V)$ $A$ $D$ $\Delta = D - A$ $\lambda$

k (G) = \frac{1}{n} \prod_{k = 1}^{n - 1} λ_{k}

$k(G) = \frac{1}{n} \prod_{k=1}^{n-1} \lambda_k$

Dans le cas d'un rectangle et les valeurs propres devraient prendre une forme particulièrement simple, que je ne trouve pas. $m \times n$ $A$

Quelle est la formule exacte (et asymptotique) pour le nombre d'arbres couvrant un rectangle ? $m \times n$

entrez la description de l'image ici

Voici un joli exemple de l'algorithme de Wilson en action.

graph-theory randomized-algorithms matrices tree John mangual
la source

2

Encyclopédie en ligne des séquences entières Les formules exactes ne semblent pas faciles à calculer.

Peter Shor

@PeterShor OEIS cite: Germain Kreweras, Complexite et circuits Euleriens dans les sommes tensorielles de graphes , J. Combin. Theory, B 24 (1978), 202-212. Il est les mêmes objets que nous non?

john mangual

Ils couvrent de nombreux objets différents, y compris le quadrillage planaire , qui est la grille .

m \times n

$m \times n$

Peter Shor

9

Selon https://www.cse.ust.hk/~golin/pubs/ANALCO_05.pdf , aucune formule sous forme fermée n'est connue.

Selon http://arxiv.org/pdf/cond-mat/0004341v1.pdf, le nombre est asymptotique (pour et deux grands) à où mais je suis Je ne sais pas s'il s'agit d'une limite rigoureuse ou du résultat d'un raisonnement heuristique basé sur la physique. Le même article donne également des formules asymptotiques de type similaire lorsque est fixé à une petite constante et est grand. $n$ $m$

\exp (z_{s q} m n)

$\exp (z_{\mathrm{sq}}mn)$

z_{s q} = \frac{4}{π} \sum_{i = 0}^{\infty} \frac{(- 1)^{i}}{(2 i + 1)^{2}} \approx 1.16624

$z_{\mathrm{sq}}=\frac{4}{\pi}\sum_{i=0}^\infty\frac{(-1)^i}{(2i+1)^2}\approx 1.16624$

m

$m$

n

$n$

David Eppstein
la source

Il existe des formules asymptotiques précises pour le nombre d'arbres couvrant dans un rectangle (et des séquences plus générales de sous-graphiques décrits par des polygones rectilignes) données ici: arxiv.org/pdf/math-ph/0011042.pdf (en particulier, corollaire 2 et proposition 13 )

Lorenzo Najt

Encore une fois, c'est dans un référentiel de physique mathématique. Prouvent-ils rigoureusement les formules asymptotiques ou utilisent-ils simplement un raisonnement ansatz de type physique?

David Eppstein

Il a été publié dans Acta Math 185 (2000) no. 2, 239-286.

Lorenzo Najt

0

Les valeurs propres du graphique rectangle m par n peuvent être utilisées pour obtenir une expression du nombre de correspondances parfaites dans de tels graphiques. Voir l'article Wikipedia sur les carrelages domino .

Tyson Williams
la source

C'est intéressant, mais pouvez-vous expliquer comment cela répond à la question? Existe-t-il une sorte de mappage entre des correspondances parfaites et des arbres couvrant dans ce cas particulier?

Saeed

Formule exacte du nombre d'arbres couvrant un rectangle

Réponses: