insya allah perfect matdisk(2)

BAB 1

PENDAHULUAN

1.1 Latar Belakang

Teori graph merupakan salah satu studi terhadap bidang matematika yang diperkenalkan pertama kali oleh seorang ahli matematika asal Swiss, Leonhard Euler pada tahun 1736. Ide besarnya muncul sebagai upaya penyelesaian masalah jembatan Konigsberg. Dari permasalahan itu, akhirnya Euler mengembangkan beberapa konsep mengenai teori graph. Materi-materi yang terdapat dalam teori graph itu sendiri adalah ilmu yang mempelajarimengenai logika dari persoalan yang berhubungan dengan himpunan dan relasi binary.

Graph merupakan topik yang banyak mendapat perhatian saat ini, karena model-model yang ada pada teori graph berguna untuk aplikasi yang luas. Walaupun teori graph berasal dari bidang ilmu Matematika, namun pada penerapannya, teori graph dapat dihubungkan dengan berbagai bidang ilmu dan juga kehidupan sehari-hari. Sedemikian banyaknya pengaplikasian graph dalam dunia ini, bila perlu dikatakan tidak ada habis-habisnya jika dibahas setiap aplikasi graph, karena setiap bidang ilmu dapat dikaitkan dengan graph seperti masalah dalam jaringan komunikasi, transportasi, ilmu komputer, riset operasi, ilmu kimia, Sosiologi, Kartografi dan lain sebagainya. Teori-teori mengenai graph ini telah banyak dikembangkan dengan berbagai algoritma yang memiliki kelebihan dan kelemahan masing-masing dalam menyelesaikannya.

Graph adalah himpunan pasangan tak berurut antara vertex (titik atau node) dan edge (garis atau arcs). Begitu banyak struktur yang dapat direpresentasikan dengan graph, dan banyak masalah yang bisa diselesaikan dengan bantuan graph. Jaringan persahabatan pada situs pertemanan online atau facebook bisa direpresentasikan dengan graph, vertex-nya adalah para pemakai facebook dan ada edge antara A dan B jika dan hanya jika A berteman dengan B. Perkembangan algoritma untuk menangani graph akan berdampak besar bagi ilmu komputer.

Teori pewarnaan graph merupakan salah satu objek yang menarik dan terkenal dalam bidang teori graph. Pewarnaan graph dibagi dalam 3 bagian, yaitu pewarnaan vertex, pewarnaan edge, dan pewarnaan region. Suatu pewarnaan region dari sebuah graph dapat dilakukan (seperti pemberian warna pada wilayah-wilayah di peta) dengan cara membuat dual dari peta tersebut.

Salah satu aplikasi dalam teori pewarnaan graph adalah menentukan warna-warna yang sesuai pada sebuah peta. Teori pewarnaan wilayah (region coloring) ini diaplikasikan pada peta Amerika Serikat. Selain itu teori pewarnaan graph juga dapat di aplikasikan untuk pembuatan jadwal. Algoritma yang digunakan dalam menentukan warna pada peta Amerika Serikat ini, yaitu algoritma Sequential Coloring meskipun algoritma ini masih bergantung pada urutan penomoran dari vertex pada graph, namun keuntungan dari algoritma Sequential Coloring adalah efiensinya. Algoritma Sequential Coloring adalah sebuah algoritma untuk

mewarnai sebuah graph dengan k-warna, k adalah bilangan integer positif. Metoda yang digunakan algoritma ini adalah dengan pewarnaan langsung pada sebuah graph dengan warna yang sesedikit mungkin. Namun Algoritma Sequential Coloring ini masih bergantung pada urutan penomoran dari vertex-vertex pada graph.

1.2 Rumusan masalah

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. Permasalahannya adalah bagaimana cara mengimplementasikan graph coloring dalam memetakan penyusunan jadwal? Penyusunan jadwal dengan penerapan pewarnaan graph ditujukan untuk membantu kita dalam mengimplementasikan suatu penjadwalan yang rumit menjadi lebih mudah dimengerti.

1.3 Batasan Masalah

Batasan masalah yang menjadi acuan dalam pengerjaan makalah ini adalah :1. Graph Coloring yang akan diimplementasikan yaitu pada bagian vertex coloring dan region coloring.

2. Penjelasan tentang macam-macam coloring serta bagaimana cara dan aturan-aturan dalam pemberian warna pada suatu graph.

