matematika diskrit - pewarnaan graf

Kata Pengantar.

Puji syukur saya ucapkan kepada Allah swt. Karena atas ijinnya Akhirnya saya dapat menyelesaikan tugas makalah matematika diskrit “ Pewarnaan Graf” dengan tepat waktu. Matematika diskrit merupakan mata kuliah yang fundamental dalam pendidikan ilmu komputer atau teknik informatika. Saat ini matematika diskrit merupakan mata kuliah wajib pada program pendidikan yang termasuk ke dalam kelompok teknologi informasi. Makalah ini membahas tentang materi matematika diskrit yaitu pewarnaan graf. Graf sangat erat kaitannya dengan kehidupan sehari-hari kita. Misalnya pada sebuah peta yg menggambarkan suatu daerah yg di dalamnya banyak terdapat objek-objek diskrit, dimana kita dapat menggambarkan dengan baik agar lebih mudah di pahami oleh pengguna peta dengan menggunakan metode graf , pewarnaan graf dalam pengaturan warna lampu lalu lintas di perempatan jalan sehingga mencegah terjadinya tabrakan di perempatan jalan tersebut, penyusunan jadwal matakuliah,jadwal shift kerja dan masih banyak persoalan-persoalan unik lain yg dapat kita selesaikan dengan metode graf. Saya menyadari bahwa makalah ini masih jauh dari sempurna, mungkin terdapat kesalahan-kesalahan. Koreksi, saran perbaikan,keritik membangun sangat saya harapkan.
 
I. PENDAHULUAN
Teori graf merupakan pokok bahasan yang sudah tua usianya namun memiliki banyak terapan sampai saat ini. Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graf adalah dengan menyatakan objek dinyatakan sebagai noktah, bulatan, atau titik, sedangkan hubungan antara objek dinyatakan dengan garis. Graf G didefinisikan sebagai pasangan himpunan (V, E), yang dalam hal ini : V = himpunan tidak-kosong dari simpul-simpul (vertices atau node) = {v1,v2,…,vn}
dan
E = himpunan sisi (edges atau arcs) yang menghubungkan sepanjang simpul = {e1,e2,…,en}
Atau dapat ditulis singkat notasi G = (V, E). definisi tersebut menyatakan V tidak boleh kosong, sedangkan E boleh kosong. Jadi sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada, minimal satu. Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Secara geometri, graf bisa digambarkan seperti contoh berikut :

Gambar 1. Contoh graf
Pada gambar diatas, sisi e3 = (1,3) dan sisi e4 = (1,3) dinamakan sisi-ganda (multiple edges atau parallel edges) karena kedua sisi tersebut menghubungkan dua simpul yang sama, yaitu simpul 1 dan simpul 3. Sedangkan sisi e8 = (3,3) dinamakan sisi gelang atau kalang (loop) karena ia berawal dan berakhir pada simpul yang sama. Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf dapat digolongkan menjadi dua jenis, yaitu graf sederhana dan graf tak-sederhana.
Graf sederhana adalah graf yang tidak mengandung gelang maupun sisi-ganda.

Gambar 2. Contoh graf sederhana
Sedangkan graf tak-sederhana adalah graf yang mengandung sisi ganda atau gelang. Ada dua jenis graf-tak-sederhana, yaitu graf ganda (multigraph) dan graf semu (pseudograph). Graf ganda adalah graf yang mengandung sisi ganda. Graf semu adalah graf yang mengandung gelang termasuk jika mempunyai sisi ganda pada graf tersebut. Graf pada Gambar 1 merupakan salah satu contoh graf semu. Gambar di bawah ini adalah graf ganda.

Gambar 3. Contoh graf ganda
Berikut ini beberapa terminologi dasar yang menyangkut tentang graf :

1. Bertetangga
Dua buah simpul pada graf tak berarah G dikatakan bertetangga bila keduanya terhubung langsung dengan sebuah sisi pada graf G.
2. Bersisian
Untuk sembarang sisi e = (vj,vk), sisi e dikatakan bersisian dengan simpul vj dan simpul vk. 3. Simpul Terpencil
Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian dengannya. Atau, dapat juga simpul terpencil adalah simpul yang tidak satupun bertetangga dengan simpul-simpul lainnya. 4. Graf Kosong
Graf kosong adalah graf yang himpunan sisinya merupakan himpunan kosong. Dan ditulis sebagai Nn, yang dalam hal ini n adalah jumlah simpul. 5. Derajat
Derajat suatu simpul pada graf tak berarah adalah jumlah sisi yang bersisian dengan simpul tersebut. 6. Lintasan
Lintasan yang panjangnya n dan simpul awal v0 ke simpul tujuan vn di dalam graf G ialah barisan selang-seling simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1, e2, v2, … , vn-1, en, vn sedemikian sehingga i1 = (v0,v1), e2 = (v1,v2), … , en = (vn-1,vn), adalah sisi – sisi dari graf G. 7. Siklus atau Sirkuit
Lintasan yang berawal dan berakhir pada simpul yang sama disebut siklus atau sirkuit. 8. Terhubung
Graf tak berarah G disebut graf terhubung jika untuk setiap pasang simpul u dan v di dalam himpunan V terdapat lintasan dari u ke v.
II. PEWARNAAN GRAF
Pewarnaan graf (graph coloring) adalah kasus khusus dari pelabelan graf. Pelabelan disini maksudnya, yaitu memberikan warna pada titik-titik pada batas tertentu. Ada tiga macam pewarnaan graf :
1. Pewarnaan simpul
Pewarnaan simpul (vertex coloring) adalah member warna pada simpul-simpul suatu graf sedemikian sehingga tidak ada dua simpul bertetangga mempunyai warna yang sama.

Gambar 4. Contoh pewarnaan simpul
2. Pewarnaan sisi
Pewarnaan sisi (edge coloring) adalah memberi warnaberbeda pada sisi yang bertetangga sehingga tidak ada dua sisi yang bertetangga mempunyai warna yang sama.

Gambar 5. Contoh pewarnaan sisi
3. Pewarnaan bidang
Pewarnaan bidang adalah memberi warna pada bidang sehingga tidak ada bidang yang bertetangga mempunyai warna yang sama. Pewarnaan bidang hanya bisa dilakukan dengan membuat graf tersebut menjadi graf planar terlebih dahulu. Graf planar adalah graf yang dapat digambarkan pada bidang datar dengan sisi-sisi yang tidak saling memotong (bersilangan), seperti yang ditunjukkan gambar di bawah ini.

Gambar 6. Contoh Grraf Planar
Setelah terbentuk graf planar, lalu memberikan warna berbeda untuk setiap bidang yang berdekatan. Dan jumlah warna yang digunakan harus sedikit mungkin.

Gambar 7. Contoh pewarnaan bidang
Dalam pewarnaan graf, jumlah warna yang digunakan untuk mewarnai simpul, sisi, maupun bidang diusahakan sesedikit mungkin. Jumlah warna minimum yang dapat digunakan tersebut disebut bilangan kromatik graf G, disimbolkan dengan χ(G). Suatu graf G yang mempunyai bilangan kromatis k dilambangkan dengan χ(G) = k.
III. PENGATURAN WARNA PADA LAMPU LALU LINTAS MENGGUNAKAN GRAF
Sudah disebutkan sebelumnya bahwa sampai saat ini, teori graf masih diterapkan di berbagai persoalan dalam kehidupan sehari-hari. Misalnya aplikasi pewarnaan graf dalam pengaturan warna lampu lalu lintas di perempatan jalan sehingga mencegah terjadinya tabrakan di perempatan jalan tersebut.

Gambar 8. Lampu lalu lintas perempatan jalan
Seperti yang ditunjukkan pada gambar diatas, sebuah perempatan jalan mempunyai 4 buah lampu lalu lintas. Lampu lalu lintas pada jalan B dan F menyala bersamaan. Lampu lalu lintas pada jalan D dan H juga menyala bersamaan. Dalam perempatan jalan tersebut diketahui jika lampu di jalan B dan F menyala hijau maka jalur yang boleh digunakan adalah dari B ke E, F ke A. selain itu jalur langsung belok kiri juga diperbolehkan, yaitu dari B ke C, dan F ke G. Jika di jalan D dan H lampu hijau menyala maka jalur yang boleh digunakan untuk melintas adalah jalur dari D ke E, D ke G, H ke A, dan H ke C. Dalam kondisi ini, jalur langsung belok kiri juga diperoblehkan. Untuk menyelesaikan permasalahan pada pembuatan lampu lalu lintas pada sebuah perempatan jalan, maka hal yang harus dilakukan terlebih dahulu adalah menentukan jalur mana yang bisa berjalan dengan member lampu hijau di tempat tertentu dan member lampu merah agar kendaraan pada lintasan yang lain berhenti sehingga tidak terjadi tabrakan.

Gambar 9. Jalur di perempatan jalan
Diketahui bahwa jalur yang bisa digunakan untuk melintas adalah dari B ke C, B ke E, D ke E, D ke G, F ke G, F ke A, H ke A, dan H ke C. Setelah mengetahui jalur mana saja yang bisa dilewati, berikut langkah-langkah untuk mengatur lampu lalu lintas menggunakan graf.
1. Membuat simpul-simpul sebagai tanda dari semua jalur yang bisa dilewati dalam perempatan jalan. Letak dari simpul-simpul tersebut bebas, tidak ada aturan tertentu untuk mengharuskan simpul harus diletakkan di posisi mana karena hal itu tidak terlalu berpengaruh.

Gambar 10. Simpul-simpul dari jalur jalan
2. Menentukan sisi untuk menghubungkan 2 simpul yang saling melintas atau berseberangan. Untuk memudahkan hal ini, carilah simpul-simpul yang menunjukkan jalur mana saja yang akan bertabrakan jika semua lampu lalu lintas berwarna hijau. Pada Gambar 9 terlihat bahwa jalur BE dan DG, BE dan HC, FA dan DG, FA dan HC saling berseberangan. Karena BE dan DG berseberangan, maka kedua simpul tersebut dihubungkan dengan garis yang disebut sisi. Setelah itu, simpul-simpul lain yang saling berseberangan juga dihubungkan dengan sebuah sisi.

Gambar 11. Graf jalur jalan
3. Setelah menghubungkan semua simpul (jalur) yang saling berseberangan, langkah selanjutnya yang harus dilakukan adalah memberi warna pada masing-masing simpul dengan ketentuan pemberian warnanya sebagai berikut :
• Menggunakan jumlah warna sedikit mungkin
• Simpul yang bertetanggaan (terhubung dengan sisi) tidak boleh berwarna sama
• Memberi warna yang sama pada simpul yang tidak terhubung secara langsung
• Simpul yang tidak terhubung dengan sisi (simpul terpencil), berarti jalur tersebut boleh berlaku lampu lalu lintas berwarna hijau terus.
• Warna yang digunakan bebas.

Gambar 12. Pewarnaan pada simpul graf
Berdasarkan gambar diatas, semua simpul telah diwarnai sesuai ketentuan pewarnaan pada graf.
Graf diatas memiliki bilangan kromatis 3 (χ(G) = 3) karena jumlah minimum warna yang digunakan sebanyak 3. Simpul FA dan BE berwarna sama yaitu hijau karena keduanya tidak terhubung/bertetanggaan. Tapi simpul DG dan HC terhubung dengan simpul FA dan BE sehingga harus diberi warna yang berbeda yaitu warna merah. Sementara simpul HA, BC, DE, FG diberi warna sama yaitu kuning karena simpul-simpul tersebut adalah simpul terpencil yang tidak terhubung dengan simpul lain dan itu berarti bahwa jalur-jalur dari simpul tersebut tidak ada yang saling melintas sehingga keempat jalur itu bisa berlaku lampu hijau terus.
4. Langkah selanjutnya adalah mengelompokkan simpul-simpul tersebut berdasarkan kesamaan warna.
• Merah = DG dan HC
• Hijau = BE dan FA
• Kuning = BC, DE, FG, dan HA
Dari pengelompokkan tersebut diperoleh 2 kondisi untuk lampu lalu lintas di perempatan jalan.
Lampu Merah = DG, HC
Lampu Hijau = BE, FA, BC, DE, FG, HA
Tabel 1. Kondisi lampu lalu lintas 1
Lampu Merah = BE, FA
Lampu Hijau = DG, HC, BC, DE, FG, HA
Tabel 2. Kondisi lampu lalu lintas 2
Berdasarkan tabel-tabel diatas, lampu merah berarti bahwa jalur tidak boleh digunakan untuk melintas, sedangkan lampu hijau menunjukkan bahwa jalur bisa digunakan untuk melintas. Pada Tabel 1, jika di jalan D dan H lampu merah menyala maka jalur DG dan HC tidak boleh digunakan. Disaat yang bersamaan di jalan B dan F lampu hijau menyala sehingga jalur BE dan FA boleh digunakan. Karena langsung belok kiri juga diperbolehkan, maka jalur BC, DE, FG, HA juga bisa digunakan untuk melintas. Hal-hal tersebut juga berlaku untuk Tabel 2, ketika di jalan B dan F lampu merah menyala maka di jalan D dan H lampu hijau akan menyala. Sehingga jalur-jalur yang bisa digunakan antara lain DG, HC, BC, DE, FG, dan HA.
IV. PENYUSUNAN JADWAL DENGAN METODE PEWARNAAN GRAF
Salah satu aplikasi penerapan pewarnaan graf dalam kehidupan sehari-hari adalah dalam penyusunan sebuah jadwal. Sebuah jadwal yang ada mula-mula dipetakan menjadi bentuk graf terlebih dahulu. Proses pewarnaan graf ini nantinya akan dilakukan pada graf yang terbentuk. Pemetaan dilakukan dengan mengasumsikan bahwa setiap jadwal adalah sebuah vertex (simpul) dan urutan jadwal atau dua jadwal yang tidak bisa diadakan bersamaan dipetakan dengan membuat edge(sisi) antara dua titik tersebut. Untuk kapasitas ruang yang ada akan dimodelkan dengan batasan jumlah warna sama yang bisa digunakan untuk mewarnai simpul. Setelah proses pewarnaan graf telah selesai, setiap simpul pada graf hasil pewarnaan tersebut akan memiliki warna sama yang berbeda-beda. Dari warnawarna tersebut akan diketahui bahwa simpul dengan warna yang sama bisa dijadwalkan bersamaan sedangkan untuk simpul dengan warna yang berlainan harus dijadwalkan berbeda. Jumlah warna yang digunakan menunjukkan banyaknya jadwal yang harus disusun dalam melakukan penyusunan jadwal. Karena penulis adalah seorang mahasiswa, disini penulis akan mengambil contoh bagaimana menyusun jadwal kuliah dengan metode pewarnaan graf ini. Misalkan terdapat himpunan delapan orang mahasiswa,
M= {1, 2, 3, 4, .., 8}
Dan lima buah mata kuliah yang dapat dipilih oleh kedelapan mahasiwa tersebut,
MK= {1, 2, 3, 4, 5}
Tabel berikut memperlihatkan matriks lima mata kuliah dan delapan orang mahasiswa.

