Korrektheitsnachweis eines Greedy-Algorithmus für minimale Vertexbedeckung eines Baumes

14

Es gibt einen gierigen Algorithmus zum Ermitteln der minimalen Scheitelpunktabdeckung eines Baums, der DFS-Traversal verwendet.

  1. Wählen Sie für jedes Blatt des Baums das übergeordnete Element aus (dh das übergeordnete Element befindet sich in der minimalen Scheitelpunktabdeckung).
  2. Für jeden internen Knoten:
    Wenn einer seiner untergeordneten Knoten nicht ausgewählt ist, wählen Sie diesen Knoten aus.

Wie beweise ich, dass diese gierige Strategie eine optimale Antwort gibt? Dass es keine Scheitelpunktabdeckung gibt, die kleiner ist als die, die der obige Algorithmus erzeugt?

algorithms trees greedy-algorithms e_noether
quelle
Ich denke nicht, dass die Logik für den 2. Schritt richtig ist. Wenn Sie einen entarteten Baum mit 6 Knoten betrachten, die ganz nach rechts abfallen (beschriften Sie sie mit 1-6 entsprechend ihrer Tiefe). Im ersten Schritt Ihres Algorithmus wird dann Knoten 5 ausgewählt. Im zweiten Schritt wird möglicherweise der erste Knoten (Root) und dann der zweite Knoten (Child) ODER der dritte Knoten ausgewählt. Dies ist jedoch falsch, da Sie nur Knoten 2 und Knoten 5 für eine korrekte Lösung auswählen möchten.
Miguel.Martin
@ miguel.martin Wenn die Scheitelpunktabdeckung nur die Scheitelpunkte 2 und 5 enthält, wird die Kante zwischen Knoten 3 und 4 nicht abgedeckt.
Laschet Jain

Antworten:

11

Wir beobachten zunächst Folgendes: Es gibt eine optimale Abdeckung , und in C befindet sich kein Blatt . Dies ist der Fall, da Sie in jeder optimalen Abdeckung X alle Blätter in X durch ihre Eltern ersetzen können und eine Scheitelabdeckung erhalten, die nicht größer als X ist .CCXXX

CCC

A.Schulz
quelle
4

|M|≤|C|MC

Yuval Filmus
quelle