APLIKASI PEWARNAAN TITIK PADA GRAPH

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. 

Browse More Articles

Tweet

Written by blog basori alawi

We are Creative Blogger Theme Wavers which provides user friendly, effective and easy to use themes. Each support has free and providing HD support screen casting.