Amplitudo Grafik Kubik Acak

Pertimbangkan grafik kubik acak yang terhubung darisimpul, diambil dari -reg (seperti yang didefinisikan di sini , yaitu adalah genap dan setiap dua grafik memiliki probabilitas yang sama). $G=(V,E)$ $n =|V|$ $G(n, 3$ $)$ $3n$

Tentu saja ada mungkin Searches Breadth First, satu untuk setiap memulai simpul . Sebuah Breadth First Search mulai simpul wakilnya tingkat untuk setiap node , di mana adalah jarak antara dan di . $n$ $s \in V$ $B_G$ $s \in V$ $d(s, v)$ $v \in V$ $d(s, v)$ $s$ $v$ $G$

Mari kita katakan bahwa Pencarian Pertama juga memberikan level untuk setiap sisi . $B_G$

L (s, {u, v}) = max {d (s, u), d (s, v)}

$L(s, \{u,v\}) = \max\{ d(s,u), d(s,v) \}$

e = {u, v} \in E

$e=\{u,v\} \in E$

Diberikan Pencarian Pertama $B_G$ , biarkan $\alpha(B_G,i)$ menjadi jumlah tepi yang telah ditetapkan level $i$ , dan biarkan $\alpha(B_G) = max_i\{\alpha(B_G,i)\}$ . Dengan kata lain $\alpha(B_G)$ adalah jumlah tepi level yang mengandung lebih banyak edge daripada level lainnya. Akhirnya, mari kita $\alpha(G)$ menjadi maksimal $\alpha(B_G)$ untuk salah satu $n$ Searches Breadth First of $G$ .

Mari kita sebut $\alpha(G)$ yang amplitudo dari $G$ .

Pertanyaan

Bagaimana nilai yang diharapkan dari $\alpha(G)$ tumbuh sebagai $n$ cenderung tak hingga? Ingatlah bahwa $G$ adalah kubik acak . Lebih tepatnya, apa yang ingin saya ketahui adalah apakah nilai yang diharapkan dari $\alpha(G)$ milik $o(n)$ .

Karena $n$ adalah genap, batasnya dianggap sehingga aku tidak peduli dengan aneh $n$ .

graph-theory co.combinatorics Giorgio Camerani
sumber

(1) Silakan tentukan dari distribusi probabilitas mana Anda menggambar grafik kubik Anda. (2) Apakah Anda tertarik pada ekspektasi sebagai fungsi dari , atau sesuatu yang lain? (3) Saya kira adalah genap (jika tidak, grafik kubik tidak ada). Jadi, saya kira batas tersebut dianggap sehingga Anda tidak peduli untuk aneh 's.

α (G)

$\alpha(G)$

n

$n$

n

$n$

n

$n$

Yoshio Okamoto

@YoshioOkamoto: (1) Dari -reg sebagaimana didefinisikan dalam stanford.edu/class/msande337/notes/… ( genap dan setiap dua grafik memiliki probabilitas yang sama). (2) Saya telah memperkaya pertanyaan untuk memperjelas hal ini. (3) Ya, adalah genap dan batasnya dipertimbangkan sehingga saya tidak peduli dengan aneh .

G (n, 3

$G(n, 3$

)

$)$

3 n

$3n$

n

$n$

n

$n$

Giorgio Camerani

@SureshVenkat: Terima kasih telah meningkatkan keterbacaan pertanyaan ;-)

Giorgio Camerani

Izinkan saya mengatakan bahwa ada kemungkinan besar bahwa ada hasil konsentrasi untuk pada grafik kubik acak, yang berarti bahwa nilai yang diharapkan, nilai probabilitas tinggi, dan sebagainya, semuanya sama. Kecuali OP menjelaskan, saya pikir jawaban untuk semua pertanyaan ini akan menjadi jawaban yang masuk akal untuk pertanyaan ini.

α (G)

$\alpha(G)$

Peter Shor

@WalterBishop: Biarkan saya bertanya satu pertanyaan lagi. Bagaimana Anda mendefinisikan jika terputus?

α (G)

$\alpha(G)$

G

$G$

Yoshio Okamoto

Jawaban:

Amplitudo untuk grafik expander. Grafik acak 3-reguler secara asimptotik hampir pasti merupakan grafik expander (lihat Wikipedia) , sehingga ekspektasi amplitudo akan menjadi , karena probabilitas bahwa itu bukan grafik ekspander menjadi saat pergi ke . $\alpha(n) = \Theta(n)$ $\Theta(n)$ $0$ $n$ $\infty$

Untuk grafik expander dengan parameter , untuk setiap set simpul dengan , ada tetangga dari himpunan. Sekarang, biarkan jumlah simpul pada level menjadi , dengan . Kami kemudian memiliki dari properti ekspansi yang selama tidak terlalu besar (yaitu, kami belum menyertakan setengah simpul) Sekarang, cari level yang berisi vertex . Ya, jadi dan $\beta$ $s$ $s \leq n/2$ $\beta s$ $j$ $\ell_j$ $\ell_0=1$ $j$

