Combien de distances les plus courtes changent lors de l'ajout d'une arête à un graphique?

22

Soit G=(V,E) un graphe complet, pondéré et non orienté. Nous construisons un deuxième graphe en ajoutant un à un les arêtes de à . Nous ajoutons des arêtes à au total.E E Θ ( | V | ) G g=(V,E)EEΘ(|V|)g

Chaque fois que nous ajoutons une arête à , nous considérons les distances les plus courtes entre toutes les paires dans et . Nous comptons combien de ces distances les plus courtes ont changé suite à l'ajout de . Soit le nombre de distances les plus courtes qui changent lorsque nous ajoutons le ème bord, et soit le nombre d'arêtes que nous ajoutons au total.E ( V , E ) ( V , E { ( u , v ) } ) ( u , v ) C i i n(u,v)E(V,E)(V,E{(u,v)})(u,v)Ciin

Quelle est la taille de ?C=iCin

Comme , également. Cette limite peut-elle être améliorée? Notez que je définis comme étant la moyenne sur toutes les arêtes qui ont été ajoutées, donc un seul tour dans lequel beaucoup de distances changent n'est pas si intéressant, même si cela prouve que .C = O ( n 2 ) C C = Ω ( n )Ci=O(|V|2)=O(n2)C=O(n2)CC=Ω(n)

J'ai un algorithme pour calculer avidement une clé géométrique qui fonctionne en temps O(Cnlogn) , donc si C est o(n2) , mon algorithme est plus rapide que l'algorithme gourmand d'origine, et si C est vraiment petit, potentiellement plus rapide que l'algorithme le plus connu (bien que j'en doute).

Quelques propriétés spécifiques au problème qui pourraient aider à une bonne limite: l'arête qui est ajoutée a toujours un poids plus important que n'importe quelle arête déjà dans le graphique (pas nécessairement strictement plus grande). De plus, son poids est plus court que le chemin le plus court entre et .u v(u,v)uv

Vous pouvez supposer que les sommets correspondent à des points dans un plan 2D et que les distances entre les sommets sont les distances euclidiennes entre ces points. Autrement dit, chaque sommet correspond à un certain point dans le plan, et pour une arête son poids est égal àv(x,y)(u,v)=((x1,y1),(x2,y2))(x2x1)2+(y2y1)2.

Alex ten Brink
la source
2
Prenez deux cliques reliées par un chemin à deux bords. L'ajout d'un bord directement entre les cliques raccourcit des chemins les plus courts. Ω(n2)
Louis
1
@Louis: oui, il y a des exemples dans lesquels une seule arête fait changer beaucoup de distances, mais existe-t-il des graphiques dans lesquels cela se produit pour chaque arête que vous ajoutez, ou du moins pour beaucoup d'entre elles? C'est exactement pourquoi j'ai défini comme étant la moyenne sur tous les bords :)C
Alex ten Brink
1
La plupart des bords de ce graphique qui peuvent être ajoutés sont du type que j'ai décrit ...
Louis
@Louis True. Les cliques contiennent cependant des arêtes , ce qui est plus que ce que j'ajouterai à mon graphique. O(n2)
Alex ten Brink
J'ai eu le même problème avant, mais mon graphique était en quelque sorte des graphiques clairsemés avec et je devrais prouver que les changements moyens sont O (1) mais je n'ai pas pu le faire :-). Mais pour votre cas, je pense que si vous trouvez une relation entre cela et la solution d'APSP, vous pouvez obtenir des résultats. |E|=O(|V|)

Réponses:

19

Considérons la chaîne linéaire suivante avec nœuds, n arêtes et des poids judicieusement choisis:n+1n

exemple
[ source ]

De toute évidence, les bords auraient été ajoutés afin de leur poids et il y a d'entre eux. L'ajout du bord en pointillés (ce qui est légal) crée des chemins plus courts pour toutes les paires ( u i , b j ) avec i , j = 1 , , k . Comme k nnO(|V|)(ui,bj)i,j=1,,kkn4nΘ(|V|)Θ(|V|)Θ(|V|2)

n+2uk1bk1(u1,b1)Θ(|V|3)

(c1,c2)ni=1ni2Θ(n3)=Θ(|V|3)

Raphael
la source
1
Cela fonctionne en effet, et de plus, votre exemple peut être légèrement modifié pour devenir euclidien. Merci :)
Alex ten Brink