PENERAPAN GREEDY COLORING ALGORITHM PADA PETA KOTAMADYA YOGYAKARTA BERBASIS FOUR-COLOUR THEOREM

Noor Saif Muhammad Mussafi (Program Studi Matematika, Fakultas Sains dan Teknologi, UIN Sunan Kalijaga Yogyakarta)

Kaunia: Integration and Interconnection of Islam and Science Journal
Vol. 11 No. 1 (2015)

Pewarnaan peta merupakan suatu proses pemberian warna pada daerah-daerah pada suatu peta sehingga pada kedua daerah yang berbatasan langsung akan memiliki warna yang berbeda. Dalam hal ini diperlukan warna yang boleh jadi sama banyak dengan jumlah daerah pada kotamadya tertentu yang dapat menyebabkan tidak efisien. Oleh karena itu perlu ditelaah bagaimana penentuan warna pada peta dengan menggunakan warna pada peta seminimal mungkin. Dalam teori graf, persoalan ini dapat direpresentasikan menggunakan graf dual dan pewarnaan graf yang lebih dikenal dengan bilangan kromatik. Penyelesaian  masalah bilangan kromatik dapat dianalisis menggunakan algoritma greedy coloring. Penelitian ini bertujuan menerapkan algoritma greedy coloring pada peta Kotamadya Yogyakarta berbasis teorema 4 warna.