Ile najkrótszych odległości zmienia się podczas dodawania krawędzi do wykresu?

Niech będzie jakimś kompletnym, ważonym, niekierowanym wykresem. Budujemy drugi wykres , dodając krawędzie jeden po drugim od do . Łącznie dodajemy krawędzie do .G ′ = ( V , E ′ ) E E ′ Θ ( | V | ) G $G=(V,E)$$G'=(V, E')$$E$$E'$$\Theta(|V|)$$G'$

Za każdym razem, gdy dodajemy jedną krawędź do , bierzemy pod uwagę najkrótsze odległości między wszystkimi parami w i . Liczymy, ile z tych najkrótszych odległości zmieniło się w wyniku dodania . Niech będzie liczbą najkrótszych odległości, które zmieniają się, gdy dodamy krawędź, a niech będzie liczbą wszystkich dodanych przez nas krawędzi.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$

Jak duże jest ?$C = \frac{\sum_i C_i}{n}$

Ponieważ , również. Czy można to poprawić? Zauważ, że definiuję jako średnią dla wszystkich dodanych krawędzi, więc pojedyncza runda, w której zmienia się wiele odległości, nie jest tak interesująca, chociaż dowodzi, że .C = O ( n 2 ) C C = Ω ( n $C_i = O(|V|^2)=O(n^2)$$C=O(n^2)$$C$$C = \Omega(n)$

Mam algorytm obliczający chciwość geometrycznego klucza T, który działa w czasie , więc jeśli to , mój algorytm jest szybszy niż oryginalny algorytm zachłanny, a jeśli jest naprawdę mały, potencjalnie szybszy niż najbardziej znany algorytm (choć w to wątpię).C o ( n 2 ) $O(C n \log n)$$C$$o(n^2)$$C$

Niektóre właściwości specyficzne dla problemu, które mogą pomóc w dobrym związaniu: dodana krawędź zawsze ma większą wagę niż jakakolwiek krawędź już na wykresie (niekoniecznie ściśle większa). Ponadto jego waga jest krótsza niż najkrótsza ścieżka między i .u $(u,v)$$u$$v$

Można założyć, że wierzchołki odpowiadają punktom na płaszczyźnie 2d, a odległości między wierzchołkami są odległościami euklidesowymi między tymi punktami. Oznacza to, że każdy wierzchołek odpowiada pewnemu punktowi na płaszczyźnie, a dla krawędzi jego waga jest równa( 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.}$

Rozważ następujący łańcuch liniowy z węzłami, krawędziami i błędnie wybranymi wagami:$n+1$$n$

^{[ źródło ]}

Oczywiste jest, że krawędzie mogły zostać dodane w kolejności ich ciężarów i jest ich . Dodanie przerywanej krawędzi (co jest zgodne z prawem) tworzy krótsze ścieżki dla wszystkich par z . Ponieważ i przy założeniu, że , zarówno pierwszy, jak i ostatni wiersz zawierają wiele węzłów każdy, a dodanie powoduje wiele najkrótszych zmian ścieżki.( u i , b j ) i , j = 1 , … , k k ≈ $n \in \mathcal{O}(|V|)$$(u_i,b_j)$$i,j = 1,\dots,k$ n∈Θ(|V|)Θ(|V|)Θ(|V|2$k \approx \frac{n}{4}$$n \in \Theta(|V|)$$\Theta(|V|)$$\Theta(|V|^2)$

Możemy teraz przejść „na zewnątrz”, tj. Dodać następną krawędź o wadze między a i tak dalej; jeśli kontynuujemy to do , powodujemy w sumie najkrótsze zmiany ścieżki.u k - 1 b k - 1 ( u 1 , b 1 ) Θ ( | V | 3$n+2$$u_{k-1}$$b_{k-1}$$(u_1,b_1)$$\Theta(|V|^3)$

Jeśli to Cię nie przekonuje, zauważ, że możesz faktycznie rozpocząć ten „proces” za pomocą i stamtąd pracować na zewnątrz; w ten sposób dodajesz krawędzi, które powodują w sumie wiele najkrótszych ścieżek zmiany --- po prostu nie można narysować, aby zmieściło się na jednym ekranie.≈ n ≈ ∑ n i = 1 i 2 ∈ Θ ( n 3 ) = Θ ( | V | 3$(c_1,c_2)$$\approx n$$\approx \sum_{i=1}^{n}i^2 \in \Theta(n^3) = \Theta(|V|^3)$