3. Penjelasan tentang teori 4 warna pada suatu graph serta penjelasan tentang teori euler sebelum ditemukannya teori 4 warna (Four Colour Theorem).

1.4 Tujuan

Tujuan pembuatan makalah ini adalah :1. Mengimplementasikan graph coloring dalam sistem penjadwalan.

2. Mengaplikasikan teori pewarnaan.

1.5 Manfaat

Makalah ini dapat dijadikan sebagai bahan acuan dalam pembelajaran untuk mengimplementasikan graph coloring dalam sistem penjadwalan. Dengan makalah ini pembaca juga dapat mengetahui beberapa teori pewarnaan.

BAB 2 LANDASAN TEORI

Bab ini akan membahas teori-teori yang berkaitan dengan graph, graph coloring dan region coloring. Pada bagian teori graph dibahas mengenai definisi graph, sejarah teori graph, jenis-jenis pewarnaan graph termasuk pewarnaan wilayah.

Definisi pewarnaan graph adalah pemberian warna, yang biasanya direpresentasikan sebagai bilangan terurut mulai dari 1 atau dapat juga direpresentasikan langsung dengan menggunakan warna merah, biru, hijau dan lain-lain pada objek tertentu pada suatu graph. Objek tersebut dapat berupa simpul, sisi, wilayah atapun kombinasi ketiganya. Seperti pada gambar 1 di bawah ini, setiap simpul yang berdekatan atau bertetangga tidak mempunyai warna yang sama.

Gambar 1. Pewarnaan graph Pewarnaan graph dibagi menjadi 3 macam, yaitu:a. Pewarnaan simpul (vertex colouring), merupakan pemberian warna atau label pada setiap simpul sehingga tidak ada 2 simpul bertetangga yang memiliki warna sama.b. Pewarnaan sisi (edge colouring), merupakan pemberian warna pada setiap sisi pada graph sehingga sisi-sisi yang berhubugan tidak memiliki warna yang sama.c. Pewarnaan wilayah (region colouring), merupakan pemberian warna pada setiap wilayahpada graph sehingga tidak ada wilayah yang bersebelahan yang memiliki warna yang sama.2.1 Pewarnaan GraphDalam pewarnaan graph jumlah warna minimum yang dapat digunakan untuk mewarnai graph dinyatakan dengan bilangan kromatik, yang disimbolkan dengan χ(G). Graph yang memiliki bilangan kromatik 1 adalah graph kosong, yaitu graph yang hanya terdiri dari sebuah simpul. Sementara suatu graph dikatakan planar jika tidak ada dua buah titik yang saling berpotongan yaitu graph yang dapat digambarkan pada bidang datar tanpa ada sisi yang menyilang diatas sisi lainnya dimana jumlah warna yang digunakan hanya 4warna. Sebuah kasus khusus yang terkenal dari ”m colorability decision problem” yaitu masalah 4 warna dari suatu graph planar. Masalah ini disertai pernyataan sebagai berikut : berikan beberapa wilayah yang dapat menimbulkan daerah-daerah yang diwarnai sedemikian rupa sehingga daerahdaerah yang berdampingan tidak memiliki warna yang sama, akan tetapi hanya empat buah warna yang dipakai. Masalah pewarnaan seperti itu dapat berubahmenjadi sangat berguna, karena wilayah tersebut dapat dengan mudah diubah bentuknya menjadi sebuah graph. Masing-masing daerah dari wilayah itu menjadi sebuah simpul dan jika dua buah daerah berdampingan maka ke dua buah simpulnya berhubungan, kemudian hubungkan dengan sebuah sisi.

Graf adalah salah satu pokok bahasan Matematika Diskrit yang telah lama dikenal dan telah banyak diaplikasikan pada berbagai bidang secara umum. Pengertian dari Graf adalah merupakan suatu pasangan himpunan (V,E) di mana V adalah himpunan tidak kosong dari simpul-simpul (vertex atau node) dan E adalah himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul pada graf tersebut.V= {v1,v2,v3......,vn}

E= {e1,e2,e3......,vn}Atau

E= {(v1,v2),(v2,v3),(v3,v4)......,(vn-1,vn)}Di mana e=(Vi,Vj) yang artinya sisi yang menghubungkan simpul Vi dan Vj.

Sebagai contoh pada definisi graf dimanaV= {1,2,3,4,5,6} danE= {(1,2),(1,5),(2,3),(3,4),(4,5),(5,2),(4,6)}Maka gambar graf tersebut

Kegunaan graf sangat banyak. Umumnya graf digunakan sebagai cara menggambarkan suatu masalah menjadi lebih mudah, yaitu dengan cara mempresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Contoh penenarapan graf dapat dilihat pada penggambaran rangkaian listrik, jaringan komunikasi, senyawa kimia, peta, struktur hierarki sosial, peta, dan lain-lain. Dalam pembacaan sebuah graf terdapat cara untuk membuat gambaran yang ditampilkan menjadi lebih mudah dipahami, yaitu dengan cara memberikan pewarnaan elemen-elemen pada sebuah graf.

BAB 3 PEMBAHASAN

Bab ini akan membahas bagian yang berkaitan dengan region coloring yang pembahasannya dilakukan dengan menggunakan algoritma dan flowchart.BAB 4 IMPLEMENTASI SISTEMBab ini menjelaskan langkah-langkah bagaimana mengimplementasikan region coloring dalam sebuah program komputer dan dilanjutkan dengan pengujian program tersebutBAB 5 KESIMPULAN DAN SARANBab terakhir akan memuat kesimpulan isi dari keseluruhan uraian bab-bab sebelumnya dan saran-saran dari hasil yang diperoleh yang diharapkan dapat bermanfaat dalam pengembangan selanjutnya.

COLORING GRAPH

Pendahuluan

Bilangan Kromatik

Bilangan kromatik χ(G ) adalah sebuah jumlah warna minimum yang dapat digunakan untuk mewarnai suatu graf. Sebuah pewarnaan yang menggunakan beberapa n buah warna biasanya disebut dengan n-coloring. Contohnya:

Pada gambar diatas menunjukan bahwa 3 buah warna sudah cukup untuk mewarnai simpul pada graf tersebut.Dalam beberapa graf tertentu dapat ditentukan langsung bilangan kromatiknya, yaitu:

1. Graf kosong memiliki χ(G )= 1 karena semua simpul tidak terhubung.2. Graf lengkap Kn memiliki χ(G )= n sebab semua simpul terhubung sehingga diperlukan n

buah warna.3. Graf bipartit mempunyai χ(G )= 2, satu untuk simpul di himpunan V1 dan satu untuk

himpunan V2.4. Graf lingkaran dengan n ganjil memiliki χ(G )= 3.5. Graf lingkaran dengan n genap memiliki χ(G )= 2.

Metode Pewarnaan Graf1. Pewarnaan Simpul/titik (vertex)

Salah satu metode pewarnaan sebuah graf adalah metode pewarnaan simpul (vertex). Pewarnaan simpul adalah memberi warna pada simpul-simpul di dalam graf sedemikian sehingga setiap dua simpul bertetangga mempunyai warna yang berbeda. Dalam pemberian warna kita dapat memberikan warna apapun asalkan berbeda dengan simpul-simpul tetangganya.

Dalam metode pewarnaan graf, terdapat beberapa algoritma yang diterapkan. Algoritma-algoritma ini membantu kita dalam pewarnaan suatu graf. Karena semakin kompleks suatu graf tidak memungkinkan kita dalam melakukan pewarnaan graf secara manual. Selain itu algoritma-algoritma ini juga membantu kita dalam menentukan warna yang seevisien mungkin. Berikut ini merupakan beberapa algoritma yang dapat digunakan dalam metode pewarnaan graf.

Algoritma Welch-PowellAlgoritma Welch-Powell dapat digunakan untuk mewarnai sebuah graf G secara efisien. Algoritma ini tidak selalu memberikan jumlah warna minimum yang diperlukan untuk mewarnai G, namun algoritma ini cukup praktis untuk digunakan dalam pewarnaan

simpul sebuah graf. Algoritma Welch-Powell hanya cocok digunakan untuk graf dengan orde yang kecil. Oleh karena itu algoritma Welch-Powell hanya dapat menentukan batas atas warna. Langkah-langkahnya adalah sebagai berikut.1. Urutkan semua simpul berdasarkan derajatnya, dari derajar besar ke derajat kecil.2. Ambil warna pertama (misalnya merah), warnai simpul pertama yang sudah diurutkan

berdasarkan derajatnya tadi. Kemudian warnai simpul berikutnya yang tidak berdampingan dengan simpul pertama tadi dengan warna yang masih sama (merah).

3. Kemudian dilanjutkan dengan warna kedua, dan seterusnya, sampai semua simpul telah diberi warna.

Contohnya:Misalkan kita ingin mewarnai simpul graf di bawah ini.

Gambar 1: Graf yang akan diwarnai simpulnya dengan algoritma Welch-Powell

Langkah-langkah yang akan dilakukan adalah:1. Urutkan simpul berdasarkan derajatnya dari besar ke kecil : Simpul berderajat terbesar

adalah E, yaitu 5 (mempunyai 5 ruas) kemudian simpul C berderajat 4, B,D,F masing-masing berderajat 3 dan A,H,G masing-masing berderajat 2. Jadi Urutannya adalah : E,C,B,D,F,A,H,G

2. Ambil warna pertama, misalnya Merah. Beri warna Merah simpul E (karena E adalah simpul urutan pertama).Kemudian cari simpul yang tidak berdampingan dengan simpul E, beri warna yang sama (merah).

3. Diberikan warna yang sama pada simpul A dan G dengan warna simpul E yaitu merah karena Simpul A dan G tidak berdampingan dengan simpul E. sehingga diperolah urutan simpul yang belum diberi warna adalah C, B, D, F, dan H.

4. Ambil warna kedua, misalnya Biru, warnai simpul C ( karena simpul C sekarang ada diurutan pertama). Kemudian cari simpul yang tidak berdampingan dengan simpul C, beri warna yang sama (Biru).

5. Diberikan warna yang sama pada simpul D dan H dengan warna simpul C yaitu biru karena Simpul D dan H tidak berdampingan dengan simpul C. Sehingga diperoleh urutan simpul yang belum diberi warna adalah B dan F.

6. Mengambil warna ketiga, misalnya warna hijau. Lalu warna tersebut ditambahkan pada simpul B dan F (simpul B dan F tidak bertetangga). Dan hasil pewarnaan graf tersebut adalah:

Gambar 2: Graf yang telah diwarnai simpulnya dengan algoritma Welch-Powell

Algoritma Recursive Largest FirstAlgoritma Recursive Largest First hampir mirip prinsipnya dengan algoritma Welch-Powell. Langkah kerja dari algoritma Recursive Largest First adalah sebagai berikut.1. Buat daftar semua simpul yang belum diwarnai dengan derajat tetangga (jumlah

simpul tetannga yang belum diwarnai) terurut secara descending.2. Ambil simpul yang memiliki derajat tetangga tertinggi dan warnai dengan sebuah

warna.3. Buang simpul yang telah diwarnai pada langkah sebelumnya dan semua simpul yang

bertetangga tersebut dari daftar simpul.4. Warnai semua simpul yang tersisa dengan warna yang sama pada simpul tadi. Lalu

ulangi langkahlangkah diatas hingga semua simpul pada graf telah terwarnai semua.

Algoritma BacktrackingAlgoritma Backtracking merupakan bentuk algoritma yang banyak dan sering digunakan

dalammemecahkan permasalahan yang bersifat kombinasi. Algoritma ini dikenal juga dengan nama algoritma runut-balik. Cara kerja dari algortima backtracking adalah mencoba satu demi satu kemungkinan cara yang bisa dilakukan untuk memperoleh hasil yang terbaik. memiliki keunggulan dalam kemampuannya untuk memperoleh hasil kombinasi yang terbaik karena mencoba semua kemungkinan yang ada. Di sisi lain algoritma ini tidak efisien sebab proses pencarian membutuhkan waktu yang lama karena pengujian dilakukan satu demi satu untuk semua kemungkinan. Dalam langkah pewarnaan menggunaan algoritma ini, graf yang ada diumpamakan sebagai graf dengan bentuk pohon (pohon merupakan salah satu bentuk graf). Langkah-langkahnya adalah sebagai berikut [3].1. Solusi dicari dengan membentuk lintasan dari akar ke daun. Aturan pembentukan

yang dipakai adalah mengikuti aturan pencarian mendalam (DFS). Simpul-simpul