Tabel 1. Tabel Mata Kuliah yang Diambil Oleh Delapan Orang Mahasiswa
Pada tabel tersebut terlihat matriks lima mata kuliah dan delapan orang mahasiwa. Angka 1 pada elemen (i, j) menandakan bahwa mahasiwa I memilih mata kuliah j, sedangkan angka 0 menyatakan bahwa mahasiswa tersebut tidak memilih mata kuliah j. Berdasarkan tabel tersebut, akan ditentukan sebuah jadwal ujian sedemikian sehingga semua mahasiwa dapat mengikuti semua ujian mata kuliah tersebut. Oleh karena itu tidak boleh terdapat jadwal ujian mata kuliah yang bertabrakan dengan jadwal ujian mata kuliah lainnya yang juga diambil oleh mahasiswa tersebut. Ujian dua buah mata kuliah dapat dijadwalkan pada waktu yang sama jika tidak ada mahasiwa yang sama yang mengikuti ujian dua mata kuliah tersebut. Penyelesaian untuk masalah ini sama dengan persoalan menentukan bilangan kromatik untuk sebuh graf. Pertama-tama, persoalan tersebut dipetakan ke dalam sebuah graf, diman setiap simpul dalam graf tersebut menyatakan mata kuliah. Dan sisi yang menghubungkan dua simpul menyatakan ada mahasiwa yang memilih kedua mata kuliah tersebut.

Gambar 3: Graf Mata Kuliah Delapan Orang Mahasiswa
Dapat dilihat pada graf tersebut bahwa apabila terdapat dua buah simpul yang dihungkan oleh kedua sisi, maka ujian kedua mata kuliah tersebut tidak dapatdiadakan secara bersamaan. Simpul (mata kuliah) tidak boleh mendapat alokasi waktu (warna simpul) yang sama.Warna-warna yang berbeda dapat diberikan kepada simpul-simpul graf tersebut. Jadwal yang efisien adalah jadwal yang memungkinkan waktu sedikit mungkin untuk melaksanakan semua kegiatan tersebut. Oleh karena itu, disini yang akan dicari adalah bilangan kromatik graf tersebut, χ(G). Dalam mengerjakan pewarnaan graf ini, dapat menggunakan langkah-langkah pewarnaan graf secara umum ataupun algoritma. Semua cara tergantung kepada individu yang akan menyusun sebuah jadwal itu sendiri. Pada graf persoalan diatas, ditemukan bahwa bilangan kromatik graf tersebut adalah dua. Oleh karena itu simpul pada graf tersebut dapat diwarnai oleh dua macam warna yang menandakan bahwa ujian-ujian kelima mata kuliah tersebut dapat dilaksanakan hanya pada dua waktu saja. Berikut merupakan gambar graf persoalan ini yang telah diberi warna.

