Hitung jumlah pohon yang merentang dengan cepat

$t(G)$ $G$ $n$ $t(G)$ $O(n^3)$ $\frac{1}{n^2} \det(J + Q)$ $Q$ $G$ $J$ $1$

Saya ingin tahu apakah ada cara untuk menghitung lebih cepat. (Ya, ada lebih cepat daripada algoritma untuk komputasi penentu tetapi saya tertarik pada beberapa pendekatan baru.) $t(G)$ $O(n^3)$

Ini juga tertarik untuk mempertimbangkan kelompok grafik khusus (planar, mungkin?).

Misalnya, untuk grafik sirkuler, dapat dihitung dalam operasi aritmatika melalui identitas , di mana adalah nilai eigen bukan nol dari matriks Laplacian dari , yang dapat dihitung dengan cepat untuk grafik sirkuler. (Mewakili baris pertama sebagai polinomial dan kemudian menghitungnya pada akar ke- persatuan - langkah ini menggunakan transformasi Discrete Fourier dan dapat dilakukan dalam operasi aritmatika .) $t(G)$ $O(n \lg n)$ $t(G) = \frac{1}{n} \lambda_1 \dotsm \lambda_{n-1}$ $\lambda_i$ $G$ $n$ $O(n \lg n)$

Terima kasih banyak!

graph-theory graph-algorithms counting-complexity spectral-graph-theory Finsky
sumber

Sergey, saya mencoba mengedit pertanyaan Anda untuk meningkatkan kejelasan. Periksa apakah saya memahami pertanyaan Anda dengan benar dan tidak menemukan kesalahan.

Tyson Williams

Berikut adalah salah satu contoh yang lebih umum dari keluarga grafik di mana menemukan kompleksitas dapat dilakukan lebih cepat: grafik Cayley untuk kelompok abelian dengan generator set , sehingga . Kita tahu bahwa nilai eigen dari matriks tersebut adalah , di mana adalah karakter yang berbeda dari grup. Semua karakter mudah ditemukan (untuk informasi lebih lanjut lihat makalah ini ) menghitung karakter-karakter tersebut adalah

dimensi FFT (lihat Cormen et al bab tentang FFT), yaitu dapat dilakukan dalam

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

Untuk informasi lebih lanjut tentang grafik Cayley, lihat buku ini .

Finsky

Melakukan aljabar Linear dengan Laplacian daripada matriks umum seringkali lebih mudah. Saya ingin tahu apakah ini relevan.

Gil Kalai

Bisakah Anda, lebih spesifik, jika mungkin, memberikan beberapa contoh, bahkan jika itu tidak terkait langsung dengan topik dalam diskusi. Terima kasih.

Finsky

Hitung jumlah pohon yang merentang dengan cepat

Jawaban: