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)$ $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. $(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_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ę). $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,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 $v$ $(x,y)$ $(u,v)=((x_1,y_1),(x_2,y_2))$ $\sqrt{(x_2-x_1)^2 + (y_2-y_1)^2.}$

— Alex ten Brink
źródło

Weź dwie kliki połączone ścieżką o dwóch krawędziach. Dodanie jednej krawędzi bezpośrednio między klikami skraca najkrótszych ścieżek.

Ω (n^{2})

$\Omega(n^2)$

— Louis,

@Louis: tak, są przykłady, w których pojedyncza krawędź powoduje zmianę wielu odległości, ale czy istnieją wykresy, w których dzieje się to dla każdej dodanej krawędzi, a przynajmniej dla wielu z nich? Właśnie dlatego zdefiniowałem jako średnią dla wszystkich krawędzi :)

C

$C$

— Alex ten Brink

Większość krawędzi na tym wykresie, które można dodać, jest typu opisanego

— Louis,

@Louis True. Kliki zawierają jednak krawędzie , co jest więcej niż kiedykolwiek dodam do mojego wykresu.

O (n^{2})

$O(n^2)$

— Alex ten Brink

Miałem wcześniej ten sam problem, ale Mój wykres był rodzajem rzadkich wykresów z i powinienem udowodnić, że średnie zmiany to O (1), ale nie mogłem tego zrobić :-). Ale w twoim przypadku myślę, że jeśli znajdziesz związek między tym a rozwiązaniem APSP, możesz uzyskać pewne wyniki.

| E | = O (| V |)

$|E|=O(|V|)$

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

przykład
^{[ ź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. $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)$

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. $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. $(c_1,c_2)$ $\approx n$ $\approx \sum_{i=1}^{n}i^2 \in \Theta(n^3) = \Theta(|V|^3)$

— Raphael
źródło

To rzeczywiście działa, a ponadto twój przykład można nieco zmienić, aby stać się euklidesowym. Dzięki :)

— Alex ten Brink