Salah satu bidang kajian yang menarik dan berkembang pesat adalah teori graf. Teori graf adalah salah satu konsep matematika diskrit, yaitu teori yang mengkaji himpunan titik (obyek) beserta himpunan garis, dimana garis menyatakan hubungan antar dua titik. Implementasi teori graf pada kehidupan nyata antara lain penjadwalan, penentuan tempat-tempat strategis agar dapat dikunjungi secara adil oleh seluruh tempat di suatu wilayah, penentuan pengelompokan yang memenuhi syarat tertentu, dan penentuan sekelompok titik (obyek) yang dapat mewakili seluruh titik yang ada pada graf tersebut.
Untuk menyelesaikan permasalahan terakhir di atas, dapat menggunakan konsep yang dikenal dalam teori graf sebaga himpunan pembeda multiset. Berikut ini disajikan konsep teori graf dan himpunan pembeda multiset secara formal. Suatu graf didefinisikan sebagai himpunan berhingga tak kosong yang anggotanya disebut titik, beserta himpunan yang anggotanya merupakan pasangan tak terurut dua titik yang berbeda dari yang disebut garis. Banyaknya titik pada graf disebut ordo dari graf dan banyaknya garis pada graf disebut ukuran dari graf Karena struktur graf terdiri atas titik dan garis, sebagaimana pada Ruang Euclide, maka pada teori graf memungkinkan dibangun definisi basis dan dimensi. Basis dalam graf menyatakan suatu himpunan titik dengan kardinalitas minimal yang menyebabkan representasi setiap titik terhadap himpunan tersebut berbeda. Dilihat dari definisi representasi setiap titik, konsep basis berkembang menjadi basis multiset. Jika konsep representasi pada basis merupakan pasangan terurut, maka konsep representasi dalam basis multiset merupakan himpunan, yang disebut sebagai representasi multiset. Dari basis multiset, dikembangkan lebih lanjut dalam basis multiset lokal. Basis multiset adalah himpunan dengan kardinalitas minimal sehingga setiap titik mempunyai representasi multiset yang berbeda terhadap himpunan tersebut, sedangkan basis multiset lokal merupakan himpunan dengan kardinalitas minimal yang menyebabkan setiap dua titik yang membentuk garis, mempunyai representasi multiset yang berbeda terhadap himpunan tersebut. Kardinalitas dari basis multiset lokal disebut dengan dimensi multiset lokal. Jika pada suatu graf tidak ditemukan himpunan basis multiset lokal, maka dikatakan graf tersebut mempunyai dimensi multiset lokal tak hingga.
Operasi corona dari graf dan graf dinotasikan dengan Karena operasi corona tidak bersifat komutatif, maka secara umum graf operasi corona tidak sama dengan . Graf hasil operasi corona yang digunakan pada penelitian ini berasal dari graf pohon. Graf pohon meliputi graf lintasan dan graf bintang. Graf lintasan berordo dinotasikan dengan dan graf bintang berordo dinotasikan dengan . Dari dua graf ini, terdapat empat kombinasi graf hasil operasi corona, yaitu , dan Dimensi multiset lokal dari keempat graf hasil operasi corona tersebut telah berhasil ditemukan pada artikel ini, berupa nilai eksaknya, yang pembuktiannya disajikan secara lengkap. Secara umum, nilai eksak dimensi multiset lokal graf hasil operasi corona dari keempat hasil di atas tergantung pada ordo salah satu graf penyusunnya dan dimensi multiset lokal dari graf penyusun lainnya.
Beberapa hasil penelitian sebelumnya yang digunakan pada penelitian ini antara lain dimensi multiset lokal graf pohon, dimensi multiset lokal graf lengkap dan karakterisasi graf dengan nilai dimensi multiset lokal tertentu. Pada artikel ini juga dilengkapi dengan contoh-contoh yang dapat mempermudah pembaca untuk memahaminya. Pada akhir artikel disajikan pula beberapa peluang untuk penelitian lebih lanjut, yang salah satunya adalah syarat suatu graf agar dimensi multiset lokal suatu graf tersebut sama dengan dimensi metrik lokalnya, yang disajikan dalam open problem.
Definisi graf operasi corona serta hasil utama secara terperinci, dapat dilihat secara lengkap pada artikel, dengan judul “Local multiset dimension of corona product of tree graphs” yang dipublikasikan pada Jurnal Discrete Mathematics, Algorithms and Applications, Tahun 2023 yang dapat diakses pada laman yang tertera di bagian bawah ini.
Penulis: Dr. Liliek Susilowati, S.Si., M.Si.
Fakultas Sains dan Teknologi, Universitas Airlangga
Artikel lengkap dengan judul: “Local multiset dimension of corona product of tree graphs”
Dapat diakses melalui laman:
https://www.worldscientific.com/doi/10.1142/S1793830923500921.
