Tahun 2024 ini Teori Graf sangat populer pada kalangan saintis karena banyaknya penerapannya pada kehidupan sehari-hari. Baik dalam machine learning maupun pada ilmu-ilmu sains lainnya (Re: Matematika, Statistik, Fisika, Kimia, Biologi, maupun dalam ilmu Teknik). Apa itu Teori Graf. Teori Graf adalah cabang ilmu matematika yang mempelajari struktur hubungan antara objek-objek yang disebut sebagai “titik” (Re: biasanya disimbolkan dengan V(G)) yang mungkin terhubung maupun tidak terhubung dengan titik lainnya dengan objek-objek yang disebut sebagai “sisi” (Re: biasanya disimbolkan dengan E(G)). Beberapa istilah lain yang digunakan pada Teori Graf yaitu: lintasan, siklus, jarak, diameter, girth, radius, dan lain-lain. Istilah-istilah tersebut didefinisikan secara jelas pada link artikel yang akan diberikan di akhir.

Setelah kita mengetahui apa itu Teori Graf, selanjutnya kita lihat lebih dalam, apa saja konsep-konsep yang dipelajari pada Teori Graf. Di antaranya: Himpunan dominasi jarak k, himpunan pembeda, pewarnaan, pelabelan, dan lain sebagainya. Konsep-konsep tersebut diterapkan pada graf-graf yang digunakan, ada beberapa graf khusus yang dikenal secara baik diantaranya: graf lintasan, gaf lingkaran, graf lengkap, dan masih banyak lagi yang lainnya. Selain graf tunggal, ada juga operasi graf yang bisa diterapkan pada satu graf, dua graf, tiga graf, dan seterusnya. Istilah-istilah tersebut juga didefinisikan secara jelas pada link artikel yang akan diberikan di akhir.

Perkembangan penelitian Teori Graf telah sampai pada penggabungan beberapa konsep-konsep pada Teori Graf, bisa dua konsep, tiga konsep, dan seterusnya. Salah satu contoh penggabungan konsep Teori Graf yaitu Himpunan Dominasi Jarak k dengan Himpunan Pembeda. Sebelum kita masuk pada definisi penggabungan dua konsep ini, terlebih dahulu kita ketahui definisi dari himpunan dominasi jarak k dan definisi himpunan pembeda. Graf yang akan kita gunakan selanjutnya kita simbolkan dengan G.

Himpunan D pada G disebut himpunan dominasi jarak k jika D merupakan himpunan bagian dari  V(G) yang sedemikian hingga titik-titik pada V(G) yang tidak terhubung dengan D memiliki jarak maksimal k terhadap D. Kardinalitas minimum dari D dinotasikan dengan k(G) dan disebut bilangan dominasi jarak k. Sedangkan W disebut himpunan pembeda jika setiap titik di V(G) memiliki representasi yang berbeda terhadap W. Kardinalitas minimum pada himpunan pembeda disebut basis. Banyaknya titik pada basis graf G disebut dimensi dinotasikan dengan dim⁡(G). Konsep dimensi pada graf ini dibangun dengan menggunakan konsep jarak (metrik), sehingga disebut dengan dimensi metrik. 

Penggabungan dua konsep tersebut disebut dengan himpunan dominasi pembeda jarak k. Himpunan S pada G disebut himpunan dominasi pembeda jarak k jika S merupakan himpunan dominasi jarak k sekaligus himpunan pembeda. Kardinalitas minimum pada himpunan dominasi pembeda jarak k disebut dengan bilangan dominasi pembeda jarak k dinotasikan dengan rk(G). Karena himpunan dominasi pembeda jarak k ini merupakan konsep baru, maka graf yang diterapkan pada konsep ini sangat luas. Berdasarkan hasil penelitian, nilai rkG bergantung pada nilai bilangan dominasi jarak k dan dimensi metrik, dengan batas bawah adalah maksimum dari k(G) dengan dim⁡(G) dan batas atasnya adalah minimum dari penjumlahan k(G) dan dim⁡(G) dengan VG-1. 

Selain itu, didapatkan karakterisasi diantaranya (1) untuk nilai k≥diam(G), rkG=dim⁡(G); (2) untuk diamG=k+1, rkG=dim G +1; (3) jika banyaknya titik dinotasikan dengan n dan diameter d, maka nilai rk dibagi dalam tiga kasus, yaitu untuk d≤k,  k+1≤d≤2k, dan d≥2k+1. (4) untuk diameter d, radius r, dan girth g maka (a) rkGd+12k+1 (b) rkG2r2k+1 (c) rkGg2k+1; (5) (a)  rkG=1 jika dan hanya jika G∈Pik+1i=2 (b) untuk n≥4, rkG=n-2 jika dan hanya jika G∈P4, Ks,ts,t≥1, Ks+Kts≥1,t≥2, Ks+K1Kts,t≥1. Untuk setiap k≥3, rkG=n-2 jika dan hanya jika G∈Ks,ts,t≥1, Ks+Kts≥1, t≥2, Ks+K1Kts,t≥1 (c) rkG=n-1 jika dan hanya jika G≅Kn. Mengenai pembuktian dari hasil-hasil yang telah disebutkan dapat dilihat secara lengkap pada link artikel yang diberikan di akhir artikel ini.

Penelitian mengenai himpunan dominasi pembeda jarak k ini masih terbuka secara luas, bisa diterapkan pada operasi graf, pada graf-graf khusus lain yang belum diteliti, maupun pada aplikasi machine learning yang dapat diterapkan pada kehidupan bermasyarakat bisa untuk bidang kelautan, pertanian, tata kota, dan lain sebagainya.

Penulis: Dr. Liliek Susilowati, S.Si., M.Si.

Artikel lengkap dapat diakses melalui laman: https://doi.org/10.7151/dmgt.2484