Perpustakaan Digital ITB

Misalkan G adalah graf terhubung, u dan v adalah titik pada G, jarak d(u,v) adalah panjang lintasan terpendek yang menghubungkan titik u dan v di G. Misal W={w_1,…,w_k} adalah himpunan terurut dari titik-titik di G dan v adalah titik di G, representasi dari v terhadap W adalah k -vektor (pasangan k -tuple) r(v│W)=(d(v,w_1 ),d(v,w_2 ),…,d(v,w_k )). Jika representasi setiap titik di G, terhadap W berbeda, maka W disebut himpunan pembeda dari G. Himpunan pembeda dengan kardinalitas minimum disebut basis metrik. Jika W={w_1,w_2,…,w_m} adalah subhimpunan titik di G dan v adalah titik di G, multiset representasi dari v terhadap W didefinisikan sebagai multiset dari jarak antara titik v dan titik-titik di W dinotasikan dengan r_m (v|W). Jika r_m (v│W)≠r_m (u│W) untuk setiap pasang titik yang berbeda, maka W disebut himpunan pembeda dari G. Himpunan pembeda dengan kardinalitas minimum disebut basis multiset. Kardinalitas dari basis multiset disebut dimensi multiset. Dalam tesis ini akan ditentukan dimensi muliset dari beberapa kelas graf seperti graf pohon k -er lengkap, graf ulat, graf sirkulan, graf hasil kali Kartesian dan graf sirkulan.