Aplikasi Algoritma Greedy Untuk Pewarnaan Wilayah pada Peta Kota Padang Berbasis Teorema Empat Warna

Muthia, Zalfa Jofie (2020) Aplikasi Algoritma Greedy Untuk Pewarnaan Wilayah pada Peta Kota Padang Berbasis Teorema Empat Warna. Diploma thesis, Universitas Andalas.

Preview	Text (cover dan abstrak) cover + abstrak.pdf - Published Version Download (275kB) | Preview
Preview	Text (bab 1 pendahuluan) pendahuluan.pdf - Published Version Download (134kB) | Preview
Preview	Text (bab 5 penutup) penutup.pdf - Published Version Download (130kB) | Preview
Preview	Text (daftar pustaka) daftar pustaka.pdf - Published Version Download (130kB) | Preview
	Text (skripsi full text) Full.pdf - Published Version Restricted to Repository staff only Download (15MB)

Abstract

Kecamatan - kecamatan pada peta kota Padang diwarnai dengan menggunakan algoritma Greedy. Pewarnaan wilayah yang mengasumsikan sebuah kecamatan sebagai simpul dan sisi sebagai penghubung antar kecamatan yang bertetangga tersebut, menggunakan teorema empat warna yang menyatakan banyak warna minimum yang akan digunakan dalam mewarnai peta. Sebelum algoritma Greedy digunakan, graf dual peta tersebut dikonstruksi dan derajat tiap simpul ditentukan. Pada penggunaan algoritma Greedy, himpunan kandidat warna dan inisialisasi solusi dibuat. Selanjutnya, dilakukan pewarnaan pertama kali untuk simpul dengan derajat terbesar, dengan cara memilih secara sebarang warna pada himpunan kandidat. Kemudian, periksa kelayakan dari warna dengan menggunakan prinsip bahwa dua simpul yang bertetangga tidak boleh memiliki warna yang sama. Warna yang dihasilkan kemudian merupakan elemen dari himpunan solusi. Proses pewarnaan tersebut diulangi hingga semua wilayah kecamatan pada peta tersebut diwarnai.

Actions (login required)

View Item