Algorithmus zum Ermitteln des Baumdurchmessers mithilfe von BFS / DFS. Warum funktioniert es?

28

Dieser Link bietet einen Algorithmus zum Ermitteln des Durchmessers eines ungerichteten Baums mithilfe von BFS / DFS . Zusammenfassend:

Führen Sie BFS auf einem beliebigen Knoten im Diagramm aus, und merken Sie sich dabei den Knoten, den Sie zuletzt entdeckt haben. Führen Sie BFS von u aus und merken Sie sich den Knoten v, der zuletzt erkannt wurde. d (u, v) ist der Durchmesser des Baumes.

Warum funktioniert es?

Seite 2 von diesem stellt eine Argumentation, aber es ist verwirrend. Ich zitiere den ersten Teil des Beweises:

Führen Sie BFS auf einem beliebigen Knoten im Diagramm aus, und merken Sie sich dabei den Knoten, den Sie zuletzt entdeckt haben. Führen Sie BFS von u aus und merken Sie sich den Knoten v, der zuletzt erkannt wurde. d (u, v) ist der Durchmesser des Baumes.

Richtigkeit: Sei a und b zwei beliebige Knoten, so dass d (a, b) der Durchmesser des Baumes ist. Es gibt einen eindeutigen Pfad von a nach b. Seien Sie nicht der erste Knoten auf diesem Pfad, der von BFS erkannt wird. Wenn sich die Pfade von s nach u und von a nach b keine Kanten teilen, enthält der Pfad von t nach u s. Sop1p2

d(t,u)d(s,u)

d(t,u)d(s,a)

.... (weitere Ungleichungen folgen ..)

Die Ungleichungen ergeben für mich keinen Sinn.

Curryage
quelle
Ich finde das Zitat nicht in der verlinkten Frage.
Raphael
1
Versuchen Sie, in der Lösung "Kanten nicht teilen" durch "Eckpunkte nicht teilen" zu ersetzen.
Yuval Filmus
Sie verwenden nur BFS, nicht DFS.
Thumbnail

Antworten:

11

Alle Teile des Nachweises der Behauptung hängen von 2 entscheidenden Eigenschaften von Bäumen mit ungerichteten Kanten ab:

  • 1-Verbundenheit (dh zwischen 2 beliebigen Knoten in einem Baum gibt es genau einen Pfad)
  • Jeder Knoten kann als Wurzel des Baums dienen.

Wählen Sie einen beliebigen Baumknoten . Angenommen, sind Knoten mit . Es sei ferner angenommen, dass der Algorithmus einen Knoten findet, der zuerst bei beginnt , und einen Knoten nächstes bei beginnt . wlog . Beachten Sie, dass muss, es sei denn, die erste Stufe des Algorithmus würde nicht bei enden . Wir werden sehen, dass .u , v V ( G )su,vV(G)x s y x d ( s , u ) d ( s , v ) d ( s , x ) d ( s , y ) x d ( x , y ) =d(u,v)=diam(G)xsyxd(s,u)d(s,v)d(s,x)d(s,y)xd(x,y)=d(u,v)

Die allgemeinste Konfiguration aller beteiligten Knoten ist in den folgenden Pseudo-Grafiken zu sehen (möglicherweise oder oder beides): s = z x ys=zuvs=zxy

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

Wir wissen das:

  1. d ( u , v ) < d i a m ( G )d(zuv,y)d(zuv,v) . ansonsten widerspricht der Annahme.d(u,v)<diam(G)
  2. d ( u , v ) < d i a m ( G )d(zuv,x)d(zuv,u) . ansonsten widerspricht der Annahme.d(u,v)<diam(G)
  3. xd(s,zxy)+d(zxy,x)d(s,zuv)+d(zuv,u) , sonst würde Stufe 1 des Algorithmus nicht habe bei angehalten .x
  4. yd(zxy,y)d(v,zuv)+d(zuv,zxy) , sonst wäre Stufe 2 des Algorithmus nicht bei .y

1) und 2) implizieren .d(u,v)=d(zuv,v)+d(zuv,u)d(zuv,x)+d(zuv,y)=d(x,y)+2d(zuv,zxy)d(x,y)

