Correctness-Proof dari greedy-algorithm untuk minimum vertex cover dari pohon

14

Ada algoritma serakah untuk menemukan tutupan simpul minimum pohon yang menggunakan traversal DFS.

  1. Untuk setiap daun pohon, pilih induknya (mis. Induknya berada dalam penutup simpul minimum).
  2. Untuk setiap simpul internal:
    jika ada dari anak-anaknya yang tidak dipilih, maka pilih simpul ini.

Bagaimana saya membuktikan bahwa strategi serakah ini memberikan jawaban yang optimal? Bahwa tidak ada penutup simpul yang lebih kecil daripada yang dihasilkan algoritma di atas?

algorithms trees greedy-algorithms e_noether
sumber
Saya tidak berpikir logika untuk langkah ke-2 benar. Jika Anda menganggap pohon degenerasi dengan 6 node turun sepenuhnya (beri label 1-6 sesuai dengan kedalamannya). Kemudian langkah pertama dari algoritma Anda akan memilih simpul 5. Langkah kedua kemudian akan mungkin memilih simpul pertama (root) dan kemudian simpul kedua (anak) ATAU simpul ketiga. Namun, ini tidak benar karena Anda hanya ingin memilih simpul 2 dan simpul 5 untuk solusi yang benar.
miguel.martin
@ miguel.martin Jika Penutup Vertex hanya berisi simpul bernomor 2 dan 5, tepi antara simpul 3 dan 4 tidak akan dibahas.
Laschet Jain

Jawaban:

11

CCXXX

CCC

A.Schulz
sumber
4

|M.|≤|C|M.C

Yuval Filmus
sumber