J. Math. and Its Appl. ISSN: 1829-605X Vol. 8, No. 2, November 2011, 17–22

## DIMENSI METRIK PENGEMBANGAN GRAF
KINCIR POLA K 1 + mK 3

## Suhud Wahyudi, Sumarno, Suharmadi
Jurusan Matematika, FMIPA ITS Surabaya suhud@matematika.its.ac.id, sumarno@matematika.its.ac.id, susan@matematika.its.ac.id

## Abstrak
Himpunan pembeda dengan kardinalitas minimum disebut himpunan pembeda minimum, dan kardinalitas tersebut dinamakan dimensi metrik dari G dinotasikan dengan dim ( G ). Graf kincir adalah graf yang dapat dinyatakan dalam bentuk K 1 + mK 2 . Dalam makalah ini ditunjukkan bahwa dimensi metrik pengembangan graf kincir pola K 1 + mK 3 dengan m ≥ 2 adalah 2m. Katakunci: Himpunan pembeda, Dimensi metrik, Pengembangan graf kin- cir

## 1. Pendahuluan
Belum diketahui secara spesifik kapan bahasan dimensi metrik pertama kali ada. Menurut [1], ide dimensi metrik muncul dari himpunan pembeda (dan himpunan pembeda minimum) yang diperkenalkan oleh [2] pada tahun 1975. [2] menguta- rakan konsep himpunan locating untuk menyatakan himpunan pembeda seperti yang dikenal saat ini. Ia menyatakan kardinalitas minimum himpunan pembeda graf G sebagai location number dinotasikan dengan log( G ). Kemudian [3] pada tahun 1990 mengutarakan konsep dimensi metrik suatu graf seperti yang dikenal saat ini. Selanjutnya [4] pada tahun 1987 mengutarakan bahwa himpunan pembe- da W sebagai himpunan dari simpul - simpul di graf G sedemikian hingga untuk
18 Dimensi Metrik Pengembangan Graf Kincir Pola K 1 + mK 3
setiap simpul di G menghasilkan jarak yang berbeda terhadap setiap simpul di W . Dimensi metrik adalah kardinalitas minimum dari himpunan pembeda. Jika G adalah graf tak berarah dan terhubung, jarak antara dua titik u dan v di G , d ( u, v ) adalah panjang lintasan terpendek diantara keduanya. Untuk himpunan terurut W = { w 1 , w 2 , · · · , w k } dari simpul - simpul dalam graf terhubung G dan simpul v ∈ V ( G ), representasi dari v terhadap W adalah k – tuple
r ( v | W ) = ( d ( v, w 1 ) , d ( v, w 2 ) , · · · , d ( v, w k )) .
Jika r ( v | W ) untuk setiap simpul v ∈ V ( G ) berbeda, maka W disebut himpunan pembeda dari V ( G ). Himpunan pembeda dengan kardinalitas minimum disebut himpunan pembeda minimum, dan kardinalitas tersebut dinamakan dimensi me- trik dari G dinotasikan dengan dim( G ) [1].
[1] menunjukkan bahwa untuk setiap pasangan integer n,k dengan 1 ≤ k ≤ n − 1, terdapat suatu graf dimensi k orde n . Kemudian [5] menunjukkan bahwa jika G suatu graf terhubung order n ≥ 2, maka a. dim( G ) = 1 jika dan hanya jika G = P n ,
b. dim( G ) = n – 1 jika dan hanya jika G = K n dan
c. untuk n ≥ 4 , dim( G ) = n − 2 jika dan hanya jika G = K r,s , r, s ≥ 1 , G = K r + K s , r ≥ 1 , s ≥ 2 , atau G = K r + ( K 1 S K s ) , r, s ≥ 1 .
Jadi selain graf path P n , dimensi metriknya minimal 2. Selanjutnya [6] menunjukkan bahwa dimensi metrik graf kincir K 1 + mK 2 adalah m .
Contoh berikut diberikan untuk memberikan gambaran mendapatkan himpun- an pembeda, himpunan pembeda minimum dan dimensi metrik dari sebuah graf terhubung.
Diberikan graf terhubung G dengan 5 simpul dan 8 sisi seperti ditunjukkan pada Gambar 1, dan akan ditentukan himpunan pembeda dari graf G tersebut.
Gambar 1: Graf terhubung dengan 5 titik dan 8 sisi
Pembahasan : Misalkan W 1 , = ( u ). Maka representasi simpul-simpul di graf G terhadap W 1 adalah r ( u | W 1 ) = (0), r ( v | W 1 ) = (1), r ( y | W 1 ) = (1), r ( x | W 1 ) = (2), r ( z | W 1 ) = (1). Karena r ( v | W 1 ) = r ( y | W 1 ) = r ( z, W 1 ) = (1) maka W 1 bukan himpunan pembe- da dari graf G . Kemudian misalkan W 2 = { u, v, y } . Maka representasi simpul- simpul di graf G terhadap W 2 adalah r ( u | W 2 ) = (0 , 1 , 1), r ( v | W 2 ) = (1 , 0 , 1), r ( y | W 2 ) = (1 , 1 , 0), r ( x | W 2 ) = (2 , 1 , 1), r ( z | W 2 ) = (1 , 2 , 1). Karena representasi simpul-simpul di graf G terhadap W 2 berbeda, maka W 2 adalah himpunan pembe- da dari G . Akan tetapi W 2 bukan himpunan pembeda minimum dari V ( G ), karena W 3 berikut mempunyai kardinalitas lebih kecil dari W 2 . Misalkan W 3 = { u, v } . Maka representasi simpul-simpul di graf G terhadap W 3 adalah r ( u | W 3 ) = (0 , 1), r ( v | W 3 ) = (1 , 0), r ( z | W 3 ) = (1 , 2), r ( y | W 3 ) = (1 , 1), r ( x | W 3 ) = (2 , 1). Karena representasi simpul-simpul di graf G terhadap W 3 berbeda, maka W 3 adalah him- punan pembeda dari V ( G ). W 3 adalah himpunan pembeda minimum dari V ( G ) karena tidak ada lagi himpunan pembeda yang kardinalitasnya lebih kecil dari 2. Jadi graf diatas mempunyai dimensi 2 atau dim G = 2.
2. Dimensi Metrik Pengembangan Graf Kincir Po-
la K 1 + mK 3
Secara umum, pengembangan graf kincir pola K 1 + mK 3 dapat digambarkan se- perti pada Gambar 1.
Gambar 2: Graf K 1 + mK 3
20 Dimensi Metrik Pengembangan Graf Kincir Pola K 1 + mK 3
Lemma 2.1 Untuk graf K 1 + mK 3 dengan m ≥ 2 berlaku,
d ( u, v ) =    0 , jika u = v 1 , jika u dan v pada satu daun yang sama atau u dan v pusat kincir 2 , jika u dan v berada pada daun kincir yang berbeda
Lemma 2.2 Minimum himpunan pembeda graf K 1 + mK 3 diperoleh dengan ti- dak memasukkan simpul pusat atau sisi pusat kincir dalam subhimpunan W karena simpul pusat tidak akan memberikan representasi yang berbeda pada simpul-simpul dari K 1 + mK 3 , sehingga pasti tidak akan menghasilkan himpunan pembeda mini- mum.
Teorema 2.3 Dimensi metrik graf K 1 + 2 K 3 adalah 4
Bukti Misalkan graf K 1 + mK 3 dengan m = 2 dinamakan graf G 2. Jadi G 2 =
K 1 + 2 K 3 . Untuk menemukan batas atas, maka ambil W = { y 11 , y 12 , y 21 , y 22 } , dengan menggunakan Lemma 2.1 maka diperoleh representasi setiap simpul graf terhadap W adalah sebagai berikut: r ( y 11 | W ) = (0 , 1 , 2 , 2), r ( y 12 | W ) = (1 , 0 , 2 , 2), r ( y 13 | W ) = (1 , 1 , 2 , 2), r ( y 21 | W ) = (2 , 2 , 0 , 1), r ( y 22 | W ) = (2 , 2 , 1 , 0), r ( y 23 | W ) = (2 , 2 , 1 , 1), r ( x | W ) = (1 , 1 , 1 , 1), yang memberikan representasi yang berbeda. Jadi batas atas dim( G 2 ) adalah 4. Sedangkan jika kardinalitas W berkurang 1 yaitu | W | = 4 − 1 = 3, maka pasti bukan himpunan pembeda, karena pasti akan ditemukan sedikitnya dua titik dengan representasi yang sama. Misal diambil W = { y 11 , y 12 , y 21 } , maka dengan menggunakan Lemma 2.1 diperoleh representasi setiap simpul dari graf terhadap W adalah sebagai berikut : r ( y 11 | W ) = (0 , 1 , 2), r ( y 12 | W ) = (1 , 0 , 2), r ( y 13 | W ) = (1 , 1 , 2), r ( y 21 | W ) = (2 , 2 , 0), r ( y 22 | W ) = (2 , 2 , 1), r ( y 23 | W ) = (2 , 2 , 1), r ( x | W ) = (1 , 1 , 1), yang tidak memberikan representasi yang berbeda, karena r ( y 22 | W ) = r ( y 23 | W ) = (2 , 2 , 1) Jadi W = { y 11 , y 12 , y 21 } bukan merupakan himpunan pembeda G 2 . Dalam hal ini sesuai dengan Lemma 2.2, maka simpul pusat x tidak dimasukkan sebagai elemen W . Jadi batas bawah dim( G 2 ) adalah 4. Karena batas atas dan batas bawah dim( G 2 ) adalah 4 maka diperoleh 4 ≤ dim( G 2 ) ≤ 4, sehingga dim( G 2 ) = 4 .
Lemma 2.4 Dimensi metrik graf K 1 + 3 K 3 adalah 6
Bukti Misalkan graf K 1 + mK 3 dengan m = 3 dinamakan graf G 3 . Ja- di G 3 = K 1 + 3 K 3 . Untuk menemukan batas atas dim( G 3 ), maka ambil W = { y 11 , y 12 , y 21 , y 22 , y 31 , y 32 } . Dengan menggunakan Lemma 2.1 maka dipe- roleh representasi setiap simpul graf terhadap W adalah sebagai berikut : r ( y 11 | W ) = (0 , 1 , 2 , 2 , 2 , 2), r ( y 12 | W ) = (1 , 0 , 2 , 2 , 2 , 2),
r ( y 13 | W ) = (1 , 1 , 2 , 2 , 2 , 2), r ( y 21 | W ) = (2 , 2 , 0 , 1 , 2 , 2),
r ( y 22 | W ) = (2 , 2 , 1 , 0 , 2 , 2), r ( y 23 | W ) = (2 , 2 , 1 , 1 , 2 , 2),
r ( y 31 | W ) = (2 , 2 , 2 , 2 , 0 , 1), r ( y 32 | W ) = (2 , 2 , 2 , 2 , 1 , 0),
r ( y 33 | W ) = (2 , 2 , 2 , 2 , 1 , 1), r ( x | W ) = (1 , 1 , 1 , 1 , 1 , 1) yang memberikan representasi yang berbeda. Jadi batas atas dim( G 3 ) adalah 6. Sedangkan jika kardinalitas | W | diambil 1 atau | W | = 6 − 1 = 5, maka pasti bukan himpunan pembeda. Misal diambil W = { y 11 , y 12 , y 21 , y 22 , y 31 } , dengan meng- gunakan Lemma 2.1 maka diperoleh representasi simpul-simpul graf terhadap W adalah sebagai berikut: r ( y 11 | W ) = (0 , 1 , 2 , 2 , 2), r ( y 12 | W ) = (1 , 0 , 2 , 2 , 2), r ( y 13 | W ) = (1 , 1 , 2 , 2 , 2), r ( y 21 | W ) = (2 , 2 , 0 , 1 , 2), r ( y 22 | W ) = (2 , 2 , 1 , 0 , 2), r ( y 23 | W ) = (2 , 2 , 1 , 1 , 2), r ( y 31 | W ) = (2 , 2 , 2 , 2 , 0), r ( y 32 | W ) = (2 , 2 , 2 , 2 , 1), r ( y 33 | W ) = (2 , 2 , 2 , 2 , 1), r ( x | W ) = (1 , 1 , 1 , 1 , 1), yang tidak memberikan representasi yang berbeda, karena r ( y 32 | W ) = r ( y 33 | W ) =
(2 , 2 , 2 , 2 , 1). Jadi W = { y 11 , y 12 , y 21 , y 22 , y 31 } bukan merupakan himpunan pem- beda G 3 . Dalam hal ini sesuai dengan Lemma 2.2, maka simpul pusat x tidak dimasukkan sebagai elemen W . Jadi batas bawah dim( G 3 ) adalah 6. Karena ba- tas atas dan batas bawah dim( G 3 ) adalah 4 maka diperoleh 6 ≤ dim( G 3 ) ≤ 6 atau dim( G 3 ) = 6 .
Teorema 2.5 Dimensi metrik graf K 1 + mK 3 adalah 2 m
Bukti Misalkan graf K 1 + mK 3 dengan m = 2 dinamakan graf G m . Jadi G m = K 1 + mK 3 . Untuk menemukan batas atas dim( G m ), maka ambil W = { y 11 , y 12 , y 21 , y 22 , y 31 , y 32 , ......, y m 1 , y m 2 } , untuk m = 2. Disini | W | = 2 m . Dengan menggunakan Lemma 2.1 maka diperoleh representasi setiap simpul graf terhadap W adalah sebagai berikut r ( y 11 | W ) = (0 , 1 , 2 , 2 , 2 , 2 , · · · , 2 , 2), r ( y 12 | W ) = (1 , 0 , 2 , 2 , 2 , 2 , · · · , 2 , 2), r ( y 13 | W ) = (1 , 1 , 2 , 2 , 2 , 2 , · · · , 2 , 2), r ( y 21 | W ) = (2 , 2 , 0 , 1 , 2 , 2 , · · · , 2 , 2), r ( y 22 | W ) = (2 , 2 , 1 , 0 , 2 , 2 , · · · , 2 , 2), r ( y 23 | W ) = (2 , 2 , 1 , 1 , 2 , 2 , · · · , 2 , 2), r ( y 31 | W ) = (2 , 2 , 2 , 2 , 0 , 1 , · · · , 2 , 2), r ( y 32 | W ) = (2 , 2 , 2 , 2 , 1 , 0 , · · · , 2 , 2), r ( y 33 | W ) = (2 , 2 , 2 , 2 , 1 , 1 , · · · , 2 , 2), · · · · · · · · · r ( y m 1 | W ) = (2 , 2 , 2 , 2 , 2 , 2 , · · · , 0 , 1), r ( y m 2 | W ) = (2 , 2 , 2 , 2 , 2 , 2 , · · · , 1 , 0),
22 Dimensi Metrik Pengembangan Graf Kincir Pola K 1 + mK 3
yang memberikan representasi yang berbeda. Jadi batas atas dim( G m ) adalah 2 m . Sedangkan jika kardinalitas | W | diambil 1 atau | W | = 2 m − 1, maka pasti buk- an himpunan pembeda. Misal diambil W = { y 11 , y 12 , y 21 , y 22 , y 31 , y 32 , ......, y m 1 } , untuk m ≥ 2, dengan menggunakan Lemma 2.1 maka diperoleh representasi setiap simpul graf terhadap W adalah sebagai berikut : r ( y 11 | W ) = (0 , 1 , 2 , 2 , 2 , 2 , · · · , 2), r ( y 12 | W ) = (1 , 0 , 2 , 2 , 2 , 2 , · · · , 2), r ( y 13 | W ) = (1 , 1 , 2 , 2 , 2 , 2 , · · · , 2), r ( y 21 | W ) = (2 , 2 , 0 , 1 , 2 , 2 , · · · , 2), r ( y 22 | W ) = (2 , 2 , 1 , 0 , 2 , 2 , · · · , 2), r ( y 23 | W ) = (2 , 2 , 1 , 1 , 2 , 2 , · · · , 2), r ( y 31 | W ) = (2 , 2 , 2 , 2 , 0 , 1 , · · · , 2), r ( y 32 | W ) = (2 , 2 , 2 , 2 , 1 , 0 , · · · , 2), r ( y 33 | W ) = (2 , 2 , 2 , 2 , 1 , 1 , · · · , 2), · · · · · · · · · r ( y m 1 | W ) = (2 , 2 , 2 , 2 , 2 , 2 , · · · , 0), r ( y m 2 | W ) = (2 , 2 , 2 , 2 , 2 , 2 , · · · , 1), r ( y m 3 | W ) = (2 , 2 , 2 , 2 , 2 , 2 , · · · , 1), r ( x | W ) = (1 , 1 , 1 , 1 , 1 , 1 , · · · , 1), yang tidak memberikan representasi yang berbeda. Dalam hal ini sesuai dengan Lemma 2.2, maka simpul pusat x tidak dimasukkan sebagai elemen W . Jadi batas bawah dim( G m ) adalah 2 m . Karena batas atas dan batas bawah dim( G m ) adalah 2 m maka diperoleh 2 m = dim( G m ) = 2 m atau dim( G m ) = 2 m.

## 3. Kesimpulan
Dimensi metrik pengembangan graf kincir pola K 1 + mK 3 dengan m ≥ 2 adalah 2 m .

## Pustaka
[1] G. Chartrand, L. Eroh, M. A. Johnson, and O. R. Oellerman , Resolvability In Graphs And The Metric Dimension Of Graph , Discrete Appl. Math, 105, 99-113, 2000.
[2] P.J. Slater , Leaves of Trees , Congressus Numerantium. 14:547-559, 1975.
[3] F. Harary, and R.A. Melter , On The Metric Dimension Of Graph , Ars. Combin. 2:101-195, 1990.
[4] P.J. slater , Domination and Location in Acyclic Graph , Network. 17:55-64, 1987.
[5] P. Zhang and G. Chartrand , The Theory And Application Of Resolvabi- lity In Graphs , Congressus Numerantium, 160, 47-68, 2003.
[6] Chandra, Suhud W. , Dimensi Metrik Graf Kincir , Tugas Akhir Jurusan , 2008.