DIMENSI PARTISI DARI GRAF ULAT

Abstract

Misalkan terdapat suatu graf sebarang G = (V;E), dimana V adalah him-
punan titik dan E adalah himpunan sisi. Misalkan terdapat suatu titik v 2 V (G) dan
suatu himpunan S V (G). Jarak antara titik v dan himpunan S, dinotasikan d(v; S),
didenisikan sebagai d(v; S) = minfd(v; x) j x 2 Sg, dimana d(v; x) adalah jarak an-
tara dua titik v dan x di G. Denisikan = fS1; S2; ; Skg sebagai himpunan yang
berisikan k-partisi tersebut. Suatu representasi titik v 2 V (G) terhadap himpunan
dapat ditulis dalam bentuk k-vektor:
r(v j ) = (d(v; S1); d(v; S2); ; d(v; Sk)):
Jika untuk setiap dua titik berbeda u; v 2 V (G) berlaku r(u j ) 6= r(v j ), maka
disebut partisi pembeda dari V (G). Partisi pembeda dengan kardinalitas minimum
disebut partisi pembeda minimum dari G. Dimensi partisi dari graf G, dinotasikan pd(G),
adalah kardinalitas dari partisi pembeda minimum dari G. Pada tulisan ini akan dibahas
kembali salah satu bagian dari disertasi [5] tentang penentuan dimensi partisi dari suatu
graf ulat.
Kata Kunci: Representasi titik, dimensi partisi, graf ulat