Perkembangan sain dan teknologi searah dengan meningkatnya pola hidup manusia, yang diiringi dengan munculnya banyak masalah baru yang membutuhkan penyelesaian terbaik. Berkaitan dengan hal ini, matematika mempunyai peran yang sangat tinggi, salah satunya adalah teori graf sebagai bagian dari matematika.
Permasalahan yang dapat diselesaikan dengan graf adalah permasalahan yang dapat disajikan dalam bentuk titik dan garis, dimana titik menyatakan obyek yang diamati dan garis menyatakan hubungan antar dua titik. Secara formal, suatu graf G didefinisikan sebagai himpunan berhingga tak kosong V(G) yang anggotanya disebut titik, beserta himpunan E(G) yang anggotanya merupakan pasangan tak terurut dua titik yang berbeda dari V(G) yang disebut garis. Pada struktur graf yang terdiri atas titik dan garis, sebagaimana pada Ruang Euclide, memungkinkan dibangun definisi basis dan dimensi. Basis dalam graf menyataka suatu himpunan dengan kardinlaitas minimal yang menyebabkan representasi setiap titik pada 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 local merupakan himpunan dengan kardilitas minimal yang menyebabkan setiap dua titik yang membentuk garis, mempunyai representasi multiset yang berbeda. Kardinalitasdari basis multiset local disebut dengan dimensi multiset lokal. Jika pada suatu graf tidak ditemukan himpunan basis multiset local, maka dikatakan graf tersebut mempunyai dimensi multiset local tak hingga.
Dalam penelitian ini, diperoleh karakterisasi suatu graf yang mempunyai dimensi multiset local satu, yaitu graf terhubung bipartite. Graf terhubung bipartite adalah graf yang himpunan titiknya dapat dipartisi menjadi dua dan garisnya menghubungkan dua titik pada partisi yang berbeda. Sebagai akibat dari karakterisasi di atas, graf pohon mempunyai dimensi multiset local graf sebesar satu. Selanjutnya, dimensi multiset local dikenakan pada graf amalgamasi. Graf amalgamasi adalah graf baru yang diperoleh dengan mengambil satu titik pada beberapa graf dan menempelkan titik-titik yang dipilih menjadi satu.
Hasil utama dalam penelitian ini adalah dimensi multiset local graf amalgamasi, untuk amalgamasi graf yang homogen. Diperoleh hasil untuk graf lintasan, graf lengkap, graf roda, dan graf kipas. Untuk graf amalgamasi graf secara umum, yang ditemukan adalah batas atas dari dimensi multiset lokalnya. Hasil secara terperinci dan pembuktian secara detil dapat dilihat secara lengkap pada artikel, dengan judul “Local Multiset Dimension of Amalgamation Graphs” yang dapat diakses pada laman yang tertera di bagian bawah ini.
Penelitian dapat dilanjutkan salah satunya dengan menemukan batas bawah dari dimensi multiset local dari graf hasil amalgamasi.
Penulis: Dr. Liliek Susilowati, S.Si., M.Si.
Fakultas Sains dan Teknologi, Universitas Airlangga
Artikel lengkap dengan judul: “Local Multiset Dimension of Amalgamation Graphs”
Dapat diakses melalui laman:
