Algorytm znajdowania średnicy drzewa za pomocą BFS / DFS. Dlaczego to działa?

To łącze zapewnia algorytm znajdowania średnicy drzewa bezkierunkowego za pomocą BFS / DFS . Zreasumowanie:

Uruchom BFS na dowolnym węźle na wykresie, pamiętając węzeł wykryty jako ostatni. Uruchom BFS, pamiętając ostatnio wykryty węzeł v. d (u, v) to średnica drzewa.

Dlaczego to działa?

Strona 2 tego zawiera uzasadnienie, ale jest mylące. Cytuję początkową część dowodu:

Uruchom BFS na dowolnym węźle na wykresie, pamiętając węzeł wykryty jako ostatni. Uruchom BFS, pamiętając ostatnio wykryty węzeł v. d (u, v) to średnica drzewa.

Prawidłowość: Niech a i b będą dowolnymi dwoma węzłami, tak aby d (a, b) była średnicą drzewa. Istnieje unikalna ścieżka od a do b. Niech będzie pierwszym węzłem na ścieżce odkrytej przez BFS. Jeśli ścieżki od s do u oraz od a do b nie dzielą krawędzi, wówczas ścieżka od t do u zawiera s. Więc$p_1$$p_2$

$d(t,u) \ge d(s,u)$

$d(t,u) \ge d(s,a)$

.... (kolejne nierówności następują ..)

Nierówności nie mają dla mnie sensu.

Wszystkie części dowodu roszczenia zależą od 2 kluczowych właściwości drzew o nieukierunkowanych krawędziach:

• 1-połączenie (tj. Między dowolnymi 2 węzłami w drzewie istnieje dokładnie jedna ścieżka)
• dowolny węzeł może służyć jako korzeń drzewa.

Wybierz dowolne węzła drzewa . Załóżmy , że u , v ∈ V ( G ) są węzłami z d ( u , v ) = d i a m ( G ) . Załóżmy ponadto, że algorytm znajduje najpierw węzeł x zaczynający się od s , a następnie jakiś węzeł y zaczynający się od x . wlog d ( s , u ) ≥ d ( s , v ) . zauważ to$s$$u, v \in V(G)$$d(u,v) = diam(G)$$x$$s$$y$$x$$d(s,u) \geq d(s,v)$ muszą zostać zachowane, chyba że pierwszy stopień algorytmu nie skończy się na x . Zobaczymy, że d ( x , y ) = d ( u , v ) .$d(s,x) \geq d(s,y)$$x$$d(x,y) = d(u,v)$

Najbardziej ogólną konfigurację wszystkich zaangażowanych węzłów można zobaczyć w następującej pseudo-grafice (prawdopodobnie lub s = z x y lub obu):$s = z_{uv}$$s = z_{xy}$

(u)                                            (x)
  \                                            /
   \                                          /
    \                                        /
     ( z_uv )---------( s )----------( z_xy )
    /                                        \
   /                                          \
  /                                            \
(v)                                            (y)

wiemy to:

1. . w przeciwnym razie d ( u , v ) < d i a m ( G ) zaprzecza założeniu.$d(z_{uv},y) \leq d(z_{uv},v)$$d(u,v) < diam(G)$
2. . w przeciwnym razie d ( u , v ) < d i a m ( G ) zaprzecza założeniu.$d(z_{uv},x) \leq d(z_{uv},u)$$d(u,v) < diam(G)$
3. , w przeciwnym razie etap 1 algorytmu nie zatrzymałby się na x .$d(s,z_{xy}) + d(z_{xy},x) \geq d(s,z_{uv}) + d(z_{uv},u)$$x$
4. , w przeciwnym razie etap 2 algorytmu nie zatrzymałby się na y .$d(z_{xy},y) \geq d(v,z_{uv}) + d(z_{uv},z_{xy})$$y$

