ANALISIS r-DYNAMIC VERTEX COLORING PADA HASIL OPERASI GRAF KHUSUS

Abstract

Teori graf banyak mengalami perkembangan yang sangat luas. Salah satu topik yang menarik untuk dikaji adalah masalah pewarnaan. Pewarnaan memi- liki tiga macam, yaitu pewarnaan titik (vertex coloring), pewarnaan sisi (edge coloring), dan pewarnaan wilayah (region coloring). Penggunaan warna yang berbeda untuk mewarnai semua titik pada graf dimana setiap dua titik yang ter- hubung diberi warna yang berbeda disebut pewarnaan titik. Dalam pewarnaan titik, tidak hanya memberi warna tetapi juga menghasilkan banyaknya warna minimum yang didapatkan biasanya disebut bilangan kromatik yang dinotasikan dengan (G). Selain itu, dikenal juga fungsi pewarnaan yang ditentukan dari keteraturan bilangan kromatik. Terdapat topik baru yang masih dalam ruang lingkup pewarnaan titik yaitu r-Dynamic Vertex Coloring atau yang biasa dise- but pewarnaan titik dinamis. r-Dynamic Vertex Coloring ini sifatnya juga hampir mirip dengan pewarnaan titik. Pewarnaan titik dapat diterapkan pada graf yang merupakan hasil operasi dari beberapa graf khusus. Adapun macam-macam pen- goperasian graf yaitu operasi Joint (G + H), Crown Product (G ⊙ H), Tensor Product (G ⊗ H), Cartesian Product (G H), Composition (G[F]), Shackle, dan Amalgamation. Pada penelitian ini menggunakan metode penelitian eksploaratif dan terapan. Penelitian eksploratif adalah jenis penelitian yang bertujuan meng- gali hal-hal yang ingin diketahui oleh peneliti dan hasil penelitian dapat digunakan sebagai dasar penelitian selanjutnya. Penelitian terapan (applied research) meru- pakan penyelidikan yang hati-hati, sistematik dan terus-menerus terhadap suatu masalah dengan tujuan untuk digunakan dengan segera untuk keperluan tertentu. Penelitian ini bertujuan untuk mencari batas atas bilangan kromatik dan fungsi pewarnaan titik pada graf yang dioperasikan serta menentukan pewarnaan titik dinamis. Selain itu juga untuk mengetahui sifat komuatif dari operasi graf. Graf viii yang digunakan pada penelitian ini adalah graf roda (wheel), graf lintasan (path), graf lingkaran (cycle), dan graf bintang (star). Pada penelitian ini menghasilkan 15 teorema dan 4 akibat dari teorema sebelumnya, antara lain: 1. Teorema 4.1.1 Misal G= (Wn + Pm)= (Pm + Wn). Untuk n ≥ 3 dan m ≥ 2, bilangan kromatik dan pewarnaan titik dinamis G adalah (G = (Wn + Pm) = 4(G = (Wn + Pm) = ( 5, untuk n genap 6, untuk n ganjil 2. Teorema 4.1.2 Misal G adalah joint dari graf roda dan graf lingkaran. Untuk n ≥ 3 dan m ≥ 3, bilangan kromatik dan pewarnaan titik dinamis G = (Wn + Cm) adalah (Wn + Cm) = 4(Wn + Cm) = ( 5, untuk n genap pada saat m genap 6, untuk n ganjil pada saat m genap (Wn + Cm) = 5(Wn + Cm) = ( 6, untuk n genap pada saat m ganjil 7, untuk n ganjil pada saat m ganjil 3. Teorema 4.1.3 Misal G adalah crown product dari graf roda dan graf lin- tasan. Untuk n ≥ 3 dan m ≥ 2, bilangan kromatik dan pewarnaan titik dinamis G adalah (Wn ⊙ Pm) = 2(Wn ⊙ Pm) = ( 3, untuk n genap 4, untuk n ganjil 4. Teorema 4.1.4 Misal G adalah crown product dari graf lintasan dan graf roda. Untuk n ≥ 3 dan m ≥ 2, bilangan kromatik dan pewarnaan titik dinamis G= (Pm ⊙Wn) adalah (Pm ⊙Wn) = 3(Wn ⊙ Pm) = ( 4, untuk n genap 5, untuk n ganjil ix 5. Teorema 4.1.5 Misal G adalah crown product dari graf roda dan graf lingkaran. Untuk n ≥ 3 dan m ≥ 3, bilangan kromatik dan pewarnaan titik dinamis G = (Wn ⊙ Cm) adalah (Wn ⊙ Cm) = 2(Wn ⊙ Cm) = 4, untuk m genap (Wn ⊙ Cm) = 3(Wn ⊙ Cm) = 4, untuk m ganjil 6. Akibat 4.1.1 Misal G= (Wn⊗Pm)= (Pm⊗Wn). Untuk n ≥ 3 dan m ≥ 2, bilangan kromatik G adalah (Wn ⊗ Pm) = 2 7. Teorema 4.1.6 Misal G= (Wn⊗Pm)= (Pm⊗Wn) untuk n ≥ 3 dan m ≥ 2, pewarnaan titik dinamis G adalah 2(Wn ⊗ Pm) = 3 8. Akibat 4.1.2 Misal G adalah tensor product dari graf roda dan graf lingkaran. Untuk n ≥ 3 dan m ≥ 3, bilangan kromatik G = (Wn ⊗ Cm) adalah (Wn ⊗ Cm) = ( 2, untuk m genap 3, untuk m ganjil 9. Teorema 4.1.7 Misal G adalah tensor product dari graf roda dan graf lingkaran. Untuk n ≥ 3 dan m ≥ 3, pewarnaan titik dinamis G = (Wn⊗Cm) adalah (Wn Cm) = 2, untuk m genap 2(Wn Cm) = 3, untuk m ganjil 10. Akibat 4.1.3 Misal G= (Wn Pm)= (Pm Wn). Untuk n ≥ 3 dan m ≥ 2, x bilangan kromatik G adalah (Wn Pm) = ( 3, untuk n genap 4, untuk n ganjil 11. Teorema 4.1.8 Misal G adalah cartesian product dari graf roda dan lin- tasan. Untuk n ≥ 3 dan m ≥ 2, pewarnaan titik dinamis G = (Wn Pm) adalah 2(Wn Pm) = 3, untuk m genap 2(Wn Pm) = 4, untuk m ganjil 12. Akibat 4.1.4 Misal G adalah cartesian product dari graf roda dan graf lingkaran. Untuk n ≥ 3 dan m ≥ 3, bilangan kromatik dan pewarnaan dinamis G = (Wn Cm) adalah (Wn Cm) = ( 3, untuk m genap dan m ganjil pada saat n genap 4, untuk m genap dan m ganjil pada saat n ganjil 13. Teorema 4.1.9 Misal G adalah cartesian product dari graf roda dan lingkaran. Untuk n ≥ 3 dan m ≥ 3, pewarnaan titik dinamis G = (Wn Cm) adalah 2(Wn Cm) = 3, untuk m genap dan m ganjil pada saat n genap 3(Wn Cm) = 4, untuk m genap dan m ganjil pada saat n ganjil 14. Teorema 4.1.10 Misal G= (Wn[Pm])= (Pm[Wn]). Untuk n ≥ 3 dan m ≥ 2, bilangan kromatik dan pewarnaan titik dinamis G adalah (Wn[Pm]) = 5(Wn[Pm]) = 6, untuk n genap (Wn[Pm]) = 6(Wn[Pm]) = 8, untuk n ganjil 15. Teorema 4.1.11Misal G adalah composition dari graf roda dan graf lingkaran. Untuk n ≥ 3 dan m ≥ 3, bilangan kromatik dan pewarnaan titik dinamis G xi adalah (Wn[Cm]) = 3(Wn[Cm]) = 9, untuk n genap pada saat m ganjil (Wn[Cm]) = 5(Wn[Cm]) = 6, untuk n genap pada saat m genap (Wn[Cm]) = 5(Wn[Cm]) = 8, untuk n ganjil pada saat m genap (Wn[Cm]) = 7(Wn[Cm]) = 12, untuk n ganjil pada saat m ganjil 16. Teorema 4.1.12 Misal G adalah amalgamation dari hasil operasi joint graf roda dan graf lintasan. Untuk n ≥ 3 dan m ≥ 2, bilangan kromatik dan pewarnaan titik dinamis G = (Amal(Wn + Pm, v = 1, r)) adalah (Amal(Wn+Pm, v = 1, r)) = 4(Amal(Wn+Pm, v = 1, r)) ( 5, untuk n genap 6, untuk n ganjil 17. Teorema 4.1.13 Misal G adalah amalgamation dari hasil operasi joint graf bintang dan graf lintasan. Untuk n ≥ 3 dan m ≥ 2, bilangan kromatik dan pewarnaan dinamis G = (Amal(Sn + Pm, v = 1, r)) adalah (Amal(Sn + Pm, v = 1, r)) = 3(Amal(Sn + Pm, v = 1, r)) = 4 18. Teorema 4.1.14 Misal G adalah shackle dari graf hasil operasi joint graf bintang dan graf lintasan. Untuk n ≥ 3 dan m ≥ 2, bilangan kromatik dan pewarnaan dinamis G = (Shack(Sn + Pm, r)) adalah (Shack(Sn + Pm, r)) = 3(Shack(Sn + Pm, r)) = 4 19. Teorema 4.1.15 Misal G adalah shackle dari graf hasil operasi joint graf roda dan graf lingkaran. Untuk n ≥ 3 dan r ≥ 3, bilangan kromatik dan