Latihan 5.

Suatu himpunan simpul \(A \subseteq V\) disebut penutup simpul jika setiap sisi graf bersisian dengan suatu simpul dalam penutup tersebut (jadi, penutup simpul menutupi sisi-sisi). Karena \(V\) sendiri merupakan penutup simpul, setiap graf memiliki penutup simpul. Pertanyaan yang menarik adalah bagaimana menemukan penutup simpul minimum, yaitu penutup yang menggunakan sesedikit mungkin simpul.
  1. Misalkan Anda memiliki suatu pencocokan pada sebuah graf. Bagaimana pencocokan itu dapat digunakan untuk memperoleh penutup simpul minimum? Apakah metode Anda selalu berhasil?
  2. Misalkan Anda memiliki penutup simpul minimum untuk suatu graf. Bagaimana penutup tersebut dapat digunakan untuk memperoleh pencocokan parsial? Apakah metode Anda selalu berhasil?
  3. Apakah hubungan antara ukuran penutup simpul minimum dan ukuran pencocokan parsial maksimum dalam suatu graf?
dalam konteks