Gambar 4: Graf yang Telah Diberi Warna Tiap Simpulnya
Pada gambar diatas, terlihat bahwa ujian untuk mata kuliah A, D, dan E dapat dilaksanakan pada waktu yang bersamaan, begitu pula dengan mata kuliah B dan C. Perbedaan warna simpul menunjukkan bahwa ujian mata kuliah tersebut dilaksanakan pada waktu yang berbeda.
Contoh lainnya adalah dalam menyusun sebuah jadwal rapat. Misalkan terdapat tugas kelompok. Dalam satu kelas tedapat enam buah kelopokmahasiswa. Satu mahasiswa dapat bergabung ke dalam kelompok lainnya juga.
Berikut merupakan daftar nama tiap-tiap kelompok.
K1= {Amir, Budi, Yanti}
K2= {Budi, Hasan, Tommy}
K3= {Amir, Tommy, Yanti}
K4= {Hasan, Tommy, Yanti}
K5= {Amir, Budi}
K6= {Budi, Tommy, Yanti}
Disini persoalan yang akan dipecahkan adalah bagaimana menyusun jadwal asistensi untuk tiap kelompok agar tidak saling bertabrakan. Hal yang pertama dilakukan adalah memetakan persoalan tersebut ke dalam graf seperti yang diperlihatkan pada graf berikut.

Gambar 5: Graf Persoalan Jadwal Asistensi
Pada graf tersebut, tiap simpul menandakan tiap kelompok dan sisi menandakan kelompok yang memiliki anggota kelopoknya yang sama. Dengan menggunakan metode pewarnaan graf, diperoleh bilangan kromatik graf tersebut adalah 5. Oleh karean itu, gambar graf yang telah diwarnai tiap simpulnya adalah sebagai berikut.

Gambar 6: Graf Persoalan Jadwal Asistensi yang Telah Diberi Warna Tiap Simpulnya
Dari gambar diatas dapat terlihat bahwa untuk menyelesaikan masalah jadwal asistensi, jadwal asistensi dapat dilakukan pada lima waktu yang berbeda. Dari contoh-contoh yang telah dijabarkan diatas. Telah dijabarkan beberapa contoh penyelesaian permasalahan penyusunan jadwaldengan metode pewarnaan graf. Untuk graf dengan jumlah simpul yang sedikit, dapat ditentukan bilangan kromatik suatu graf dengan mudah. Namun untuk graf dengan jumlah simpul yang banyak, disini diperlukan sebuah software komputer. Dalam pembuatan software tersebut dapat menerapkan algoritma-algoritma yang telah dijabarkan pada bab 4 diatas.
V. KESIMPULAN
1. Teori graf merupakan pokok bahasan yang sudah lama tapi sampai sekarang masih memiliki terapan di berbagai persoalan dalam kehidupan sehari-hari, salah satu contohnya adalah penggunaan pewarnaan graf pada pengaturan lampu lalu lintas di perempatan jalan & Peyusunan Jadwal Dengan Metode Pewarnaan Graf
2. Masalah pembuatan lampu lalu lintas dan masalah penyusunan jadwal dapat dimodelkan dalam bentuk graf. Untuk mencari solusi dari permasalahan pengaturan warna lampu lintas dapat digunakan teknik pewarnaan simpul pada graf.
3. Untuk penyelesaian dari pengaturan warna pada lampu lalu lintas di perempatan jalan, jumlah minimum warna yang digunakan untuk pewarnaan simpul adalah 3.
4. Langkah awal penyelesaian adalah dengan memetakan suatu jadwal ke dalam graf lalu menentukan bilangan kromatik graf tersebut.
5. Untuk graf dengan jumlah simpul yang sedikit, dapat ditentukan bilangan kromatik suatu graf dengan mudah, Namun untuk graf dengan jumlah simpul yang banyak, disini diperlukan sebuah software komputer.
VI. REFERENSI
1) Munir,Rinaldi, Matematika diskrit revisi ke 5,Informatika Bandung,2012.
2) Lipschutz,Seymor & Marc Lars Lipson,2000 Solved Problems in Discrete Mathematics,McGraw-Hill,1992
3) P engaturan-warna-pada-lampu-lalu-lintas, http://bloglogika.blogspot.com/2011/02/pengaturan warna-pada-lampu-lalu-lintas.html.
Wikipedia, “Graph Coloring”, http://en.wikipedia.org/wiki/Graph_coloring.


Semoga bermanfaat....,