Gunakan teknik-teknik dalam bab ini untuk mencari pencocokan maksimum dari \(V_1\) ke \(V_2\) dalam graf pada Gambar 14.11. Simpul-simpul di bagian bawah membentuk himpunan \(V_1\text{,}\) sedangkan simpul-simpul di bagian atas membentuk himpunan \(V_2\text{.}\) Jika Anda tidak dapat menemukan pencocokan yang menjenuhkan semua simpul dalam \(V_1\text{,}\) jelaskan alasannya.
Gunakan teknik-teknik dalam bab ini untuk mencari pencocokan maksimum dari \(V_1\) ke \(V_2\) dalam graf pada Gambar 14.12. Simpul-simpul di bagian bawah membentuk himpunan \(V_1\text{,}\) sedangkan simpul-simpul di bagian atas membentuk himpunan \(V_2\text{.}\) Jika Anda tidak dapat menemukan pencocokan yang menjenuhkan semua simpul dalam \(V_1\text{,}\) jelaskan alasannya.
Para mahasiswa sedang mempersiapkan proyek akhir untuk mata kuliah kombinatorika terapan. Lima topik yang tersedia bagi proyek akhir mereka adalah algoritma graf, poset, induksi, teori graf, dan fungsi pembangkit. Kelas ini terdiri atas lima mahasiswa, dan masing-masing telah memberikan kepada dosen daftar topik yang bersedia mereka kerjakan. Alice tertarik pada poset atau graf. Bob bersedia mengerjakan proyek tentang algoritma graf, poset, atau induksi. Carlos hanya mempertimbangkan poset atau graf. Dave menyukai fungsi pembangkit dan induksi. Yolanda ingin mengerjakan proyek tentang graf atau poset. Untuk mencegah kolaborasi tanpa izin, dosen tidak ingin dua mahasiswa mengerjakan topik yang sama. Dapatkah setiap mahasiswa diberi satu topik dari daftar di atas sehingga tidak ada dua mahasiswa yang mengerjakan proyek yang sama? Jika dapat, carilah penugasan semacam itu. Jika tidak, carilah penugasan yang memaksimumkan jumlah mahasiswa yang memperoleh topik dari daftar mereka dan jelaskan mengapa semua permintaan mahasiswa tidak dapat dipenuhi.
Tujuh perguruan tinggi bersaing merekrut enam pemain sepak bola dari sekolah menengah untuk bergabung dengan tim universitas mereka. Setiap perguruan tinggi hanya boleh menerima satu pemain tambahan, dan setiap pemain hanya boleh berkomitmen kepada satu perguruan tinggi. Tabel di bawah mencantumkan ketujuh lembaga beserta siswa-siswa yang ingin mereka rekrut, yang telah diterima, dan yang juga berminat bermain bagi perguruan tinggi tersebut. (Tidak ada gunanya menugaskan kepada suatu perguruan tinggi pemain yang tidak memenuhi persyaratan akademik atau tidak ingin bergabung dengan timnya.) Para pemain diidentifikasi dengan bilangan bulat \(1\) sampai \(6\text{.}\) Carilah cara menugaskan para pemain kepada perguruan tinggi yang memaksimumkan jumlah perguruan tinggi yang menerima salah satu dari keenam pemain.
Pertanyaan-pertanyaan dalam latihan ini merujuk pada diagram jaringan dalam Gambar 14.13. Jaringan ini bersesuaian dengan poset \(\bfP\text{.}\) Seperti biasa, semua kapasitas diasumsikan bernilai \(1\) dan semua sisi diarahkan ke atas. Jawablah pertanyaan berikut tentang \(\bfP\)tanpa menggambar diagram poset.
Elemen mana saja yang lebih besar daripada \(x_1\) dalam \(\bfP\text{?}\)
Gunakan metode yang dikembangkan dalam bab ini untuk mencari lebar \(w\) dari poset yang bersesuaian dengan jaringan dalam Gambar 14.13. Carilah pula antirantai berukuran \(w\) dan partisi menjadi \(w\) rantai.
Pada Gambar 14.14 ditampilkan poset \(\bfP\) dan jaringan yang digunakan untuk mencari partisi rantai dari \(\bfP\text{.}\) (Semua sisi jaringan berkapasitas \(1\) dan diarahkan dari bawah ke atas. Sisi-sisi tebal saat ini membawa aliran sebesar \(1\text{.}\)) Dengan menggunakan jaringan tersebut, carilah lebar \(w\) dari \(\bfP\text{,}\) partisi \(\bfP\) menjadi \(w\) rantai, dan antirantai dengan \(w\) elemen.
Gambarlah jaringan yang bersesuaian dengan poset \(\bfP\) pada Gambar 14.15. Gunakan jaringan tersebut untuk mencari lebar \(w\) dari \(\bfP\text{,}\) partisi menjadi \(w\) rantai, dan antirantai berukuran \(w\text{.}\)
