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!

graph-theory graph-algorithms counting-complexity spectral-graph-theory 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

Szybko policz liczbę drzew spinających

Odpowiedzi: