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.