yang sudah dilahirkan dinamakan simpul hidup (live node). Simpul hidup yang sedang diperluas dinamakan simpul- E (Expand-node).

2. Tiap kali simpul-E diperluas, lintasan yang dibangun olehnya bertambah panjang. Jika lintasan yang sedang dibentuk tidak mengarah ke solusi, maka simpul-E tersebut “dibunuh” sehingga menjadi simpul mati (dead node). Fungsi yang digunakan untuk membunuh simpul- E adalah dengan menerapkan fungsi pembatas (bounding function). Simpul yang sudah mati tidak akan pernah diperluas lagi.

3. Jika pembentukan lintasan berakhir dengan simpul mati, maka proses pencarian diteruskan dengan membangkitkan simpul anak yang lainnya. Bila tidak ada lagi simpul anak yang dapat dibangkitkan, maka pencarian solusi dilanjutkan dengan melakukan runut-balik ke simpul hidup terdekat (simpul orangtua). Selanjutnya simpul ini menjadi simpul-E yang baru.

4. Pencarian dihentikan bila kita telah menemukan solusi atau tidak ada lagi simpul hidup untuk runut-balik.

2. Pewarnaan Sisi (Edge Coloring)

Pewarnaan sisi merupakan pemberian warna pada setiap sisi pada graf sehingga sisi-sisi yang berhubungan tidak memiliki warna yang sama. pewarnaan sisi-sisinya secara tepat berarti cara pemberian warna pada garis sedemikian rupa sehingga setiap garis yang bertumpuan pada titik yang sama diberi warna yang berbeda. Pewarnaan sisi dengan warna-warna (sebut saja dengan variabel k) dinamakan sebagai pewarnaan sisi k. Dan ekuivalen dengan persoalan membagi sisi dengan warna-warna tertentu pada himpunan sisi dengan warna tertentu. Angka terkecil dari warna-warnayang dibutuhkan untuk pewarnaan sisi graf G disebut sebagai indeks kromatik atau angka kromatiksisi, χ’(G). Pewarnaan tait adalah sebuah pewarnaan tiga sisi dari sebuah graf kubus. Teori empat warna (teori yang berawal dari penyataan mengenai: “Dapatkah sembarang graf planar diwarnai hanya dengan empat warna saja?”) ekuivalen dengan bahwa tiap graf planar kubus tanpa jembatan (sisi) menunjukkan sebuah pewarnaan tait.

3. Pewarnaan Area

Pewarnaan wilayah adalah pemberian warna pada setiap wilayah pada graf sehingga tidak ada wilayah bersebelahan yang memiliki warna yang sama. Pewarnaan wilayah ini diterapkan pada pewarnaan peta. Pada pewarnaan peta, diberikan warna yang berbeda pada setiap propinsi yang saling bersebelahan. Dalam mengerjakan pewarnaan wilayah, kita dapat menggunakap prinsip pewarnaan simpul pada graf. Misalnya adalah masalah pewarnaan peta. Tiap wilayah pada peta dinyatakan sebagai simpul graf. Sedangkan sisi menyatakan bahwa terdapat dua wilayah yang berbatasan langsung (disebut juga bertetangga). Oleh karena itu, graf yang terbentuk merupakan graf planar. Graf planar ialah graf yang dapat digambarkan pada bidang datar sedemikian sehingga tidak ada sisi-sisinya yang saling berpotongan [1]. Bilangan kromatik pada graf planar tidak lebih dari empat. Sehingga dalam pewarnaan

sebuah peta, cukup hanya menggunkan empat warna saja. Warna yang digunakan dalam pewarnaan peta adalah hijau, kuning, merah, dan biru.

Contoh pewarnaan peta Amerika Serikat dengan 4 warna

Four Colour Theorem

Four Colour Theorem merupakan salah satu teorema pewarnaan graf yang menyatakan bahwa pada setiap bidang yang terpisah dalam berbagai wilayah seperti negara-negara dalam peta wilayahnya dapat diwarnai dengan maksimum 4 warna sesuai dengan syarat pewarnaan graf. Jadi tidak ada wilayah atau negara yang bersebelahan yang mempunyai warna yang sama. Pembuktian teorema ini tidak bisa dituliskan menggunakan tangan karena Apple dan Hakken yang menemukan ini menggunakan banyak program dalam computer untuk menemukan teori ini.

