Aplikasi
pewarnaan titik pada graph
Pewarnaan titik pada graph dapat diaplikasi keberbagai
bidang, diantaranya :
1. Penjadwalan
ujian.
Persoalan yang mempunyai
karakteristik seperti pewarnaan graph adalah persoalan menentukan jadwal ujian.
Misalkan terdapat delapan orang mahasiswa (1,
2, 3, . . ., 8) dan lima mata kuliah yang
dipilihnya (A, B,
C, D, E). Tabel
berikut memperlihatkan matriks lima mata kuliah dan delapan orang mahasiswa.
Angka 1 pada elemen (i,j) berarti mahasiswa i memilih mata kuliah j, sedangkan
angka 0 menyatakan mahasiswa i tidak memilih mata kuliah j.
Berdasarkan tabel
tadi, administatur mata kuliah ingin
menentukan jadwal ujian sedemikian sehingga semua mahasiswa dapat mengikuti
ujian mata kuliah yang diambilnya tanpa bertabrakan waktunya dengan jadwal
ujian kuliah lain yang juga diambilnya. Pendek kata, jika ada mahasiswa yang
mengambil dua buah mata kuliah atau lebih, jadwal ujian mata kuliah tersebut
harus pada waktu yang tidak bersamaan. Ujian dua mata kuliah dapat dijadwalkan
pada waktu yang sama jika tidak ada mahasiswa yang sama yang mengikuti ujian
dua mata kuliah itu. Berapa paling sedikit jumlah hari yang dibutuhkan untuk
jadwal ujian tersebut?
Penyelesaian
:
Penyelesaian
persoalan menentukan jadwal ujian semua mata kuliah sama dengan menentukan
bilangan kromatik suatu graph. Kita dapat menggambarkan graph yang menyatakan
penjadwalan ujian, dengan titik – titik pada graph menyatakan mata kuliah
sedangkan sisi yang menghubungkan dua titik pada graph menyatakan ada mahasiswa
yang memilih kedua mata kuliah itu.
Persoalan di atas dapat
dinyatakan dalam bentuk graph seperti di bawah ini :
Bilangan kromatik
dari graph di atas adalah 2. Jadi jumlah hari yang paling sedikit dibutuhkan untuk jadwal ujian lima mata
kulaih untuk delapan orang mahasiswa tersebut adalah 2 hari.
2. Penempatan
bahan – bahan kimia secara efisien
Ada enam jenis zat kimia
yang perlu di simpan di dalam gudang. Beberapa pasang dari zat itu tidak dapat
disimpan di dalam ruangan yang sama, karena campuran gasnya bersifat eksplosif
(mudah meledak). Utnuk zat yang semacam itu perlu dibangun ruang – ruang yang
terpisah yang dilengkapi ventilasi dan penyedot udara keluar yang berlainan.
Jika lebih banyak ruangan yang dibutuhkan, berarti lebih banyak ongkos yang
harus dikeluarkan karena itu perlu diketahui berapa banyak minimum ruangan yang
diperlukan untuk dapat menyimpan semua zat kimia dengan aman. Berikut ini
adalah daftar pasangan zat kimia yang tidak dapat disimpan di dalam ruangan
yang sama.
Penyelesaian
:
Graph dari tabel di atas
adalah:
Keterangan :
Titik menyatakan zat
kimia dan sisi yang menghubungkan dua zat kimia yang tidak boleh terletak dalam
satu ruangan.
Bilangan kromatik dari graph
di atas adalah 3, berarti dibutuhkan banyak ruangan minimum untuk menyimpan
enam zat kimia pada soal di atas adalah sebanyak 3 ruangan.
