PEWARNAAN TITIK r-DINAMIS PADA GRAF HASIL OPERASI EDGE COMB PRODUCT GRAPH DIKAITKAN DENGAN KETERAMPILAN BERPIKIR TINGKAT TINGGI

Abstract

Salah satu topik yang menarik untuk dikembangkan dalam teori graf adalah pewarnaan (colouring). Pewarnaan suatu graf terdiri dari pewarnaan titik, pewarnaan sisi dan pewarnaan wilayah. Penelitian ini terfokus pada pewarnaan titik yang dikembangkan pada pewarnaan r-dinamis. Pengembangan pewarnaan titik r-dinamis bertujuan untuk mencari nilai kromatik pada pewarnaan graf. Penelitian ini menggunakan graf hasil operasi comb sisi yang dinotasikan dengan G D H. Tujuan dari penelitian yaitu untuk menentukan kardinalitas, menentukan pewarnaan titik r-dinamis, dan keterkaitan antara pewarnaan titik r-dinamis pada graf hasil operasi edge comb product graph dalam mengasah keterampilan berpikir tingkat tinggi. Metode yang digunakan adalah metode deduktif aksiomatik yaitu menurunkan teorema tentang pewarnaan titik r-dinamis, kemudian diterapkan dalam pewarnaan titik r-dinamis, berikutnya dikenalkan pada beberapa teorema me-ngenai pewarnaan titik r-dinamis pada graf comb sisi. Selanjutnya menurunkan teorema tersebut untuk memperoleh pewarnaan titik dan nilai kromatik r-dinamis. Setelah ditemukan pewarnaan titik r-dinamis pada graf tersebut, maka dilanjutkan dengan pendeteksian pola, yaitu dengan menentukan pola pewarnaan r-dinamis sedemikian hingga diperoleh bentuk pola umumnya. Hasil penelitian ini berupa teorema baru mengenai nilai kromatik dari pewarnaan titik r-dinamis pada graf hasil operasi edge comb product graph. Berdasarkan penelitian dihasilkan kardinalitasnya yaitu graf Cm D W3, dimana m= 2 mod 4, m > 2, memiliki kardinalitas jV (Cm D W3)j = p = 18m dan jE(Cm D W3)j = q = 30m, graf Sm D C3, dimana m ¸ 3, memiliki kardinalitas jV (Sm D C3)j = p = 2m + 1 dan jE(Sm D C3)j = q = 3m, graf Pm D C3, dimana m ¸ 2, memiliki kardinalitas jV (Pm D C3)j = p = m + 1 dan jE(Pm D C3)j = q = m, graf L3m D C3, dimana m ¸ 1, Sm, memiliki kardinalitas jV (L3m D C3)j = p = 15m ¡ 2 dan jE(L3m D C3)j = q = 27m ¡ 6, C6m D C3, dimana m ¸ 1, memiliki kardinalitas jV (C6m D C3)j = p = 12m dan jE(C6m D C3)j = q = 18m, C6m D B2, dimana m ¸ 1, memiliki kardinalitas jV (C6m D B2)j = p = 18m dan jE(C6m D B2)j = q = 30m. Teorema baru yang dihasilkan pada graf graf Cm D W3, m= 2 mod 4, dan m > 2, Sm D C3, m ¸ 3, graf Pm D C3, m ¸ 2, graf L3m D C3, m ¸ 1, graf C6m D C3, m ¸ 1, dan graf C6m D B2, m ¸ 1 adalah sebagai berikut: 1.) Teorema 3.4.1 Cm D W3, dimana m= 2 mod 4, m > 2, maka pewarnaan titik r-dinamis dari graf G adalah Â(Cm D W3) = Â1·r·±(Cm D W3) = 4, ±+1·r·¢¡1(Cm DW3) = r + 1, Âr¸¢(Cm DW3) = ¢ + 1. 2.) Teorema 4.1.1 Sm D C3, dimana m ¸ 3, maka pewarnaan titik r-dinamis dari graf SmDC3 adalah Â(SmDC3) = Â1·r·±(SmDC3) = 3, ±+1·r·¢¡1(SmD C3) = r + 1, Âr¸¢(Sm D C3) = ¢ + 1. 3.) Teorema 4.1.2 Misalkan graf G merupakan graf hasil operasi dari Pm D C3 dimana m ¸ 2, L3m D C3 dimana m ¸ 1, C6m D C3 dimana m ¸ 1, dan C6mDB2 dimana m ¸ 1, maka pewarnaan titik r-dinamis dari graf G atau graf hasil operasi tersebut adalah Â(G) = Â1·r·±(G) = 3, ±+1·r·¢¡1(G) = r+1, Âr¸¢(G) = ¢ + 1. Kaitan antara keterampilan berpikir tingkat tinggi dengan pewarnaan titik r-dinamis pada graf hasil operasi yaitu dalam mengidentikasi famili graf, menentukan kardinalitas elemen pada graf hasil operasi edge comb product yang akan diterapkan pada pewarnaan titik, menerapkan dan menentukan pewarnaan titik r-dinamis pada edge comb product graph, menentukan pola nilai kromatik r-dinamis, menentukan fungsi pewarnaan r-dinamis serta mengevaluasi dalam membuktikan kebenaran fungsi, dan menemukan teorema baru. 1.Masalah Terbuka 4.3.1 Misalkan graf hasil operasi dari B2 D Cm, tentukan nilai kromatik pewarnaan titik r-dinamis dari graf G untuk m=2 mod 4, m > 2.