¿Cuántas distancias más cortas cambian al agregar un borde a un gráfico?

22

Sea un gráfico completo, ponderado y no dirigido. Construimos un segundo gráfico agregando bordes uno por uno de a . Añadimos bordes de en total.G=(V,E)G=(V,E)EEΘ(|V|)G

Cada vez que agregamos un borde a , consideramos las distancias más cortas entre todos los pares en y . Contamos cuántas de estas distancias más cortas han cambiado como consecuencia de sumar . Deje que sea ​​el número de distancias más cortas que cambian cuando agregamos el ésimo borde, y sea n el número de bordes que sumamos en total.(u,v)E(V,E)(V,E{(u,v)})(u,v)Ciin

¿Qué tan grande es C=iCin ?

Como Ci=O(|V|2)=O(n2) , C=O(n2) también. ¿Se puede mejorar este límite? Tenga en cuenta que defino que C es el promedio sobre todos los bordes que se agregaron, por lo que una sola ronda en la que cambian muchas distancias no es tan interesante, aunque demuestra que C=Ω(n) .

Tengo un algoritmo para calcular un t-spanner geométrico con avidez que funciona en el tiempo O(Cnlogn) , por lo que si C es o(n2) , mi algoritmo es más rápido que el algoritmo codicioso original, y si C es realmente pequeño, potencialmente más rápido que el algoritmo más conocido (aunque lo dudo).

Algunas propiedades específicas del problema que podrían ayudar con un buen límite: el borde (u,v) que se agrega siempre tiene mayor peso que cualquier borde que ya esté en el gráfico (no necesariamente estrictamente más grande). Además, su peso es más corto que el camino más corto entre u y v .

Puede suponer que los vértices corresponden a puntos en un plano 2d y que las distancias entre vértices son las distancias euclidianas entre estos puntos. Es decir, cada vértice v corresponde a algún punto (x,y) en el plano, y para un borde (u,v)=((x1,y1),(x2,y2)) su peso es igual a (x2x1)2+(y2y1)2.

Alex ten Brink
fuente
2
Tome dos camarillas conectadas por un camino con dos bordes. Agregar un borde directamente entre las camarillas acorta Ω(n2) de los caminos más cortos.
Louis
1
@Louis: sí, hay ejemplos en los que un solo borde hace que cambien muchas distancias, pero ¿existen gráficos en los que eso sucede para cada borde que agrega, o al menos para muchos de ellos? Esta es exactamente la razón por la que definí como el promedio en todos los bordes :)C
Alex ten Brink
1
La mayoría de los bordes en este gráfico que se pueden agregar son del tipo que describí ...
Louis
@Louis True. Sin embargo, las camarillas contienen bordes , que es más de lo que agregaré a mi gráfico. O(n2)
Alex ten Brink
Tuve el mismo problema antes, pero mi gráfico era un poco escaso con y debo demostrar que los cambios promedio son O (1) pero no pude hacerlo :-). Pero para su caso, creo que si encuentra una relación entre esto y la solución de APSP, puede obtener algunos resultados. |E|=O(|V|)

Respuestas:

19

Considere la siguiente cadena lineal con nodos, aristas y pesos viciosamente elegidos:n+1n

ejemplo
[ fuente ]

Claramente, los bordes podrían haberse agregado en orden de sus pesos y hay de ellos. Agregar el borde discontinuo (que es legal) crea rutas más cortas para todos los pares con . Como y suponiendo que , tanto la primera como la última fila contienen muchos nodos cada uno y la suma causa muchos cambios de ruta más cortos.nO(|V|)(ui,bj)i,j=1,,kkn4nΘ(|V|)Θ(|V|)Θ(|V|2)

Ahora podemos movernos "hacia afuera", es decir, agregar la siguiente arista con un peso entre y y así sucesivamente; si continuamos esto a en total cambios de ruta más cortos.n+2uk1bk1(u1,b1)Θ(|V|3)

Si esto no lo convence, tenga en cuenta que realmente puede comenzar este "proceso" con y trabajar desde allí; de esta manera agrega aristas que causan en total muchas rutas más cortas cambios --- esto es simplemente imposible de dibujar para que quepa en una pantalla.(c1,c2)ni=1ni2Θ(n3)=Θ(|V|3)

Rafael
fuente
1
De hecho, esto funciona y, además, su ejemplo se puede cambiar un poco para convertirse en Euclidiano. Gracias :)
Alex ten Brink