Perpustakaan Digital ITB

Graf yang dibahas dalam tesis ini adalah graf hingga, sederhana, dan terhubung. Misalkan G = (V;E) adalah suatu graf dengan himpunan titik berhingga V (G) dan himpunan sisi E(G): Jarak antara dua titik yang berbeda u; v 2 V (G) adalah panjang lintasan terpendek antara dua titik tersebut di G; dinotasikan dengan d(u; v): Misalkan W = (w1,w2,.....wk) c V (G): Untuk sebuah titik v E V (G); representasi dari titik v terhadap W adalah k-pasang terurut, r(vlW) = (d(v,w1), d(v,w2), ....., d(v;wk)): Himpunan W adalah himpunan pembeda dari graf G jika setiap dua titik yang berbeda memiliki representasi yang berbeda terhadap W: Himpunan pembeda dengan kardinalitas minimum disebut sebagai basis dari graf G dan kardinalitasnya dinyatakan sebagai dimensi metrik dari graf G; dinotasikan dengan betha(G): Dalam tesis ini, kami menentukan dimensi metrik dari graf yang diperoleh dengan melakukan operasi comb terhadap dua graf terhubung. Misalkan G dan H adalah dua graf terhubung. Misalkan o E V (H): Operasi comb dari dua graf G dan H; dinotasikan dengan G . H; diperoleh dari satu buah graf G dan sebanyak jV (G)j buah graf H yakni H1,H2, .....H/V (G)/; dengan cara menempelkan titik o dari graf Hi ke titik ke-i dari V (G): Pada tesis ini akan ditentukan dimensi metrik dari graf G -> H; dengan G adalah sembarang graf terhubung dan H adalah graf bukan lintasan untuk sembarang titik tempel o. Selain itu, kami mengkaji dimensi metrik dari G -> H dengan G adalah sembarang graf terhubung dan H adalah graf lintasan untuk titik tempel o tertentu.