1) i 2) implikować .$\, \\ d(u,v) = d(z_{uv},v) + d(z_{uv},u) \\ \qquad\geq d(z_{uv},x) + d(z_{uv},y) = d(x,y) + 2\, d(z_{uv}, z_{xy}) \\ \qquad\qquad\geq d(x,y)$

3) i 4) sugerują $\, \\ d(z_{xy},y) + d(s,z_{xy}) + d(z_{xy},x) \\ \qquad\geq d(s,z_{uv}) + d(z_{uv},u) + d(v,z_{uv}) + d(z_{uv},z_{xy}) \qquad\qquad\qquad\qquad \\ \,$ równoważny .$\, \\ d(x,y) = d(z_{xy},y) + d(z_{xy},x) \\ \qquad\geq 2*\,d(s,z_{uv}) + d(v,z_{uv}) + d(u,z_{uv}) \\ \qquad\qquad\geq d(u,v)$

dlatego .$d(u,v) = d(x,y)$

proofy analogowe obowiązują dla alternatywnych konfiguracji

                 (u)                          (x)
                   \                          /
                    \                        /
                     \                      /
     ( s )---------( z_uv )----------( z_xy )
                     /                      \
                    /                        \
                   /                          \
                 (v)                          (y)

i

                          (x)        (u)  
                          /            \  
                         /              \ 
                        /                \
     ( s )---------( z_xy )----------( z_uv )
                        \                /          
                         \              /           
                          \            /            
                          (y)        (v)            

są to wszystkie możliwe konfiguracje. w szczególności ze względu na wynik etapu 1 algorytmu oraz y ∉ p a t h ( x , u ) , y ∉ p a t h ( x , v ) ze względu na etap 2.$x \not\in path(s,u), x \not\in path(s,v)$$y \not\in path(x,u), y \not\in path(x,v)$

Intuicja jest bardzo łatwa do zrozumienia. Załóżmy, że muszę znaleźć najdłuższą ścieżkę, która istnieje między dowolnymi dwoma węzłami w danym drzewie.

Po narysowaniu niektórych diagramów możemy zaobserwować, że najdłuższa ścieżka zawsze będzie występować między dwoma węzłami liścia (węzły połączone tylko jedną krawędzią). Można to również udowodnić przez sprzeczność, że jeśli najdłuższa ścieżka znajduje się między dwoma węzłami i jeden lub oba z dwóch węzłów nie jest węzłem liścia, wówczas możemy przedłużyć ścieżkę, aby uzyskać dłuższą ścieżkę.

Jednym ze sposobów jest sprawdzenie, które węzły są węzłami liścia, a następnie uruchomienie BFS z jednego z węzłów liścia, aby uzyskać węzeł najdalej od niego.

Zamiast najpierw dowiedzieć się, które węzły są węzłami liścia, uruchamiamy BFS z losowego węzła, a następnie sprawdzamy, który węzeł jest najdalej od niego. Niech węzłem najdalej będzie x. Oczywiste jest, że x jest węzłem liścia. Teraz, jeśli uruchomimy BFS od x i sprawdzimy od niego najdalszy węzeł, otrzymamy naszą odpowiedź.

Ale jaka jest gwarancja, że ​​x będzie końcowym punktem maksymalnej ścieżki?

Zobaczmy na przykładzie: -

       1   
    / /\ \
   6 2  4 8
         \ \
          5 9
           \
            7

Załóżmy, że uruchomiłem mój BFS od 6. Węzłem w maksymalnej odległości od 6 jest węzeł 7. Za pomocą BFS możemy uzyskać ten węzeł. Teraz zaczynamy BFS od węzła 7, aby uzyskać węzeł 9 w maksymalnej odległości. Ścieżka od węzła 7 do węzła 9 jest wyraźnie najdłuższą ścieżką.

Co jeśli BFS, który rozpoczął się od węzła 6, dał 2 jako węzeł w maksymalnej odległości. Następnie, gdy będziemy BFS od 2, otrzymamy 7 jako węzeł w maksymalnej odległości, a najdłuższa ścieżka będzie wtedy 2-> 1-> 4-> 5-> 7 o długości 4. Ale rzeczywista najdłuższa długość ścieżki wynosi 5. Nie można dzieje się tak, ponieważ BFS z węzła 6 nigdy nie da węzła 2 jako węzła w maksymalnej odległości.

