Latihan 7.
Kedua masalah berikut dapat diselesaikan dengan menggunakan pewarnaan graf. Untuk setiap masalah, representasikan situasinya dengan graf, nyatakan apakah Anda perlu mewarnai simpul atau sisi beserta alasannya, lalu gunakan pewarnaan tersebut untuk menyelesaikan masalah.
(a)
Liga Quidditch Anda memiliki 5 tim. Minggu depan akan diadakan turnamen yang mempertemukan setiap tim dengan setiap tim lainnya tepat satu kali. Setiap tim hanya dapat memainkan paling banyak satu pertandingan per hari, tetapi tersedia cukup waktu dalam sehari untuk mengadakan beberapa pertandingan. Berapa harikah waktu paling singkat yang diperlukan untuk menyelenggarakan turnamen tersebut?
Petunjuk.
Representasikan tim sebagai simpul dan pertandingan sebagai sisi. Manakah yang lebih tepat untuk diwarnai?
(b)
Sepuluh anggota Klub Matematika akan berkendara ke sebuah konferensi matematika di negara bagian tetangga. Namun, beberapa siswa tersebut pernah berpacaran dan hubungan mereka masih agak canggung. Setiap siswa mencantumkan siswa lain yang tidak bersedia berbagi mobil dengannya; konflik-konflik tersebut dicatat dalam tabel berikut. Berapakah jumlah mobil paling sedikit yang diperlukan klub untuk melakukan perjalanan itu? Abaikan keterbatasan jumlah tempat duduk; cukup hindari konflik yang ada.
| Siswa: | A | B | C | D | E | F | G | H | I | J |
| Konflik: | BEJ | ADG | HJ | BF | AI | DJ | B | CI | EHJ | ACFI |