Teori Graf UAS [PDF]

Citation preview

UJIAN AKHIR “PENERAPAN TEORI GRAF”



Oleh



: Ine F. Habel



NIM



: 1722004



Mata Kuliah



: Matematika Kombinatorika



Dosen



: Andi Pujo Rahadi M.Sc.



Universitas Advent Indonesia Jurusan Pendidikan Matematika Fakultas Ilmu Keguruan dan Pendidikan 2020



PENERAPAN PEWARNAAN GRAF DALAM PEMBUATAN JADWAL DENGAN MENGGUNAKAN ALGORITMA WELCH-POWELL



1. Teori Graf Suatu graf G terdiri dari dua himpunan yaitu himpunan V (Vertex) dan himpunan E(Edge). Himpunan V merupakan himpunan simpul yang tak kosong dari simpul-simpul ( Vertices atau node) dan adalah himpunan berhingga. Sedangkan himpunan E merupakan himpunan busur yang menghubungkan sepasang simpul. Himmpunan E dibentuk dari pasangan tak berurut dari elemen-elemen V(G) yang berbeda yang disebut dengan sisi(Edge). Secara matematis, sebuah graf G didefinisikan sebagai pasangan himpunan(V,E). Notasi graf ditulis G= (V,E). Graf yang tidak memiliki sisi disebut graf nol atau graf kosong. Sedangkan graf yang hanya memiliki satu buah simpul tanpa sebuah sisi disebut graf trivial. 2. Terminologi Graf Agar dapat memahami graf dengan baik, perlu untuk mengetahui istilah yang digunakan pada graf. Terdapat beberapa terminologi graf, yaitu : a. Ketetanggaan (Adjacent) Dua simpul dikatakan bertetangga ketika sebuah simpul dihubungkan dengan satu sisi yang sama. b. Bersisian ( Incidency) Suatu sisi bersisian dengan simpul-simpul yang duhubungkannya. c. Simpul Terpencil ( Isolated Vertex) Simpul yang tidak memliki sisi yang bersisian dengannya disebut dengan Simpul Terpencil. d. Derajat (Degree) Derajat adalah jumlah sisi yang bersisian dengan suatu simpul. e. Lintasan (Path) Lintasan adalah sisi yang ditempuh dari satu simpul ke simpul lainnya. f. Sirkuit



Sirkuit adalah sebuah lintasan yang berawal dan berakhirnya pada simpul yang sama g. Terhubung (Connected) Dua simpul dikatakan berhubung apabila terdapat lintasan yang menghubungkan dua simpul tersebut. Graf yang semua simpulnya terhubung disebut Graf Terhubung. h. Cut-Set Cut-Set adalah himpunan sisi yang menyebabkan suatu graf terhubung. Dengan kata lain, jika sisi tersebut dihilangkan maka graf menjadi tidak terhubung. 3. Jenis-Jenis Graf a. Berdasarkan ada tidaknya gelang atau edge ganda pada suatu graf, maka graf digolongkan menjadi dua 1. Graf Sederhana ( Simple Graph) Graf sederhana adalah graf yang tidak memiliki edge maupun edge ganda. 2. Graf tak-sederhana (Unsimple-Graf) Yaitu graf yang memiliki edge ganda atau edge.



Berikut contoh Graf sederhana dan Tak-Sederhana



b. Ada beberapa graf khusus, diantaranya 1. Graf Lengkap Graf lengkap adalah graf sederhana( tidak memiliki sisi ganda maupun gelang), yang setiap simpulnya mempunyai sisike semua simpul lainya. Graf lengkap dengan n simpul memiliki jumlah sisi



𝑛(𝑛−1) 2



.



Contoh Graf Lengkap



2. Graf Lingkaran Graf lingkaran adalah graf yang setiap simpulnya memiliki dua sisi( berderajat dua). Contoh graf Lingkaran



3. Graf Teratur Graf teratur adalah graf yang mempunyai deraja yang sama pada setiap simpulnya. Jumlah sisi pada graf teratur adalah



𝑛𝑟 2



simpul dan r adalah derajat tiap simpulnya. Contoh Graf teratur



, dengan n adalah jumlah



4. Graf Bipartit Graf yang himpunan simpulnya dapat dipisah menjadi dua himpunan bagian, sedemikian sehingga setiap sisi pada graf tersebut mengubungkan sebuah simpul di himpunan bagian pertama ke sebuah simpul di himpunan bagian ke dua disebut Graf bipartit. Contoh Graf Bipartit