3) und 4) implizieren Äquivalent bis .d(zxy,y)+d(s,zxy)+d(zxy,x)d(s,zuv)+d(zuv,u)+d(v,zuv)+d(zuv,zxy)d(x,y)=d(zxy,y)+d(zxy,x)2d(s,zuv)+d(v,zuv)+d(u,zuv)d(u,v)

daher ist .d(u,v)=d(x,y)

Analoge Beweise gelten für die alternativen Konfigurationen

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

und

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

Dies sind alles mögliche Konfigurationen. insbesondere aufgrund des Ergebnisses von Stufe 1 des Algorithmus und aufgrund von Stufe 2.y p a t h ( x , u ) , y p a t h ( x , v )xpath(s,u),xpath(s,v)ypath(x,u),ypath(x,v)

Collapsar
quelle
(1) Sollte der Pfad von s nach x in Bezug auf die erste Grafik nicht immer die Eckpunkte u und v in einer bestimmten Reihenfolge enthalten, da sie in einem von BFS generierten Baum vorhanden sind? (2) Können Sie klären, wie die Ungleichungen entstehen? (3) Da die BFS ab s und die mit x irgendwo auf dem Pfad u, v enthalten, sollte die Grafik meines Erachtens dem Link imgur.com/jQ94erY entsprechen . Wie trifft die Begründung zu, die Sie hier angegeben haben?
Curryage
@curryage beachte, dass der Baum gegeben ist und nicht vom BFS erstellt wird! Konkrete Antworten: ad 1) nein. Stellen Sie sich eine Verfeinerung des Baums in Grafiken (1) vor, indem Sie beliebig viele Knoten an der Kante und genau 1 Knoten an der Kante hinzufügen . das erste bfs endet dann bei x. ad 2) Welche Ungleichungen sind unklar? Wir gehen immer davon aus, dass ein Pfad ist, der der Länge des Durchmesserdiagramms . Dies ist gut definiert, da G 1-verbunden ist. ad 3) no: 3.1 es gibt mehr als 1 Pfad zwischen 2 beliebigen Knoten mit Ausnahme von , sodass der Graph kein Baum ist. ...( z x y , x ) ( u , v ) , d i a g ( G ) ( s , y )(s,zxy)(zxy,x)(u,v)diag(G)(s,y)
collapsar
@curryage ... 3,2 ; Dies ist unmöglich, da angenommen wird und der Durchmesser eines Graphen der maximale Mindestabstand zwischen zwei beliebigen Knoten ist. Im Fall eines Baums gibt es genau 1 Pfad zwischen 2 beliebigen Knoten, daher wird die Definition auf den „maximalen Abstand zwischen zwei beliebigen Knoten“ reduziert. d ( u , v ) = d i a m ( G )d(x,y)>d(u,v)d(u,v)=diam(G)
Collapsar
9

Die Intuition dahinter ist sehr leicht zu verstehen. Angenommen, ich muss den längsten Pfad finden, der zwischen zwei beliebigen Knoten im angegebenen Baum existiert.

Nach dem Zeichnen einiger Diagramme können wir beobachten, dass der längste Pfad immer zwischen zwei Blattknoten auftritt (Knoten, bei denen nur eine Kante verknüpft ist). Dies kann auch durch den Widerspruch bewiesen werden, dass, wenn der längste Pfad zwischen zwei Knoten liegt und einer oder beide Knoten kein Blattknoten sind, wir den Pfad erweitern können, um einen längeren Pfad zu erhalten.

Eine Möglichkeit besteht darin, zuerst zu überprüfen, welche Knoten Blattknoten sind, und dann BFS von einem der Blattknoten aus zu starten, um den am weitesten von diesem entfernten Knoten zu ermitteln.

Anstatt zuerst herauszufinden, welche Knoten Blattknoten sind, starten wir BFS von einem zufälligen Knoten und sehen dann, welcher Knoten am weitesten davon entfernt ist. Der am weitesten entfernte Knoten sei x. Es ist klar, dass x ein Blattknoten ist. Wenn wir nun BFS mit x starten und den am weitesten entfernten Knoten überprüfen, erhalten wir unsere Antwort.

Aber was ist die Garantie, dass x ein Endpunkt eines maximalen Pfades sein wird?

Schauen wir uns ein Beispiel an:

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

