PEWARNAAN TITIK r-DINAMIS PADA AMALGAMASI DAN SAKEL SERTA GENERALISASINYA DARI GRAF KHUSUS

Abstract

Teori graf merupakan cabang ilmu matematika diskrit yang penerapannya banyak ditemukan dalam kehidupan sehari-hari. Fungsi graf sangat banyak, namun pada umumnya digunakan sebagai alat bantu dalam memodelkan suatu masalah agar mu- dah dimengerti dan diselesaikan seperti penggambaran rangkaian listrik, senyawa kimia, penyusunan jadwal dan sebagainya. Teori graf berkembang sangat luas. Salah satu topik yang menarik untuk dikaji adalah pewarnaan. Macam-macam pe- warnaan yang dapat dikaji dalam teori graf yaitu pewarnaan titik, pewarnaan sisi, dan pewarnaan total. Pewarnaaan titik adalah pewarnaan yang diberikan kepada se- tiap titik-titik graf. Pewarnaan sisi adalah pewarnaan yang diberikan kepada setiap sisi-sisi graf, sedangkan untuk pewarnaan total adalah pewarnaan yang diberikan pada titik dan sisi graf. Pewarnaan graf haruslah berbeda di mana tidak boleh ada warna sama yang berdekatan namun pewarnaan haruslah seminimum mungkin yang disebut bilangan kromatik biasanya dinotasikan (G). Bilangan-bilangan kromatik akan membentuk fungsi yang disebut fungsi pewarnaan. Topik-topik yang dapat dikaji dalam lingkup pewarnaan, salah satunya adalah topik dari perwarnaan titik yaitu pewarnaan titik r-dinamis yang dinotasikan dengan r(G). Suatu graf G yang memiliki k pewarnaan memetakan himpunan titiknya ke himpunan pewarnaan dino- tasikan c : V (G) ⇒ (1; 2; 3; :::; k), jadi untuk titik-titik yang bertetangga memiliki minimal dua warna berbeda. r − dinamis dengan k pewarnaan pada graf G se- hingga |c(N(v))| ≥ min{r; d(v)} untuk v di V (G). Bilangan kromatik r-dinamis ditulis dengan r(G) untuk nilai minimum k sehingga graf G memiliki r-dinamis dengan k pewarnaan (Jahanbekam, et al, 2014). Pewarnaan r-dinamis merupakan pengembangan dari pewarnaan k-warna dinamis yang diperkenalkan oleh Mont- gomery pada tahun 2002. Pewarnaan k warna dinamis pada graf G merupakan pewarnaan titik pada graf G sebanyak k-warna sedemikian sehingga setiap titik mempunyai derajat minimum sebanyak dua dan memiliki dua warna yang berbeda dengan titik tetangganya. Pewarnaan k warna dinamis memiliki nilai k terkecil yang disebut sebagai bilangan kromatik dinamis yang disimbolkan dengan d(G). Pewarnaan titik r-dinamis dapat diterapkan pada hasil operasi graf pada beber- apa graf khusus. Salah satunya adalah operasi amalgamasi dan operasi shakel erta generalisasinya. Adapun graf-graf hasil operasi yang digunakan dalam penelitian ini yaitu: graf kipas amal(Fn; v;m), windmill (gshack(Wd33 ; e; n), graf roda amal(W4; v; n), graf lengkap (shack(K4; v; n), graf lengkap (gshack(K4; e; n) dan lengkap amal(K4; v; n). Penelitian ini menggunakan metode deduktif aksiomatik dan pendeteksian pola. Tujuan dari penelitian ini adalah menentukan kardinalitas titik dan sisi, bilangan kromatik titik r-dinamis, dan fungsi pewarnaan titik r- dinamis.