Jalan acak dan rata-rata waktu tempuh dalam grafik sederhana yang tidak diarahkan

Misalkan menjadi grafik sederhana yang tidak diarahkan pada n simpul dan tepi m .$G=(V,E)$$n$$m$

Saya mencoba untuk menentukan waktu menjalankan diharapkan dari algoritma Wilson untuk menghasilkan pohon rentang acak . Di sana, itu ditunjukkan menjadi O ( τ ) , di mana τ adalah waktu memukul rata - rata : τ = ∑ v ∈ V π ( v ) ⋅ H ( u , v ) , di mana:$G$$O(\tau)$$\tau$

• adalahdistribusi stasioner π ( v ) = d ( v $\pi$ ,$\pi(v)=\frac{d(v)}{2m}$
• adalah titik sembarang, dan$u$
• adalahwaktu memukul(waktuaksesAKA), yaitu, jumlah langkah yang diharapkan sebelum titik v dikunjungi, mulai dari titik u .$H(u,v)$$v$$u$

Apa batas atas umum untuk waktu memukul rata-rata? Dan apa grafik kasus terburuk yang memaksimalkan waktu memukul berarti?$G$

Untuk memperjelas pertanyaan saya, saya tidak memerlukan perhitungan atau bukti terperinci (meskipun mungkin bermanfaat bagi orang lain yang menghadapi pertanyaan ini di masa mendatang). Bagi saya pribadi, kutipan akan cukup.

$\Theta(n)$$\Theta(n \log n)$

$\Theta(n^2)$$\Theta(n^3)$$O(n^2)$$O(n^3)$

Ada dua implementasi algoritma Wilson yang tersedia untuk umum yang saya ketahui. Satu di Boost Graph Library , sedangkan yang kedua di graph-tool . Dokumentasi yang pertama tidak menyebutkan waktu berjalan, sedangkan yang terakhir menyatakan:

$O(n \log n)$

Yang tidak menjawab pertanyaan itu, dan sebenarnya tampaknya tidak konsisten dengan makalah Wilson. Tetapi saya melaporkan hal ini untuk berjaga-jaga, untuk menghemat waktu siapa pun dengan ide yang sama untuk berkonsultasi dengan dokumentasi implementasi.

$\Omega(n^3)$$\frac{1}{n}$$O(n^2)$

$4n^3/27$$\frac{2}{3} n$

Saya telah memutuskan untuk bertanya kepada David Wilson sendiri, segera setelah itu mendapat balasan:

$n$$\Theta(n^3)$$n/3$$n/3$$H(x,y)$$x$$y$$H(x,y)$$x$$y$$x$

Bahkan ada bukti dari fakta ini dalam buku di atas, yang berbunyi seperti ini:

$n=2n_1+n_2$$n_1$$v_l \neq v_L$$v_R \neq v_r$$v_L - w_1 - \cdots w_{n_2} - v_R$

$n_1$$v_L$$\frac{1}{n_1}$$w_1$$n_1^2$$w_1$$w_1$$\frac{1}{n_2}$$n_1^2 n_2$

$n_1 = n_2 = n/3$$O(n^3)$

Harus diakui, saya tersesat pada titik yang mereka nyatakan:

$w_1$$\frac{1}{n_2}$

$\frac{(n+1)^3}{54}$

Namun, komentar tentang bukti informal masih diterima.

Dalam sebuah makalah baru-baru ini , kami menemukan batas atas mn (tidak ada O besar) pada jumlah yang diharapkan dari "siklus muncul" oleh algoritma Wilson dan itu mendekati konstanta. Itu tidak secara langsung menjawab pertanyaan waktu berjalan algoritma Wilson sebagai ukuran rata-rata siklus muncul tampaknya tidak jelas. Di sisi lain, saya tidak memiliki "reputasi" yang cukup untuk memberikan komentar ...