Teori graf merupakan salah satu cabang ilmu matematika dalam bidang Aljabar. Graf terdiri dari himpunan titik dan himpunan sisi dengan syarat himpunan titik tidak boleh kosong. Sedangkan himpunan sisi memuat pasangan tak teurut dua titik yang berbeda. Salah satu penggunaan graf adalah pewarnaan graf. Pengertian dari pewarnaan graf adalah proses pemberian warna pada titik atau garis dengan persyaratan tertentu.
Salah satu pewarnaan graf adalah pada pewarnaan peta suatu peta benua dengan menyatakan suatu negara sebagai titik dan dua negara bertetangga dihubungkan dengan satu garis. Pewarnaan dilakukan dengan syarat dua negara yang bertetangga dinyatakan dengan warna yang berbeda. Permasalahannya adalah bagaimana mewarnai peta dengan syarat tersebut dengan jumlah warna minimal. Melalui graf ini diperoleh bahwa banyaknya warna minimal yang digunakan adalah empat.
Aplikasi pewarnaan graf yang lainnya adalah pada bidang pertanian, yaitu terkait dengan penjadwalan dalam pemakaian alat pertanian pada kelompok tani. Contohnya, proses penyemprotan yang dilakukan secara rutin satu minggu tiga kali. Misalkan pada suatu daerah terdapat dua belas kelompok tani, dan akan disusun jadwal pemakaian alat pertanian selama 7 hari.
Permasalahan dari penjadwalan adalah mencari jadwal yang tepat untuk pemakaian alat pertanian sedemikian hingga alat pertanian yang paling minimum. Masalah ini dalam graf dikenal sebagai permasalahan pewarnaan titik ketakteraturan lokal. Pada tabel di atas, dengan 12 kelompok tani, diperoleh bahwa kebutuhan alat pertanian yang paling minimum adalah sebanyak 8 alat.
Pewarnaan titik pada graf adalah memberikan warna berbeda pada titik yang saling bertetangga. Bila terdapat k warna dalam pewarnaan titik, maka dikatakan sebagai k-pewarnaan. Banyaknya warna minimum yang digunakan dalam pewarnaan graf disebut sebagai bilangan kromatik.
Misalkan setiap titik pada graf G diberi label warna 1 sampai dengan k dan bobot dari setiap titik dari graf G merupakan jumlah semua label pada titik yang bertetangga dengan titik tersebut. Pelabelan tersebut dinamakan pewarnaan titik ketakberaturan lokal jika (1) maksimum pelabelan warna sama dengan minimum dari semua maksimum label yang bisa dibuat; (2) setiap dua titik yang bertetangga mempunyai bobot yang berbeda. Bilangan kromatik ketakberaturan local merupakan kardinalitas minimum dari pewarnaan titik ketakberaturan lokal.
Penelitian ini mengkaji tentang bilangan kromatik ketakberaturan lokal dari graf website, graf helm, graf helm tertutup, graf gir, graf kipas, graf sun let, graf roda ganda. Penelitian ini menghasilkan tujuh teorema. Teorema pertama, bilangan kromatik ketakberaturan lokal dari graf website berordo n sama dengan 5, 6, dan 7 berturut-turut untuk n sama dengan 4,6; n sama dengan 5 atau n sama dengan 7 dengan n bilangan genap; dan n lebih besar sama dengan 7 dengan n bilangan gasal.
Teorema kedua, bilangan kromatik ketakberaturan lokal dari graf helm berordo n lebih besar sama dengan 3, sama dengan 5 dan 6 berturut turut untuk n bilangan genap dan bilangan gasal. Teorema ketiga, bilangan kromatik ketakberaturan lokal dari graf helm terututp berordo n lebih besar sama dengan 4, sama dengan 4, 5 dan 6 berturut turut untuk n sama dengan 4; bilangan genap n lebih bbesar sama dengan 5; dan n bilangan gasal lebih besar sama dengan 5.
Teorema keempat, bilangan kromatik ketakberaturan lokal dari graf gir berordo n lebih besar sama dengan 4 adalah 3. Teorema kelima, bilangan kromatik ketakberaturan lokal dari graf kipas berordo n lebih besar sama dengan 4 adalah 4. Teorema keenam, bilangan kromatik ketakberaturan lokal dari graf sun let berordo n lebih besar sama dengan 4, sama dengan 3 dan 5 berturut turut untuk n bilangan genap dan bilangan gasal. Teorema ketujuh, bilangan kromatik ketakberaturan lokal dari graf roda ganda berordo n lebih besar sama dengan 4, sama dengan 3 dan 4 berturut turut untuk n bilangan genap dan bilangan gasal. (*)
Penulis: Mohammad Imam Utoyo
Artikel lengkapnya dapat diakses melalui laman berikut ini,
https://iopscience.iop.org/article/10.1088/1742-6596/1211/1/012003
