Rumus yang tepat untuk jumlah pohon spanning dari persegi panjang

10

Blog ini berbicara tentang menghasilkan "labirin kecil berliku" menggunakan komputer dan menghitungnya. Pencacahan dapat dilakukan dengan menggunakan algoritma Wilson untuk mendapatkan UST , tapi saya tidak ingat rumus untuk berapa banyak.

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

Pada prinsipnya Teorema Pohon Matriks menyatakan jumlah pohon spanning dari suatu grafik adalah sama dengan determinan dari matriks Laplacian dari grafik. Misalkan menjadi grafik dan menjadi matriks kedekatan, menjadi matriks derajat, lalu dengan nilai eigen , lalu: $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$

Dalam kasus rectangle, baik nilai dan eigen harus mengambil bentuk yang sangat sederhana, yang tidak dapat saya temukan. $m \times n$ $A$

Apa rumus yang tepat (dan asimptotik) untuk # spanning tree dari rectangle? $m \times n$

masukkan deskripsi gambar di sini

Berikut adalah contoh yang bagus dari algoritma Wilson dalam aksi.

graph-theory randomized-algorithms matrices tree John Mangual
sumber

2

Ensiklopedia Online Urutan Bilangan Bulat Rumus yang tepat tidak terlihat mudah untuk diturunkan.

Peter Shor

@PeterShor OEIS mengutip: Germain Kreweras, Complexite et circuits Euleriens dans les sommes tensorielles de graphes , J. Combin. Teori, B 24 (1978), 202-212. Dia benda yang sama seperti kita kan?

john mangual

Mereka menutupi banyak objek yang berbeda, termasuk alun-alun segi empat , yang merupakan grid .

m \times n

$m \times n$

Peter Shor

9

Menurut https://www.cse.ust.hk/~golin/pubs/ANALCO_05.pdf tidak ada rumus bentuk tertutup yang diketahui.

Menurut http://arxiv.org/pdf/cond-mat/0004341v1.pdf angkanya asimptotik (untuk dan keduanya besar) ke mana tapi saya tidak yakin apakah ini adalah ikatan ketat atau hasil dari penalaran berbasis fisika heuristik. Kertas yang sama juga memberikan formula asimptotik dari jenis yang sama ketika difiksasi ke konstanta kecil dan besar. $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
sumber

Ada formula asimtotik yang tepat untuk jumlah pohon spanning dalam persegi panjang (dan urutan subgraph yang lebih umum dijelaskan oleh poligon bujursangkar) yang diberikan di sini: arxiv.org/pdf/math-ph/0011042.pdf (khusus, wajar 2 dan proposisi 13 )

Lorenzo Najt

Sekali lagi, itu ada dalam repositori fisika matematika. Apakah mereka membuktikan formula asimtotik dengan ketat atau mereka hanya menggunakan penalaran ansatz seperti fisika?

David Eppstein

Itu diterbitkan dalam Acta Math 185 (2000) no. 2, 239-286.

Lorenzo Najt

0

Nilai eigen dari grafik persegi panjang m-by-n dapat digunakan untuk mendapatkan ekspresi untuk jumlah kecocokan sempurna dalam grafik tersebut. Lihat artikel Wikipedia tentang domino tilings .

Tyson Williams
sumber

Ini menarik, tetapi bisakah Anda menguraikan bagaimana ini menjawab pertanyaan? Apakah ada semacam pemetaan antara pencocokan sempurna dan spanning tree dalam kasus khusus ini?

Saeed

Rumus yang tepat untuk jumlah pohon spanning dari persegi panjang

Jawaban: