Algoritma untuk menemukan diameter pohon menggunakan BFS / DFS. Mengapa ini berhasil?

Tautan ini menyediakan algoritme untuk menemukan diameter pohon tak berarah menggunakan BFS / DFS . Meringkas:

Jalankan BFS pada sembarang simpul dalam grafik, mengingat simpul yang Anda temukan terakhir. Jalankan BFS dari Anda mengingat simpul v yang ditemukan terakhir. d (u, v) adalah diameter pohon.

Mengapa ini berhasil?

Halaman 2 dari ini memberikan alasan, tetapi membingungkan. Saya mengutip bagian awal dari bukti:

Jalankan BFS pada sembarang simpul dalam grafik, mengingat simpul yang Anda temukan terakhir. Jalankan BFS dari Anda mengingat simpul v yang ditemukan terakhir. d (u, v) adalah diameter pohon.

Kebenaran: Biarkan a dan b berupa dua simpul sehingga d (a, b) adalah diameter pohon. Ada jalur unik dari a ke b. Biarkan t menjadi simpul pertama di jalur itu yang ditemukan oleh BFS. Jika jalur $p_1$ dari s ke u dan $p_2$ dari a ke b tidak berbagi tepi, maka jalur dari t ke u termasuk s. Begitu

$d(t,u) \ge d(s,u)$

$d(t,u) \ge d(s,a)$

.... (lebih banyak ketidaksetaraan mengikuti ..)

Ketidaksamaan tidak masuk akal bagi saya.

Semua bagian dari pembuktian klaim bergantung pada 2 sifat penting pohon dengan tepi yang tidak terarah:

• 1-connectedness (mis. Antara 2 node di pohon ada persis satu jalur)
• simpul apa pun dapat berfungsi sebagai akar dari pohon.

Pilih simpul pohon sembarang . Asumsikan u , v ∈ V ( G ) adalah simpul dengan d ( u , v ) = d i a m ( G ) . Asumsikan lebih lanjut bahwa algoritma menemukan sebuah simpul x mulai dari pertama, beberapa simpul y mulai dari x berikutnya. wlog d ( s , u ) ≥ d ( s , v ) . perhatikan itu$s$$u, v \in V(G)$$d(u,v) = diam(G)$$x$$s$$y$$x$$d(s,u) \geq d(s,v)$ harus dimiliki, kecuali tahap pertama algoritma tidak akan berakhir pada x . Kita akan melihat bahwa d ( x , y ) = d ( u , v ) .$d(s,x) \geq d(s,y)$$x$$d(x,y) = d(u,v)$

Konfigurasi yang paling umum dari semua node yang terlibat dapat dilihat pada pseudo-grafis berikut (mungkin atau s = z x y atau keduanya):$s = z_{uv}$$s = z_{xy}$

(u)                                            (x)
  \                                            /
   \                                          /
    \                                        /
     ( z_uv )---------( s )----------( z_xy )
    /                                        \
   /                                          \
  /                                            \
(v)                                            (y)

kami tahu bahwa:

1. . jika tidak d ( u , v ) < d i a m ( G ) yang bertentangan dengan asumsi.$d(z_{uv},y) \leq d(z_{uv},v)$$d(u,v) < diam(G)$
2. . jika tidak d ( u , v ) < d i a m ( G ) yang bertentangan dengan asumsi.$d(z_{uv},x) \leq d(z_{uv},u)$$d(u,v) < diam(G)$
3. , jika tidak, tahap 1 dari algoritma tidak akan berhenti di x .$d(s,z_{xy}) + d(z_{xy},x) \geq d(s,z_{uv}) + d(z_{uv},u)$$x$
4. , jika tidak, tahap 2 dari algoritma tidak akan berhenti pada y .$d(z_{xy},y) \geq d(v,z_{uv}) + d(z_{uv},z_{xy})$$y$

1) dan 2) menyiratkan .$\, \\ d(u,v) = d(z_{uv},v) + d(z_{uv},u) \\ \qquad\geq d(z_{uv},x) + d(z_{uv},y) = d(x,y) + 2\, d(z_{uv}, z_{xy}) \\ \qquad\qquad\geq d(x,y)$

