Pewarnaan graf

PEWARNAAN GRAF

1.    Latar belakang

            Indonesia memilki banyak universitas, baik yang negeri maupun swasta. Universitas ini dijadikan oleh pemuda-pemudi Indonesia sebagai tempat untuk menuntut ilmu yang lebih tinggi yang sering orang menyebutnya adalah perkuliahan. Dalam perkuliahan ini pasti ada yang namanya mata kuliah. Mata kuliah inilah yang membuat seorang mahasiswa beraktivitas dikampus, namun sering kita lihat permasalahan dalam penyusunan jadwal kuliah seperti pada waktu dan ruangan yang sering terjadi benturan antara kelas dan semester yang lain. Oleh karena itu, penjadwalan kuliah harus di susun denbgan baik agar tidak terjadi tabrakan jadwal baik dalam hal ruangan maupun waktu.

            Salah satu cabang teori graf yang digunakan untuk menyelesaikan masalah ini adalah dengan menggunakan pewarnaan graf (graph coloring). Pewarnaan graf yaitu pemberian warna pada elemen graf yang akan dijadikan subjeck dalam memahami suatu permasalaha . Contohnya pewarnaan graf dalam permasalahan penyusunan jadwal kuliah di kampus khusus di masing-masing jurusan. Ada 3 hal yang harus diperhatikan salam pewarnaan graf yaitu :

·         Pewarnaan titik (vertex)

·         Pewarnaan sisi (edge)

·         Pewarnaan wilayah (region)

2.    Tujuan

            Tujuan dari pewarnaan graf adalah untuk memudahkan dalam menyusun suatu jadwal perkuliahan dimasing-masing jurusan di kampus tertentu agar tidak terjadi tabrakan jadwal perkuliahan seperti waktu dan ruangan. Karena, sering kita lihat bahwa seringt sekali terjadi tabrakan jadwal perkuliaahn yang mengakibatkan mahasiswa menjadi kesuliatan untuk beraktivitas dikampus. Selain itu pewarnaan graf juga bisa untuk hal lainnya seperti jadwal ujian, jadwal pelajaran disekolah, jadwal jam kerja dan sebagainya.

            Maka dari itu dilakukanlah pewarnaan graf sehingga penygusunan jadwal kuliah, jadwal ujian, penyusunan jam kerja dan sebagainya tersusun rapid an berwarna menarik.

3.    Langkah-langkah pewarnaan graf

            Sebelumnya kita bisa melihat dari

Dan inilah langkah-langkah yang legih lengkap lagi :

Ø  Mengumpulkan data seperti data penjadwalan kulia, ruang kuliahdan sebagainya.

Ø  Mengelompokkan data seperti : penjadwalan mata kuliah yang terdiri atasa mata pelajaran dan kelas.

Ø  Setelah mengumpulkan data dan mengelompokkannya, kita dapat membuat data tersebut dalam bentuk graf. Contoh : penjadwalan mata kuliah.

Ø  Lalu kita dapat melakukan pewarnaan pada graf tersebut. Dengan memperhatikan langkah-langkah berikut :

(pewarnaan pada busur)

a.       Urutkan semua titik dari yang terbesar hingga terkecil

b.      Cari titik dengan drajat terbesar

c.       Beri warna pertama pada salah satu busur di titik tersebut.

d.      Untuk busur kedua pada titik yang sama carilah warna yang berbeda dengan kata lain setiap yang bersisian warna harus berbeda.

e.       Lalu kita lihat pada titik yang lain jika busur tidak bersisian dengan titik pertama maka busur itu boleh diberi warna yang sama seperti warna pada busur dititik pertama.

f.        Lalku hitung bilangan kromatinnya.

(pewarnaan pada simpul)

a.       Buatlah data dalam bentuk table supaya gampang dalam melihat ketetanggaannya

b.      Urutkan semua titik dari yang terbesar hingga terkecil

c.       Cari titik dengan drajat terbesar

d.      Cari simpul yang tidak bertetangga dengan simpul lain lalku beri warna yang sama dengan simpul yang pertama jika bertetangga beri warna yang berbeda dengan simpul pertama.

e.       Laku pilih, drajat terbesar dari yang ke dua setelah yang pertama.

f.        Selanjutnya lakukan seperti langkah yang diatas hingga drajat yang paling sedikit.

g.       Setelah itu tentukan nilai kromatinnya.

4.       Contoh :

Contoh 1 (menetukan jadwal kuliah antara mata kuliah ,kelas dan ruangan pada hari senin )

Note : contoh 1 ini dengan busur yang diwarnai