PERBANDINGAN ALGORITMA WELCH POWELL DENGANALGORITMA GREEDY PADA PEWARNAAN PETAPROVINSI SUMATERA UTARA
| Main Author: | Roy Mukti Ayu Lestari, |
|---|---|
| Format: | Thesis NonPeerReviewed Book |
| Bahasa: | eng |
| Terbitan: |
, 2014
|
| Subjects: | |
| Online Access: |
http://repository.uin-suska.ac.id/3815/1/fm.pdf http://repository.uin-suska.ac.id/3815/2/Bab%20I.pdf http://repository.uin-suska.ac.id/3815/3/Bab%20II.pdf http://repository.uin-suska.ac.id/3815/4/Bab%20III%28a%29.pdf http://repository.uin-suska.ac.id/3815/5/Bab%20IV.pdf http://repository.uin-suska.ac.id/3815/6/Bab%20V.pdf http://repository.uin-suska.ac.id/3815/7/em.pdf http://repository.uin-suska.ac.id/3815/ |
Daftar Isi:
- Pewarnaan pada teori graf terdiri atas tiga macam yaitu pewarnaan simpul, pewarnaan sisi dan pewarnaan wilayah. Pada pewarnaan simpul, setiap simpul diberi warna sedemikian sehingga setiap simpul yang bertetangga memiliki warna yang berbeda.Tujuan utama dari pewarnaan simpul adalah mendapatkan banyaknya warna minimum yang dibutuhkan untuk mewarnai suatu graf, yang biasa disebut bilangan kromatik. Salah satu penerapan pewarnaan simpul adalah pewarnaan suatu peta sedemikian sehingga setiap daerah yang bersebelahan harus diberi warna yang berbeda. Algoritma yang digunakanpada tugas akhir iniialah algoritma Welch Powell dan algoritma Greedy.Kedua algoritma ini akan digunakan untuk mewarnai peta Provinsi Sumatera Utara. Pewarnaan peta Provinsi Sumatera Utara dengan kedua algoritma tersebut, mendapatkan bilangan kromatik yang sama yaitu χ (G) = 4. Kemudian dari hasil pewarnaan peta Provinsi Sumatera Utara dapat disimpulkan bahwa algoritma Welch Powell lebih efisien dibandingkan algoritma Greedydimana banyak operasi yang dilakukan pada algoritma Welch Powell23 operasi sedangkan algoritma Greedy 318 operasi. Katakunci:algoritma Greedy, algoritma Welch Powell, bilangan