DIMENSI METRIK PADA GRAF DAN GRAF mPK + 1 n mCK + 1 n

Abstract

Sebarang himpunan tak kosong yang dilengkapi dengan suatu urutan disebut himpunan terurut. Himpunan terurut ),...,,( wwwW = dari titik-titik pada graf terhubung G dengan titik r pada G , adalah vektor-k (pasangan k-tuple), )),(),...,,(),,(()( 21 k 21 k wvdwvdwvdWvr = menunjukkan representasi dari titik v pada G terhadap W . Himpunan W dinamakan himpunan pembeda (resolving set) G jika titik-titik G mempunyai representasi berbeda. Himpunan pembeda dengan kardinalitas minimum disebut himpunan pembeda minimum (minimum resolving set), dan kardinalitas tersebut menyatakan dimensi metrik dari G dan dinotasikan dengan ).(Gβ Permasalahan yang dibahas adalah menentukan dimensi metrik pada graf mCK + 1 n dan graf mPK + , dengan langkah - langkah penyelesaian meliputi: pertama adalah menentukan pemilihan titik yang memungkinkan sebagai anggota W 1 n resolving set, untuk mempermudah penentuan, dilakukan penotasian di setiap titik di ;G langkah kedua adalah mencari W resolving set dari kemungkinan titik yang ada pada ;G selanjutnya langkah ketiga yaitu mencari W resolving set dengan kardinalitas minimum. Jika ya maka kardinalitas tersebut adalah dimensi metrik dari G , tetapi jika tidak maka kembali ke langkah kedua. Hasil dari penelitian ini adalah dimensi metrik graf mCK + , 3≥n , 2≥m dan dimensi metrik graf mPK + 1 n , 2≥n , .Ν∈m 1 n , 3≥n , 2≥m , n , m bilangan asli yaitu .2)( 1 Dimensi metrik pada graf mmCK n mCK + 1 =+β Dimensi metrik pada graf n mPK + , 2≥n , Ν∈m , yaitu sebagai berikut: untuk ;1 =m dimensi metrik dari graf 1 n mPK + adalah 2)( PKβ untuk ,52 ≤≤ n ,3)( 1 =+ n =+ PKβ 61 )( 1 =+   2 1 PKβ untuk ,7≥n dan untuk ;2≥m dimensi metrik dari graf mPK + 1 n n n − mmPK =+β ,12)( −=+ mmPKβ ,2)( 31 mmPK =+β 41 mPK )( 1 n adalah ,)( =+β untuk 5≥n ganjil, 1)( mPKβ untuk 6≥n genap. nm n −=+ 2 1 mnm n 2 1 − 21