Mam nadzieję, że to pomaga.

Oto dowód, który jest zgodny z zestawem rozwiązań MIT powiązanym z pierwotnym pytaniem. Dla jasności użyję tego samego zapisu, którego używają, aby łatwiej było dokonać porównania.

Załóżmy, że mamy dwa wierzchołki oraz b tak, że odległość pomiędzy i B na ścieżce P ( , b ) ma średnicę, na przykład na odległość d ( , b ) jest maksymalna odległość między dwoma punktami w drzewie. Załóżmy, że mamy również węzeł s ≠ a , b (jeśli s = a , to byłoby oczywiste, że schemat działa, ponieważ pierwszy BFS otrzyma b , a drugi wróci do a). Załóżmy również, że mamy węzeł$a$$b$$a$$b$$p(a, b)$$d(a, b)$$s \neq a, b$$s = a$$b$ taki, że d ( s , u ) = max x d ( s , x ) .$u$$d(s, u) = \max_x d(s, x)$

Lemat 0: Zarówno i b są węzłami liści.$a$$b$

Dowód: gdyby nie były węzłami liścia, moglibyśmy zwiększyć poprzez rozszerzenie punktów końcowych na węzły liścia, przeciwstawiając się d ( a , b ) jako średnicy.$d(a,b)$$d(a, b)$

$\max [d(s,a), d(s, b)] = d(s, u)$

$d(s, a)$$d(s,b)$$d(s, u)$

$p(a, b)$$s$$d(a, b)$$t$$p(a, b)$$s$$d(a, u) = d(a, t) + d(t, s) + d(s, u) > d(a, b) = d(a, t) + d(t, b)$$d(s, u) > d(s, b) = d(s, t) + d(t, b) > d(t, b)$$d(b, u) > d(a, b)$$d(a, b)$

$p(a, b)$$s$$d(a, b)$ $u$$d(s, u) = \max_x d(s, x)$$d(a, u)$$d(b, u)$$d(a, b)$

$u$$u$$s$$u$$v$$d(s, v) = d(s, u)$$d(a, b) = 2d(s, u)$$u$$v$

Najpierw uruchom DFS z losowego węzła, a następnie średnica drzewa jest ścieżką między najgłębszymi liśćmi węzła w jego poddrzewie:

Zgodnie z definicją BFS odległość (od węzła początkowego) każdego eksplorowanego węzła jest albo równa odległości poprzedniego badanego węzła, albo większa o 1. Zatem ostatni węzeł badany przez BFS będzie jednym z najdalszych od początku węzeł.

$x$$a$$x$$x$$b$$a$$a$

Jedną z kluczowych rzeczy, o których należy wiedzieć, jest to, że drzewo jest zawsze płaskie, co oznacza, że ​​można je ułożyć na płaszczyźnie, dlatego często działa zwykłe myślenie dwuwymiarowe. W takim przypadku algorytm mówi, że należy rozpocząć od dowolnego miejsca, a następnie odejść jak najdalej. Odległość od tego punktu do możliwie największej odległości od tego punktu to największa odległość w drzewie, a zatem średnica.

Ta metoda działałaby również w celu znalezienia średnicy prawdziwej, fizycznej wyspy, gdybyśmy zdefiniowali ją jako średnicę najmniejszego okręgu, który całkowicie otaczałby wyspę.

@op, sposób definiowania przypadków w pliku PDF może być nieco wyłączony.

Myślę, że te dwa przypadki powinny być:

1. $p_1$$p_2$$p_1$$p_2$$t$$p_2$$s$

2. $p_1$$p_2$$t$$p_2$$p_1$

Reszta dowodu w pliku PDF powinna nastąpić.

Przy tej definicji liczba pokazana przez OP mieści się w przypadku 2.