Wie viele kürzeste Abstände ändern sich, wenn einer Grafik eine Kante hinzugefügt wird?

Sei ein vollständiger, gewichteter, ungerichteter Graph. Wir konstruieren einen zweiten Graphen G ' = ( V , E ' ), indem wir die Kanten einzeln von E nach E ' addieren . Wir addieren Θ ( | V | ) Kanten zu G ' insgesamt.$G=(V,E)$$G'=(V, E')$$E$$E'$$\Theta(|V|)$$G'$

Jedes Mal , wenn wir einen Rand hinzuzufügen bis E ' , betrachten wir die kürzesten Abstände zwischen allen Paaren in ( V , E ' ) und ( V , E ' ∪ { ( u , v ) } ) . Wir zählen, wie viele dieser kürzesten Abstände sich infolge der Addition von ( u , v ) geändert haben . Sei C i die Anzahl der kürzesten Abstände, die sich ändern, wenn wir das i addieren$(u,v)$$E'$$(V, E')$$(V, E' \cup \{ (u,v) \})$$(u,v)$$C_i$$i$th edge, und sei die Anzahl der Kanten, die wir insgesamt hinzufügen.$n$

Wie groß ist ?$C = \frac{\sum_i C_i}{n}$

Da , ist auch C = O ( n 2 ) . Kann diese Grenze verbessert werden? Beachten Sie, dass ich C als Durchschnitt über alle Kanten definiere, die hinzugefügt wurden. Daher ist eine einzelne Runde, in der sich viele Abstände ändern, nicht so interessant, obwohl sich ergibt, dass C = Ω ( n ) .$C_i = O(|V|^2)=O(n^2)$$C=O(n^2)$$C$$C = \Omega(n)$

Ich habe einen Algorithmus zur Berechnung eines geometrischen t-Schlüssel Gierig , dass die Arbeiten in Zeit, so dass , wenn C ist o ( n 2 ) , mein Algorithmus schneller als das Original Greedy - Algorithmus ist, und wenn C ist wirklich klein , möglicherweise schneller als der bekannteste Algorithmus (obwohl ich das bezweifle).$O(C n \log n)$$C$$o(n^2)$$C$

Einige problemspezifische Eigenschaften, die bei einer guten Bindung hilfreich sein können: Die hinzugefügte Kante hat immer eine größere Gewichtung als jede bereits im Diagramm enthaltene Kante (nicht unbedingt eine streng größere). Außerdem ist sein Gewicht kürzer als der kürzeste Weg zwischen u und v .$(u,v)$$u$$v$

Sie können annehmen, dass die Eckpunkte Punkten in einer 2D-Ebene entsprechen und die Abstände zwischen den Eckpunkten die euklidischen Abstände zwischen diesen Punkten sind. Das heißt, jeder Scheitelpunkt entspricht einem Punkt ( x , y ) in der Ebene, und für eine Kante ( u , v ) = ( ( x 1 , y 1 ) , ( x 2 , y 2 ) ) ist sein Gewicht gleich zu $v$$(x,y)$$(u,v)=((x_1,y_1),(x_2,y_2))$$\sqrt{(x_2-x_1)^2 + (y_2-y_1)^2.}$

Betrachten Sie die folgende lineare Kette mit Knoten, n Kanten und bösartig gewählten Gewichten:$n+1$$n$

^{[ Quelle ]}

$n \in \mathcal{O}(|V|)$$(u_i,b_j)$$i,j = 1,\dots,k$$k \approx \frac{n}{4}$$n \in \Theta(|V|)$$\Theta(|V|)$$\Theta(|V|^2)$

$n+2$$u_{k-1}$$b_{k-1}$$(u_1,b_1)$$\Theta(|V|^3)$

$(c_1,c_2)$$\approx n$$\approx \sum_{i=1}^{n}i^2 \in \Theta(n^3) = \Theta(|V|^3)$