Berapa banyak jarak terpendek berubah saat menambahkan tepi ke grafik?

Biarkan menjadi beberapa grafik lengkap, tertimbang, tidak terarah. Kami membuat grafik kedua dengan menambahkan tepi satu per satu dari ke . Kami menambahkan tepi ke secara total.G ′ = ( V , E ′ ) E E ′ Θ ( | V | ) G $G=(V,E)$$G'=(V, E')$$E$$E'$$\Theta(|V|)$$G'$

Setiap kali kita menambahkan satu sisi ke , kami mempertimbangkan jarak terpendek antara semua pasangan dalam dan . Kami menghitung berapa banyak dari jarak terpendek ini telah berubah sebagai konsekuensi dari penambahan . Biarkan menjadi jumlah jarak terpendek yang berubah ketika kita menambahkan tepi ke- , dan biarkan menjadi jumlah tepi yang kita tambahkan secara total.E ′ ( V , E ′ ) ( V , E ′ ∪ { ( u , v ) } ) ( u , v ) C i i $(u,v)$$E'$$(V, E')$$(V, E' \cup \{ (u,v) \})$$(u,v)$$C_i$$i$$n$

Seberapa besar ?$C = \frac{\sum_i C_i}{n}$

Sebagai , juga. Bisakah ikatan ini ditingkatkan? Perhatikan bahwa saya mendefinisikan sebagai rata-rata di semua tepi yang ditambahkan, jadi satu putaran di mana banyak perubahan jarak tidak begitu menarik, meskipun itu membuktikan bahwa .C = O ( n 2 ) C C = Ω ( n $C_i = O(|V|^2)=O(n^2)$$C=O(n^2)$$C$$C = \Omega(n)$

Saya memiliki algoritme untuk menghitung geometri t-spanner dengan rakus yang bekerja pada waktu , jadi jika adalah , algoritme saya lebih cepat daripada algoritma serakah asli, dan jika adalah sangat kecil, berpotensi lebih cepat dari algoritma yang paling dikenal (meskipun saya ragu itu).C o ( n 2 ) $O(C n \log n)$$C$$o(n^2)$$C$

Beberapa sifat khusus masalah yang mungkin membantu dengan ikatan yang baik: tepi yang ditambahkan selalu memiliki bobot lebih besar dari tepi mana pun yang sudah ada dalam grafik (tidak harus benar-benar lebih besar). Selanjutnya, beratnya lebih pendek dari jalur terpendek antara dan .u $(u,v)$$u$$v$

Anda dapat mengasumsikan bahwa simpul sesuai dengan titik-titik dalam bidang 2d dan jarak antara simpul adalah jarak Euclidian antara titik-titik ini. Yaitu, setiap titik sesuai dengan beberapa titik di pesawat, dan untuk tepi beratnya sama dengan( x , y ) ( u , v ) = ( ( x 1 , y 1 ) , ( x 2 , y 2 ) ) $v$$(x,y)$$(u,v)=((x_1,y_1),(x_2,y_2))$$\sqrt{(x_2-x_1)^2 + (y_2-y_1)^2.}$

Pertimbangkan rantai linear berikut dengan node, n edge dan bobot yang dipilih dengan kejam:$n+1$$n$

^{[ sumber ]}

Jelas, ujung-ujungnya bisa ditambahkan dalam urutan bobotnya dan ada dari mereka. Menambahkan tepi putus-putus (yang legal) menciptakan jalur yang lebih pendek untuk semua pasangan ( u i , b j ) dengan i , j = 1 , … , k . Sebagai k ≈ $n \in \mathcal{O}(|V|)$$(u_i,b_j)$$i,j = 1,\dots,k$ dan dengan asumsi bahwan∈Θ(|V|), baik baris pertama dan terakhir mengandungΘ(|V|)masing-masing banyak node dan penambahan menyebabkanΘ(|V|2)banyak perubahan jalur terpendek.$k \approx \frac{n}{4}$$n \in \Theta(|V|)$$\Theta(|V|)$$\Theta(|V|^2)$

Kita sekarang dapat memindahkan "ke luar" sekarang, yaitu menambahkan tepi berikutnya dengan bobot antara u k - 1 dan b k - 1 dan seterusnya; jika kita melanjutkan ini ke ( u 1 , b 1 ) , kita menyebabkan total perubahan jalur terpendek Θ ( | V | 3 ) .$n+2$$u_{k-1}$$b_{k-1}$$(u_1,b_1)$$\Theta(|V|^3)$

Jika ini tidak meyakinkan Anda, perhatikan bahwa Anda sebenarnya dapat memulai "proses" ini dengan dan bekerja keluar dari sana; dengan cara ini Anda menambahkan ≈ n tepi yang menyebabkan total ≈ ∑ n i = 1 i 2 ∈ Θ ( n 3 ) = Θ ( | V | 3 ) banyak perubahan jalur terpendek --- ini hanya mustahil untuk menggambar agar sesuai pada satu layar.$(c_1,c_2)$$\approx n$$\approx \sum_{i=1}^{n}i^2 \in \Theta(n^3) = \Theta(|V|^3)$