DIMENSI METRIK GRAF HASIL OPERASI COMB DARI GRAF LINTASAN DAN GRAF BERLIAN = METRIC DIMENSIONS OF GRAPHS RESULTING FROM COMB OPERATIONS FROM PATH GRAPHS AND DIAMOND GRAPHS

Graf sederhana G adalah pasangan (V(G),E(G)), dengan V(G) adalah himpunan diskrit berhingga dan tidak kosong , yang anggotanya disebut titik, dan E(G) adalah himpunan pasangan-pasangan tak terurut dan berbeda dari anggota-anggota V(G) yang disebut sisi. Misalkan G adalah graf terhubung, terdapat himpunan terurut S={s_1,s_2,…,s_k }⊂V(G). Representasi titik v terhadap S didefinisikan sebagai jarak dari v ke tiap-tiap elemen di S, ditulis r(v│S)=(d(v,s_1 ),d(v,s_2 ),…,d(v,s_k )). S disebut sebagai himpunan penentu dari V(G). Jika untuk setiap i≠j∈V(G) memiliki representasi yang berbeda terhadap S, yakni berlaku r(u_i│S)≠r(u_j│S). Himpunan penentu dengan kardinalitas (banyak anggotanya) minimum disebut himpunan penentu minimum atau basis dari graf G. Kardinalitas dari basis disebut dimensi metrik dari G, dinotasikan dengan dim⁡(G). Pada skripsi ini akan ditentukan dimensi metrik graf hasil operasi comb dari graf lintasan dan graf berlian. Hasil penelitian menunjukkan bahwa dim(Br_n )=2,untuk n=3,4,dan 5, dim(Br_n )=3,untuk n=6, dim(Br_n )=⌊(2n+2)/5⌋,untuk n≥7, serta dim(P_m⊳Br_n )=m,untuk n=3 dan dim(P_m⊳Br_n )= dim(Br_n )×m,untuk n≥4.

Keywords : teori graf, himpunan penentu, dimensi metrik, graf hasil operasi comb, graf lintasan, graf berlian.