4.Pewarnaan Graf Pewarnaan graf (graf coloring) merupakan proses untuk menandai simpul atau sisi suatu graf. 1. Pewarnaan Simpul ( Vertex Coloring) Pewarnaan simpul adalah memberikan warna pada setiap simpul sedemikian sehingga simpul yang bertetangga memiliki warna yang berbeda. Dalam pewarnaan graf, kita tidak hanya mencari warna yang berbeda, tetapi juga mencari cari cara agar warna yang digunakan seminimum mungkin.



Jumlah warna



minimum yang



dibutuhkan untuk mewarnai graf disebut dengan bilangan kromatik dengan simbol 𝜒(𝐺). Graf kosong memiliki bilangan kromatik sebanyak 1 karena semua simpul tidak terhubung, sehingga untuk mewarnai semua simpul graf tersebut cukup dengan satu warna saja. Graf lengkap memiliki bilangan kromatik= jumlah simpul atau 𝜒(𝐺) = 𝑛, karena semua simpul saling terhubung satu sama lain, sehingga untuk mewarnai semua simpul graf tersebut dibutuhkan warna sebanyak n.



Pewarnaan Simpul



2. Pewarnaan Sisi ( Edge Coloring) Pewarnaan sisi merupakan pemberian warna pada setiap sisi pada graf sedemikian sehingga setiap sisi-sisi yang berhubungan tidak memiliki warna yanga sama. Jumlah warna minimum yang dibutuhkan untuk mewarnai sisi graf disebut indeks kromatik disimbolkan dengan 𝜒′(𝐺). Indeks kromatik pada suatu graf selalu sama dengan derajat maksimumnya atau derajat maksimum +1



3. Pewarnaan Wilayah (Region Coloring) Pewarnaan wilayah merupakan pemberian warna pada setiap wilayah pada graf sehingga semua wilayah yang bersebelahan mempunyai warna yang berbeda. Posisi kota



5.Algoritma Welch-powell Pada graf-graf tertentu, proses pewarnaan dapat dilakukan secara cepat dan mudah, contohnya untuk kasus graf lingkaran dan graf lengkap. Namun pada kenyataannya graf seringkali didapati dalam bentuk yang tidak teratur. Pada kondisi ini, sangat dibutuhkan algoritma tertentu untuk menyelesaikan proses pewarnaannya. Algoritma Welch-Powell merupakan salah satu algoritma yang dapat digunakan untuk menyelesaikan kasus ini. Menurut Rinaldi Munir, Algoritma Welch-Powell dapat digunakan untuk mewarnai graf G secara efektif. Langkah-langkah Algoritma Welch-Powell sebagai berikut : 1. Urutkan simpul-simpul dari G dalam derajat yang menurun. Urutan yang didapatkan bisa saja bersifat tidak unik karena adanya beberapa simpul yang memiliki derajat yang sama.



2. Gunakan satu warna untuk mewarnai simpul pertama yang derajatnya paling tinggi dan simpul-simpul lain( dalam urutan yang berurut) yang tidak bertetangga dengan simpul pertama. 3. Mulai lagi dengan memberikan warna berdasarkan simpul tertinggi berikutnya didalam daftar terurut yang belum diwarnai. 4. Ulangi pemberian warna berbeda pada simpul-simpul berikutnya hingga semua simpul telah diwarnai.



Berikut Flowchart Algoritma Welch-Powell



Mulai



Cari satu simpul berderajat tertinggi sebagai simpul utama warna(SUW) Tidak Ada Ada Beri warna baru Cari satu simpul yang tidak bertetangga dengan SUW dan derajatnya paling tinggi Tidak Ada Ada Beri warna yang sam dengan SUW



Selesai



Berikut contoh pewarnaan graf mengikuti algoritma Welch-Powell yang dibuat oleh Pasnur dari jurusan Sistem Informasi, STMIK AKBA, Makassar, dikutip dari jurnal berjudul



