NILAI KROMATIK DAN PEWARNAAN TITIK r-DINAMIS PADA GRAF KHUSUS DAN OPERASI SHAKEL

Abstract

Teori graf merupakan bagian dari matematika diskrit yang penerapannya masih banyak digunakan dalam kehidupan sehari-hari. Pada tahun 1736 seorang matematikawan dari Swiss bernama Leonard Euler berhasil memecahkan masalah jembatan yang berada di kota Konigsberg. Permasalahan yang muncul pada jembatan Konigsberg adalah kemungkinan bisa atau tidaknya melewati ketujuh jembatan di Konigsberg yang masing-masing tepat satu kali dan kembali lagi ke tempat semula. Euler memecahkan masalah jembatan Konigsberg dengan cara mengilustrasikannya menjadi graf yaitu menggambarkan empat daratan sebagai titik, tujuh jembatan sebagai sisi yang menghubungkan setiap daratan. Dari permasalahan tersebut teori graf berkembang dengan luas. Salah satu perkembangan topik dari teori graf yang menarik untuk dikaji adalah pewarnaan. Terdapat tiga jenis pewarnaan antara lain pewarnaan titik (vertex colouring), pewarnaan sisi (edge colouring), dan pewarnaan wilayah (region colouring). Penggunaan warna yang berbeda untuk mewarnai semua titik pada graf dimana setiap dua titik yang terhubung diberi warna yang berbeda dise- but pewarnaan titik. Dalam pewarnaan titik, tidak hanya memberi warna tetapi juga menghasilkan banyaknya warna minimum yang didapatkan biasanya dise- but bilangan kromatik yang dinotasikan dengan Â(G). Adapun perkembangan dari pewarnaan titik yaitu r-Dynamic Vertex Coloring (Âr(G)) atau yang biasa disebut pewarnaan titik r-dinamis. Penelitian ini bertujuan untuk mencari bilangan kromatik r-dinamis dan fungsi pewarnaan titik r-dinamis pada graf khusus yang telah ditentukan. Ada- pun graf yang digunakan pada penelitian ini adalah graf kipas (Fn), graf triangular book (BTn), graf tangga tiga siklus (TCLn), graf tangga (Ln), shakel graf okta hedral (Shack(j4;2; v = 1; n), shakel graf triangular book (shack(BTn; v = 1;m)) dan graf banana tree (Bm;4). Pada penelitian ini menghasilkan 7 teorema, antara lain: 1. Teorema 4.1.1 Misalkan G merupakan graf kipas Fn. Jika n ¸ 3, maka bilangan kromatik r-dinamis graf kipas adalah Â(G) = Âd(G) = 3 Âr(G) = r + 1; r ¸ n 2. Teorema 4.1.2 Misalkan G merupakan graf triangular book BTn. Jika n ¸ 2, maka bilangan kromatik r-dinamis graf triangular book adalah Â(G) = Âd(G) = 3 Âr(G) = r + 1; n ¸ r ¡ 1; r ¸ 3 3. Teorema 4.1.3 Misalkan G merupakan graf tangga tiga siklus (TCLn). Jika n ¸ 1, maka bilangan kromatik r-dinamis graf tangga tiga siklus adalah Â(G) = Âd(G) = 3 Â3(G) = 4 Â4(G) = 5 Âr(G) = 6; n ¸ 2; r ¸ 5 4. Teorema 4.1.4 Misalkan G merupakan graf tangga (Ln). Jika n ¸ 2, maka bilangan kromatik r-dinamis graf tangga adalah Â(G) = 2 Âr(G) = 4; r ¸ 2 5. Teorema 4.1.5 Misalkan G merupakan shakel graf oktahedral (Shack(j4;2; v = 1; n). Jika n ¸ 2, maka bilangan kromatik r-dinamis shakel graf oktahedral adalah Â(G) = Âd(G) = 3 Â3(G) = 5 Â4(G) = Â5(G) = 6 Âr(G) = ( r + 1; 6 · r · 7; 9; r ¸ 8: 6. Teorema 4.1.6 Misalkan G merupakan shakel graf Triangular Book (shack (BTn; v = 1;m)). Jika n ¸ 2 dan m ¸ 2 , maka bilangan kromatik r- dinamis shakel graf Triangular Book adalah Â(G) = Âd(G) = 3 Âr(G) = ( r + 1; 3 · r · 6; r + 1; r ¸ 7; n ¸ dr 2e ¡ 1: 7. Teorema 4.1.7 Misalkan G merupakan Banana Tree (Bm;4). Jika m ¸ 2 dan n = 4 , maka bilangan kromatik r-dinamis graf Banana Tree adalah Âr(G) = r + 1