Dalam Proses Makalah Logika.docx

MAKALAH PEWARNAAN (COLORING)

Anggota:

       

Melati Teodora yanti Diko kurniadi Iswandi Albertus frengki kurniadi Heri Muhammad andra M.wisnu prasetya kurniawan

Kelas Dosen Rabiatuladwiyah

(12184904) (12181754) (12181465) (12180660) (12181356) (12181615) (12180488) (12181210)

: 12.1E.30 :

SISTEM INFORMATIKA UNIVERSITAS BINA SARANA INFORMATIKA JL. Abdurahman saleh no.A-18,Bangka belitung laut,pontianak tenggara,kota pontianak,kalimantan barat 78112

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 membangunsangasayasiapkan.

DAFTAR ISI

Halaman HALAMAN JUDUL ........................................................................................ KATA PENGANTAR ...................................................................................... DAFTAR ISI ...................................................................................................

BAB I

PEMBAHASAN A.Pendahuluan B.penjelasan graf........................................................................ C.pengertian pewarnaan garf ..................................................... D.macam-macam pewarnaan graf ............................................. E.contoh-contoh pewarnaan garf...............................................

BAB II

PENUTUP A.Kesimpulan ............................................................................ B.saran .......................................................................................

DAFTAR PUSTAKA ...............................................................................

A.PENDAHULUAN Jika kalian melihat peta, kalian akan melihat banyak sekali warna - warna yang terdapat pada setiap wilayah di peta. Biasanya warna – warna pada peta tersebut disesuaikan dengan ketinggian wilayah dan juga berdasarkan provinsi, kota, atau bahkan negara. Kali ini, yang akan dibahas adalah bagaimana untuk memberikan warna pada peta dengan teori graf dan teori pewarnaan graf yang sudah dipelajari pada semester 1 ini. Teorema Pewarnaan Graf menyatakan bahwa jumlah maksimal yang dapat digunakan untuk memberikan warna pada graf planar adalah 6, sehingga dapat ditulis bilangan kromatik <= 6 yang artinya jumlah warnanya kurang dari 6. Namun seiring berjalannya waktu, teorema tersebut berubah-ubah sehingga teorema yang paling terakhir adalah jumlah maksimal yang dapat digunakan untuk memberian warna pada graf planar adalah 4 atau disebut juga bilangan kromatiknya <= 4. Teorema Pewarnaan Graf tersebut itulah yang akhirnya dijadikan sebagai landasan untuk menentukan jumlah warna yang akan dipakai dalam sebuah peta. Awal mula dibentuknya sebuah teori graf adalah pada sekitar abad 18. Saat itu di kota Konigsberg terdapat banyak sungai – sungai dan ada 7 jembatan yang menghubungkan sungai – sungai tersebut. Waktu itu terbentuklah suatu tantangan untuk membuat rute perjalanan mengelilingi jembatan tersebut, namun satu jembatan harus dilewati maksimal satu kali saja. Akhirnya seorang ilmuwan bernama Leonhard Euler merasa tertantang dan ingin membuat solusi dari tantangan tersebut. Dan inilah yang merupakan akar dari ilmu teori graf.

A.PENGERTIAN GRAF Graf adalah sesuatu yang berfungsi untuk menggambarkan hubungan antara suatu objek – objek terutama objek diskrit. Contohnya adalah rute pesawat, rute perjalanan, atau bahkan yang seperti kita bahas sekarang, peta, juga termasuk ke dalam graf. Graf terdiri atas dua bagian penting, yaitu simpul atau disebut juga dengan vertex, dan sisi atau disebut juga dengan edge. Sisi adalah sesuatu yang menjadi penghubung antara objek – objek diskrit, sedangkan simpul adalah objek diskrit itu sendiri, sehingga pada dasarnya sisi adalah sesuatu yang dapat menghubungkan simpul – simpul.

B.PENGERTIAN PEWARNAAN GRAF (COLORING) Pewarnaan graf adalah proses pelabelan setiap simpul dalam graf dengan label tertentu (warna) sehingga tidak ada dua simpul bertetangga yang memiliki warna sama. Warna yang kita gunakan untuk mewarnai objek diusahakan seminimal mungkin. Jumlah warna minimum yang dapat digunakan untuk mewarnai simpul disebut bilangan kromatik

C. MACAM-MACAM PEWARNAAN GRAF (COLORING) a.pewarnaan simpul Pewarnaan simpul atau yang disebut juga dengan vertex coloring adalah bagaimana cara memberikan warna pada simpul – simpul sehingga simpul – simpul yang berdekatan atau bersebelahan atau bertetangga tidak memiliki warna yang sama. b. Pewarnaan sisi Pewarnaan sisi atau yang disebut juga dengan edge coloring adalah bagaimana cara memberikan warna sisi – sisi pada graf sehingga sisi – sisi yang berdekatan atau bersebelahan atau bertetangga tidak memiliki warna yang sama, sehingga tidak ada dua sisi berdekatan yang memiliki warna yang sama.

c. Pewarnaan ruang / bidang Sama halnya dengan pewarnaan simpul dan sisi, pewarnaan ruang atau disebut juga dengan pewarnaan bidang adalah bagaimana cara memberikan warna pada bidang – bidang sehingga tidak ada ruang yang berdekatan atau bertetangga yang memiliki warna yang sama. Dalam mewarnai objek – objek graf harus digunakan warna sejumlah banyak warna minimal. Jumlah warna minimal yang harus digunakan itulah yang dinamakan dengan bilangan kromatik atau dilambangkan dengan 𝐾

E. CONTOH-CONTOH PEWARNAAN GRAF (COLORING)  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.

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.

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.

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.

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.

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  Gambar peta

BAB 2 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.

Saran Secara keseluruhan tujuan penelitian sudah tercapai, namun sistem ini belum dilengkapi dengan keamanan data dan keamanan sistem, sehingga penulis memberikan saran bagi peneliti berikutnya untuk membuat sistem keamanan sehingga dapat menyempurnakan makalah ini.

DAFTAR PUSTAKA 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.