Sampul Waktu Grafik yang Diarahkan

Diberikan jalan acak pada grafik, waktu sampul adalah yang pertama (jumlah langkah yang diharapkan) yang setiap titik telah tekan (tertutup) oleh jalan. Untuk grafik yang tidak diarahkan yang terhubung, waktu tutup diketahui dibatasi oleh . Ada digraf yang sangat terhubung dengan eksponensial waktu sampul dalam n . Contoh dari ini, adalah digraph yang terdiri dari siklus diarahkan ( 1 , 2 , . . . , N , 1 ) , dan tepi ( j , 1 ) , dari simpul j $O(n^3)$$n$$(1, 2, ..., n, 1)$$(j, 1)$ . Mulai dari titik 1 , waktu yang diharapkan untuk jalan acak untuk mencapai titik n adalah Ω ( 2 n ) . Saya punya dua pertanyaan:$j = 2, ..., n − 1$$1$$n$$\Omega(2^n)$

1) Apa saja kelas yang diketahui dari grafik berarah dengan waktu tutup polinomial? Kelas-kelas ini dapat dikarakterisasi dengan sifat-sifat teori-graf (atau) oleh sifat-sifat dari matriks kedekatan yang sesuai (katakanlah ). Sebagai contoh, jika A adalah simetris maka waktu tutupan grafik adalah polinomial.$A$$A$

2) Apakah ada contoh yang lebih sederhana (seperti contoh siklus yang disebutkan di atas) di mana waktu tutupan adalah eksponensial?

3) Apakah ada contoh dengan waktu tutup kuasi polinomial?

Saya akan menghargai petunjuk apa pun untuk survei / buku bagus tentang topik ini.

Jelas waktu pencampuran polinomial menyiratkan waktu penutup polinomial. (Ya, tidak secara umum. Kami membutuhkan probabilitas stasioner setidaknya di setiap titik.) Jadi, periksa makalah Mihail, Konduktansi dan konvergensi rantai Markov - perlakuan kombinasi ekspander$1/poly(n)$ yang membuktikan pencampuran cepat reguler. grafik diarahkan dan rantai Markov umum berdasarkan konduktansi.

Juga lihat kertas Pseudorandom berjalan pada digraf reguler dan masalah RL vs L oleh Reingold, Trevisan, dan Vadhan. Mengikuti pekerjaan Mihail. Mereka mendefinisikan parameter yang setara dengan λ 2 ( G ) , nilai eigen terbesar kedua dalam nilai absolut, ketika grafik G dapat dibalik waktu, dan tetap terdefinisi dengan baik untuk rantai Markov umum. Parameter ini kemudian digunakan untuk terikat waktu pencampuran G .$\lambda_\pi(G)$$\lambda_2(G)$$G$$G$

Colin Cooper dan Alan Frieze memiliki serangkaian hasil dalam konteks digraf acak yang mungkin menarik. Mereka mempelajari sifat-sifat jalan acak sederhana pada grafik berarah acak ketika n p = d log n , d > 1 . Mereka telah membuktikan bahwa:$D_{n,p}$$np=d \log n, d>1$

• Untuk , whp waktu tutup D n , p asimptotik ke d log ( d / ( d - 1 ) ) n log n . Jika d = d ( n ) → ∞ dengan n , waktu tutupan asimptotik ke n log n .$d > 1$$D_{n,p}$$d \log (d/(d-1)) n \log n$$d=d(n) \rightarrow \infty$$n$$n \log n$

• Jika dan d > 1 maka whp C G n , p ∼ d log ( d / ( d - 1 ) ) n log n .$p = d \log n/n$$d>1$$C_{G_{n,p}} \sim d \log (d/(d-1)) n \log n$

• Biarkan dan biarkan x menunjukkan solusi dalam ( 0 , 1 ) dari x = 1 - e - d x . Misalkan X g adalah komponen raksasa G n , p , p = d / n . Kemudian whp C X g ∼ d x ( 2 - x $d>1$$x$$(0,1)$$x = 1-e^{-dx}$$X_g$$G_{n,p},p=d/n$.$C_{X_g} \sim \dfrac{dx(2-x)}{4(dx-\log d)} n (\log n)^2$

• Jika adalah konstanta dan G n , r menunjukkan grafik r- reguler acak pada set simpul [ n ] dengan r ≥ 3 maka whp C G n , r ∼ r - $r \geq 3$$G_{n,r}$$r$$[n]$$r \geq 3$.$C_{G_{n,r}} \sim \dfrac{r-1}{r-2} n \log n$

• Jika adalah konstan dan G m menunjukkan grafik lampiran preferensial rata-rata tingkat 2 m maka whp C G m ~ 2 $m \geq 2$$G_m$$2m$.$C_{G_m} \sim \dfrac{2m}{m-1} n \log n$

• Jika dan G r , k adalah grafik geometri acak dalam R k dari ukuran bola r sedemikian rupa sehingga derajat yang diharapkan dari suatu simpul adalah asimptotik terhadap d log n , maka whp C G r , k ∼ d log ( $k \geq 3$$G_{r,k}$$\mathcal{R}^k$$r$$d \log n$.$C_{G_{r,k}} \sim d \log ( \dfrac{d}{d-1}) n \log n$

Lihat Cooper, C., & Frieze, A. Distribusi stasioner dan waktu penutup jalan acak pada digraf acak. Jurnal Teori Kombinatorial, Seri B. (2011).