3) dan 4) menyiratkan $\, \\ d(z_{xy},y) + d(s,z_{xy}) + d(z_{xy},x) \\ \qquad\geq d(s,z_{uv}) + d(z_{uv},u) + d(v,z_{uv}) + d(z_{uv},z_{xy}) \qquad\qquad\qquad\qquad \\ \,$ setara dengan .$\, \\ d(x,y) = d(z_{xy},y) + d(z_{xy},x) \\ \qquad\geq 2*\,d(s,z_{uv}) + d(v,z_{uv}) + d(u,z_{uv}) \\ \qquad\qquad\geq d(u,v)$

oleh karena itu .$d(u,v) = d(x,y)$

bukti analog berlaku untuk konfigurasi alternatif

                 (u)                          (x)
                   \                          /
                    \                        /
                     \                      /
     ( s )---------( z_uv )----------( z_xy )
                     /                      \
                    /                        \
                   /                          \
                 (v)                          (y)

dan

                          (x)        (u)  
                          /            \  
                         /              \ 
                        /                \
     ( s )---------( z_xy )----------( z_uv )
                        \                /          
                         \              /           
                          \            /            
                          (y)        (v)            

ini semua kemungkinan konfigurasi. khususnya, karena hasil tahap 1 dari algoritma dan y ∉ p a t h ( x , u ) , y ∉ p a t h ( x , v ) karena tahap 2.$x \not\in path(s,u), x \not\in path(s,v)$$y \not\in path(x,u), y \not\in path(x,v)$

Intuisi di belakang sangat mudah dipahami. Misalkan saya harus menemukan jalur terpanjang yang ada di antara dua node di pohon yang diberikan.

Setelah menggambar beberapa diagram kita dapat mengamati bahwa jalur terpanjang akan selalu terjadi antara dua node daun (node ​​hanya memiliki satu sisi yang terhubung). Ini juga dapat dibuktikan dengan kontradiksi bahwa jika jalur terpanjang antara dua node dan salah satu atau keduanya bukan node daun maka kita dapat memperluas jalur untuk mendapatkan jalur yang lebih panjang.

Jadi salah satu caranya adalah dengan memeriksa dulu apa itu daun, lalu mulai BFS dari salah satu simpul daun untuk mendapatkan simpul yang paling jauh darinya.

Alih-alih pertama-tama menemukan node mana yang merupakan node daun, kita memulai BFS dari node acak dan kemudian melihat node mana yang paling jauh darinya. Biarkan node terjauh menjadi x. Jelas bahwa x adalah simpul daun. Sekarang jika kita memulai BFS dari x dan memeriksa node terjauh darinya, kita akan mendapatkan jawaban kita.

Tapi apa jaminan bahwa x akan menjadi titik akhir dari jalur maksimum?

Mari kita lihat dengan sebuah contoh: -

       1   
    / /\ \
   6 2  4 8
         \ \
          5 9
           \
            7

Misalkan saya memulai BFS saya dari 6. Node pada jarak maksimum dari 6 adalah node 7. Menggunakan BFS kita bisa mendapatkan node ini. Sekarang kita beri bintang BFS dari node 7 untuk mendapatkan node 9 pada jarak maksimum. Jalur dari simpul 7 ke simpul 9 jelas merupakan jalur terpanjang.

Bagaimana jika BFS yang dimulai dari node 6 memberi 2 sebagai node pada jarak maksimum. Kemudian ketika kita akan BFS dari 2 kita akan mendapatkan 7 sebagai simpul pada jarak maksimum dan jalur terpanjang akan menjadi 2-> 1-> 4-> 5-> 7 dengan panjang 4. Tetapi panjang jalur terpanjang sebenarnya adalah 5. Ini tidak bisa terjadi karena BFS dari node 6 tidak akan pernah memberikan simpul 2 sebagai simpul pada jarak maksimum.

Semoga itu bisa membantu.

Berikut ini adalah bukti yang mengikuti rangkaian solusi MIT yang tertaut dalam pertanyaan awal dengan lebih dekat. Untuk lebih jelasnya, saya akan menggunakan notasi yang sama yang mereka gunakan sehingga perbandingan bisa lebih mudah dibuat.

$a$$b$$a$$b$$p(a, b)$$d(a, b)$$s \neq a, b$$s = a$$b$$u$$d(s, u) = \max_x d(s, x)$

Lemma 0: Baik dan adalah simpul daun.$a$$b$

Bukti: Jika mereka bukan simpul daun, kita bisa meningkatkan dengan memperluas titik akhir ke simpul daun, bertentangan dengan menjadi diameter.$d(a,b)$$d(a, b)$

