BILANGAN KROMATIK PADA GRAF LIMAS, PRISMA DAN GABUNGAN LIMAS_PRISMA

Abstract

Pewarnaan peta pada graf merupakan aplikasi yang erat kaitannya dengan penentuan bilangan kromatik. Bilangan kromatik merupakan sasaran utama dari pewarnaan pada suatu graf. Dimana bilangan kromatik pada pewarnaan peta menunjukkan minimum banyaknya warna yang diperlukan untuk mewarnai semua wilayah pada sebuah peta, sedemikian sehingga setiap dua wilayah yang berhubungan langsung atau berbatasan mendapatkan warna yang berbeda. Penelitian ini dilakukan untuk menentukan bilangan kromatik graf limas, prisma dan gabungan limas_prisma dengan menggunakan tiga algoritma pewarnaan graf, yaitu algoritma simple sequence coloring, algoritma welch-powell dan algoritma recursive large first. Langakh-langkah yang dilakukan adalah : a) Bangun ruang limas, prisma dan gabungan limas_prisma ditransformasikan menjadi graf bidang, b) Simpul-simpul representasi dari graf bidang diwarnai dengan menggunakan algoritma pewarnaan, c) Bilangan kromatik disimulasikan secara manual dan dengan menggunakan software Microsoft Visual Basic 6.0.