Bilangan Kromatik Graceful pada Keluarga Graf sebagai E-Monograf

Abstract

Salah satu topik pada pewarnaan graf yang dijadikan sebagai kajian pada penelitian ini adalah topik pewarnaan graceful. Pewarnaan graf dibagi menjadi tiga, yaitu pewarnaan simpul, pewarnaan sisi, dan pewarnaan wilayah. Pewarnaan simpul yaitu pemberian warna pada simpul graf dengan syarat simpul yang bertetangga memiliki warna yang berbeda. Pewarnaan sisi yaitu pemberian warna pada sisi graf dengan syarat sisi yang bertetangga memiliki warna yang berbeda. Pewarnaan wilayah adalah pemberian warna pada bagian atau wilayah pada graf dengan syarat wilayah atau bagian yang bertetangga memiliki warna yang berbeda. Salah satu contoh pewarnaan simpul yaitu pewarnaan graceful, yang merupakan topik yang dibahas pada penelitian ini. Pewarnaan k-graceful pada graf 𝐺 tak kosong adalah pewarnaan titik proper 𝑐: 𝑉(𝐺) → {1,2,3, … , 𝑘} dimana 𝑘 ≥ 2 yang menginduksi pada pewarnaan sisi proper 𝑐′: 𝑉(𝐺) → {1,2,3, … , (𝑘 − 1)} dan didefinisikan dengan 𝑐 ′ (𝑢𝑣) = |𝑐(𝑢) − 𝑐(𝑣)|. Banyaknya jumlah warna minimum pewarnaan graceful pada graf disebut bilangan kromatik. Penelitian ini fokus mencari bilangan kromatik graceful pada keluarga graf bintang, meliputi graf sapu, graf kelabang, graf MBintang, dan graf H-Bintang. Penelitian ini termasuk kedalam jenis penelitian eksploratif, karena penelitian bertujuan untuk menemukan hal baru dan memberikan gambaran dasar mengenai topik ini agar lebih tergeneralisasi. Metode yang digunakan dalam penelitian ini yaitu metode duduktif aksiomatik dan pendeteksian pola dalam menentukan nilai dari bilangan kromatik graceful pada keluarga graf bintang. Dari hasil penelitian diperoleh empat teorema diantaranya sebagai berikut. 1. Teorema 1. Bilangan kromatik graceful pada graf sapu 𝐵𝑛,𝑚 untuk 𝑛 ≥ 3 adalah χ𝑔(𝐵𝑛,𝑚) = 𝑛 + 2 2. Teorema 2. Bilangan kromatik graceful pada graf kelabang 𝑆3,𝑛𝑃𝑚 untuk n  3,𝑚 ≥ 5 adalah χ𝑔(𝑆3,𝑛𝑃𝑚) = 𝑛 + 2 3. Teorema 3. Bilangan kromatik graceful pada graf M-Bintang 𝑀𝑆𝑛 untuk n  3 adalah χ𝑔 (𝑀𝑆𝑛 ) = 𝑛 + 2 4. Teorem 4. Bilangan kromatik graceful pada graf H-Bintang (𝐻𝑆 𝑛) untuk n  3 adalah χ𝑔 (𝐻𝑆𝑛 ) = { 6, 𝑢𝑛𝑡𝑢𝑘 𝑛 = 3 𝑛 + 2, 𝑢𝑛𝑡𝑢𝑘 𝑛 ≥ 4 Selain empat teorema baru yang diperoleh, dilakukan desiminasi mengenai pewarnaan graceful. Desiminasi ini dilakukan dengan membuat media pembelajaran berbentuk E-Monograf. Media pembelajaran berbentuk EMonograf ini dapat dengan mudah diakses oleh masyarakat umum karena berbasis online