Dokładna formuła dla liczby drzew rozpinających prostokąta

10

Ten blog mówi o generowaniu „krętych małych labiryntów” za pomocą komputera i ich liczeniu. Wyliczenia można dokonać za pomocą algorytmu Wilsona, aby uzyskać UST , ale nie pamiętam wzoru na ich liczbę.

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

Zasadniczo Twierdzenie o Drzewie Matrycowym stwierdza, że liczba drzew spinających na wykresie jest równa wyznacznikowi macierzy Laplaciana na wykresie. Niech będzie wykresem, a będzie macierzą przylegania, będzie macierzą stopni, następnie z wartościami własnymi , a następnie: $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$

W przypadku prostokąta zarówno jak i wartości własne powinny przyjąć szczególnie prostą formę, której nie mogę znaleźć. $m \times n$ $A$

Jaka jest dokładna formuła (i asymptotyka) dla liczby drzew obejmujących prostokąta ? $m \times n$

wprowadź opis zdjęcia tutaj

Oto ładny przykład działania algorytmu Wilsona.

graph-theory randomized-algorithms matrices tree John Mangual
źródło

2

Encyklopedia online sekwencji całkowitych Dokładne formuły nie wydają się łatwe do uzyskania.

Peter Shor,

@PeterShor OEIS cytuje: Germain Kreweras, Complexite et circuits Euleriens dans les sommes tensorielles de graphes , J. Combin. Theory, B 24 (1978), 202-212. On jest tym samym przedmiotem co my, prawda?

John Mangual

Obejmują one wiele różnych obiektów, w tym płaszczyznę kwadratu , czyli siatkę .

m \times n

$m \times n$

Peter Shor,

9

Według https://www.cse.ust.hk/~golin/pubs/ANALCO_05.pdf nie jest znana żadna formuła zamknięta.

$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
źródło

Istnieją dokładne asymptotyczne formuły dla liczby drzew spinających w prostokącie (i bardziej ogólne sekwencje podgrafów opisanych prostokątami wielokątnymi) podane tutaj: arxiv.org/pdf/math-ph/0011042.pdf (konkretnie, następstwo 2 i propozycja 13 )

Lorenzo Najt

Znów jest to w repozytorium fizyki matematycznej. Czy rygorystycznie udowadniają asymptotyczne formuły, czy po prostu wykorzystują logiczne rozumowanie ansatz?

David Eppstein

Został opublikowany w Acta Math 185 (2000) nr. 2, 239–286.

Lorenzo Najt

0

Wartości własne wykresu prostokątnego m-by-n można wykorzystać do uzyskania wyrażenia liczby idealnych dopasowań na takich wykresach. Zobacz artykuł w Wikipedii na temat domina .

Tyson Williams
źródło

To interesujące, ale czy możesz wyjaśnić, w jaki sposób rozwiązuje to pytanie? Czy w tym konkretnym przypadku istnieje jakieś odwzorowanie między idealnymi dopasowaniami a drzewami łączącymi?

Saeed,

Dokładna formuła dla liczby drzew rozpinających prostokąta

Odpowiedzi: