Nachweis der Richtigkeit:Algorithmus für den Durchmesser eines Baumes in der Graphentheorie

StackOverflow https://stackoverflow.com//questions/20010472

Frage

Um den Durchmesser eines Baums zu ermitteln, kann ich einen beliebigen Knoten aus dem Baum nehmen, BFS durchführen, um einen Knoten zu finden, der am weitesten von ihm entfernt ist, und dann BFS für diesen Knoten ausführen.Der größte Abstand vom zweiten BFS ergibt den Durchmesser.

Ich bin mir allerdings nicht sicher, wie ich das beweisen soll?Ich habe versucht, Induktion über die Anzahl der Knoten anzuwenden, aber es gibt zu viele Fälle.

Für alle Ideen wäre ich sehr dankbar ...

War es hilfreich?

Lösung

Lassen Sie uns den von der ersten BFS X gefundenen Endpunkt aufrufen. Der entscheidende Schritt beweist, dass das in diesem ersten Schritt gefundene X immer "arbeitet" - das heißt, dass es immer an einem Ende eines längsten Weges ist. (Beachten Sie, dass es im Allgemeinen mehr als einen gleich längsten Pfad geben kann.) Wenn wir dies etablieren können, ist es unkompliziert, zu sehen, dass ein von X verwurzelter BFS einen Knoten, der von x möglich ist, ein Knoten findet, der daher ein Gesamtzahl ist längster Pfad.

Hinweis: Angenommen (im Gegenteil), dass ein längerer Weg zwischen zwei Scheitelpunkten u und v ist, von denen keiner X ist.

Beobachten Sie, dass auf dem einzigartigen Pfad zwischen U und V ein bisschen am höchsten sein muss (am nächsten zum Wurzel) Scheitelpunkt h. Es gibt zwei Möglichkeiten: entweder h steht auf dem Pfad von der Wurzel der BFS bis X oder nicht. Zeigen Sie einen Widerspruch, indem Sie zeigen, dass der U-V-Pfad in beiden Fällen mindestens so lang gemacht werden kann, indem er ein paar Pfadsegment darin mit einem Pfad zu X ersetzt.

[edit] eigentlich ist es möglicherweise nicht notwendig, die 2 Fälle doch separat zu behandeln. Aber ich finde es oft einfacher, eine Konfiguration in mehrere (oder sogar viele) Fälle zu brechen und jeden separat zu behandeln. Hier ist der Fall, in dem H auf dem Pfad von der BFS-Wurzel bis X auf dem Pfad ist, leichter zu handhaben, und gibt einen Hinweis für den anderen Fall.

[edit 2] zum späteren zurückkommt, scheint mir jetzt, dass die beiden Fälle, die berücksichtigt werden müssen, dass (i) der UV-Pfad den Pfad von der Wurzel auf X schneidet ( bei einigen vertex y, nicht unbedingt an dem höchsten Punkt der UV-Bahn H); und (ii) es nicht. Wir brauchen immer noch H, um jeden Fall zu beweisen.

Andere Tipps

Ich werde trainieren j_random_hackers Hinweis.Lassen s, t ein maximal entferntes Paar sein.Lassen u sei der beliebige Scheitelpunkt.Wir haben einen Schaltplan wie

    u
    |
    |
    |
    x
   / \
  /   \
 /     \
s       t ,

Wo x ist die Kreuzung von s, t, u (d. h.der eindeutige Scheitelpunkt, der auf jedem der drei Pfade zwischen diesen Scheitelpunkten liegt).

Nehme an, dass v ist ein Scheitelpunkt, der maximal entfernt ist u.Wenn der Schaltplan jetzt so aussieht

    u
    |
    |
    |
    x   v
   / \ /
  /   *
 /     \
s       t ,

Dann

d(s, t) = d(s, x) + d(x, t) <= d(s, x) + d(x, v) = d(s, v),

wo die Ungleichung gilt, weil d(u, t) = d(u, x) + d(x, t) Und d(u, v) = d(u, x) + d(x, v).Es gibt einen symmetrischen Fall, in dem v hängt dazwischen s Und x statt dazwischen x Und t.

Der andere Fall sieht so aus

    u
    |
    *---v
    |
    x
   / \
  /   \
 /     \
s       t .

Jetzt,

d(u, s) <= d(u, v) <= d(u, x) + d(x, v)
d(u, t) <= d(u, v) <= d(u, x) + d(x, v)

d(s, t)  = d(s, x) + d(x, t)
         = d(u, s) + d(u, t) - 2 d(u, x)
        <= 2 d(x, v)

2 d(s, t) <= d(s, t) + 2 d(x, v)
           = d(s, x) + d(x, v) + d(v, x) + d(x, t)
           = d(v, s) + d(v, t),

Also max(d(v, s), d(v, t)) >= d(s, t) durch ein Durchschnittsargument, und v gehört zu einem maximal entfernten Paar.

Hier ist eine alternative Möglichkeit, es anzusehen:

vermuten g = ( v , e ) ist ein nicht leerer, endlicher Baum mit Scheitelpunkt v und randset e .

Betrachten Sie den folgenden Algorithmus:

    .
  1. lass count = 0. Lassen Sie alle Kanten in e zunächst färbelt. Lassen Sie c zunächst gleich v sein.
  2. Betrachten Sie die Subset v 'von v , die alle Scheitelpunkte mit genau einem unbefristelten Rand enthält:
    • Wenn v 'leer ist, dann lassen Sie d = count * 2 und stoppt. .
    • Wenn v 'genau zwei Elemente enthält, dann färben Sie ihre gegenseitige (färbte) Kantegrün, lassen Sie d = count * 2 + 1 und stoppt.
    • Ansonsten, v enthält mindestens drei Scheitelpunkte; Gehen Sie wie folgt vor:
  3. inkrementieren count um eins.
  4. Entfernen Sie alle Scheitelpunkte von c , die keine farblosen Kanten haben.
  5. Für jeden Scheitelpunkt in v mit zwei oder mehr farblosen Kanten, wieder färben Sie jedes seiner grünen Kanten rot (einige Scheitelpunkte können keine solchen Kanten aufweisen).
  6. für jeden Scheitelpunkt in v ', färben Sie seine farbige Randgrün.
  7. Rückkehr zu Schritt (2).

    8. das grundsätzlich den Graphen aus den Blättern nach innen färbt, Markierungspfade mit maximaler Entfernung zu einem Blatt in grün und markieren diese mit nur kürzeren Abständen in Rot. Inzwischen sind die Knoten von c , der Mitte, mit kürzeren maximalen Abstand zu einem Blatt weg, bis c enthält nur die ein oder zwei Knoten mit dem größten maximalen Abstand zu einem Blatt.

    Durch die Konstruktion sind alle einfachen Wege von Blattscheitelpunkten zu ihrem nächstgelegenen Mitte-Scheitelpunkt, der nur grüne Kanten durchqueren, die gleiche Länge ( count ) und alle anderen einfachen Wege von einem Blattscheitelpunkt in sein nächstgelegenes Zentrum Scheitelpunkt (durchqueren mindestens eine rote Kante) sind kürzer. Es kann außerdem bewiesen werden, dass

    • Dieser Algorithmus endet immer unter den gegebenen Bedingungen, wobei jede Kante von g entweder rot oder grün gefärbt ist und c verließ mit einem oder zwei Elementen.
    • Bei Algorithmus-Terminierung ist d der Durchmesser von g , gemessen in Kanten.
    • gegeben einen Scheitelpunkt v in v , die einfachen maximal langen einfachen pfade in g < / Stark> Beginnen Sie bei v sind genau diejenigen, die alle Scheitelpunkte der Mitte enthalten, an einem Blatt enden und nur grüne Kanten zwischen der Mitte und dem fernen Endpunkt durchqueren. Diese gehen von v , über die Mitte, an einem der Blätter, die am weitesten vom Zentrum entfernt sind.

    Betrachten Sie nun Ihren Algorithmus, der in Anbetracht der oben genannten praktischer ist. Ausgehend von jedem Scheitelpunkt v gibt es genau einen einfachen Pfad p von diesem Scheitelpunkt, der an einem mittleren Scheitelpunkt endet und alle Scheitelpunkte enthält Zentrum (weil g ein Baum ist, und wenn es zwei Scheitelpunkte in c gibt, teilen sie dann einen Rand) . Es kann gezeigt werden, dass die maximalen einfachen Pfade in g mit v als ein Endpunkt mit allen die Form der Union von p mit einem einfachen Pfad von der Mitte des Blattes, das nur grüne Kanten durchquert.

    Der Schlüsselpunkt für unsere Zwecke ist, dass der ankommende Rand des anderen Endpunkts notwendigerweise grün ist. Wenn wir also eine Suche nach den längsten von dort beginnenden Wegen durchführen, haben wir Zugang zu denjenigen, die nur grüne Kanten von Blatt über (alle Scheitelpunkte von) des Zentrums zu einem anderen Blatt durchqueren. Das sind genau die maximalen einfachen Pfade in g , so dass wir zuversichtlich sein können, dass die zweite Suche tatsächlich den Diagrammdurchmesser enthüllen wird.

1:procedureTreeDiameter(T)

2:pick an arbitrary vertex v where v∈V

3:u = BFS ( T, v )

4:t = BFS ( T, u )

5:return distance ( u, t )

Result: Complexity = O(|V|)

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top