Perpustakaan Digital ITB

Dimensi multiset yang merupakan suatu varian dari dimensi metrik merupakan kajian yang menarik karena banyak graf yang memiliki dimensi metrik hingga namun dimensi multisetnya tak hingga. Untuk W ? V himpunan tak kosong, representasi multiset dari titik v pada G terhadap W dinotasikan rm(v|W). Jika untuk setiap pasangan titik berbeda u dan v di G berlaku rm(u|W) ?= rm(v|W), maka W dikatakan sebagai himpunan pembedam. Himpunan pembeda-m dengan kardinalitas terkecil disebut basis multiset. Jika G mempunyai himpunan pembeda-m, maka kardinalitas dari basis multisetnya disebut dimensi multiset (dinotasikan md(G)). Jika G tidak mempunyai himpunan pembeda, maka didefinisikan md(G) = ?. W dikatakan sebagai himpunan pembeda lokal jika rm(u|W) ?= rm(v|W), untuk setiap u, v ? G dengan d(u, v) = 1. Jika G mempunyai himpunan pembeda lokal, maka kardinalitasnya disebut dimensi multiset lokal (dinotasikan ?l(G)). Jika G tidak mempunyai himpunan pembeda lokal, maka ?l(G)) = ?. Fokus penelitian ini adalah menentukan dimensi multiset dan dimensi multiset lokal beberapa kelas graf seperti lintasan, siklus, roda dan kipas. Selain itu, akan dikaji dimensi multiset dan dimensi multiset lokal dari graf hasil kali kartesius pada grafgraf tersebut. Dalam penelitian ini, ditemukan beberapa graf yang memiliki dimensi multiset tak hingga, namun dimensi multiset lokalnya berhingga.