Perpustakaan Digital ITB

Misalkan ????! G = (V;E) merupakan graf berarah terhubung kuat yang sederhana de- ngan himpunan titik V dan himpunan sisi berarah E. Untuk u; v 2 V ( ????! G ), jarak dari u ke v, d(u; v) merupakan panjang lintasan berarah minimum dari u ke v. Misalkan B = fb1; b2; b3; :::bkg adalah subhimpunan terurut yang tak kosong dari V , representasi suatu v terhadap B didenisikan sebagai pasangan terurut (d(v; b1); d(v; b2); :::; d(v; bk)) dan dino- tasikan dengan r(vjB). Jika untuk setiap dua titik berbeda u; v berlaku r(ujB) 6= r(vjB) maka B disebut sebagai himpunan pembeda dari G. Jika kardinalitas dari B minimum, maka B disebut basis dari ????! G dan kardinalitas dari B disebut dimensi metrik dari ????! G , dinotasikan dim( ????! G ). Misalkan n 3 adalah bilangan bulat positif dan ????! G memuat selimut???? ????! Cn. Orientasi ????! Cn????sederhana adalah orientasi pada graf berarah ????! G sehingga setiap ????! Cn ????! G terhubung kuat. Dalam penelitian ini akan dikaji dimensi metrik graf persahabatan berarah ( ????! Fn), graf kipas berarah ( ????????! Fm;n), graf roda berarah ( ????! Wn), dan amalgamasi graf lingkaran berarah.