Angenommen, ich habe mein BFS bei 6 gestartet. Der Knoten mit der maximalen Entfernung von 6 ist Knoten 7. Mit BFS können wir diesen Knoten abrufen. Jetzt starten wir BFS von Knoten 7, um Knoten 9 auf maximale Entfernung zu bringen. Der Pfad von Knoten 7 zu Knoten 9 ist eindeutig der längste Pfad.

Was wäre, wenn BFS, das von Knoten 6 aus gestartet wurde, bei maximaler Entfernung 2 als Knoten ergibt? Wenn wir dann BFS von 2 erhalten, erhalten wir 7 als Knoten bei maximaler Entfernung und der längste Pfad ist dann 2-> 1-> 4-> 5-> 7 mit der Länge 4. Die tatsächlich längste Pfadlänge ist jedoch 5. Dies ist nicht möglich passieren, weil BFS von Knoten 6 niemals Knoten 2 als Knoten mit maximaler Entfernung ergibt.

Hoffentlich hilft das.

MayankPratap
quelle
1
Das ist eine einfache und klare Erklärung! Danke :)
Anekix
4

Hier ist ein Beweis, der dem in der ursprünglichen Frage verknüpften MIT-Lösungssatz genauer folgt. Der Klarheit halber werde ich die gleiche Notation verwenden, die sie verwenden, damit der Vergleich einfacher durchgeführt werden kann.

Angenommen, wir haben zwei Eckpunkte und so dass der Abstand zwischen und auf dem Pfad ein Durchmesser ist, z. B. ist der Abstand maximal mögliche Abstand zwischen zwei beliebigen Punkten im Baum. Angenommen, wir haben auch einen Knoten (wenn , dann wäre es offensichtlich, dass das Schema funktioniert, da das erste BFS würde und das zweite zu a zurückkehren würde). Nehmen wir an , dass wir einen Knoten haben derart , dass .b a b pababp(a,b)d(a,b)sa,bs=abud(s,u)=maxxd(s,x)

Lemma 0: Sowohl als auch sind Blattknoten.ab

Beweis: Wenn sie keine Blattknoten wären, könnten wir vergrößern indem wir die Endpunkte auf Blattknoten erweitern, was im Gegensatz dazu steht, dass ein Durchmesser ist.d(a,b)d(a,b)

Lemma 1: .max[d(s,a),d(s,b)]=d(s,u)

Beweis: Nehmen wir zum Zwecke des Widerspruchs an, dass sowohl als auch streng kleiner als . Wir betrachten zwei Fälle:d(s,a)d(s,b)d(s,u)

