Perpustakaan Digital ITB

Konsep himpunan pembeda dan dimensi metrik dari suatu graf pertama kali diper-kenalkan oleh Harary dan Melter pada tahun 1976. Kemudian Okamoto pada tahun 2010 memperkenalkan konsep himpunan pembeda lokal dan dimensi metrik lokal. Misalkan G=(V,E) graf sederhana, jarak antara dua titik u dan v pada G di-notasikan d(u,v) adalah panjang lintasan terpendek yang menghubungkan titik u dan v. Misalkan W={w_1,w_2,...,w_k} subhimpunan tak kosong dari V(G) dan v sebarang titik di G, maka representasi metrik dari v terhadap W yang dinotasikan r(v│W) didefinisikan sebagai k-vektor (d(v,u_1 ),d(v,u_2 ),...,d(v,u_k )). Jika untuk setiap dua titik yang berbeda pada G juga memiliki representasi metrik yang berbeda terhadap W, maka W disebut himpunan pembeda dari G. Himpunan pembeda dengan kardinalitas terkecil disebut basis dari G. Kardinalitas dari basis suatu graf G disebut dimensi metrik dari graf G dan dinotasikan dim(G). Jika untuk setiap dua titik yang bertetangga pada G memiliki representasi metrik yang berbeda terhadap W, maka W disebut himpunan pembeda lokal dari G. Himpunan pembeda lokal dengan kardinalitas terkecil disebut basis lokal dari G. Kardinalitas dari basis lokal suatu graf G disebut dimensi metrik lokal dari graf G dan dinotasikan lmd(G). Graf sirkulan C_n (a_1,a_2,...,a_k ) adalah graf dengan himpunan titik {v_0,v_1,...,v_(n-1) } dan setiap titik v_i bertetangga dengan titik v_((i+a_j )mod n), dimana j=1,2,...,k. Himpunan {a_1,a_2,...,a_k } disebut himpunan penghubung dari graf sirkulan tersebut. Dalam tesis ini, dibahas tentang nilai dimensi metrik lokal dari graf sirkulan dengan himpunan penghubung {1,2},{1,2,3} dan {1,k}.