SIMULASI ALGORITMA WELCH-POWELL UNTUK MELAKUKAN PEWARNAAN GRAPH

22064173, LEONARD RINALDY MAHAKAM PUTRA GINTING (2012) SIMULASI ALGORITMA WELCH-POWELL UNTUK MELAKUKAN PEWARNAAN GRAPH. Bachelor thesis, Universitas Kristen Duta Wacana.

	Text (Skripsi Informatika) 22064173_bab1_bab5_daftarpustaka.pdf Download (2MB)
	Text (Skripsi Informatika) 22064173_bab2-sd-bab4_lampiran.pdf Download (3MB)

Abstract

Teori graph merupakan topik yang banyak mendapatkan perhatian saat ini, karena model-model yang ada pada teori graph berguna untuk aplikasi yang luas. Walaupun teori graph berasal dari bidang ilmu matematika, namun pada penerapannya, teori graph dapat dihubungkan dengan berbagai ilmu dan juga kehidupan sehari-hari. Setiap ilmu dapat dikaitkan dengan graph seperti masalah dalam Jaringan Komunikasi, Transportasi, Ilmu Komputer, Riset Operasi, Ilmu Kimia, Sosiologi, Kartografii dan ilmu lainnya. Teori-teori mengenai graph ini telah banyak dikembangkan dengan berbagai algoritma yang memiliki kelebihan dan kelemahan masing-masing dalam menyelesaikannya. Teori pewarnaan graph merupakan salah satu objek yang menarik dan terkenal dalam bidang ilmu graph. Pewarnaan simpul (vertex coloring) suatu graph adalah pemberian warna pada vertex hingga dua vertex yang berdampingan mempunyai warna yang berlainan. Sebuah vertex dapat diberikan sembarang warna asalkan warna yang diberikan berbeda dengan vertex yang berdekatan dengannya. Salah satu algoritma pewarnaa graph adalah algoritma welch-powell. Schaerf (1999) menyatakan bahwa pada algoritma welch-powell, vertex dengan derajat terbesar diwarnai terlebih dahulu, yaitu vertex yang memiliki jumlah edge paling banyak, sebab vertex dengan derajat yang besar merupakan vertex yang paling sulit diwarnai. Hasil pada penelitian ini berupa sebuah sistem untuk mencari jumlah warna minimum yang diperlukan untuk mewarnai graph disebut bilangan chromatic (kromatik) dari G atau dapat disimbolkan dengan K(G). Sebuah graph komplit (Kn) memiliki bilangan kromatik K sebanyak n, artinya warna minimal yang dibutuhkan graph komplit adalah sebanyak n warna. Setelah melakukan percobaan-percobaan dengan menggunakan graph sembarang yang memiliki bagian graph komplit (Kn) dengan menggunakan algoritma Welch-Powell, hasil yang diperoleh adalah algoritma Welch-Powell tidak menjamin hasil pewarnaan yang diperoleh sudah optimal, karena dari 20 percobaan ada satu percobaan yang pewarnaannya tidak optimal.

Actions (login required)

View Item