Sebagai contoh 4 wilayah peta diganti dengan puncak dari grafik, dan dua vektor tersebut dihubungkan oleh sebuah tepi jika dan hanya jika dua daerah perbatasan berbagi segmen (tidak hanya sudut). Jadi graf tersebut membutuhkan 4 warna. Gambar grafik tersebut adalah

Sebelum terbuktinya teorema ini terdapat banyak kesalahan-kesalahan yang terjadi dalam pembuktiannya. Ada beberapa metode yang dipercaya masyarakat selama beberapa waktu sampai akhirnya metode itu terbukti salah. Dan juga banyak pembuktian yang dilakukan para matematikawan yang masih amatir yang tidak dipublikasikan.

Berikut ini adalah salah satu pengaplikasian metode yang salah.

Dari gambar tersebut terlihat bahwa graf tersebut menggunakan 5 warna. Seharusnya dengan mengubah 4 dari 10 wilayah tersebut kita hanya perlu menggunakan 4 warna saja. Gambarnya seperti dibawah ini.

Biasanya contoh-contoh kasus sederhana yang salah terhadap teori ini adalah pada saat menciptakan sebuah wilayah yang menyentuh wilayah yang lainnya. Hal ini menyebabkan tersisa 3 daerah yang diwarnai dengan 3 warna. Karena 4 colour theorem telah dibuktikan kebenarannya maka pewarnaan tadi selalu mungkin. Tetapi biasanya orang menggambar peta yang terfokus pada satu wilayah besar sehingga dia tidak sadar terdapat sisa daerah yang dapat diwarnai dengan 3 warna.

Kesalahan terhadap teori pada jaman dahulu itu dapat diterangkan sebagi berikut: jika ada warna banyak wilayah dalam peta yang telah ditetapkan warnanya maka untuk mewarnai wilayah lainnya mustahil tanpa menggunakan warna lebih dari empat. Dan orang orang yang memeriksa teorema yang salah ini tidak berpikir untuk mengganti warna dari wilayah-wilayah sebelumnya sehingga teorema ini seakan-akan benar.

Mungkin salah satu akibat yang mendasari kesalahpahaman konsep teori ini adalah kenyataan dimana pembatasan warna yang tidak lengkap. Dimana suatu wilayah harus diberi warna yang berbeda dari wilayah lain yang bertetangga dengannya secara langsung, bukan wilayah yang bertetangga dengan wilayah lain yang bertetangga dengannya secara langsung. Batasan ini yang menyebabkan pewarnaan graf planar membutuhkan warna yang banyak.

Pembuktian lain yang salah dalam mengasumsikan teori pewarnaan graf adalah seperti dalam penggunaan wilayah yang terdiri dari beberapa bagian yang terputus atau menolak wilayah yang mempunyai warna yang sama yang saling menyentuh dalam suatu simpul.

Sebelum teori 4 warna ditemukan pada umumnya jaman dahulu menggunakan teori euler. Teori ini juga dapat digunakan selain dalam suatu bidang. Contohnya dalam pewarnaan dalam bola maupun silinder cara pewarnaan wilayahnya sama dengan pewarnaan wilayah dalam suatu bidang. Untuk permukaan yang tertutup dengan genus positif maka jumlah warna tergantung dengan karakteristik euler χ dengan rumus seperti dibawah ini

Kurung siku diatas berfungsi sebagai floor function. Pengecualian dalam fungsi diatas adalah karateristik euler 0 (karena itu fungsi diatas memberikan p = 7 ) dan membutuhkan 6 warna.

Cara lain untuk rumusan diatas sebagai hubungan dengan genus dari permukaan (g) adalah dengan rumus seperti dibawah ini

Sebagai contoh sebuah bidang yang memiliki χ= 0 , genus g = 1 maka p adalah 7. Dalam arti maksimum warna dalam pewarnaan bidang tersebut adalah 7.

Pewarnaan dalam bidang

Pewarnaan dalam silinder

Pewarnaan dalam bola

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.

Mahasiswa ke-

A B C D E

1 0 1 0 0 12 0 1 0 1 03 0 0 1 1 04 1 1 0 0 05 0 1 0 1 06 0 0 1 1 07 1 0 1 0 08 0 0 1 1 0

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 yang telah dipaparkan pada bab IV di atas. 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 kelopok mahasiswa. 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.