Bilangan Kromatik Graceful pada Keluarga Graf Unicyclic

Abstract

Teori graf adalah cabang kajian yang mempelajari sifat-sifat graf. Sebuah graf G adalah pasangan himpunan (V, E) dimana V adalah himpunan tidak kosong dari elemen G yang disebut titik (vertex) dan E adalah himpunan (boleh kosong) dari pasangan tidak terurut dua titik v1, v2 dimana v1, v2 ∈ V (G) yang disebut sisi (edge). Graf yang digunakan dalam penelitian ini adalah graf unicyclic. Graf unicyclic adalah graf dengan order dan size sama yang mempunyai satu siklus. Sebagai contoh kasus, graf yang digunakan pada penelitian ini adalah graf bull, graf net, graf cricket, graf caveman, graf peach, dan graf flowerpot. Adapun alasan memilih graf tersebut sebagai bahan penelitian ini dikarenakan proses generalisasi. Proses generalisasi yang dimaksud pada penelitian ini adalah bilangan kromatik graceful dari enam graf yang telah ditemukan belum pernah diteliti/didapatkan oleh peneliti lain, sehingga menjadikan topik pewarnaan graceful semakin umum dan semakin luas. Karena topik pewarnaan ini telah tergeneralisasi sehingga dapat memberikan gambaran kepada peneliti lain untuk mengembangkan topik ini. Topik yang dijadikan sebagai bahan kajian pada penelitian ini adalah salah satu topik pada teori graf, yaitu pewarnaan titik pada graf. Pewarnaan titik pada graf adalah memberikan warna pada titik yang bertetangga dengan warna yang berbeda sehingga tidak ada dua titik yang bertetangga memiliki warna yang sama. Banyaknya warna yang optimum yang bisa digunakan untuk mewarnai titik-titik pada suatu graf disebut bilangan kromatik. Selanjutnya pada penelitian ini dikembangkan pewarnaan graceful pada graf. Alasan memilih topik ini dikarenakan topik pewarnaan ini termasuk topik yang baru, belum banyak peneliti yang telah meneliti topik pewarnaan ini. Pewarnaan graceful merupakan penggabungan konsep graceful dengan pewarnaan titik. Pewarnaan graceful dilakukan dengan meminimumkan warna titik dan sisi secara proper. Warna sisi didapat karena akibat dari pewarnaan titik yang bertetangga dengan sisi tersebut. Pewarnaan sisi dilakukan dengan menghitung nilai absolut selisih dari titik yang berkaitan dengan sisi tersebut. Bilangan kromatik pada pewarnaan graceful graf dilambangkan dengan χg(G). Batas bawah dari pewarnaan graceful pada graf G yaitu menggunakan Lemma mengenai subgraf H dari graf G yang menyatakan, jika H adalah subgraf dari graf (G), maka χg(G) ≥ χg(H). Selanjutnya untuk menemukan batas atas dari pewarnaan graceful yaitu dengan menemukan fungsi setiap titik dan setiap sisi dari graf G. Penelitian ini fokus mencari bilangan kromatik graceful pada keluarga graf unicyclic. Setelah mendapatkan bilangan kromatiknya, diperlukan pengajaran dan desiminasi berupa video pembelajaran mengenai topik pewarnaan graceful ke masyarakat luas yang ingin mempelajari topik pewarnaan graceful. Online teaching platform yang digunakan pada penelitian ini adalah Sevima EdLink. Selain dapat diakses dengan mudah dan tidak berbayar, alasan memilih Sevima EdLink adalah agar masyarakat dapat mengenal aplikasi ini. Penelitian ini termasuk dalam jenis penelitian eksploratif. Alasan penelitian ini termasuk penelitian eksploratif yaitu karena penelitian bertujuan untuk menemukan hal baru dan memberikan gambaran dasar mengenai topik ini agar lebih dikenal masyarakat dan menggeneralisasikan topik ini untuk penelitian selanjutnya. Metode yang digunakan dalam penelitian ini yaitu metode deduktif aksiomatik dan pendeteksian pola dalam menentukan nilai dari bilangan kromatik graceful pada keluarga graf unicyclic. Hasil utama dari penelitian yang dibahas terkait topik ini adalah teorema. Terdapat enam teorema baru yang ditemukan secara eksperimental dalam penelitian ini, yaitu bilangan kromatik graceful pada graf bull B3,m dengan m ≥ 2 adalah 4, bilangan kromatik graceful pada graf net N3,m, untuk m ≥ 2 adalah 5, bilangan kromatik graceful pada graf cricket Crm,n, untuk n ≥ 3 dan m ≥ 2 adalah 5, bilangan kromatik graceful pada graf caveman Cn,m, untuk n ≥ 3 dan m ≥ 1 adalah 4, bilangan kromatik graceful pada graf peach C m n , untuk n ≥ 3 dan m ≥ 1 adalah m + 3, dan bilangan kromatik graceful pada graf flowerpot CnSm, untuk n, m ≥ 3 adalah m + 2.