DIMENSI METRIK GRAF , , , Hindayani Jurusan Matematika UIN Maulana Malik Ibrahim Malang email:
[email protected] ABSTRACT The concept of minimum resolving set has proved to be useful and or related to a variety of fields such as Chemistry, Robotic Navigation, and Combinatorial Search and Optimization. So that, this thesis explains the metric dimension of graph , , , . Resolving set of a graph is a subset of that its distance representation is distinct to all vertices of graph . Resolving set with minimum cardinality is called minimum resolving set, and cardinal states metric dimension of and noted with . By drawing the graph, it will be found the resolving set, minimum resolving set and the metric dimension easily. After that, formulate those metric dimensions into a theorem. This research search for the metric dimension of , 2, , , and its outcome are 2 and 1 1. This research can be continued for determining the metric dimension of another graph, by changing the operation of its graph or partition graph. Keywords: distance, resolving set, metric dimension, graph PENDAHULUAN Dimensi Metrik menjadi menarik untuk dibahas karena konsep himpunan pemisah yang mempunyai kardinalitas minimum telah terbukti sangat berguna dan atau terpakai untuk pembahasan pada bidang lain seperti Kimia (berdasarkan jurnal Chartrand, dkk, Boundary vertices in Graph and Poisson and Zhang, The Metric Dimension of unicyclic graphs), Navigasi Robot dan Pencarian (berdasarkan jurnal Khuller, Raghavachari, and Rosenfeld, Landmarks in graphs) dan Optimasi Kombinasi (berdasarkan jurnal Sebo and Tannier, On Metric generator of graphs) (Hernando, dkk, 1). Dimensi Metrik adalah kardinalitas minimum himpunan pemisah (resolving set) pada . Misalkan dan adalah vertex-vertex dalam graf terhubung , maka jarak , adalah panjang lintasan terpendek antara dan pada . Untuk himpunan terurut ! , !" , !# , … , !% & dari vertex-vertex dalam graf terhubung dan vertex , representasi dari terhadap adalah '-vektor (pasangan '-tuple)
| , ! , , !" , … , , !%
Jika | untuk setiap vertex berbeda, maka disebut himpunan pemisah dari . Himpunan pemisah dengan kardinalitas minimum disebut himpunan pemisah minimum (basis metrik), dan kardinalitas dari basis metrik tersebut dinamakan dimensi metrik dari dinotasikan (Wahyudi dan Sumarno, 2010:736). Kajian tentang dimensi metrik pada graf ini merupakan kajian yang sedang marak
dibicarakan. Terbukti dengan adanya banyak jurnal dan penelitian-penelitian yang membahas tentang kajian ini, misalnya Graphs with Metric Dimension Two- A Characterization (Sudhakara dan Herman, 2009), On the Metric Dimension of Grassmann graphs (Robert dan Karen, 2010), On the Metric Dimension of Some Families of Graphs (Jose dan Mari, 2010), Dimensi Metrik Graf Kincir dengan Pola # (Wahyudi dan Sumarno, 2010), On the Metric Dimension of Corona Product Graphs (Yero, dkk, 2010) dan lain sebagainya. Semuanya membahas tentang dimensi metrik pada graf. Penelitian ini sendiri sebenarnya merupakan pengembangan dari penelitian tentang dimensi metrik graf yang telah diteliti oleh peneliti sebelumnya, yaitu Dimensi Metrik Graf Kincir dengan Pola # . Graf Kincir dinotasikan dengan ") adalah graf yang dibangun dengan menghubungkan semua vertex " dengan sebuah vertex pusat. Peneliti ingin mengembangkan penelitian ini pada graf . Oleh sebab itu, peneliti memilih “Dimensi Metrik Graf , , , ” sebagai pokok bahasan pada penelitian ini. KAJIAN TEORI Graf
Suatu graf adalah suatu pasangan himpunan , * dimana adalah himpunan tak kosong dan berhingga dari objek-objek yang disebut titik (vertex), dan * adalah himpunan dari pasangan tak terurut dari titik-titik berbeda di yang disebut sisi (edge). Himpunan titik di graf ditulis dan himpunan sisi di graf
Hindayani dilambangkan dengan * (Chartrand dan Lesniak, 1986:4). Suatu sisi + , dikatakan menghubungkan titik dan . Jika + , adalah sisi pada graf maka dan disebut terhubung langsung (adjacent) sedangkan dan + disebut terkait langsung (incident), begitu juga dengan dan + (Chartrand dan Lesniak, 1986:4). Gabungan (union) dari dan " , ditulis / " , adalah graf dengan / " dan * * / *" . Jika graf merupakan gabungan dari sebanyak 0 graf 1, 0 2, maka ditulis 01 (Abdussakir, dkk, 2009:33). Contoh:
Gambar 1. Graf 2 / 3 " / 3
Definisi operasi jumlah dari graf dan " ditulis " , adalah graf dengan himpunan vertex / " dan himpunan edge-nya * * / *" / , | , " & (Abdussakir, dkk, 2009:33). Contoh dari operasi penjumlahan pada graf dapat dilihat di bawah ini;
G1
Jenis Graf
Graf dikatakan komplit jika setiap dua titik yang berbeda saling terhubung langsung (adjacent). Graf komplit dengan order n dinyatakan dengan 9 . Dengan demikian, maka graf 9 merupakan graf beraturan 0 1 0 99< dengan order : 0 dan size ; = > " 2 Berikut ini adalah gambar graf , " , # , 3 , dan ? ;
Gambar 3. Graf Komplit , " , # , 3 , 40 ?
Graf kincir dinotasikan dengan ") adalah graf yang dibangun dengan menghubungkan semua vertex " /AABA " …A/ " dengan @A AAC "A )
sebuah vertex yang disebut vertex pusat c. Secara matematis graf kincir dituliskan dengan ") " . Vertex pusat dalam graf kincir diberi nama c, sedangkan D untuk dua vertex luar di bilah dimana 1 E E (Wahyudi dan Sumarno, 2010: 736). Berikut adalah contoh dari graf kincir dengan 3-bilah;
G2
v5
v6
v1
G1 + G2 = G
c
Gambar 2. Graf "
Jarak, Eksentrisitas, dan Diameter Graf
Jarak , antara dua titik u dan v adalah panjang minimum dari lintasan yang menghubungkan pada graf jika ada, jika tidak ada , ∞ (Harary, 1969:14). Eksentrisitas titik di graf dinotasikan dengan + adalah jarak terbesar dari ke semua titik di . Jadi, + 45 , | & Jika dan adalah titik pada sehingga + , , maka disebut titik eksentrik dari . Dengan kata lain, titik disebut titik eksentrik dari jika jarak dari ke sama dengan eksentrisitas dari . Diameter dari graf G dinotasikan dengan diam G, adalah eksentrisitas terbesar dari semua titik di G. Jadi, 4 45 + | & (Abdussakir, dkk, 2009:56-57).
166
v2 v4 v3
Gambar 4. Graf Kincir dengan 3 bilah "# v1
v5
x1
v2
v6
x2
v4
v3
Gambar 5. Graf dengan Pola " 3 "
Pengembangan dari graf kincir adalah graf " " yaitu graf kincir yang memiliki dua titik pusat. Graf dengan pola " " ini didefinisikan sebagai graf yang dibangun dengan menghubungkan semua vertex " dengan dua buah vertex yang disebut vertex pusat 5 dan 5" yang saling terhubung. Dua vertex pusat dalam graf
Volume 1 No. 4 Mei 2011
Dimensi Metrik Graf , , , tersebut diberi nama 5 dan 5" , sedangkan D untuk dua vertex luar di bilah i dimana 1 E E . Contoh dari graf dengan pola " " dengan 3bilah dapat dilihat pada Gambar 5. Dimensi Metrik Dimensi Metrik adalah kardinalitas minimum himpunan pemisah (resolving set) pada . Misalkan dan adalah vertex-vertex dalam graf terhubung , maka jarak , adalah panjang lintasan terpendek antara dan pada . Untuk himpunan terurut ! , !" , !# , … , !% & dari vertex-vertex dalam graf terhubung dan vertex , representasi dari terhadap adalah '-vektor (pasangan '-tuple)
| , ! , , !" , … , , !%
Jika | untuk setiap vertex berbeda, maka disebut himpunan pemisah dari . Himpunan pemisah dengan kardinalitas minimum disebut himpunan pemisah minimum (basis metrik), dan kardinalitas dari basis metrik tersebut dinamakan dimensi metrik dari dinotasikan (Wahyudi dan Sumarno, 2010: 736).
Lemma 1 Graf dan 1 saling lepas dan ber-order minimum 2, berlaku: dim 1 dim dim1 Bukti: Misal J adalah himpunan pemisah di 1. Diameter dari 1 paling banyak 2. Karena itu, jarak di 1 antara sebuah titik di dan sebuah anggota himpunan J K adalah 0, 1, atau 2 tergantung pada apakah di J, terhubung langsung pada sebuah anggota himpunan J K , atau yang lain. Jarak di antara sebuah titik dengan sebuah titik J K ) adalah 0, 1 atau paling tidak 2 tergantung dari apakah LMN , adalah 0,1, atau tepat 2. Cara yang sama berlaku pada graf 1, yaitu antara graf H dengan J K 1). Karena J K ) adalah himpunan pemisah untuk graf maka J K 1) adalah himpunan pemisah untuk graf 1 (Glenn, dkk. 2005:5).
Lemma 2 Misal dan 1 graf dengan order minimum 2, dan 1 saling lepas, dan misal dim dan dim1 " maka dim / 1 dim dim1 Bukti: dim , berarti mempunyai himpunan pemisah minimum yang kardinalitasnya , sebut JL , " , … , OP &. dim1 " , berarti 1 mempunyai himpunan pemisah minimum dengan kardinalitas " sebut JN , " , … , OQ &. Jurnal CAUCHY – ISSN: 2086-0382
Ambil 5, R / 1 maka ada beberapa kemungkinan: a. 5, R maka representasi jarak JL berbeda dan minimum terhadap graf / 1. dim / 1 . b. 5, R 1 maka representasi jarak JN berbeda dan minimum terhadap graf / 1. dim / 1 " . c. 5 dan R 1 maka representasi jarak antara 5 40 R adalah tak hingga. Oleh karena itu, JL 40 JN memuat anggota himpunan ∞. Jadi representasi jarak JL 40 JN yang memuat ∞ berbeda dan minimum terhadap graf / 1. dim / 1 " . d. 5 1 dan R maka representasi jarak antara 5 40 R adalah tak hingga. Oleh karena itu, JL 40 JN memuat anggota himpunan ∞. Jadi representasi jarak JL 40 JN yang memuat ∞ berbeda dan minimum terhadap graf / 1. dim / 1 " . sehingga terbukti bahwa: dim / 1 dim dim 1 Lemma 3 Jika , 2 dan @AAAAAABAAAAAAC / / / … / , )
maka:
dim dim Bukti: Akan dibuktikan dengan induksi matematika; Untuk 1, dim dim , benar Untuk 2, dim2 dim / dim dim 2 dim , S+04 Diasumsikan benar untuk ', maka dim' dim T @AAAABAAAAC / / … / U %
dim' dim @AAAAAAAAAAABAAAAAAAAAAAC dim V dim %
dim' ' dim Akan ditunjukkan benar untuk ' 1
dim' 1 dim T @AAAABAAAAC / / … / U %M
dim' 1 dim T @AAAABAAAAC / / … / / U %
Misal @AAAABAAAAC / / … / , maka %
dim' 1 dim / dim' 1 dim dim dim' 1 ' dim dim dim' 1 ' 1dim Jadi, terbukti bahwa dim dim +0W40 2.
Contoh: Diberikan graf " 2 seperti Gambar 6, akan ditunjukkan bahwa dim( " 2 ) = 2
167
Hindayani
v1
a
b
v2
Bukti:
Gambar 6. Graf " 2
Ambil J &, representasi jaraknya adalah:
|J 0 ; " |J 2
4XJ 1 ; SXJ 1 karena 4|J S|J 1 maka J & bukan himpunan pemisah dan juga bukan merupakan basis metrik. Sehingga banyaknya anggota J & tidak dapat dikatakan sebagai dimensi metrik. Oleh karena itu, ambil J yang lain. Ambil J , 4&, representasi jaraknya adalah:
|J 0,1 ; " |J 2,1
4XJ 1,0 ; SXJ 1,1 karena tidak ada satupun representasi jarak yang sama untuk J , 4&, maka J , 4& merupakan himpunan pemisah dan basis metrik. Selain itu, banyaknya anggota basis ini merupakan yang paling minimum sehingga banyaknya anggota J , 4& dapat dinyatakan sebagai dimensi metrik dari graf dengan pola " 2 . Jadi, dim( " 2 ) = 2.
Bukti: Menurut Lemma 4, diperoleh bahwa jarak titik daun terhadap pusat ( ) adalah 1, sehingga jika tidak ada titik dari yang masuk ke dalam subhimpunan S, maka representasi jaraknya akan sama untuk masing-masing titik pada
terhadap subhimpunan yang diambil. Sehingga harusnya hanya ada satu titik dari yang tidak masuk dalam subhimpunan S. Lemma 6 Untuk graf " , dengan , , maka: untuk m ≥ 2, s = 1 m dim(K 2 + mK s ) = s m untuk m, s ≥ 2 ( − 1 ) + 1 Bukti: 1. Untuk 1, 2 akan dibuktikan bahwa " . Untuk menentukan dimensi metrik dari graf " dengan 2, 1, maka dicari dulu batas atas terkecil dan batas bawah terbesar dari graf " tersebut. a. Untuk menemukan batas atas Ambil J 5 , , " , # , … , )< &. Graf " dengan pengambilan S dapat digambarkan sebagai berikut; v11
v21
v31
vm1
v41
v( m−1)1
v51
v( m −2 )1
v61 x2
v71
x1
PEMBAHASAN Dimensi Metrik Graf
Lemma 4 Untuk graf dengan , , berlaku;
0 jika u = v 1 jika u dan v pada daun atau bilah yang sama d (u, v) = atau jika u atau v adalah titik di K r 2 jika u dan v berada pada daun atau bilah yang berbeda
Bukti: Jika 40 pada satu bilah yang sama dan graf yang digunakan pada bilahnya adalah graf komplit maka jarak dari setiap titik ke titik lainnya adalah 1, karena setiap titik dihubungkan oleh satu sisi. Sedang titik yang terletak pada bilah yang berbeda akan terpisah oleh titik pusatnya sehingga jaraknya adalah 2. Dan titik pusat dengan titik yang ada pada daun atau bilahnya mempunyai jarak 1. Lemma 5 Basis metrik dari graf , dengan , 2 dan , , diperoleh dengan memasukkan sebanyak 1 titik yang ada pada ke dalam subhimpunan J. 168
v81 v151
v91
v101
v141 v131
v121
v111
Gambar 6. Graf " dengan pengambilan J
Sehingga S mempunyai representasi jarak yang berbeda terhadap setiap titik pada graf " . Dengan demikian S merupakan himpunan pemisah dari graf " yang kardinalitasnya |J| , yang diperoleh dari sebanyak 1 titik pada daun dan 1 titik pada " . J ini merupakan himpunan pemisah, tapi belum tentu merupakan sebuah basis metrik. Jika J bukan merupakan basis metrik, maka tentu saja ada J yang kardinalitasnya lebih minimum menjadi sebuah basis metrik. Jadi berlaku, batas atas dim( " E . b. Untuk menemukan batas bawah, Ambil |J| 1. Maka pasti S ini bukan himpunan pemisah, karena ada setidaknya dua titik pada graf " yang memiliki representasi jarak yang sama. Misal diambil
Volume 1 No. 4 Mei 2011
Dimensi Metrik Graf , , , J 5 , , " , # , … , )<" &, maka akan didapatkan dua titik pada graf " yang mempunyai jarak yang sama terhadap J, yaitu )< dan ) . Sehingga J pada pemisalan ini bukan merupakan himpunan pemisah. Titik yang tidak dimasukkan sebagai anggota himpunan J pada pemisalan tersebut adalah 5" , )< , ) . Artinya, ada dua titik pada dua bilah yang berbeda yang tidak masuk sebagai anggota himpunan J, padahal jika ingin mendapatkan representasi jarak yang berbeda hanya boleh ada satu titik dari keseluruhan daun yang tidak termasuk dalam anggota himpunan J. Hal inilah yang kemudian memberikan representasi jarak yang sama pada )< dan ) . Sehingga salah satu dari )< dan ) harus menjadi anggota himpunan S. Untuk memudahkan penulisan, yang masuk sebagai anggota himpunan S adalah )< , dengan asumsi bahwa adalah bilah terakhir dari " . Jadi batas bawahnya E |J| atau dapat dituliskan E dim " . Karena batas atas dan batas bawah dari dim " adalah E dim " E maka dim " . Jadi, terbukti bahwa dim " , untuk 2, 1.
2. Untuk 2, 2 akan dibuktikan bahwa dim " 1 1 Menurut Lemma 1, diperoleh: dim " dim " dim dim " 1 1 Ambil J 5 , , " , … , < , " , "" , … , " < , … , ) , )" , … , ) < &
Berikut adalah gambar graf " dengan pengambilan S; ...
v2 ( s −1)
v26 v25 v24
v1( s −1)
v33
...
v4 ( s −1) v4 s
v32v45 v44 v43
v56
x2
v13 vm ( s −1)
v66
vms
vm 5 vm 4
vm 3
...
v53 v6( s −1)
v( m −1)5 v( m −1) 4
v52
v62
v63 v( m −1)( s −1)
v( m −1)1
x3
x1
v91
v21
x2
v31 v81
v( m −1) 2
Gambar 7. Graf " dengan pengambilan J v( m −1)3
v11
v101
v61
v64
v( m −1) s vm 2 .. v( m −1) 6 .
vm1
v6 s
v65
vm1
v111
v5 s
v( m −1)1
...
v51
v54
v12
...
v42...
...
v5( s −1)
v55
x1
untuk m ≥ 2, s = 1 m + 1 dim(K 3 + mK s ) = ( s − 1)m + 2 untuk m, s ≥ 2 Bukti: 1. Untuk 2, 1, akan dibuktikan dim # 1. Untuk menentukan dimensi metrik dari graf # dengan 2, 1, maka dicari dulu batas atas terkecil dan batas bawah terbesar dari graf # tersebut. a. Untuk menemukan batas atas Ambil J 5 , 5" , , " , # , … , )< &. Sedemikian sehingga S mempunyai representasi jarak yang berbeda terhadap setiap titik pada graf # . Dengan demikian S merupakan himpunan pemisah dari graf # yang kardinalitasnya |J| 1, yaitu sebanyak 1 titik di bilah dan 2 titik yang ada di graf # . J ini merupakan himpunan pemisah, tapi belum tentu merupakan sebuah basis metrik. Jika J bukan merupakan basis metrik, maka tentu saja ada J yang kardinalitasnya lebih minimum menjadi sebuah basis metrik. Jadi berlaku, batas atas dim( # E 1. Graf # dapat dilihat pada gambar di bawah ini;
v41
v1s
v11
vm 6
vv4631
v22
v23
v15 v14
v3s
Lemma 7 Untuk graf # , dengan , , maka:
..
...
v2 s v35 v34 v21
...
v16
v3( s −1)
...
v36
|J| diperoleh dengan memasukkan sebanyak 1 titik di daun dan 1 titik graf " , maka |J| 1 1, sehingga diperoleh: dim " E 1 1 Kesimpulannya, dim " 1 1 dan dim " E 1 1 Jadi terbukti bahwa: dim " 1 1
Karena S memiliki representasi jarak yang berbeda maka S ini adalah himpunan pemisah. Misal B adalah basis metrik berlaku: |^| E |J| dim " E |J| Jurnal CAUCHY – ISSN: 2086-0382
v41
v71 v61
v51
Gambar 8. Graf # dengan pengambilan S
b. Untuk menemukan batas bawah Ambil |J| Maka pasti S ini bukan himpunan pemisah, karena ada setidaknya
169
Hindayani dua titik pada graf # yang memiliki representasi jarak yang sama. Misal diambil J 5 , 5" , , " , # , … , )<" & maka akan didapatkan dua titik pada graf # yang mempunyai jarak yang sama terhadap S yaitu )< dan ) . Sehingga S pada pemisalan ini bukan merupakan himpunan pemisah. Telah diketahui bahwa titik yang tidak termasuk dalam anggota himpunan S pada pemisalan tersebut adalah 5# , )< , ) . Artinya, ada dua titik pada dua bilah yang berbeda yang tidak masuk sebagai anggota himpunan S, padahal jika ingin mendapatkan representasi jarak yang berbeda hanya boleh ada satu titik dari keseluruhan bilah yang tidak termasuk dalam anggota himpunan S. Hal inilah yang kemudian memberikan representasi jarak yang sama pada )< dan ) . Sehingga salah satu dari )< dan ) harus menjadi anggota himpunan S. Untuk memudahkan penulisan, yang masuk sebagai anggota himpunan S adalah )< , dengan asumsi bahwa m adalah bilah terakhir dari # . Jadi batas bawahnya 1 E |J| atau dapat dituliskan 1 E dim # . Karena batas atas dan batas bawah dari dim # adalah 1 E dim # E 1 maka dim # 1. Jadi terbukti bahwa dim # 1, untuk 2, 1.
2. Untuk , 2, akan dibuktikan bahwa dim # 2 1 Menurut Lemma 1, diperoleh: dim # dim # dim dim # 2 1 Ambil J 5 , 5" , , " , … , < , " , "" , …, " < , … , ) , )" , … , ) < & Maka graf # dengan pengambilan S dapat dilihat pada gambar di bawah ini; ...
v16
...
vm 6
vm ( s −1)
vm 5
v24
v( m −1) s .. v( m −1)( s −1) v( m −1) 6 .
v( m −1)5 v( m −1) 4
v13
v11 v26 v12 v25
vm 2
vm 3
v2( s −1)
...
v23 v36
x1
x2
v46
... . v66
...
v6 s v61
v64
v62
v63
v22 v 3( s −1) ...
v56
v3 s
...
v( m −1)1
...
vm1
v111
x1
v11
x2 v101
v21
x4
...
v5( s −1) v44 v5 s
v55
v34 v32 v4 ( s −1v)33 v4 s ... v41 v43
v42
v51
v54 v53
x3
v31
v52
v41
v71
Gambar 9. Graf # dengan pengambilan S
170
v( m − 2 )1
v81
v31
v45
v6 ( s −1)
v65
Bukti: 1. Untuk 2, 1 akan dibuktikan bahwa dim 3 2. Untuk menentukan dimensi metrik dari graf 3 dengan 2, 1, maka dicari dulu batas atas terkecil dan batas bawah terbesar dari graf 3 tersebut. a. Untuk menemukan batas atas Ambil J 5 , 5" , 5# , , " , # , … , )< &. Berikut adalah gambar graf 3 dengan pengambilan S;
v91
v2 s
v35
v( m −1)1
v( m −1)3
untuk m ≥ 2, s = 1 untuk m, s ≥ 2
v21
x3
v( m −1) 2
m + 2 dim(K 4 + mK s ) = ( s − 1)m + 3
v1s
v14
vm1
vm 4
Lemma 8 Untuk graf 3 , dengan , , maka:
v1( s −1)
v15
vms
Karena S mempunyai representasi jarak yang berbeda terhadap seluruh titik pada graf # maka S adalah himpunan pemisah dan jika B adalah basis, berlaku: |^| E |J| dim # E |J| |J| diperoleh dengan memasukkan sebanyak 1 titik yang ada di daun dan 2 titik yang berada di # , maka |J| 2 1, , Sehingga diperoleh: dim # E 2 1 Kesimpulannya: dim # 2 1 dan dim # E 2 1 Jadi terbukti bahwa: dim # 2 1
v61
v51
Gambar 10. Graf 3 dengan pengambilan J
Sedemikian sehingga S mempunyai representasi jarak yang berbeda terhadap setiap titik pada graf 3 . Dengan demikian S merupakan himpunan pemisah dari graf 3 yang kardinalitasnya |J| 2, yaitu sebanyak 1 titik di bilah dan 3 titik dari graf 3 . J ini merupakan Volume 1 No. 4 Mei 2011
Dimensi Metrik Graf , , ,
Jurnal CAUCHY – ISSN: 2086-0382
v( m −1) 6 ...
vm 6
vm ( s −1)
vm5
v16
vm 4 v1( s −1) vm 3 ... v1s
v( m −1) s ... v( m −1)( s −1)
v( m −1) 5 vms v( m −1) 4 vm1 v( m −1) 3
v( m −1)1
v( m −1) 2
...
Ambil J 5 , 5" , 5# , , " , … , < , " , "" , …, " < , … , ) , )" , … , ) < & Karena S memiliki representasi jarak yang berbeda terhadap graf 3 dan misal B basis, maka berlaku: |^| E |J| dim 3 E |J| |J| diperoleh dengan memasukkan sebanyak 1 titik di daun dan 3 titik di 3 , maka|J| 3 1.
Sehingga diperoleh: dim 3 E 3 1. Kesimpulannya: dim 3 3 1 dan dim 3 E 3 1 Jadi terbukti bahwa: dim 3 3 1 Graf 3 dengan pengambilan S dapat digambarkan sebagai berikut;
vm 2
x2
x1
v11
v15 v14 v26 v25
v21 v36 v23
v56
...
v5( s −1) v5 s
v55
x3 v12 v13 v 2 ( s −1) ... v2 s
v24
...
himpunan pemisah, tapi belum tentu merupakan sebuah basis metrik. Jika J bukan merupakan basis metrik, maka tentu saja ada J yang kardinalitasnya lebih minimum menjadi sebuah basis metrik. Jadi berlaku, batas atas dim 3 E 2. b. Untuk menemukan batas bawah Ambil |J| 1 Maka pasti S ini bukan himpunan pemisah, karena ada setidaknya dua titik pada graf 3 yang memiliki representasi jarak yang sama. Misal diambil J 5 , 5" , 5# , , " , # , … , )<" & maka akan didapatkan dua titik pada graf 3 yang mempunyai jarak yang sama terhadap S yaitu )< dan ) . Sehingga S pada pemisalan ini bukan merupakan himpunan pemisah. Telah diketahui bahwa titik yang tidak termasuk dalam anggota himpunan S pada pemisalan tersebut adalah 53 , )< , ) . Artinya, ada dua titik pada dua bilah yang berbeda yang tidak masuk sebagai anggota himpunan S, padahal jika ingin mendapatkan representasi jarak yang berbeda hanya boleh ada satu titik dari keseluruhan bilah yang tidak termasuk dalam anggota himpunan S. Hal inilah yang kemudian memberikan representasi jarak yang sama pada )< dan ) . Sehingga salah satu dari )< dan ) harus menjadi anggota himpunan S. Untuk memudahkan penulisan, yang masuk sebagai anggota himpunan S adalah )< , dengan asumsi bahwa m adalah bilah terakhir dari 3 . Jadi batas bawahnya 2 E |J| atau dapat dituliskan 2 E dim 3 . Karena batas atas dan batas bawah dari dim 3 adalah 2 E dim 3 E 2 maka dim 3 2. Jadi terbukti bahwa dim 3 2, untuk 2, 1. 2. Untuk , 2, akan dibuktikan bahwa dim 3 3 1 Dari Lemma 1 diperoleh: dim 3 dim 3 dim dim 3 3 1
v22
x4
...
v3( s −1)
v35 v34 v33
v46 v v3 s 45 v44 v31
v51
v54 v4 ( s −1) v53 ... v4 s v41
v43
v42
v32
Gambar 11. Graf 3 dengan pengambilan S
Lemma 9 Untuk graf ? , dengan , , maka: untuk m ≥ 2, s = 1 m + 3 dim(K 5 + mK s ) = untuk m, s ≥ 2 ( s − 1)m + 4 Bukti: 1. Untuk 2, 1 akan dibuktikan bahwa dim ? 3. Untuk menentukan dimensi metrik dari graf ? dengan 2, 1, maka dicari dulu batas atas terkecil dan batas bawah terbesar dari graf ? tersebut. a. Untuk menemukan batas atas Ambil J 5 , 5" , 5# , 53 , , " , # , … , )< &, sedemikian sehingga S mempunyai representasi jarak yang berbeda terhadap setiap titik pada graf ? . Dengan demikian S merupakan himpunan pemisah dari graf ? yang kardinalitasnya |J| 3 yaitu, sebanyak 1 titik dari graf yang ada di bilah dan 4 titik dari graf ? . J ini merupakan himpunan pemisah, tapi belum tentu merupakan sebuah basis metrik. Jika J bukan merupakan basis metrik, maka tentu saja ada J yang kardinalitasnya lebih 171
v52
Hindayani
v( m −1)1
..
..
..
vm1 v11
x1
x5 v101
v21
x2
x4
v91
x3
v31
v81
v41
v71
v51
v61
Gambar 12. Graf ? dengan pengambilan S
b. Untuk menemukan batas bawah Ambil |J| 2. Maka pasti S ini bukan himpunan pemisah, karena ada setidaknya dua titik pada graf ? yang memiliki representasi jarak yang sama. Misal diambil J 5 , 5" , 5# , 53 , , " , # , … , )<" & maka akan didapatkan dua titik pada graf ? yang mempunyai jarak yang sama terhadap S yaitu )< dan ) . Sehingga S pada pemisalan ini bukan merupakan himpunan pemisah. Telah diketahui bahwa titik yang tidak termasuk dalam anggota himpunan S pada pemisalan tersebut adalah 5? , )< , ) . Artinya, ada dua titik pada dua bilah yang berbeda yang tidak masuk sebagai anggota himpunan S, padahal jika ingin mendapatkan representasi jarak yang berbeda hanya boleh ada satu titik dari keseluruhan bilah yang tidak termasuk dalam anggota himpunan S. Hal inilah yang kemudian memberikan representasi jarak yang sama pada )< dan ) . Sehingga salah satu dari )< dan ) harus menjadi anggota himpunan S. Untuk memudahkan penulisan, yang masuk sebagai anggota himpunan S adalah )< , dengan asumsi bahwa m adalah bilah terakhir dari ? . Jadi batas bawahnya 3 E |J| atau dapat dituliskan 3 E dim ? . Karena batas atas dan batas bawah dari dim ? adalah 3 E dim ? E 3 maka dim ? 3. Jadi terbukti bahwa dim ? 3, untuk 2, 1. 2. Untuk , 2, akan dibuktikan bahwa dim ? 4 1 172
v( m −1) s .. v( m −1)( s −1) v( m −1) 6 . v( m −1) 5
v( m −1)1
v( m −1) 4
...
v( m − 2 )1
Dari Lemma 1, diperoleh: dim ? dim ? dim dim ? 4 1 Ambil J 5 , 5" , 5# , 53 , , " , … , < , " , "" , … , " < , … , ) , )" , … , ) < &. Karena representasi jarak S terhadap graf ? berbeda, maka S adalah himpunan pemisah dan misal B basis metrik maka berlaku: |^| E |J| dim ? E |J| |J| diperoleh dengan memasukkan sebanyak 1 titik pada daun dan 4 titik di ? , maka |J| 4 1. Sehingga diperoleh: dim ? E 4 1, Kesimpulannya: dim ? 4 1 dan dim ? E 4 1 Jadi terbukti bahwa: dim ? 4 1 Graf ? dapat digambarkan sebagai berikut;
v( m −1) 2 vm 6 vm 5
v( m −1) 3
...
minimum menjadi sebuah basis metrik. Jadi berlaku, batas atas dim( ? E 3. Graf ? dengan pengambilan S dapat digambarkan sebagai berikut;
v56
...
v51 v53
v46
x4
...
v41 ... v36
v43
v42
v3 s
v24
v31
v34 v33
v1s
v11
v2 ( s −1)
v26 v25
v3( s −1)
v35
v1( s −1)
v14
x3
v4 s
v44
...
v15
x2
v4 ( s −1)
v45
vm 2
vm 3 v16
v52 ...
vms vm1
x1
x5
v5 s
v54
vm ( s −1)
vm 4
v5( s −1)
v55
...
v13
v12
v2 s v21
v23
v22
v32
Gambar 13. Graf ? dengan pengambilan S
Teorema Untuk graf , dengan , , , berlaku: m + (r − 2) untuk m ≥ 2, s = 1 dim(K r + mK s ) = ( s − 1)m + (r − 1) untuk m, s ≥ 2 Bukti: 1. Untuk 2, 1, akan dibuktikan bahwa 2. Untuk menentukan dimensi metrik dari graf dengan 2, 1, maka dicari dulu batas atas terkecil dan batas bawah terbesar dari graf tersebut. Volume 1 No. 4 Mei 2011
Dimensi Metrik Graf , , , a. Untuk menemukan batas atas Ambil J 5 , 5" , 5# , 53 , 5? , … , 5 < , , " , # , … , )< &, sedemikian sehingga S mempunyai representasi jarak yang berbeda terhadap setiap titik pada graf . Dengan demikian S merupakan himpunan yang pemisah dari graf |J| 2, kardinalitasnya yaitu sebanyak 1 titik pada bilah dan 1 titik pada graf . J ini merupakan himpunan pemisah, tapi belum tentu merupakan sebuah basis metrik. Jika J bukan merupakan basis metrik, maka tentu saja ada J yang kardinalitasnya lebih minimum menjadi sebuah basis metrik. Jadi berlaku, batas atas dim( E 2. Graf dengan pengambilan J adalah sebagai berikut; v11
vm1
v21
v( m −1)1
v31 x1
xr
v41 x2 x3
...
... ...
xr −1
x6
v51
x4
x5
)< dan ) harus menjadi anggota himpunan S. Untuk memudahkan penulisan, yang masuk sebagai anggota himpunan S adalah )< , dengan asumsi bahwa m adalah bilah terakhir dari . Jadi batas bawahnya 2 E |J| atau dapat dituliskan 2 E dim . Karena batas atas dan batas bawah dari dim adalah 2 E dim E 2, maka dim 2. Jadi terbukti bahwa dim 2, untuk 2, 1. 2. Untuk , 2, akan dibuktikan bahwa dim 1 1 Dari Lemma 1, Lemma 2, Lemma 6, Lemma 7, Lemma 8, dan Lemma 9, diperoleh: dim dim dim dim 1 1 Ambil J 5 , 5" , … , 5 < , , " , … , < , " , "" , … , " < , … , ) , )" , … , ) < &. Graf dengan pengambilan S dapat digambarkan sebagai berikut; v( m −1)( s −1) .. v( m −1) 6 . v( m −1) s
v61
v( m −1)1
v( m −1)5
v111
v71 v81
b. Untuk menemukan batas bawah Ambil |J| 3. Maka pasti S ini bukan himpunan pemisah, karena ada setidaknya dua titik pada graf yang memiliki representasi jarak yang sama. Misal diambil J 5 , 5" , 5# , 53 , 5? , … , 5 < , , " , # , … , )<" &, maka akan didapatkan dua titik pada graf yang mempunyai jarak yang sama terhadap S yaitu )< dan ) . Sehingga S pada pemisalan ini bukan merupakan himpunan pemisah. Telah diketahui bahwa titik yang tidak termasuk dalam anggota himpunan S pada pemisalan tersebut adalah 5 , )< , ) . Artinya, ada dua titik pada dua bilah yang berbeda yang tidak masuk sebagai anggota himpunan S, padahal jika ingin mendapatkan representasi jarak yang berbeda hanya boleh ada satu titik dari keseluruhan bilah yang tidak termasuk dalam anggota himpunan S. Hal inilah yang kemudian memberikan representasi jarak yang sama pada )< dan ) . Sehingga salah satu dari Jurnal CAUCHY – ISSN: 2086-0382
xr −1
v46
...
v4 ( s −1) v4 s
v45
v43
vm 3
x2
x5
v16
x3
x4 ...
vms
v3( s −1) v26 v31 v
v33
v32
v24
v1( s −1) v1s v11
v14
v2 s
v13
v12
v21
25
v34
...
vm 2
v15
v2 ( s −1) ...
v3s
v35
vm1
x1
v42
v36
vm 6
vm ( s −1)
vm 4
xr
x6
v41
v44
...
vm 5
..
Gambar 14. Graf dengan pengambilan S
...
v91
v( m −1) 2
v( m −1)3
. . .
v101
v( m −1) 4
v23
v22
Gambar 15. Graf dengan pengambilan S
S mempunyai representasi jarak yang berbeda terhadap graf , sehingga S merupakan himpunan pemisah. Misal B adalah basis metrik, maka berlaku: |^| E |J| dim E |J| Karena |J| 1 1, maka: dim E 1 1 Sehingga diperoleh: dim 1 1 dan 173
Hindayani dim 1 1 Jadi terbukti bahwa: dim 1 1 PENUTUP Dari pembahasan tentang dimensi metrik graf ini didapatkan kesimpulan bahwa untuk , , , berlaku: untuk m ≥ 2, s = 1 m + (r − 2) dim(K r + mK s ) = (s − 1)m + (r − 1) untuk m, s ≥ 2
Jadi, graf memiliki dimensi masingmasing sesuai dengan , , yang diinginkan. DAFTAR PUSTAKA [1] Abdussakir, dkk. 2009. Teori Graf. Malang: UIN Malang Press. [2] Hernando, Carmen, dkk. On The Metric Dimension of Some Families of Graphs. preprint. [3] Chartrand, Garry dan Linda Lesniak. 1986. Graph and Digraphs. California: Pacific Graw. [4] Glenn, dkk. 2005. Bounds on The Metric and Partition Dimension of a Graph. University of Alaska. [5] Harary, Frank. 1969. Graph Theory. America: Addison-Wesley Publishing Company Inc [6] Wahyudi, Suhud dan Sumarno. 2010. Dimensi Metrik pada Graf Kincir dengan Pola # . FMIPA ITS, 731-744.
174
Volume 1 No. 4 Mei 2011
