Genaue Formel für die Anzahl der Spannbäume eines Rechtecks

10

In diesem Blog geht es darum, mit einem Computer "verdrehte kleine Labyrinthe" zu erzeugen und diese aufzuzählen. Die Aufzählung kann mit Wilsons Algorithmus durchgeführt werden , um die UST zu erhalten , aber ich erinnere mich nicht an die Formel für wie viele dort.

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

Im Prinzip besagt der Matrixbaumsatz , dass die Anzahl der Spannbäume eines Graphen gleich der Determinante der Laplace-Matrix des Graphen ist. Sei der Graph und die Adjazenzmatrix, die Gradmatrix, dann mit Eigenwerten , dann: $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$

Im Fall eines Rechtecks sollten sowohl als auch die Eigenwerte eine besonders einfache Form annehmen, die ich nicht finden kann. $m \times n$ $A$

Was ist die genaue Formel (und Asymptotik) für die Anzahl der überspannenden Bäume eines Rechtecks? $m \times n$

Geben Sie hier die Bildbeschreibung ein

Hier ist ein hübsches Beispiel für Wilsons Algorithmus in Aktion.

graph-theory randomized-algorithms matrices tree John Mangual
quelle

2

Online-Enzyklopädie ganzzahliger Sequenzen Die genauen Formeln lassen sich nicht leicht ableiten.

Peter Shor

@PeterShor OEIS zitiert: Germain Kreweras, Complexite et Circuits Euleriens dans les sommes tensorielles de graphes , J. Combin. Theory, B 24 (1978), 202 & ndash; 212. Er ist das gleiche Objekt wie wir, oder?

John Mangual

Sie decken viele verschiedene Objekte ab, einschließlich des Quadrillage Planaire , dem Raster.

m \times n

$m \times n$

Peter Shor

9

Laut https://www.cse.ust.hk/~golin/pubs/ANALCO_05.pdf ist keine geschlossene Formel bekannt.

Laut http://arxiv.org/pdf/cond-mat/0004341v1.pdf ist die Zahl asymptotisch (für und beide groß) bis wobei aber ich bin Ich bin mir nicht sicher, ob dies eine strenge Grenze ist oder das Ergebnis heuristischer physikalischer Überlegungen. Das gleiche Papier gibt auch asymptotische Formeln ähnlichen Typs an, wenn auf eine kleine Konstante festgelegt ist und groß ist. $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
quelle

Es gibt genaue asymptotische Formeln für die Anzahl der Spannbäume in einem Rechteck (und allgemeinere Sequenzen von Teilgraphen, die durch geradlinige Polygone beschrieben werden), die hier angegeben sind: arxiv.org/pdf/math-ph/0011042.pdf (speziell Korollar 2 und Satz 13) )

Lorenzo Najt

Auch das ist in einem Repository für mathematische Physik. Beweisen sie die asymptotischen Formeln rigoros oder verwenden sie nur physikalisch-artiges Ansatz-Denken?

David Eppstein

Es wurde in Acta Math 185 (2000) No. 2, 239 & ndash; 286.

Lorenzo Najt

0

Die Eigenwerte des m-mal-n-Rechteckgraphen können verwendet werden, um einen Ausdruck für die Anzahl perfekter Übereinstimmungen in solchen Graphen zu erhalten. Siehe den Wikipedia-Artikel über Domino-Fliesen .

Tyson Williams
quelle

Das ist interessant, aber können Sie näher erläutern, wie dies die Frage beantwortet? Gibt es in diesem speziellen Fall eine Zuordnung zwischen perfekten Übereinstimmungen und überspannenden Bäumen?

Saeed

Genaue Formel für die Anzahl der Spannbäume eines Rechtecks

Antworten: