Perpustakaan Digital ITB

Misalkan G=(V,E) adalah graf terhubung dan u,v ? V(G),u ? v. Jarak antar u ke v dalam graf G, dinotasikan dengan d(u,v), merupakan panjang lintasan terpendek dari u ke v. Adapun diameter graf G, ditulis diam(G)=max {d(u,v)|u,v ? V(G)}. Misalkan S ? V(G) dan S={s_1, …, s_k}. Untuk setiap v ? V(G) definisikan representasi r(v|S) sebagai k-tupel (d(v,s_1 ), …, d(v,s_k)). Jika u?v ? V(G), r(u |S) ? r(v|S) maka S disebut himpunan pembeda dari graf G. Sekarang misalkan S? V(G) dan v? V(G), misalkan pula ? =(S_1, …, S_k) merupakan k-partisi terurut dari V(G). Representasi v terhadap ? adalah k-tupel r(v|?)=(d(v,S_1 ), …, d(v,S_k)). Jika semua representasi r(v|?) berbeda, maka ? disebut partisi pembeda. Dimensi partisi dari graf G, dinotasikan dengan pd(G), adalah bilangan bulat terkecil k sedemikian sehingga G memiliki partisi pembeda dengan k kelas partisi. Penentuan dimensi partisi termasuk ke dalam masalah dengan tingkat kesulitan Non-deterministic Polynomial Complete (NP-Complete). Oleh karena itu, penentuan dimensi partisi masih terbatas untuk kelas-kelas graf tertentu. Dimensi partisi graf terhubung yang sudah berhasil ditentukan diantaranya adalah graf lintasan P_n, graf komplit K_n, karakterisasi graf terhubung dengan pd(G)=n-1, dan karakterisasi graf terhubung dengan pd(G)=n-2. Proyek ini membahas tentang graf tehubung orde n ? 9 berdiameter 2 dengan pd(G)=n-3. Hasil dari kajian proyek ini menunjukan bahwa graf G1,G2, H1, H2,...H4, K1 + (K1 ? K1,n-3), dan (K2+K1,n-3). memiliki dimensi partisi n-3, dengan n merupakan orde dari graf tersebut.