Makalah teori graf revisi2
Download as docx, pdf3 likes7,543 views
Dokumen ini membahas pembuktian deletion-contraction theorem dan penerapannya dalam penjadwalan ujian akhir program studi matematika, di mana graf digunakan untuk merepresentasikan hubungan antar mata kuliah. Metode pewarnaan simpul digunakan untuk menentukan bilangan kromatik yang menunjukkan waktu yang diperlukan agar ujian mata kuliah tidak bertumpukan. Hasil penelitian ini diharapkan dapat memberikan kontribusi sebagai referensi bagi mahasiswa yang mempelajari pewarnaan graf dan teorinya.
Makalah teori graf revisi2
- 1. 1 TUGAS MATA KULIAH TEORI GRAF PEMBUKTIAN DELETION-CONTRACTION THEOREM SERTA PENERAPANNYA DALAM PEMBUATAN JADWAL UJIAN AKHIR PROGRAM STUDI MATEMATIKA Disusun oleh: 1. Wigati P. Putri 07305141038 2. Ratnasari Dwi Ambarwati 10305141004 3. Meita Putri Rahayu 10305141005 4. Dwi Prihastuti 10305141020 5. Amalia Sita Nursanti 10305141038 PROGRAM STUDI MATEMATIKA JURUSAN PENDIDIKAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS NEGERI YOGYAKARTA 2012
- 2. 2 BAB I PENDAHULUAN A. Latar Belakang Matematika memiliki beberapa pokok bahasan, salah satunya adalah graf. Graf adalah himpunan tak kosong berhingga, yang terdiri dari himpunan rusuk dan himpunan simpul yang himpunan simpulnya tidak boleh kosong. Graf biasa digunakan sebagai visualisasi obyek-obyek agar lebih mudah dimengerti. Graf merupakan salah satu cabang ilmu matematika yang dapat diterapkan baik dalam ilmu matematika maupun dalam kehidupan sehari-hari. Salah satu topik pada graf adalah pewarnaan graf. Pewarnaan graf dibagi menjadi dua macam, yaitu pewarnaan simpul dan pewarnaan rusuk. Akan tetapi, jika tidak diberikan kualifikasinya, pewarnaan graf diartikan sebagai pewarnaan simpul dan pada makalah ini dikhususkan pada pewarnaan simpul. Mewarnai sebuah graf berarti memberi warna pada setiap simpul graf sedemikian hingga simpul dan rusuk yang berikatan dapat diwarnai dengan warna yang berbeda. Misalkan G adalah graf sederhana, banyaknya warna yang digunakan untuk mewarnai simpul graf G sedemikian sehingga simpul yang berikatan berlainan warna dinyatakan dengan k-pewarnaan. Jika G memiliki k-pewarnaan, maka G dikatakan dapat diberi warna dengan k warna. Pada pewarnaan simpul, jumlah warna yang boleh dipergunakan haruslah seminimal mungkin. Jumlah warna paling minimum yang dapat diterapkan pada graf ini sering disebut dengan bilangan kromatik (χ(G)). Salah satu metode yang digunakan untuk mewarnai graf adalah dengan menggunakan polinomial kromatik. Pewarnaan graf dapat diaplikasikan pada berbagai permasalahan sehari-hari, beberapa contoh diantaranya yaitu saluran televisi ditentukan ke pemancar-pemancar, sedemikian sehingga tidak ada dua pemancar dapat beroperasi pada saluran yang sama dalam jarak tertentu, struktur organisasi, bagan alir pengambilan mata kuliah, peta, rangkaian listrik, dan lain-lain. Makalah ini, membahas tentang penerapan pewarnaan simpul dalam penjadwalan ujian dengan metode Deletion-Contraction Theorem. Dalam masalah penjadwalan
- 3. 3 yang dinyatakan dalam bentuk graf, simpul menyatakan mata kuliah dalam jadwal. Rusuk antar dua buah simpul menyatakan bahwa kedua buah mata kuliah tidak dapat dikerjakan secara bersamaan. Warna menunjukkan waktu yang tersedia. Setiap mata kuliah membutuhkan satu waktu. Jadi dapat dituliskan: simpul v menerima mata kuliah i jika dan hanya jika v dieksekusi dalam waktu i. Sehingga graf k-warna berarti semua mata kuliah dapat dikerjakan dalam k waktu secara tidak bersamaan. B. Rumusan Masalah Berdasarkan latar belakang yang telah diuraikan diatas, maka rumusan masalah yang dapat diajukan adalah sebagai berikut: 1. Bagaimana pembuktian Deletion-Contraction Theorem? 2. Bagaimana cara menentukan banyaknya bilangan kromatik pada suatu graf dengan metode Deletion-Contraction Theorem? 3. Bagaimana penerapan pewarnaan simpul pada kasus penjadwalan ujian kuliah dengan metode Deletion-Contraction Theorem? C. Tujuan Tujuan dari makalah ini adalah sebagai berikut: 1. Membuktikan Deletion-Contraction Theorem. 2. Menentukan banyaknya bilangan kromatik pada suatu graf dengan metode Deletion-Contraction Theorem. 3. Menyelesaikan kasus penjadwalan ujian kuliah dengan metode Deletion- Contraction Theorem. D. Manfaat Hasil penelitian ini bermanfaat sebagai tambahan literatur bagi mahasiswayang sedang mempelajari mengenai pewarnaan simpul, khususnya bilangan kromatik dengan metode Deletion-Contraction Theorem serta contoh penerapannya.
- 4. 4 BAB II LANDASAN TEORI A. Pengertian Graf Graf adalah himpunan tak kosong berhingga, yang terdiri dari himpunan rusuk dan himpunan simpul yang himpunan simpulnya tidak boleh kosong. Notasi graf: G(V,E) artinya graf G memiliki V simpul dan E rusuk. Simpul-simpul pada graf dapat merupakan obyek sembarang seperti kota, nama orang, jenis buah, komponen alat elektronik dan sebagainya. Rusuk dapat menunjukkan hubungan sembarang seperti rute penerbangan, jalan raya, sambungan telepon, ikatan kimia, dan lain-lain. B. Pewarnaan Graf Pewarnaan graf terbagi menjadi dua macam yaitu pewarnaan simpul dan pewarnaan rusuk. 1. Pewarnaan simpul didefinisikan sebagai berikut : Misalkan G adalah graf sederhana, k-pewarnaan untuk G menyatakan penggunaan sebanyak k-warna untuk simpul G sedemikian hingga simpul-simpul yang berikatan mendapat warna yang berbeda. Jika G memiliki k-pewarnaan, maka G dikatakan dapat diwarnai dengan k-warna (Wilson dan Watkins, 1989: 235). Berikut adalah contoh pewarnaan simpul pada graf G . Gambar 1. Pewarnaan Simpul pada Graf G
- 5. 5 Gambar 1(a), (b), dan (c) secara berturut-turut adalah 3-pewarnaan, 4-pewarnaan, dan 5-pewarnaan dari graf G . Gambar 1 (d) bukan merupakan pewarnaan simpul dari graf G , karena terdapat dua simpul berikatan yang memiliki warna sama. 2. Pewarnaan rusuk didefinisikan sebagai berikut : Misal G adalah graf sederhana, k-pewarnaan rusuk untuk G adalah pemberian sebanyak k warna pada rusuk-rusuk G sedemikian hingga setiap dua rusuk yang bertemu dengan simpul yang sama mendapat warna berbeda. Jika G memiliki k- pewarnaan rusuk, maka rusuk graf G dikatakan dapat diwarnai dengan k warna (Wilson dan Watkins, 1989: 240). Berikut adalah contoh pewarnaan rusuk pada graf G Gambar 2. Pewarnaan Rusuk pada Graf G Gambar 2 (a), (b), dan (c) secara berturut-turut adalah 4-pewarnaan rusuk, 5- pewarnaan rusuk, dan 6-pewarnaan rusuk dari graf G. Gambar 2 (d) bukan merupakan pewarnaan rusuk dari graf G, karena terdapat dua rusuk berwarna sama yang bertemu pada simpul yang sama.
- 6. 6 BAB III PEMBAHASAN A. Pewarnaan Simpul Pewarnaan simpul pada graf adalah suatu pemetaan dari himpunan simpul ke himpunan warna sedemikian sehingga setiap dua simpul yang berikatan mempunyai warna yang berbeda. Misalkan G adalah graf sederhana, k-pewarnaan untuk G menyatakan penggunaan sebanyak k-warna untuk simpul G. (Wilson dan Watkins, 1989: 235). Pewarnaan graf dapat dilakukan dengan menggunakan Algoritma Welsh dan Powell. Algoritma ini memberikan cara mewarnai sebuah graf dengan memberi label simpul-simpulnya sesuai dengan derajatnya. Langkah-langkahnya sebagai berikut: Langkah 1 Setiap simpul pada graf diberi label sesuai dengan derajatnya. Simpul diurutkan mulai dari yang berderajat terbesar sampai dengan derajat terkecil. Simpul diberi nama , sedemikian hingga atau membentuk barisan tidak naik. Langkah 2 Memberikan warna pertama pada simpul yang pertama (yang berderajat terbesar) pada daftar simpul tersebut. Kemudian dicari simpul yang tidak berdekatan dengan simpul yang pertama tadi kemudian warnai simpul tersebut dengan warna yang sama dengan warna simpul yang pertama. Lakukan terus menerus sesuai urutan sampai tidak ada lagi yang tidak berdekatan. Langkah 3 Jika ada simpul yang belum berwarna, maka ulangi lagi langkah ke 2 dengan warna yang berbeda sampai semua simpul telah diberi warna. Langkah 4 (selesai). Pewarnaan graf sudah selesai. B. Polinomial Kromatik Misal G merupakan graf sederhana, dan adalah banyak cara mewarnai simpul G dengan k warna sedemikian hingga dua simpul yang berikatan mendapat warna yang berbeda. Fungsi disebut polinomial kromatik G atau suku banyak kromatik G .
- 7. 7 Contoh berikut dapat menjelaskan alasan banyak pewarnaan-k dari G harus menjadi polinomial dalam k, dengan k adalah bilangan bulat positif. Jadi: Contoh 1 Gambar 3. Polinomial Kromatik pada Graf adalah graf lengkap-3. Simpul puncak dapat diberi warna sembarang dari k warna tersebut. Simpul di sebelah kirinya dapat diberi warna sembarang dari (k-1) warna yang belum diberikan pada simpul puncak. Simpul di sebelah kanan simpul puncak dapat diberi warna sembarang dari (k-2) warna yang belum terpakai. Sehingga, banyak cara mewarnai adalah atau (Wilson dan Watkins, 1989: 237, 238). Contoh 2 Gambar 4. Polinomial Kromatik pada Graf Jika G adalah lintasan graf P3 simpul paling kiri dapat diwarnai dengan sebanyak k-warna, simpul tengah dapat diwarnai dengan k-1 warna selain warna yang diberikan pada simpul kiri, dan simpul kanan dapat diwarnai dengan k-1 warna yang sama dengan simpul tengah. Pemberian warna pada tidak tunggal, sehingga jika simpul tengah diberikan sebanyak k warna, maka simpul kiri diberi k-1 warna selain warna yang diberikan pada simpul tengah, begitu juga pada simpul kanan diberi warna sebanyak k-1 warna selain yang warna yang diberikan pada simpul tengah. Sehingga, banyak cara mewarnai adalah atau . Berdasarkan contoh diatas, dapat disimpulkan bahwa: Jika G adalah pohon dengan n-simpul, maka . k k-1 k-1
- 8. 8 Dari kesimpulan tersebut, didapat bahwa graf non-isomorfis mempunyai polinomial kromatik yang sama. Jika polinomial kromatik diketahui, maka bilangan kromatik suatu graf dapat dihitung dengan mudah, karena bilangan kromatik graf G adalah bilangan bulat positif terkecil k yang memenuhi Jika cara untuk menentukan polinomial kromatiknya sudah ditemukan, maka dapat diturunkan sebuah algoritma untuk menentukan bilangan kromatik. Dari contoh diatas dapat dilihat bahwa Sehingga, dimana G, G e, dan G e seperti graf berikut: Gambar 5. G, G e, dan G e Dengan G e didapat dari G dengan menghapus rusuk e. G e didapat dari G dengan memampatkan rusuk e. Gagasan tersebut menghasilkan sebuh teorema, yang disebut Deletion-Contraction Theorem. C. Pembuktian teorema Deletion-Contraction Theorem Teorema Misal G adalah graf sederhana, dan G e serta G e adalah graf yang diperoleh dari G dengan menghapus dan memampatkan suatu rusuk e. Maka, G G e e G e e
- 9. 9 Pembuktian: Misal e = vw adalah rusuk dari G. G e adalah graf yang secara umum diperoleh dengan menghapus rusuk e dan G e adalah graf yang diperoleh dengan memampatkan rusuk e. Jika simpul v dan w pada graf G e diberikan warna berbeda, maka banyak cara mewarnai G e sama dengan banyak cara mewarnai G. Jika simpul v dan w pada graf G e diberikan warna sama, maka banyak cara mewarnai G e sama dengan banyak cara mewarnai G e. Sehingga, jumlah total pewarnaan-k untuk G e adalah Contoh: Gambar 6. Pembentukan Polinomial Kromatik Graf G
- 10. 10 Diperoleh bahwa: Karena dengan adalah K minimal sehingga > 0, maka . (Wilson dan Watkins, 1989:240) D. Penerapan Pewarnaan Simpul pada Kasus Penjadwalan Ujian Kuliah dengan Metode Deletion-Contraction Salah satu aplikasi pewarnaan simpul dalam kehidupan sehari-hari adalah kasus penjadwalan ujian kuliah. Misalkan, terdapat 10 mahasiswa yang akan mengikuti ujian kuliah. Pada prodi Matematika terdapat lima mata kuliah yang akan diujikan, yaitu FPK, Aljabar Abstrak, Teori Graf, Sistem Geometri, dan Statistika Matematika, mata kuliah tersebut disimbolkan secara berurutan sebagai berikut A, B, C, D, dan E. Setiap mahasiswa memilih dua mata kuliah yang berbeda, matriks mahasiswa dan mata kuliahnya adalah sebagai berikut: Tabel 2. Matriks Mahasiswa dan Mata Kuliah A B C D E 1 0 1 0 1 0 2 1 1 0 0 0 3 0 0 1 0 1 4 0 0 0 1 1 5 1 0 0 1 0 6 0 1 0 1 0 7 1 0 1 0 0 8 1 0 0 0 1 9 1 0 0 1 0 10 0 0 0 1 1 Tentukan banyaknya jadwal ujian yang dapat dibuat sedemikian rupa sehingga semua siswa dapat mengikuti ujian mata kuliah tersebut tanpa ada kesulitan waktu.
- 11. 11 Solusi: Masalah penjadwalan ujian ini dapat diselesaikan dengan menggunakan metode pewarnaan simpul, dengan simpul mewakili mata kuliah dan rusuk antara dua simpul mewakili bahwa ada mahasiswa yang mengambil kedua mata kuliah yang diwakili simpul-simpul tersebut, sehingga ujian kedua mata kuliah yang diambil mahasiswa tersebut tidak dapat dilakukan bersamaan. Masalah tersebut dapat dibuat dalam bentuk graf, yaitu sebagai berikut Gambar 7. Graf Representasi Masalah Penjadwalan Ujian Dengan menggunakan metode Deletion-Contraction, maka: Gambar 8. Pembentukan Polinomial Kromatik dengan Metode Deletion- Contraction
- 12. 12 dengan polinomial Kromatiknya yaitu: Karena =0, =0, =0, dan =6, adalah K minimal, sehingga > 0. Jadi, bilangan kromatik dari graf tersebut adalah 3. Dari kesimpulan tersebut, terdapat 3 jadwal yang dapat dibuat agar setiap mahasiswa tidak mendapatkan jadwal ujian dua mata kuliah yang diambil dalam waktu yang bersamaan. Untuk menentukan pewarnaan graf pada graf tersebut, akan di tentukan dengan menggunakan Algoritma Welsh-Powell: 1. Memberikan label simpul sedemikian sehingga
- 13. 13 2. Memberi warna merah pada simpul v1, karena v1 berikatan dengan v2, v3, v4, dan v5 maka tidak ada simpul lain yang mempunyai warna yang sama dengan v1. 3. Memberi warna biru pada simpul v2, berikan warna yang sama pada simpul- simpul yang tidak berikatan dengan v2 yaitu v5. 4. Memberi warna hijau pada simpul v3, berikan warna yang sama pada simpul- simpul yang tidak berikatan dengan v3 yaitu v4. 5. Karena semua simpul sudah diberi warna maka algoritma selesai. Berdasarkan pewarnaan simpul dengan menggunakan algoritma Welsh-Powell, maka peroleh: simpul diberi warna merah, simpul diberi warna hijau, simpul diberi warna biru, sehingga terdapat 3 macam warna pada graf tersebut.
- 14. 14 BAB IV PENUTUP A. KESIMPULAN 1. Berdasarkan pembahasan di atas maka Deletion-Contraction Theorem terbukti. 2. Penentuan banyaknya bilangan kromatik dengan metode Deletion-Contraction Theorem yaitu: 3. Salah satu aplikasi penghitungan banyaknya cara memberikan warna simpul yang menggunakan Deletion-Conttraction Theorem adalah pembuatan jadwal ujian Prodi Matematika FMIPA UNY. B. SARAN Deletion-Contraction Theorem sebaiknya digunakan untuk menghitung banyaknya pewarnaan simpul pada graf yang rumit.
- 15. 15 DAFTAR PUSTAKA ----. ----. MateriPewarnaanGraf. Diakses dari http://www.itt elkom.ac.id pada Sabtu, 10 November 2012 pukul 7:08 PM Devadas, Srini dan Eric Lehman. 2005. Graph Teory II. Diakses darihttp://files.myopera.com/m4th03/files/vertex_coloring_graph.pdf pada Sabtu, 10 November 2012 pukul 6:42 PM Maaruf, Faridah. ----. Pengenalan Teori Graf. Diakses dari http://books.google.co.id/books?id=teQ1aMau9i8C&pg=PA113&lpg=PA113&d q=cara+menentukan+polinomial+kromatik&source=bl&ots=p9KCYF0gog&sig= yhqKLURDCZAsqHttx8zDlfdQ5zY&hl=id&sa=X&ei=fTqgUKvklcqVmQW4y YHQCA&ved=0CBoQ6AEwAA#v=onepage&q&f=falsepada Rabu, 14 November 2012 pukul 16.00 PM Priatna, Nanang. ----. Pewarnaan Graf. Diakses dari http://file.upi.edu/Direktori/FPMIPA/JUR._PEND._MATEMATIKA/196303311 988031-NANANG_PRIATNA/Pewarnaan_Graph.pdf pada Rabu, 14 November 2012 pukul 16.00 PM Wilson, Robin J.& John J. Watkins. 1990. Graphs: An Introducing Approach. Singapore