Hapus simpul sampai tidak ada tepi yang tersisa
Diberikan grafik yang tidak berarah G (V, E), temukan jumlah minimum dari simpul yang akan dihilangkan sehingga Kumpulan Tepi dari grafik menjadi kosong.
Dengan kata lain: Jika kita menghapus satu simpul kita menghapus simpul itu bersama dengan semua sisi yang terhubung ke simpul itu. Tentukan jumlah minimum simpul yang akan dihapus sehingga tidak ada sisi yang tersisa di G setelah penghilangannya.
Jawaban
Sepertinya Anda menemukan jawabannya sendiri, Anda menjelaskan Vertex Cover , yang dalam banyak hal sangat mirip dengan Set Independen, kedua soal tersebut NP-complete .
Hubungan dengan Himpunan Independen adalah dalam grafik $G = (V,E)$, satu set $S$ adalah penutup simpul minimal jika dan hanya jika $V \setminus S$ adalah himpunan independen maksimal.
Jika Anda mengetahui bahwa Set Independen adalah NP-complete, maka Vertex Cover juga NP-complete.
Dengan kata lain, Anda juga mencari Set Independen maksimum.
Penutup simpul . Diberikan grafik$G = (V,E)$ dan bilangan bulat $k$, apakah ada satu set $S \subseteq V$ dari ukuran paling banyak $k$ sedemikian rupa sehingga semua tepinya masuk $G$ bersisian dengan simpul di $S$?
Set independen . Diberikan grafik$G = (V,E)$ dan bilangan bulat $k$, apakah ada satu set $S \subseteq V$ ukuran setidaknya $k$sedemikian rupa sehingga grafik yang diinduksi $G[S]$ tidak memiliki tepian?