Perpustakaan Digital ITB

Semua graf yang dikaji dalam tesis ini adalah graf sederhana, terhubung, dan terbatas. Misalkan G = (V (G), E(G)) adalah suatu graf dengan V (G) sebagai himpunan titik dan E(G) sebagai himpunan sisi dari G: Jarak antara dua titik x dan y dalam graf terhubung G adalah panjang lintasan terpendek dari titik x ke y di G; dinotasikan dengan dG(x; y): Misalkan W = (w1,w2, .....wk) adalah subhimpunan dari V (G). Representasi dari titik v terhadap W didefinisikan sebagai pasangan k-terurut r(v W) = (dG(v,w1); dG(v,w2), ...., dG(v,wk)): Himpunan W disebut himpunan pembeda lokal jika r(u W) 6= r(v W) untuk setiap pasangan titik bertetangga u; v 2 V (G): Bilangan terkecil k dimana G memiliki himpunan pembeda lokal dengan kardinalitas k disebut dimensi metrik lokal, dinotasikan dengan lmd(G): Suatu himpunan pembeda lokal di G dengan kardinalitas lmd(G) disebut basis lokal dari G. Penentuan dimensi metrik lokal dari graf hasil operasi merupakan salah satu kajian menarik dalam konsep dimensi metrik lokal. Studi yang dilakukan pada kajian ini adalah penentuan kaitan antara dimensi metrik lokal dari graf hasil operasi dengan dimensi metrik lokal dari graf asalnya. Dalam tesis ini, kami mengkaji penentuan dimensi metrik lokal dari beberapa graf yang diperoleh dari operasi graf, yaitu amalgamasi, operasi comb, fraktal, dan penambahan satu sisi pada sebarang pohon. Misalkan (H1,H2, .....Hn) adalah koleksi graf terhubung. Misalkan setiap Hi, iE (1, 2, ..... ng) memuat suatu subgraf J yang dikatakan subgraf terminal. Amalgamasi subgraf dari H1,H2,....,Hn) dinotasikan dengan Subgraph (Amal(Hi; J), adalah graf yang diperoleh dari 1 kopi Hi untuk setiap i E (1, 2, ...., n) dengan menempelkan setiap subgraf terminalnya. Untuk dua buah graf terhubung yang sederhana G dan H; graf hasil operasi comb G -> H adalah graf yang diperoleh dari satu kopi graf G dan jV (G)j kopi graf H dengan menempelkan titik x dari kopi ke-i dari graf H ke titik ke-i dari graf G. ....... Misalkan G adalah suatu graf pohon T yang ditambahkan satu sisi e = xy dengan x dan y adalah dua titik tidak bertetangga di T: Untuk sebarang pohon T dan sisi e; graf G memuat tepat satu lingkaran sehingga G disebut sebagai graf unicyclic.