Lemma 1: .$\max [d(s,a), d(s, b)] = d(s, u)$

Bukti: Misalkan demi kontradiksi bahwa baik dan benar-benar kurang dari . Kami melihat dua kasus:$d(s, a)$$d(s,b)$$d(s, u)$

Kasus 1: path tidak tidak mengandung simpul . Dalam hal ini, tidak boleh diameter. Untuk melihat alasannya, mari menjadi simpul unik pada dengan jarak terkecil ke . Kemudian, kita melihat bahwa , karena . Demikian pula, kita juga akan memiliki . Ini bertentangan dengan menjadi diameter.$p(a, b)$$s$$d(a, b)$$t$$p(a, b)$$s$$d(a, u) = d(a, t) + d(t, s) + d(s, u) > d(a, b) = d(a, t) + d(t, b)$$d(s, u) > d(s, b) = d(s, t) + d(t, b) > d(t, b)$$d(b, u) > d(a, b)$$d(a, b)$

Kasus 2: jalur berisi simpul . Dalam hal ini, lagi tidak bisa menjadi diameter, karena untuk beberapa simpul sedemikian sehingga , keduanya dan akan lebih besar dari .$p(a, b)$$s$$d(a, b)$ $u$$d(s, u) = \max_x d(s, x)$$d(a, u)$$d(b, u)$$d(a, b)$

Lemma 1 memberikan alasan mengapa kita memulai pencarian Breadth-First kedua pada titik terakhir yang ditemukan dari BFS pertama. Jika adalah simpul unik dengan jarak kemungkinan terbesar dari , maka oleh Lemma 1, itu harus menjadi salah satu titik akhir dari beberapa lintasan dengan jarak yang sama dengan diameter, dan karenanya BFS kedua dengan sebagai root dengan jelas menemukan diameter. Di sisi lain, jika ada setidaknya satu simpul lain sehingga , maka kita tahu bahwa diameternya adalah , dan tidak masalah apakah kita memulai BFS kedua di atau .u s u v d ( s , v ) = d ( s , u ) d ( a , b ) = 2 d ( s , u ) u $u$$u$$s$$u$$v$$d(s, v) = d(s, u)$$d(a, b) = 2d(s, u)$$u$$v$

Pertama-tama jalankan DFS dari simpul acak kemudian diameter pohon adalah jalur antara daun terdalam dari simpul dalam subtree DFS-nya:

Dengan definisi BFS, jarak (dari node awal) dari setiap node yang dieksplorasi sama dengan jarak dari node sebelumnya yang dieksplorasi atau lebih besar dengan 1. Dengan demikian, node terakhir yang dieksplorasi oleh BFS akan berada di antara mereka yang paling jauh dari awal. simpul

$x$$a$$x$$x$$b$$a$$a$

Satu hal utama yang perlu diketahui adalah bahwa pohon selalu planar, yang berarti dapat diletakkan di atas pesawat, sehingga sering kali pemikiran 2 dimensi biasa bekerja. Dalam hal ini, algoritma mengatakan mulai dari mana saja, pergi sejauh yang Anda bisa. Jarak dari titik itu sejauh yang bisa Anda dapatkan dari titik itu adalah jarak terpanjang di pohon, dan karenanya diameternya.

Metode ini juga akan berfungsi untuk menemukan diameter pulau fisik yang nyata jika kita mendefinisikannya sebagai diameter lingkaran terkecil yang akan sepenuhnya menutupi pulau.

@OP, cara kasus didefinisikan dalam PDF mungkin agak tidak aktif.

Saya pikir dua kasus itu seharusnya:

1. $p_1$ tidak berpotongan dengan , yaitu tidak ada simpul umum antara jalur dan . Dalam hal ini, tentukan sebagai simpul pertama pada ditemukan oleh BFS pertama dimulai dari .$p_2$$p_1$$p_2$$t$$p_2$$s$

2. $p_1$ dan memiliki setidaknya satu simpul umum. Dalam hal ini, tentukan untuk menjadi simpul pertama pada ditemukan oleh BFS pertama yang juga ada di .$p_2$$t$$p_2$$p_1$

Buktinya dalam PDF harus mengikuti.

Dengan definisi ini, angka yang ditunjukkan oleh OP termasuk dalam Kasus 2.