Roy Mukti Ayu Lestari (2014) PERBANDINGAN ALGORITMA WELCH POWELL DENGANALGORITMA GREEDY PADA PEWARNAAN PETAPROVINSI SUMATERA UTARA. Skripsi thesis, Universitas Islam Negeri Sultan Syarif Kasim Riau.

Preview	Text fm.pdf Download (92kB) | Preview
Preview	Text Bab I.pdf Download (26kB) | Preview
Preview	Text Bab II.pdf Download (131kB) | Preview
Preview	Text Bab III(a).pdf Download (15kB) | Preview
	Text Bab IV.pdf Restricted to Registered users only Download (3MB)
Preview	Text Bab V.pdf Download (20kB) | Preview
Preview	Text em.pdf Download (8kB) | Preview

Abstract

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

Actions (login required)

View Item