r-DYNAMIC VERTEX COLORING PADA HASIL OPERASI GRAF KHUSUS DAN KAITANNYA DENGAN KETERAMPILAN BERIPIKIR TINGKAT TINGGI

Abstract

Berkembangnya ilmu pengetahuan dan teknologi mengakibatkan banyak munculnya permasalahan yang kompleks dalam kehidupan sehari-hari. Untuk mengatasi permasalahan tersebut, diperlukan adanya ilmu pengetahuan yang strategis dan mampu memberikan solusi, salah satunya ialah matematika. Kegiata- n pemecahan masalah matematika tidak dapat dipisahkan dari proses berpikir kognitif. Bloom mengklasifikasikan ranah kognitif menjadi enam tingkatan yang dikenal dengan Taksonomi Bloom. Revisi Taksonomi Bloom yang meliputi: mengi- ngat, memahami, menerapkan, menganalisis, mengevaluasi dan menciptakan. Di dalam matematika diskrit, berkembang beberapa pokok bahasan, salah satunya yaitu teori graf.Salah satu pokok bahasan yang menarik untuk dikembang- kan dalam teori graf adalah pewarnaan (colouring). Ada beberapa macam pe- warnaan dalam teori graf, yaitu pewarnaan titik (vertex colouring), pewarnaan sisi (edge colouring), pewarnaan wilayah (region colouring), dan r-dynamic col- oring. Pewarnaan dapat diaplikasikan dalam berbagai hal, misalnya pada penye- lesaian masalah sistem lampu lalu lintas, penentuan frekuensi radio, pengaturan jadwal ujian, penyimpanan bahan kimia, dan manajemen transportasi (Soimah, 2013). Pewarnaan titik (vertex colouring) adalah pemberian warna pada titik- titik graf dimana dua titik yang bertetangga diberi warna yang berbeda. Jumlah warna paling sedikit yang digunakan untuk mewarnai titik pada graf G dise- but bilangan kromatik yang dilambangkan dengan χ(G). Pewarnaan titik juga termasuk ke dalam r-dynamic vertex coloring yang dinotasikan dengan χr(G). Pewarnaan titik dinamis dapat diterapkan pada berbagai graf ataupun graf yang merupakan hasil operasi dari beberapa graf khusus yaitu graf yang mempunyai keunikan dan karakteristik bentuk khusus. Pewarnaan titik dinamis didefinisi- kan dengan |c(N(v))| ≥ min{r, d(v)} untuk setiap titik v di V (G), dimana N(v) adalah lingkungan v dan c(S) = {c(v) : v ∈ S} untuk setiap titik bagian dari S (Jahanbekam, et al. 2014). Penelitian ini dikategorikan kedalam penelitian eksploratif, yaitu jenis pe- nelitian yang bertujuan menggali hal-hal yang ingin diketahui oleh peneliti dan hasil penelitian dapat digunakan sebagai dasar penelitian selanjutnya. Metode yang digunakan dalam penelitian ini adalah metode deduktif aksiomatik. Setiap langkah pada penelitian ini akan dikaitkan dengan 6 tahapan taksonomi Bloom untuk mencapai keterampilan berpikir tingkat tinggi. Penelitian ini bertujuan untuk mencari batas atas bilangan kromatik pewarnaan titik dinamis dan fungsi pewarnaan titik pada graf yang dioperasikan. Graf yang digunakan adalah graf lingkaran (cycle), graf bintang (star), graf lengkap (complete), dan graf lintasan (path). Penelitian ini menghasilkan teorema dan akibat dari teorema sebelumnya mengenai bilangan kromatik dari suatu r-dynamic vertex coloring, antara lain: 1. Teorema 4.1.1 Misal G= (Cn + Cm). Untuk n ≥ 3 dan m ≥ 3, bilangan kromatik pewarnaan titik dinamis G adalah untuk n genap χ(G) = χd(G) = χ3(G) = ( 4, untuk m genap 5, untuk m = 4k3−21k2+41k−9 3 , kǫN χ(G) = χd(G) = χ3(G) = χ4(G) = 5, untuk m = (mod 3), m ganjil untuk n ganjil χ(G) = χd(G) = χ3(G) = χ4(G) = 6, untuk m = 4k3−21k2+41k−9 3 , kǫN χ(G) = χd(G) = χ3(G) = χ4(G) = χ5(G) = 6, untuk n dan m = (mod 3), m ganjil