Dimensi Metrik Pada Graf Sun, Graf Helm Dan Graf Double Cones

Oleh :
Bangkit Joko Widodo - M0109015 - Fak. MIPA

Graf G terdiri dari himpunan vertex V (G) = {v1; v2; :::; vn} dan himpunan edge E(G) = {e1; e2; :::; en}. Suatu graf G dikatakan terhubung jika terdapat lintasan yang menghubungkan setiap vertex pada G. Jarak antara dua vertex u dan v, dinotasikan d(u; v), adalah panjang lintasan terpendek dari vertex u ke v. Misalkan W = {w1;w2; :::;wn} adalah subhimpunan vertex-vertex dari graf terhubung G dan v ∈ V (G), representasi vertex v terhadap W didenisikan sebagai k-pasang terurut r(v|W) = (d(v;w1); d(v;w2); :::; d(v;wk)). Himpunan W dikatakan sebagai himpunan pembeda dari G jika untuk setiap dua vertex berbeda x; y ∈ V (G) berlaku r(x|W) ̸= r(y|W). Himpunan pembeda dengan kardinalitas terkecil disebut himpunan pembeda minimum atau basis dari G. Sedangkan banyaknya elemen dari suatu basis di G disebut dimensi metrik dari G, dinotasikan Dim(G). Dalam penelitian ini diperoleh dimensi metrik pada graf sun Sn, graf helm Hn dan graf double cones DCn. Kata kunci: dimensi metrik, himpunan pembeda, basis, graf sun, graf helm, graf double cones.