Quantas distâncias mais curtas mudam ao adicionar uma aresta a um gráfico?

Seja um gráfico completo, ponderado e não direcionado. Construímos um segundo gráfico G ' = ( V , E ' ) adicionando arestas uma a uma de E a E ' . Adicionamos arestas Θ ( | V | ) a G ′ no total.$G=(V,E)$$G'=(V, E')$$E$$E'$$\Theta(|V|)$$G'$

Cada vez que adicionar uma borda a E ' , nós consideramos as menores distâncias entre todos os pares em ( V , E ' ) e ( V , E ' ∪ { ( u , v ) } ) . Contamos quantas dessas distâncias mais curtas mudaram como consequência da adição ( u , v ) . Seja C i o número de distâncias mais curtas que mudam quando adicionamos o $(u,v)$$E'$$(V, E')$$(V, E' \cup \{ (u,v) \})$$(u,v)$$C_i$$i$ª aresta e seja o número de arestas que adicionamos no total.$n$

Quão grande é ?$C = \frac{\sum_i C_i}{n}$

Como , C = O ( n 2 ) também. Esse limite pode ser melhorado? Note que eu defino C como a média de todas as arestas adicionadas, portanto, uma única rodada na qual muitas distâncias mudam não é tão interessante, embora prove que C = Ω ( n ) .$C_i = O(|V|^2)=O(n^2)$$C=O(n^2)$$C$$C = \Omega(n)$

Eu tenho um algoritmo para calcular uma chave-t geométrica avidamente que funciona em , portanto, se C é o ( n 2 ) , meu algoritmo é mais rápido que o algoritmo ganancioso original e se C é realmente pequeno , potencialmente mais rápido que o algoritmo mais conhecido (embora eu duvide disso).$O(C n \log n)$$C$$o(n^2)$$C$

Algumas propriedades específicas do problema que podem ajudar com um bom limite: a aresta adicionada sempre tem um peso maior do que qualquer aresta já existente no gráfico (não necessariamente estritamente maior). Além disso, seu peso é menor que o caminho mais curto entre u e v .$(u,v)$$u$$v$

Você pode assumir que os vértices correspondem aos pontos em um plano 2D e as distâncias entre os vértices são as distâncias euclidianas entre esses pontos. Ou seja, todo vértice corresponde a algum ponto ( x , y ) no plano e para uma aresta ( u , v ) = ( ( x 1 , y 1 ) , ( x 2 , y 2 ) ) seu peso é igual para $v$$(x,y)$$(u,v)=((x_1,y_1),(x_2,y_2))$$\sqrt{(x_2-x_1)^2 + (y_2-y_1)^2.}$

$n+1$$n$

^{[ fonte ]}

$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)$