Pewarnaan Titik Ketakteraturan Lokal Refleksif pada Keluarga Graf Roda

Abstract

Pewarnaan graf adalah memberikan warna yang berbeda pada elemen graf yaitu titik, sisi, dan wilayah. Sehingga setiap elemen yang bertetangga memiliki warna yang berbeda. Banyaknya warna minimal yang digunakan untuk mewarnai titik pada suatu graf G disebut bilangan kromatik yang dinotasikan χ(G). Penelitian ini mengkaji pewarnaan titik ketakteraturan lokal refleksif pada keluarga graf roda. Pewarnaan titik ketakteraturan lokal refleksif merupakan hasil penggabungan konsep dari pewarnaan titik dan pelabelan titik ketakteraturan refleksif. Pewarnaan titik ketakteraturan lokal refleksif adalah pewarnaan yang dilakukan dengan cara mencari pewarnaan titik terlebih dahulu kemudian melabeli titik pada graf dengan label titik yaitu f : V (G) −→ {0, 2, ..., 2kv} dan melabeli sisi pada graf dengan menggunakan label sisi yaitu f : E(G) −→ {1, 2, ..., ke} dimana k = max{2kv, ke} dengan 2kv, ke merupakan bilangan asli, untuk titik yang memiliki warna yang sama maka bobot titiknya juga harus sama begitupun sebaliknya jika untuk titik yang memiliki warna yang berbeda maka bobot titiknya juga harus berbeda. Bobot titik diperoleh dengan cara menjumlahkan label titik dirinya sendiri dengan label sisi yang bersisian dangan titik tersebut. Pewarnaan titik ketakteraturan lokal refleksif pada intinya yaitu meminimumkan k−pelabelan dengan mencapai bilangan kromatik pewarnaan titik ketakteraturan lokal refleksif yang sama dengan bilangan kromatik pewarnaan titik. Banyaknya nilai bobot titik minimal yang dibutuhkan untuk mewarnai semua titiknya sehingga setiap titik yang bertetangga tidak memiliki warna yang sama disebut bilangan kromatik titik ketakteraturan lokal refleksif yang dinotasikan dengan χlrvs(G). Selanjutnya k minimum yang dibutuhkan bilangan kromatik χlrvs(G) = χ(G) adalah local reflexive vertex color strength, yang dinotasikan dengan lrvcs(G).Jenis penelitian ini merupakan penelitian yang bersifat eksploratif dan terapan. Latar belakang digunakannya jenis penelitian eksploratif dan terapan yaitu karena penelitian ini bertujuan untuk memberikan gambaran dasar terhadap topik bahasan yang diteliti, menjadikan topik baru menjadi lebih dikenal oleh masyarakat luas, mengembangkan gagasan teori yang bersifat dapat diubah, dan mengembangkan teori yang membuka kemungkinan adanya penelitian lanjutan mengenai topik yang dibahas. Sedangkan metode penelitian yang digunakan adalah metode deduktif aksiomatik dan pendeteksian pola. Kedua metode penelitian tersebut mendukung proses penelitian ini karena untuk mendapatkan nilai lrvcs pewarnaan titik ketakteraturan lokal refleksif dibutuhkan proses pencarian pola pelabelan dan pola pewarnaan, setelah diperoleh keduanya maka membuat dan membuktikan teorema nilai lrvcs pewarnaan titik ketakteraturan lokal refleksif Penelitian ini menghasilkan lima teorema tentang nilai lrvcs pewarnaan titik ketakteraturan lokal refleksif. Berikut teorema yang dihasilkan pada penelitian ini : Teorema 1. Diberikan Fn merupakan graf kipas, untuk setiap bilangan bulat positif n ≥ 3, sehingga lrvcs(Fn) = 2. Teorema 2. Diberikan Wn,n merupakan graf roda ganda, untuk setiap bilangan bulat positif n ≥ 3, sehingga lrvcs(Wn,n) = 2. Teorema 3. Diberikan CHn merupakan graf helm tertutup, untuk setiap bilangan bulat positif n ≥ 4, sehingga lrvcs(CHn) = 2. Teorema 4. Diberikan Fln merupakan graf bunga, untuk setiap bilangan bulat positif n ≥ 3, sehingga lrvcs(Fln) = 2. Teorema 5. Diberikan CFn merupakan graf bunga tertutup, untuk setiap bilangan bulat positif n ≥ 3, sehingga lrvcs(CFn) = 2.