eprintid: 3741
rev_number: 10
eprint_status: archive
userid: 52
dir: disk0/00/00/37/41
datestamp: 2020-10-08 06:08:48
lastmod: 2020-10-08 06:08:48
status_changed: 2020-10-08 06:08:48
type: thesis
metadata_visibility: show
contact_email: repository@staff.ukdw.ac.id
creators_name: 22064173, LEONARD RINALDY MAHAKAM PUTRA GINTING
creators_id: 22064173@ukdw.ac.id
contributors_type: http://www.loc.gov/loc.terms/relators/THS
contributors_type: http://www.loc.gov/loc.terms/relators/THS
contributors_name: Santosa, R. Gunawan
contributors_name: C., Antonius Rachmat
corp_creators: Universitas Kristen Duta Wacana
title: SIMULASI ALGORITMA WELCH-POWELL UNTUK MELAKUKAN PEWARNAAN GRAPH
ispublished: pub
subjects: QA75
subjects: T1
divisions: tek_informatika
full_text_status: public
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.
date: 2012-06
date_type: published
pages: 46
institution: Universitas Kristen Duta Wacana
department: Informatika
thesis_type: skripsi
thesis_name: other
citation:   22064173, LEONARD RINALDY MAHAKAM PUTRA GINTING  (2012) SIMULASI ALGORITMA WELCH-POWELL UNTUK MELAKUKAN PEWARNAAN GRAPH.  Final Year Projects (S1) thesis, Universitas Kristen Duta Wacana.   
document_url: https://katalog.ukdw.ac.id/3741/1/22064173_bab1_bab5_daftarpustaka.pdf
document_url: https://katalog.ukdw.ac.id/3741/2/22064173_bab2-sd-bab4_lampiran.pdf