Fall 1: Pfad enthält keinen Scheitelpunkt . In diesem Fall kann nicht der Durchmesser sein. Um zu sehen, warum, sei der eindeutige Eckpunkt auf mit dem kleinsten Abstand zu . Dann sehen wir, dass , da . In ähnlicher Weise hätten wir auch . Dies widerspricht, dass ein Durchmesser ist.s d ( a , b ) , t p ) + d ( t , b ) , d ( s , u ) > d ( s , bp(a,b)sd(a,b)tp(a,b)sd(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)

Fall 2: Pfad enthält Vertex . In diesem Fall kann wieder nicht der Durchmesser sein, da für einen Scheitelpunkt so dass , sowohl als auch wäre größer als .s d ( a , b )p(a,b)sd(a,b) ud(s,u)=maxxd(s,x)d(a,u)d(b,u)d(a,b)

Lemma 1 gibt den Grund an, warum wir die zweite Breitensuche am zuletzt entdeckten Scheitelpunkt des ersten BFS starten . Wenn der eindeutige Scheitelpunkt mit der größtmöglichen Entfernung von , muss es nach Lemma 1 einer der Endpunkte eines Pfades mit einer Entfernung sein, die dem Durchmesser entspricht, und daher findet ein zweites BFS mit als Wurzel das Durchmesser. Wenn es andererseits mindestens einen anderen Eckpunkt so dass , dann wissen wir, dass der Durchmesser , und es ist egal, ob wir das zweite BFS bei oder starten .u s u v d ( s , v ) = d ( s , u ) d ( a , b ) = 2 d ( s , u ) u vuusuvd(s,v)=d(s,u)d(a,b)=2d(s,u)uv

xdavidliu
quelle
Genial. Vielen Dank für das Posten dieser Antwort. Ich bin überrascht, dass diese Antwort keine Gegenstimmen erhalten hat.
Zephyr
0

Führen Sie zuerst ein DFS von einem zufälligen Knoten aus. Dann ist der Durchmesser eines Baums der Pfad zwischen den tiefsten Blättern eines Knotens in seiner DFS-Unterstruktur: Bildbeschreibung hier eingeben

seddik11
quelle
4
Warum funktioniert das?
Yuval Filmus
0

Nach der Definition von BFS ist die Entfernung (vom Startknoten) jedes erkannten Knotens entweder gleich der Entfernung des vorherigen erkannten Knotens oder um 1 größer. Somit gehört der letzte von BFS erkannte Knoten zu den am weitesten vom Start entfernten Knoten.

Somit Wählen der Algorithmus der Verwendung BFS zweimal beträgt“einen beliebigen Knoten . Finden der Knoten am weitesten von (letzten Knoten durch BFS gefunden von Ausgang ). Findet die Knoten am weitesten von (letzten Knoten gefunden BFS ausgehend von ). ", der somit zwei Knoten maximaler Entfernung voneinander findet.a x xxaxxbaa

Extrarius
quelle
1
Danke für die Antwort mit der Intuition. Das "also" in Ihrem letzten Satz ist jedoch nicht offensichtlich. Warum folgt das? Warum muss der von am weitesten entfernte Knoten einer der beiden Knoten mit maximalem Abstand voneinander sein? Es scheint, dass das einige Beweise braucht. x
DW
Ich bin mir nicht sicher, wie ich einen solchen Beweis konstruieren soll. Ich halte das Gegenteil intuitiv für richtig: Wenn zwei Knoten den größtmöglichen Abstand voneinander haben, ist einer der beiden Knoten für einen bestimmten Knoten so weit wie möglich voneinander entfernt.
Extrarius
Die Behauptung "intuitiv wahr" gilt nicht generell für allgemeine Diagramme. Sehen Sie sich das Diagramm in cs.stackexchange.com/a/213/755 an und stellen Sie sich vor , Sie starten das BFS vom Knoten (dh Sie lassen ). dann wählt es und findet den Knoten in der größten Entfernung von , aber das findet nicht die zwei Knoten mit der maximalen Entfernung voneinander. Wenn die behauptete Aussage wahr ist, muss sie sich auf eine spezielle Eigenschaft von Bäumen stützen, die für allgemeine Graphen nicht gilt. x = v a = u b avx=va=uba
DW
Ja, aber diese Frage gibt ungerichtete Bäume an. Dies ist der Kontext, in dem ich mich gerade vorstelle. Durch das Sperren von Zyklen und gerichteten Kanten lassen sich viele Grafikprobleme erheblich einfacher erklären.
Extrarius
0

Eine wichtige Erkenntnis ist, dass ein Baum immer planar ist, was bedeutet, dass er in einer Ebene angeordnet werden kann, so dass gewöhnliches zweidimensionales Denken oft funktioniert. In diesem Fall sagt der Algorithmus, dass Sie überall starten und so weit wie möglich davon entfernt sein sollen. Die Entfernung von diesem Punkt bis zu dem Punkt, an dem Sie sich befinden, ist die längste Entfernung im Baum und daher der Durchmesser.

Diese Methode würde auch funktionieren, um den Durchmesser einer realen, physischen Insel zu bestimmen, wenn wir diesen als den Durchmesser des kleinsten Kreises definieren würden, der die Insel vollständig einschließen würde.

Alter Pro
quelle
0

@op, die Art und Weise, wie die Fälle in der PDF definiert sind, ist möglicherweise ein bisschen anders.

Ich denke, dass die beiden Fälle sein sollten:

  1. p1 schneidet nicht mit , dh es gibt keine gemeinsamen Eckpunkte zwischen den Pfaden und . Definieren Sie in diesem Fall als den ersten Knoten auf der vom ersten BFS ab erkannt wurde .p2p1p2tp2s

  2. p1 und haben mindestens einen gemeinsamen Scheitelpunkt. In diesem Fall definieren Sie als den ersten Knoten auf der von dem ersten BFS erkannt wurde, der sich ebenfalls auf .p2tp2p1

Der Rest des Proofs im PDF sollte folgen.

Mit dieser Definition fällt die von OP gezeigte Zahl in Fall 2.

user650654
quelle