ℓ_{j} \geq β \sum_{i = 0}^{j - 1} ℓ_{i}

$\ell_j \geq \beta\, \sum_{i=0}^{j-1} \ell_{i}$

ℓ_{j}

$\ell_j$

\frac{n}{3}

$\frac{n}{3}$

\sum_{i = 0}^{j - 1} ℓ_{i} < n / 3

$\sum_{i=0}^{j-1} \ell_i < n/3$

\sum_{i = 0}^{j} ℓ_{i} \geq n / 3

$\sum_{i=0}^{j} \ell_i \geq n/3$ . Jika level ini besar, yaitu, , kita selesai. Jika tidak, level selanjutnya memiliki ukuran dan kita sudah selesai.

ℓ_{j} \geq n / 6

$\ell_j \geq n/6$

ℓ_{j + 1} \geq β \sum_{i = 0}^{j} ℓ_{i} \geq β \frac{n}{3},

$\ell_{j+1} \geq \beta \, \sum_{i=0}^{j} \ell_{i} \geq \beta \frac{n}{3},$

Sementara bukti ini melihat jumlah simpul dalam level daripada jumlah tepi (yang ditanyakan OP), selalu ada paling sedikit tepi yang ditambahkan pada langkah sebagai simpul pada level , karena setiap simpul harus dicapai sedikit banyak. $i$ $i$

Peter Shor
sumber

Terima kasih atas jawaban anda! Ini sangat mengejutkan (setidaknya bagi saya): bahkan jika jumlah total tepi adalah , dan jumlah level adalah , yang paling tingkat ramai masih tepi. Dengan demikian ujung-ujungnya tidak tersebar secara seragam di antara tingkat-tingkat: intuisi saya (empiris, salah) adalah bahwa, kecuali beberapa tingkat awal dan beberapa tingkat akhir, seharusnya ada tingkat pusat di mana ujung-ujungnya akan telah tersebar agak seragam.

m = 1.5 \cdot n \in Θ (n)

$m = 1.5 \cdot n \in \Theta(n)$

Ω (l o g (n))

$\Omega(log(n))$

Θ (n)

$\Theta(n)$

Ω (l o g (n))

$\Omega(log(n))$

Giorgio Camerani

dengan "empiris" yang Anda maksudkan Anda benar-benar menjalankan tes? adalah sekitar untuk grafik acak kubik, lihat ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/Bol88.pdf

β

$\beta$

0.1845

$0.1845$

didest

Ya saya menjalankan tes dari hingga dan mengukur kuantitas . Jika mendekati dengan meningkat, ini akan memberikan bukti empiris bahwa . Sekitar , adalah sekitar , sementara sekitar , adalah sekitar (tentu saja saya tidak pernah menganggap angka-angka ini sebagai bukti empiris, karena masih terlalu kecil untuk mewakili asimtotik). Namun ketika saya mengatakan "intuisi empiris"

n = 100

$n = 100$

n = 150000

$n = 150000$

k = \frac{α (G)}{m}

$k = \frac{\alpha(G)}{m}$

k

$k$

0

$0$

n

$n$

α (G) \in o (n)

$\alpha(G) \in o(n)$

n = 100

$n=100$

k

$k$

0.3

$0.3$

n = 150000

$n=150000$

k

$k$

0.26

$0.26$

n = 150000

$n = 150000$

Giorgio Camerani

... Maksud saya sebenarnya (salah) perasaan daripada hasil tes: Saya agak merasa bahwa BFS itu harus memiliki bentuk "sosis" (yaitu kecil di ekstrem, dan detak konstan di tengah). "Mereka harus seperti itu", pikirku. Bukti di atas menunjukkan betapa salahnya intuisi saya. Meskipun demikian, saya masih terkejut: edge, level, tetapi bukan edge pada setiap level.

Θ (n)

$\Theta(n)$

Ω (l o g (n))

$\Omega(log(n))$

O (\frac{n}{l o g (n)})

$O(\frac{n}{log(n)})$

Giorgio Camerani

Jawaban Peter Shor benar-benar baik, tetapi ada cara lain untuk menjawab ini: membuktikan bahwa treewidth dibatasi oleh dua kali amplitudo (versi vertex). Karena kita tahu bahwa ekspander 3-reguler memiliki treewidth linier, kita selesai.

Lihat konstruksi dekomposisi pohon yang diberi pohon BFS, slide 15 dari presentasi ini: http://www.liafa.jussieu.fr/~pierref/ALADDIN/MEETING2/soto.pdf

Sangat mudah untuk melihat bahwa ukuran setiap tas dibatasi oleh dua kali tingkat terluas.

Didest
sumber

Terima kasih atas jawaban Anda, presentasi itu sangat membantu.

Giorgio Camerani