Dowód poprawności algorytmu zachłannego dla minimalnego pokrycia wierzchołka drzewa

14

Istnieje chciwy algorytm znajdowania minimalnego pokrycia wierzchołka drzewa, które korzysta z przejścia DFS.

Dla każdego liścia drzewa wybierz jego element nadrzędny (tzn. Jego element nadrzędny znajduje się w minimalnej osłonie wierzchołków).
Dla każdego węzła wewnętrznego:
jeśli nie zostanie wybrane żadne z jego elementów podrzędnych, wybierz ten węzeł.

Jak udowodnić, że ta chciwa strategia daje optymalną odpowiedź? Czy nie ma pokrywy wierzchołków mniejszej niż ta, którą wytwarza powyższy algorytm?

algorithms trees greedy-algorithms

— e_noether
źródło

Nie sądzę, aby logika drugiego kroku była poprawna. Jeśli weźmiesz pod uwagę zdegenerowane drzewo z 6 węzłami idącymi w dół do końca w prawo (oznacz je jako 1-6 odpowiadające ich głębokości). Następnie pierwszy krok algorytmu wybierze węzeł 5. Drugi krok prawdopodobnie wybierze pierwszy węzeł (root), a następnie drugi węzeł (child) LUB trzeci węzeł. Jest to jednak niepoprawne, ponieważ chcesz wybrać tylko węzeł 2 i 5, aby uzyskać prawidłowe rozwiązanie.

— miguel.martin

@ miguel.martin Jeśli osłona wierzchołków zawiera tylko wierzchołki o numerach 2 i 5, krawędź między węzłami 3 i 4 nie zostanie pokryta.

— Laschet Jain

11

$C$ $C$ $X$ $X$ $X$

$C$ $C$ $C$

— A.Schulz
źródło

4

$|M| \leq |C|$ $M$ $C$

— Yuval Filmus
źródło