PEWARNAAN GRAF

Ina Agustina, Nargis Riana

Abstract


Teori graf merupakan pokok bahasan yang sudah tua usianya namun memiliki banyak terapan sampai saat
ini. Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.
Representasi visual dari graf adalah dengan menyatakan objek dengan simpul, noktah, bulatan, titik, atau
vertex, sedangkan hubungan antara objek dinyatakan dengan garis atau edge. Salah satu aplikasi yang
berkaitan dengan graf adalah pewarnaan graf (graph colouring) yang terdiri dari pewarnaan simpul, sisi, dan
wilayah. Dalam makalah ini akan dibahas pewarnaan simpul saja. Pewarnaan simpul adalah memberi warna
pada simpul-simpul suatu graf sedemikian sehingga tidak ada dua simpul bertetangga mempunyai warna
yang sama. Jumlah warna minimum yang dapat digunakan untuk mewarnai graf dinyatakan dengan bilangan
kromatik. Pewarnaan graf dapat diselesaikan salah satunya dengan menggunakan algoritma runutbalik
(backtracking). Algoritma runut-balik adalah algoritma yang berbasis pada Depth First Search untuk mencari
solusi persoalan secara lebih mangkus


Full Text:

PDF

Refbacks

  • There are currently no refbacks.