Точная формула для количества остовных деревьев прямоугольника

10

Этот блог рассказывает о создании "извилистых маленьких лабиринтов" с помощью компьютера, перечисляя их. Перечисление может быть выполнено с использованием алгоритма Уилсона для получения UST , но я не помню формулы для того, сколько их там.

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

В принципе теорема о матричном дереве утверждает, что число остовных деревьев графа равно определителю матрицы Лапласа графа. Пусть - граф, - матрица смежности, - матрица степеней, тогда с собственными значениями , тогда: $G= (E,V)$ $A$ $D$ $\Delta = D - A$ $\lambda$

К (г) знак равно \frac{1}{N} Π_{К знак равно 1}^{N - 1} λ_{К}

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

В случае $m \times n$ прямоугольника и $A$ и собственные значения должны принимать особенно простую форму, которую я не могу найти.

Какова точная формула (и асимптотика) для числа связующих деревьев прямоугольника $m \times n$ ?

введите описание изображения здесь

Вот прекрасный пример алгоритма Уилсона в действии.

graph-theory randomized-algorithms matrices tree Джон Мангуаль
источник

2

Онлайн-энциклопедия целочисленных последовательностей Точные формулы не так просто вывести.

Питер Шор

@PeterShor OEIS цитирует: Жермен Креверас, Complexite и схемы Euleriens dans les sommes tenorielles de graphes , J. Combin. Теория, B 24 (1978), 202-212. Он такой же объект, как и мы, верно?

Джон Мангал

m \times n

$m \times n$

9

Согласно https://www.cse.ust.hk/~golin/pubs/ANALCO_05.pdf не существует известной формулы в закрытой форме.

$n$ $m$

ехр (Z_{s Q} м N)

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

Z_{s Q} знак равно \frac{4}{π} Σ_{я знак равно 0}^{\infty} \frac{(- 1)^{я}}{(2 я + 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$

Дэвид Эппштейн
источник

Здесь приведены точные асимптотические формулы для числа остовных деревьев в прямоугольнике (и более общие последовательности подграфов, описываемых прямолинейными многоугольниками): arxiv.org/pdf/math-ph/0011042.pdf (в частности, следствие 2 и предложение 13 )

Лоренцо Найт

Опять же, это в хранилище математической физики. Строго ли они доказывают асимптотические формулы или используют физические рассуждения анзаца?

Дэвид Эппштейн

Он был опубликован в Acta Math 185 (2000) №. 2, 239-286.

Лоренцо Найт

0

Собственные значения графа m-by-n можно использовать для получения выражения для числа совершенных совпадений в таких графах. Смотрите статью в Википедии о домино .

Тайсон Уильямс
источник

Это интересно, но можете ли вы уточнить, как это решает вопрос? Есть ли какое-либо отображение между идеальными совпадениями и связующими деревьями в данном конкретном случае?

Саид

Точная формула для количества остовных деревьев прямоугольника

Ответы: