Perpustakaan Digital ITB

Misalkan G=(V,E) adalah graf sederhana dengan V adalah himpunan titik dan E adalah himpunan sisi. Jarak antara dua titik u dan v pada G dinotasikan d(u,v) adalah panjang lintasan terpendek yang menghubungkan titik u dan v. Misalkan W = { w_1, w_2, …, w_k} adalah himpunan terurut titik-titik di V. Representasi metrik dari titik v terhadap W didefinisikan sebagai k-vektor: r(v|W)=(d(v,w_1 ),d(v,w_2 ),…,d(v,w_k )) Himpunan W disebut himpunan pembeda lokal jika r(u|W) ≠ r(v|W) untuk setiap u, v titik yang bertetangga di G. Bilangan positif terkecil k di mana G mempunyai himpunan pembeda lokal dengan k anggota disebut dimensi metrik lokal dan dinotasikan lmd (G). Himpunan pembeda lokal G dengan kardinalitas lmd (G) disebut basis lokal dari G. Dalam tugas akhir ini, dibahas dimensi metrik lokal dari graf roda, graf roda gigi, graf kipas, dan graf bunga.