Szybko policz liczbę drzew spinających

Niech oznacza liczbę drzew opinających na wykresie z wierzchołkami. Istnieje algorytm obliczający w operacjach arytmetycznych . Ten algorytm oblicza , gdzie jest Laplacianem z a jest macierzą składającą się wyłącznie z 's. Aby uzyskać więcej informacji na temat tego algorytmu, zobacz Biggs - teoria grafów algebraicznych lub to pytanie Math SE . $t(G)$ $G$ $n$ $t(G)$ $O(n^3)$ $\frac{1}{n^2} \det(J + Q)$ $Q$ $G$ $J$ $1$

Zastanawiam się, czy jest jakiś sposób na szybsze obliczenie $t(G)$ . (Tak, istnieje szybsze niż $O(n^3)$ algorytmy obliczania wyznacznika, ale interesuje mnie nowe podejście.)

Jest również zainteresowany rozważeniem specjalnych rodzin grafów (może planarnych?).

Na przykład w przypadku grafów cyrkulacyjnych $t(G)$ można obliczyć w operacjach arytmetycznych $O(n \lg n)$ za pomocą tożsamości $t(G) = \frac{1}{n} \lambda_1 \dotsm \lambda_{n-1}$ , gdzie $\lambda_i$ są niezerowymi wartościami własnymi macierzy Laplaciana $G$ , którą można szybko obliczyć dla grafów krążących. (Reprezentuj pierwszy wiersz jako wielomian, a następnie oblicz go na $n$ pierwiastkach jedności - ten krok wykorzystuje dyskretną transformację Fouriera i może być wykonany w operacjach arytmetycznych $O(n \lg n)$ .)

Dziękuję Ci bardzo!

— Fiński
źródło

Siergiej, próbowałem edytować twoje pytanie, aby poprawić jasność. Sprawdź, czy poprawnie zrozumiałem twoje pytanie i nie wprowadziłem żadnych błędów.

— Tyson Williams

Oto jeden ogólny przykład rodzin wykres, na którym znalezienie złożoność może być wykonane szybciej: wykresy Cayley abelowe dla grup z wytwórcami zestaw , tak, że . Wiemy, że wartości własne takiej macierzy to , gdzie są różnymi znakami grupy. Wszystkie znaki są łatwe do znalezienia (więcej informacji można znaleźć w tym artykule ), ponieważ obliczenie tych znaków jest wymiarowe FFT (patrz Cormen i in. Rozdział o FFT), tzn. Można to zrobić w .

G

$G$

S

$S$

S^{- 1} = S

$S^{-1} = S$

\sum_{h \in S} χ (h)

$\sum_{h \in S} \chi (h)$

χ

$\chi$

n

$n$

O (n \lg n)

$O(n \lg n)$

— Finsky

Więcej informacji na temat wykresów Cayleya można znaleźć w tej książce .

— Finsky,

Często łatwiej jest wykonywać algebrę liniową za pomocą Laplaciana zamiast ogólnej macierzy. Zastanawiam się, czy to może być istotne.

— Gil Kalai

Czy mógłbyś, bardziej szczegółowo, podać, jeśli to możliwe, przykłady, nawet jeśli nie jest to bezpośrednio związane z omawianym tematem. Dziękuję Ci.

— Finsky

Jest znane , że do w ograniczonym treewidth, w TUTTE wielomianu może być oceniany w każdym przy użyciu operacji arytmetycznych. Jeśli jest podłączony, to . $G$ $T(G;x,y)$ $(x,y)$ $O(n)$ $G$ $t(G)=T(G;1,1)$

— Radu Curticapean
źródło