Teori graf merupakan teori yang mengkaji masalah diskrit yang dapat disajikan sebagai titik dan garis. Dalam implementasinya, titik menyatakan obyek yang diamati dan garis menyatakan hubungan antar obyek yang diamati. Oleh karena itu, teori graf merupakan teori yang dapat digunakan untuk menyelesaikan permasalahan yang dapat disajikan sebagai titik dan garis.
Permasalahan yang berkembang dalam dunia nyata juga diiringi dengan perkembangan konsep, salah satunya dalam konsep teori graf. Konsep yang berkembang cukup pesat dalam teori graf adalah konsep dimensi metrik. Dalam pembahasan dimensi metrik pada graf, maka graf yang dikaji adalah graf terhubung, yaitu graf yang setiap dua titiknya dihubungkan dengan jalan.
Dimensi metrik adalah konsep yang mengkaji himpunan titik pada graf yang dapat membedakan setiap titik pada graf secara berbeda. Dengan memandang sifat titik yang dibedakan oleh suatu himpunan titik, maka konsep dimensi metrik berkembang menjadi dimensi metrik lokal. Lebih lanjut, dengan memperhatikan bagaimana himpunan titik pada graf dapat membedakan setiap titik pada graf, maka konsep dimensi metrik berkembang salah satunya menjadi dimensi multiset. Penggabungan dua konsep di atas menghasilkan dimensi multiset lokal. Konsep dimensi multiset lokal ini merupakan pengembangan konsep dimensi multiset pada graf yang dibangun oleh Simanjuntak.
Pada penelitian ini dikaji dimensi multiset lokal yang diterapkan pada graf hasil operasi comb. Pada artikel ini disajikan definisi formal dimensi multiset lokal yang disertai contoh yang memudahkan para pembaca untuk memahami konsep tersebut. Pada penelitian ini disajikan dua karakterisasi, yaitu dimensi multiset lokal suatu graf bernilai satu jika hanya jika graf tersebut adalah graf bipartite. Karakterisasi tersebut didukung dengan karakterisasi bahwa graf merupakan graf bipartite jika hanya jika tidak memuat siklus gasal. Dua karakterisasi ini beserta dimensi metrik lokal dari beberapa graf khusus, mendukung hasil utama dari penelitian.
Hasil utama dari penelitian ini adalah dimensi multiset lokal pada graf hasil operasi comb. Hasil penelitian diawali dengan karakterisasi graf operasi kali comb. Karakterisasi yang pertama adalah graf hasil operasi comb adalah graf bipartite jika hanya jika dua graf yang dioperasikan juga merupakan graf bipartite dan graf hasil operasi comb adalah graf lintasan jika hanya jika dua graf yang dioperasikan masing-masing adalah graf lintasan.
Karakterisasi selanjutnya adalah karakterisasi dimensi multiset graf hasil operasi kali comb, yaitu dimensi multiset lokal graf hasil operasi kali comb adalah satu jika hanya jika dimensi multiset dua graf yang dioperasikan masing-masing adalah satu. Hasil lain adalah sifat dimensi multiset suatu graf. Hasil lain yang diperoleh adalah karakterisasi dimensi multiset lokal pada graf hasil operasi kali comb dikaitkan dengan dimensi multiset lokal graf pembentuknya, hubungan dimensi multiset lokal pada graf hasil operasi comb dengan dimensi metrik lokalnya.
Semua hasil di atas didukung dengan pembuktian matematis serta diberi contoh, sehingga memudahkan pembaca untuk memahaminya. Hasil penelitian ini bersifat matematis teoritis, sehingga dapat dikategorikan pada pengembangan konsep dasar pada matematika. Penelitian ini merupakan kerjasama riset antara dosen Universitas Airlangga dan Universitas Jember. Bukti lebih rinci dapat dilihat di laman Journal STATISTICS, OPTIMIZATION AND INFORMATION COMPUTING, Stat., Optim. Inf. Comput., Vol. 14, No. 3 September 2025, pp 1356–1361, dengan penerbit International Academic Press, sebagaimana disajikan di bawah ini.
Penulis: Prof. Dr. Liliek Susilowati, S.Si., M.Si.
Fakultas Sains dan Teknologi, Universitas Airlangga
Artikel lengkap dengan judul:
“On the Local Multiset Dimension of Comb Product Graphs”
Dapat diakses melalui laman: http://www.iapress.org/index.php/soic/article/view/2431/1379.