“Implementasi Algoritma Welch-Powell Dalam Pembuatan Jadwal Ujian Akhir Semester” (Tersedia: https://jurnal.akba.ac.id/index.php/inspiration/article/view/16/16 ) Sebuah graf diperlihatkan seperti pada gambar 3 berikut in, terdiri atas 6 simpul yang diberi nama simpul A, B, C, D, E, dan F. Graf tersebut akan diberikan pewarnaan mengikuti algoritma WelchPowell.



Gambar 3 : Contoh sebuah graf Langkah pertama : mengurutkan simpul dalam derajat yang menurun, didapatkan hasil dengan urutan B (derajat 4), E (derajat 4), A (derajat 3), C (derajat 3), D (derajat 2), dan F (derajat 2). Langkah kedua : berikan warna (misalnya merah) untuk simpul dengan derajat tertinggi, dalam hal ini adalah simpul B ( gambar 4).



Gambar 4 : Pewarnaan simpul pertama dengan derajat tertinggi. Selanjutnya berikan warna yang sama kepada simpul-simpul lain yang tidak bertetangga dengan simpul B, dalam hal ini simpul E (gambar 5).



Gambar 5 : Pewarnaan simpul lain yang tidak bertetangga dengan simpul B Langkah ketiga : mulai lagi pewarnaan dengan warna yang berbeda (misalnya kuning) pada simpul yang belum diwarnai dengan derajat tertinggi, dalam hal ini adalah simpul A (gambar 6).



Gambar 6 : Pewarnaan simpul selanjutnya dengan derajat tertinggi Selanjutnya berikan warna yang sama (warna kuning) kepada simpul-simpul lain yang tidak bertetangga dengan simpul A, dalam hal ini simpul D dan F (gambar 7).



Gambar 7 : Pewarnaan simpul lain yang tidak bertetangga dengan simpul A Langkah keempat : mulai lagi pewarnaan dengan warna yang berbeda (misalnya hijau) pada simpul yang belum diwarnai dengan derajat tertinggi, dalam hal ini adalah simpul C dan merupakan simpul terakhir yang belum diwarnai (gambar 8).



Gambar 8 : Pewarnaan simpul terakhir Berdasarkan proses pewarnaan sebelumnya, dapat diketahui bahwa untuk melakukan pewarnaan graf seperti yang ditunjukkan pada gambar 3, diperlukan minimal 3 warna. Jumlah tersebut disebut juga sebagai bilangan kromatik. 6.Penjadwalan Pewarnaan graf dan algoritma Welch-Powell dapat diterapkan dalam pembuatan jadwal, contohnya jadwal ujian skripsi, jadal ujian akhir semester,dll. Cara pembuatan jadwal mengikuti langkah-langkah yang telah dibahas pada kedua materi tersebut. 7. Perancangan Sistem Untuk menerapkan pewarnaan graf dan algoritma Welch Powel diperlukan perencanaan sistem. Berikut contoh Perencanaan sistem dan hasil dari peneletian penerapan algoritma WelchPowell dan Pewarnaan graf pada pendjadwalan yang dilakukan oleh Pasnur dari jurusan Sistem Informasi, STMIK AKBA, Makassar, dikutip dari jurnal berjudul “Implementasi Algoritma Welch-Powell Dalam Pembuatan Jadwal Ujian Akhir Semester” (Tersedia: https://jurnal.akba.ac.id/index.php/inspiration/article/view/16/16 ) Berikut implementasinya : Dalam perancangan sistem, digunakan sebuah flowchart yang memperlihatkan alur pembuatan jadwal yang disesuaikan dengan algoritma WelchPowell (gambar 10).



Tahap



pertama



yang



akan



dilakukan



oleh



sistem



adalah



membuka



koneksi ke server database MySQL. Apabila koneksi berhasil dilakukan, maka sistem akan membersihkan tabel temporary 1 yang berisi data daftar mata kuliah secara berpasangan yang



memiliki keterhubungan (terdapat minimal seorang mahasiswa yang memprogramkan secara bersamaan kedua mata kuliah tersebut), serta tabel temporary 2 yang berisi data daftar simpul mata kuliah beserta derajat dan status pewarnaannya. Pada tahap selanjutnya program akan membuat dua buah array, masing-masing berisi daftar mahasiswa aktif (mahasiswa yang mengikuti perkuliahan minimal satu mata kuliah) dan daftar mata kuliah aktif (mata kuliah yang memiliki minimal satu peserta). Mata kuliah akan dianggap sebagai simpul dan akan diatur derajatnya masing-masing dengan angka 0. Selanjutnya program akan melakukan perhitungan derajat setiap simpul mata kuliah dilanjutkan dengan pengisian data pada tabel temporary 1 dan temporary 2. Untuk mulai proses pewarnaan graf, program akan memulai pengurutan simpul mata kuliah berdasarkan derajat tertinggi. Simpul mata kuliah dengan derajat tertinggi akan diberikan warna, dan dilanjutkan dengan pewarnaan simpul mata kuliah lain yang tidak bertetangga dengan simpul mata kuliah sebelumnya. Proses ini akan dilakukan secara berulang hingga semua simpul mata kuliah telah diwarnai. Pada tahap terakhir, program akan menampilkan daftar mata kuliah yang boleh memiliki jadwal ujian bersamaan dan program akan berakhir dengan penutupan koneksi database. 1. Hasil dan Pembahasan Pada



pengujian



program, digunakan database percobaan yang



terdiri atas tiga buah tabel, yaitu tabel mahasiswa, tabel mata kuliah, dan tabel pengujian. Data yang terdapat pada masing-masing tabel disederhanakan seperti pada tabeltabel berikut ini. Tabel 1 : Data mahasiswa NIM 20112205001 20112205002 20112205003 20112205004 20112205005



Nama Mahasiswa Andi Budi Wati Fadil Fatma



Tabel 2 : Data mata kuliah Kode MK-1 MK-2 MK-3 MK-4 MK-5 MK-6 MK-7



Nama Mata Kuliah Kecerdasan Buatan Sistem Basis Data Matematika Diskrit Pemrograman Web Statistika Pemodelan dan Simulasi Keamanan Komputer



Tabel 3 : Data perkuliahan Nama Mahasiswa Andi Andi Budi Budi Wati Wati Wati Fadil Fadil Fatma



Nama Mata Kuliah Kecerdasan Buatan Sistem Basis Data Matematika Diskrit Pemrograman Web Kecerdasan Buatan



Sistem Basis Data Pemodelan dan simulasi Kecerdasan Buatan Pemrograman Web Pemrograman Web



Pada saat program dijalankan, maka



program



akan



melakukan serangkaian proses seperti yang telah digambarkan pada gambar 10 tentang flowchart sistem. Setelah program menyelesaikan proses persiapan, maka program akan membuat daftar mata kuliah aktif sebagai simpul dan diurutkan berdasarkan derajat tertinggi. Gambar 11 berikut memperlihatkan graf simpul mata kuliah sebelum proses iterasi dimulai.



Gambar 11 : Kondisi graf sebelum proses iterasi dimulai Pada gambar 11 diketahui daftar simpul mata kuliah yang diurutkan berdasarkan derajat tertinggi, seperti pada tabel 4 berikut ini. Tabel 4 : Daftar simpul mata kuliah sebelum proses iterasi yang diurutkan berdasarkan derajat tertinggi Simpul Derajat MK-1 3 MK-2 2 MK-3 1 MK-4 2 MK-6 2 Pada proses iterasi pertama, program akan memberikan warna kepada simpul MK-1 sebagai simpul berderajat tertinggi ( gambar 12).



Gambar 12 : Pewarnaan simpul MK-1 sebagai simpul berderajat tertinggi. Selanjutnya program juga akan memberikan warna yang sama kepada simpul mata kuliah yang tidak bertetangga (tidak berhubungan langsung) dengan simpul MK-1, dalam hal ini adalah simpul MK-3 (gambar 13).



Gambar 13 : Pewarnaan simpul MK-3 dengan warna yang sama dengan simpul MK-1. Pada iterasi kedua, program akan mengurutkan kembali simpul mata kuliah yang belum diwarnai berdasarkan derajat tertinggi. Pada iterasi ini, didapatkan bahwa simpul MK2 merupakan simpul berderajat tertinggi. Program akan memberikan warna yang kedua terhadap simpul MK-2 (gambar 14).



Gambar 14 : Pewarnaan simpul MK-2 dengan warna yang kedua sebagai simpul berderajat tertinggi pada proses iterasi yang kedua. Program juga akan memberikan warna yang sama dengan simpul mata kuliah lain yang tidak bertetangga dengan simpul MK2, dalam hal ini adalah simpul MK-4 (gambar 15).



Gambar 15 : Pewarnaan simpul MK-4 dengan warna yang sama dengan simpul MK-2. Pada iterasi yang ketiga, ternyata masih terdapat satu simpul mata kuliah yang belum diwarnai, dalam hal ini adalah simpul MK-6. Simpul tersebut akan diberikan warna yang ketiga (gambar 16).



Gambar 16 : Pewarnaan simpul MK-6 dengan warna yang ketiga sebagai simpul berderajat tertinggi pada proses iterasi yang ketiga. Proses pewarnaan graf akan selesai jika semua simpul mata kuliah telah diberikan warna. Simpul-simpul yang memiliki warna yang sama merupakan mata kuliah yang boleh memiliki jadwal ujian akhir semester yang bersamaan. Mata kuliah yang boleh memiliki jadwal ujian akhir bersamaan, yaitu MK-1 dengan MK3, serta MK-2 dengan MK-4. Mata kuliah MK-6 memiliki jadwal tersendiri. Jumlah warna yang dipakai menunjukkan jumlah jadwal minimum yang harsu dilaksanakan, dalam hal ini berjumlah 3 (tiga). Pada saat program diakses melalui web browser, maka akan tampil informasi jadwal ujian akhir semester seperti pada gambar 17 berikut ini.



Gambar 17 : Tampilkan hasil eksekusi program melalui web browser. Pada gambar 17 di atas terlihat informasi mengenai jadwal ujian akhir semester untuk kasus data yang diteliti. Jadwal tersebut terdiri atas jadwal pertama yang menyelenggarakan ujian untuk mata kuliah MK-1 dan MK-3, jadwal kedua yang menyelenggarakan ujian MK2 dan MK-4, serta jadwal ketiga yang menyelengarakan ujian MK-6. Hasil tersebut sejalan dengan proses pewarnaan graf secara konvensional. KESIMPULAN Dari seluruh pembahasan di atas dan berdasarkan beberapa hasil penelitian tentang Penerapan Pewarnaan Graf dalam menentukan jadwal menggunakan Algoritma WelchPowell maka dapat disimpulkan beberapa hal : 1. Pewarnaan graf dapat diterapkan dalam pembuatan jadwal, contohnya jadwal ujian akhir, jadwal penerbangan, jadwal ujian skripsi, dll 2. Langkah pertama yang dilakukan untuk membuat jadwal adalah memetakan jadwal ke dalam graf lalu menentukan bilangan kromatik graf tersebut.



3. Pewarnaan graf dengan menggunakan algoritma Welch-Powell dapat menyelesaikan pembuatan jadwal sedemikian sehingga tidak terjadi masalah penjadwalan yang bertumbukan atau jadwal yang bentrok. 4. Algoritma Welch-Powell cukup praktis untuk digunakan dalam pewarnaan simpul dala sebuah graf dan memiliki hasil yang lebih efisien.



Daftar Pustaka Pasnur.(2012). “Implementasi Algoritma Welch-Powell dalam Pembuatan Jadwal Ujian Akhir



Semester”.



Tersedia



:



https://jurnal.akba.ac.id/index.php/inspiration/article/view/16/16 Harianto, Koko, dkk. (2016). “Penerapan Simpul Graf untuk Menentukan Jadwal Ujian Skripsi pada STMIK Amik Riau Menggunakan Algoritma Welch-Powell”. Tersedia : http://bpm.stmik-amik-riau.ac.id/index.php/satin/article/view/27 Susiloputro, Agus, dkk. (2012). “Penerapan Pewarnaan Graf pada Penjadwalan Ujian Menggunakan Algoritma Welch-Powell”. Tersedia : https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact= 8&ved=2ahUKEwiNgNeF0KDpAhXZdCsKHb31DRAQFjABegQIARAB&url=https%3A %2F%2Fjournal.unnes.ac.id%2Fsju%2Findex.php%2Fujm%2Farticle%2Fdownload%2F6 10%2F899&usg=AOvVaw2e_pWrKkf-JcC98reRcjxo Supiyandi, dkk. (2019). “ Penerapan Tekik Pewarnaan Graf pada Penjadwalan Ujian dengan Algoritma Welch-Powell”. Tersedia : http://jurnal.uinsu.ac.id/index.php/algoritma/article/view/3153/1876 Ghassani, Hishshah. (2015). “Aplikasi Graf pada Penentuan Jadwal dan Jalur Penerbangan”. Tersedia : https://www.google.com/search?client=firefox-bd&q=Aplikasi+Graf+pada+Penentuan+jadwal+dan+jalur+penerbangan-+Hishshah Astuti, Setia.(2011). “Penyusunan Jadwal Ujian Mata Kuliah dengan Algoritma Pewarnaan Welch-Powell”. Tersedia : https://publikasi.dinus.ac.id/index.php/dian/article/view/23