| dc.description.abstract | Teori graf merupakan salah satu cabang ilmu matematika yang sudah tua
usianya namun mempunyai banyak terapan bagi seluruh masyarakat sampai saat ini.
Salah satu teori graf yang memiliki kontribusi besar bagi perkembangan ilmu
pengetahuan adalah pewarnaan graf. Pewarnaan graf adalah suatu pewarnaan ke
objek tertentu. Objek tersebut dapat berupa titik, sisi, atau wilayah. Suatu pewarnaan
graf diasumsikan dengan tidak memberi warna untuk dua titik yang bertetangga
dengan warna yang sama. Dalam hal ini, “bertetangga” berarti titik-titik yang terletak
pada sisi yang sama.
Ukuran terkecil banyaknya warna yang dapat diberikan kepada sebuah graf G
dinamakan dengan bilangan kromatik. Pertanyaan yang menarik adalah berapa
banyak cara berbeda yang digunakan untuk pemberian warna pada G dengan warna
yang disediakan atau biasa disebut polinomial kromatik. Polinomial kromatik
pertama kali diperkenalkan pada tahun 1946 oleh Birkhoff dalam upaya untuk
menyelesaikan masalah empat warna. Dalam Chartrand dan Oellermann (1993), kajian tentang polinomial kromatik telah dibahas oleh beberapa ilmuwan, diantaranya Read dan Skiena. Pada tahun 2004, Kurniawati juga telah meneliti polinomial kromatik dari graf terhubung, yaitu graf lengkap, graf sikel, dan graf lintasan. Pada skripsi ini, penulis ingin meneliti polinomial kromatik menggunakan partisi himpunan titik pada kelas graf sederhana yang lain yaitu graf bintang Sn, graf roda Wn, dan graf tangga Ln. Tujuan penelitian adalah untuk mendapatkan polinomial kromatik dari kelas graf sederhana tersebut.
Penelitian dilakukan dalam empat langkah, yaitu mencari bilangan kromatik
pada graf, kemudian menentukan kemungkinan pewarnaan titik yang terjadi,
selanjutnya mempartisi himpunan titik dari kemungkinan tersebut, dan terakhir mendapatkan polinomial kromatik suatu graf. Dari langkah terakhir akan didapatkan polinomial kromatik suatu graf dalam bentuk khusus. Jadi, untuk mendapatkan polinomial kromatik suatu graf secara umum, digunakan metode induktif.
Dari hasil penelitian diperoleh bahwa polinomial kromatik suatu graf pada
prinsipnya diperoleh dari graf lengkap Kn, Kn-1, dan seterusnya hingga nilai n sama
dengan bilangan kromatiknya. Jadi, polinomial kromatik dari masing-masing graf
n
bintang, graf roda, dan graf tangga adalah f (
n n
Sn , t) t ( t 1 ) ,
2 n 1
f (Wn ,t) t[(t 2) (1 ) (t 2)] , dan f (,L n(1t)( t t3 t t | en_US |
