Jln. Perintis Kemerdekaan, Makassar, Indonesia, Kode Pos BASIS FOR DETERMINING THE WHEEL GRAPH

PENETUAN BASIS BAGI GRAF RODA Nur Ulfah Dwiyanti Obed1*), Nurdin2), Amir Kamal Amir3) 1 Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Hasanuddin Jln. Perintis Kemerdekaan, Makassar, Indonesia, Kode Pos 90245

BASIS FOR DETERMINING THE WHEEL GRAPH Nur Ulfah Dwiyanti Obed1*), Nurdin2), Amir Kamal Amir3) 1 Departement of Mathematic, Faculty of Mathematics and Natural Sciences, Hasanuddin University Perintis Kemerdekaan Street, Makassar, Indonesia, Post Code 90245

ABSTRAK Misalkan 𝐺 = (𝑉, 𝐸) suatu graf terhubung dan S adalah suatu himpunan bagian dari 𝑉. Himpunan S disebut himpunan penentu (resolving set) pada G jika untuk setiap titik pada G memiliki representasi jarak yang berbeda terhadap S. Himpunan penentu dengan banyak anggota (kardinalitas) minimum disebut himpunan penentu minimum (resolving set minimum) atau basis dari G dan kardinalitas himpunan tersebut menyatakan dimensi metrik (metric dimension) graf G, dinotasikan dengan dim(G). Pada skripsi ini telah diketahui dimensi metrik untuk graf roda 𝑊𝑛 . Berdasarkan hasil pembahasan diperoleh basis-basis S bagi graf roda 𝑊𝑛 untuk 𝑛 ≥ 7 adalah 1. 𝑆 = 𝑣1 , 𝑣3 , 𝑣5𝑖+2 , 𝑣5𝑖+4 |𝑖 = 1, 2, ⋯ , 2𝑘 − 1 , dimana 𝑛 = 10𝑘 − 1, 𝑛 = 10𝑘 dan 𝑛 = 10𝑘 + 1 untuk suatu 𝑘 bilangan asli. 2. 𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 , 𝑣12 , dimana 𝑛 = 12 dan 𝑛 = 13, 𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 , 𝑣10.𝑗 +2 , 𝑣10.𝑗 +4 , 𝑣10.𝑗 +7 , 𝑣10.𝑗 +9 , ⋯ , 𝑣10.𝑘+2 , dimana 𝑛 = 10𝑘 + 2 dan 𝑛 = 10𝑘 + 3, untuk 𝑘 ≥ 2. 3. 𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 , 𝑣12 , 𝑣14 , dimana 𝑛 = 14, 𝑛 = 15 dan 𝑛 = 16, 𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 , 𝑣10.𝑗 +2 , 𝑣10.𝑗 +4 , 𝑣10.𝑗 +7 , 𝑣10.𝑗 +9 , ⋯ , 𝑣10.𝑘+2 , 𝑣10.𝑘+4 , dimana 𝑛 = 10𝑘 + 4, 𝑛 = 10𝑘 + 5 dan 𝑛 = 10𝑘 + 6, untuk 𝑘 ≥ 2. 4. 𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 , 𝑣12 , 𝑣14 , 𝑣17 , dimana 𝑛 = 17 dan 𝑛 = 18, 𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 ,𝑣10.𝑗 +2 , 𝑣10.𝑗 +4 , 𝑣10.𝑗 +7 , 𝑣10.𝑗 +9 , ⋯ , 𝑣10.𝑘+2 , 𝑣10.𝑘+4 , 𝑣10.𝑘+7 , dimana 𝑛 = 10𝑘 + 7 dan 𝑛 = 10𝑘 + 8, untuk 𝑘 ≥ 2. Kata Kunci : Dimensi Metrik, Graf Roda, Himpunan Penentu.

ABSTRACT Let 𝐺 = (𝑉, 𝐸) be a connected graph and S be a vertices subset of 𝑉. The set S is called resolving set for G if the representation of every vertex on G with respect to S are distinct. A resolving set containing a minimum number of vertices is called a basis for G. The metric dimension of G, denoted by 𝑑𝑖𝑚(𝐺), is the cardinality of basis. In this thesis we have been known the metrics dimension of wheel graph 𝑊𝑛 . Based on the discussion of the results we obtained that bases S for wheels graph 𝑊𝑛 for 𝑛 ≥ 7 is 1. 𝑆 = 𝑣1 , 𝑣3 , 𝑣5𝑖+2 , 𝑣5𝑖+4 |𝑖 = 1, 2, ⋯ , 2𝑘 − 1 , where 𝑛 = 10𝑘 − 1, 𝑛 = 10𝑘 and 𝑛 = 10𝑘 + 1 for some 𝑘 natural number. 2. 𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 , 𝑣12 , where 𝑛 = 12 and 𝑛 = 13, 𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 , 𝑣10.𝑗 +2 , 𝑣10.𝑗 +4 , 𝑣10.𝑗 +7 , 𝑣10.𝑗 +9 , ⋯ , 𝑣10.𝑘+2 , where 𝑛 = 10𝑘 + 2 and 𝑛 = 10𝑘 + 3, for 𝑘 ≥ 2.

*Penulis Koresponden E-mail : [email protected]

𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 , 𝑣12 , 𝑣14 , where 𝑛 = 14, 𝑛 = 15 and 𝑛 = 16, 𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 , 𝑣10.𝑗 +2 , 𝑣10.𝑗 +4 , 𝑣10.𝑗 +7 , 𝑣10.𝑗 +9 , ⋯ , 𝑣10.𝑘+2 , 𝑣10.𝑘+4 ,where 𝑛 = 10𝑘 + 4, 𝑛 = 10𝑘 + 5 and 𝑛 = 10𝑘 + 6, for 𝑘 ≥ 2. 4. 𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 , 𝑣12 , 𝑣14 , 𝑣17 , where 𝑛 = 17 and 𝑛 = 18, 𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 ,𝑣10.𝑗 +2 , 𝑣10.𝑗 +4 , 𝑣10.𝑗 +7 , 𝑣10.𝑗 +9 , ⋯ , 𝑣10.𝑘+2 , 𝑣10.𝑘+4 , 𝑣10.𝑘+7 , where 𝑛 = 10𝑘 + 7 and 𝑛 = 10𝑘 + 8, for 𝑘 ≥ 2. Keyword : Metric Dimension, Wheel Graph, Resolving Set. 3.

1.

Pendahuluan Cabang matematika yang saat ini semakin berkembang dan menarik salah satunya adalah teori graf. Teori graf merupakan teori yang unik dan memiliki banyak penerapan. Kesederhanaan pokok bahasan yang dipelajari merupakan salah satu keunikan dari teori graf karena dapat disajikan sebagai titik (vertex) dan sisi (edge). Teori graf dan aplikasinya tidak hanya dijumpai dalam cabang-cabang matematika, tetapi juga dalam disiplin-disiplin ilmiah seperti teknik, ilmu komputer, riset operasi, dan manajemen sains. Dimensi metrik pertama kali dikenalkan oleh Harary dan Melter pada tahun 1966. Kajian tentang dimensi metrik menjadi sebuah compleks problem artinya tidak mudah untuk mendapatkan dimensi metrik bentuk graf tertentu ataupun kelas tertentu dengan melakukan analisis dari subkelas dahulu agar lebih mudah mencari dimensi metrik dari graf secara umum.

2.

Tinjauan Pustaka 2.1 Graf dan Terminologi Graf Definisi 2.1.1 Graf 𝐺 = 𝑉, 𝐸 adalah pasangan himpunan 𝑉, 𝐸 dimana 𝑉 adalah himpunan tidak kosong yang disebut himpunan titik, dan 𝐸 adalah himpunan pasangan tidak terurut titik-titik di 𝐺 yang disebut himpunan sisi pada 𝐺. Definisi 2.1.2 Misal G adalah graf dengan 𝑢, 𝑣 ∈ 𝑉 𝐺 . Jika 𝑒 = 𝑢𝑣 adalah sisi pada 𝐺 maka 𝑢 dan 𝑣 disebut bertetangga (adjacent), sedangkan 𝑢 disebut terkait dengan 𝑒, demikian pula sebaliknya yaitu 𝑒 terkait dengan 𝑣. Definisi 2.1.3

Banyaknya anggota himpunan titik pada suatu graf 𝐺 disebut order, sedangkan

banyaknya anggota himpunan sisinya disebut ukuran 𝐺. Definisi 2.1.4 Derajat (degree) titik v pada graf G,dinotasikan deg(v), adalah banyaknya sisi yang terkait dengan v. Minimum derajat titik pada G dinotasikan dengan 𝛿(𝐺), sedangkan maksimum derajat titik pada G dinotasikan dengan ∆(𝐺). Definisi 2.1.5 Graf 𝐺 disebut graf terhubung jika terdapat lintasan untuk setiap dua titik di 𝐺. Definisi 2.1.6 Jarak (distance) antara dua titik u dan v pada G adalah panjang lintasan terpendek yang menghubungkan antara u dan v, dinotasikan dengan 𝑑(𝑢, 𝑣). G. Chartrand dan Zhang P,2002. 2.2

Graf Roda

Definisi 2.2.1 Graf lingkaran (cycle) dengan n titik, dilambangkan dengan 𝐶𝑛 , adalah graf terhubung yang semua titiknya berderajat 2.

*Penulis Koresponden E-mail : [email protected]

Definisi 2.2.2 Graf roda (wheel) adalah graf yang dikonstruksi dari graf Cn dinotasikan dengan Wn, dengan menambahkan satu titik v dan n sisi sedemikian sehingga v bertetangga dengan semua titik di Cn. 𝒱2 𝒱3

𝒱1

𝒱0

𝒱8

𝒱4

Gambar 2.5 Graf Roda W𝒱85 𝒱7 2.3 Dimensi Metrik Definisi 2.3.1 Misal S = 𝑣1 , 𝑣2 , … , 𝑣𝑛

𝒱6 ⊆ 𝑉. Representasi titik 𝒱 ∈ 𝑉 relatif terhadap 𝑆 adalah

barisan berurutan 𝑛-tuple yaitu 𝑟 𝑣 𝑆 = 𝑑 𝑣, 𝑥1 , … … , 𝑑 𝑣, 𝑥𝑛 . Definisi 2.3.2 Himpunan 𝑆 disebut himpunan penentu pada graf 𝐺 jika untuk setiap 𝒰, 𝒱 ∈ 𝑉, 𝒰 ≠ 𝒱 pada graf 𝐺 berlaku 𝑟(𝒰│𝑆) ≠ 𝑟(𝒱│𝑆). Definisi 2.3.3 Basis pada graf 𝐺 adalah himpunan penentu yang memiliki jumlah anggota minimum. Definisi 2.3.4 Dimensi metrik pada graf 𝐺, dinotasikan dengan dim(G), adalah banyaknya anggota basis 𝑆 di graf 𝐺. 3.

Hasil dan Pembahasan Teorema 1 Misalkan 𝑊𝑛 adalah graf roda, maka 𝑑𝑖𝑚 𝑊𝑛 =

2𝑛+2 5

untuk

𝑛 ≥ 7, dengan himpunan penentu pada Lemma 5, Lemma 6, Lemma 7, Lemma 8 dan Lemma 9. Bukti : Perhatikan bahwa 𝑆 = 4𝑘 pada graf roda 𝑊𝑛 dimana 𝑛 = 10𝑘 untuk suatu 𝑘 bilangan asli dengan 𝑆 = 𝑣1 , 𝑣3 , 𝑣5𝑖+2 , 𝑣5𝑖+4 |𝑖 = 1, 2, ⋯ , 2𝑘 − 1 . Berdasarkan Teorema A bahwa 𝑑𝑖𝑚 𝑊𝑛 =

2𝑛+2 5

untuk 𝑛 ≥ 7.

Selanjutnya akan dibuktikan bahwa 𝑆 = 4𝑘 pada graf roda 𝑊𝑛 dimana 𝑛 = 10𝑘 untuk suatu 𝑘 bilangan asli, maka 𝑑𝑖𝑚 𝑊10𝑘 =

2 10𝑘 +2 5

= 4𝑘 +

1 5

= 4𝑘.

Karena 𝑆 himpunan penentu dengan 𝑆 = 4𝑘, maka 𝑆 himpunan penentu minimum. Karena basis dari 𝑊𝑛 adalah 𝑆, dengan demikian dapat disimpulkan bahwa a.

𝑆 = 𝑣1 , 𝑣3 , 𝑣5𝑖+2 , 𝑣5𝑖+4 |𝑖 = 1, 2, ⋯ , 2𝑘 − 1 ,

dimana 𝑛 = 10𝑘 − 1, 𝑛 = 10𝑘 dan 𝑛 = 10𝑘 − 1 untuk suatu 𝑘 bilangan asli pada Lemma 5 dan Lemma 6 adalah himpunan penentu minimum.

*Penulis Koresponden E-mail : [email protected]

b.

𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 , 𝑣12 , dimana 𝑛 = 12 dan 𝑛 = 13 pada Lemma 7 adalah himpunan penentu minimum. 𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 , 𝑣10.𝑗 +2 , 𝑣10.𝑗 +4 , 𝑣10.𝑗 +7 , 𝑣10.𝑗 +9 , ⋯ , 𝑣10.𝑘+2 , dimana 𝑛 = 10𝑘 + 2 dan 𝑛 = 10𝑘 + 3, untuk 𝑘 ≥ 2 pada Lemma 7 adalah himpunan penentu minimum.

c.

𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 , 𝑣12 , 𝑣14 , dimana 𝑛 = 14, 𝑛 = 15 dan 𝑛 = 16 pada Lemma 8 adalah himpunan penentu minimum. 𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 , 𝑣10.𝑗 +2 , 𝑣10.𝑗 +4 , 𝑣10.𝑗 +7 , 𝑣10.𝑗 +9 , ⋯ , 𝑣10.𝑘+2 , 𝑣10.𝑘+4 , dimana 𝑛 = 10𝑘 + 4, 𝑛 = 10𝑘 + 5 dan 𝑛 = 10𝑘 + 6, untuk 𝑘 ≥ 2 pada Lemma 8 adalah himpunan penentu minimum.

d.

𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 , 𝑣12 , 𝑣14 , 𝑣17 , dimana 𝑛 = 17 dan 𝑛 = 18 pada Lemma 9 adalah himpunan penentu minimum. 𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 ,𝑣10.𝑗 +2 , 𝑣10.𝑗 +4 , 𝑣10.𝑗 +7 , 𝑣10.𝑗 +9 , ⋯ , 𝑣10.𝑘+2 , 𝑣10.𝑘+4 , 𝑣10.𝑘+7 , dimana 𝑛 = 10𝑘 + 7 dan 𝑛 = 10𝑘 + 8, untuk 𝑘 ≥ 2 pada Lemma 9 adalah himpunan penentu ∎

minimum. 4.

Penutup

4.1 Kesimpulan Berdasarkan hasil penelitian, diperoleh basis-basis 𝑆 sebagai berikut : 1.

𝑆 = 𝑣1 , 𝑣3 , 𝑣5𝑖+2 , 𝑣5𝑖+4 |𝑖 = 1, 2, ⋯ , 2𝑘 − 1 , dimana 𝑛 = 10𝑘 − 1, 𝑛 = 10𝑘 dan 𝑛 = 10𝑘 + 1 untuk suatu 𝑘 bilangan asli.

2.

𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 , 𝑣12 , dimana 𝑛 = 12 dan 𝑛 = 13, 𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 , 𝑣10.𝑗 +2 , 𝑣10.𝑗 +4 , 𝑣10.𝑗 +7 , 𝑣10.𝑗 +9 , ⋯ , 𝑣10.𝑘+2 , dimana 𝑛 = 10𝑘 + 2 dan 𝑛 = 10𝑘 + 3, untuk 𝑘 ≥ 2.

3.

𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 , 𝑣12 , 𝑣14 , dimana 𝑛 = 14, 𝑛 = 15 dan 𝑛 = 16, 𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 , 𝑣10.𝑗 +2 , 𝑣10.𝑗 +4 , 𝑣10.𝑗 +7 , 𝑣10.𝑗 +9 , ⋯ , 𝑣10.𝑘+2 , 𝑣10.𝑘+4 ,dimana

𝑛 = 10𝑘 + 4,

𝑛=

10𝑘 + 5 dan 𝑛 = 10𝑘 + 6, untuk 𝑘 ≥ 2. 4.

𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 , 𝑣12 , 𝑣14 , 𝑣17 , dimana 𝑛 = 17 dan 𝑛 = 18, 𝑆 = 𝑣1 , 𝑣3 , 𝑣7 , 𝑣9 ,𝑣10.𝑗 +2 , 𝑣10.𝑗 +4 , 𝑣10.𝑗 +7 , 𝑣10.𝑗 +9 , ⋯ , 𝑣10.𝑘+2 , 𝑣10.𝑘+4 , 𝑣10.𝑘+7 , dimana 𝑛 = 10𝑘 + 7 dan 𝑛 = 10𝑘 + 8, untuk 𝑘 ≥ 2.

4.2 Saran Untuk melanjutkan pembahasan mengenai skripsi ini, penulis menyarankan untuk meninjau menentukan basis graf roda dengan menggunakan program.

DAFTAR PUSTAKA [1] Buczkowski, P., Chartrand, G., Poisson, C., dan Zhang, P. 2003: On k-Dimensional Graphs and Their Bases, Period. Math. Hungar. 46(1), 9 – 15. [2] Chartrand, G. dan Zhang, P.2002: Introduction To Graph Teory, Mc Graw International Edition. [3] Harary, F. dan Melter, R. 1976: On the Metric Dimension of a Graph, Ars Combin. 2, 191 – 195.

*Penulis Koresponden E-mail : [email protected]

[4] Hindayani. 2011: Dimensi Metrik Graf 𝐾𝑟 + 𝑚𝐾𝑠 , 𝑚, 𝑟, 𝑠 ∈ 𝑁, UIN Maulana Malik Ibrahim Malang. [5] Kurniati HM, Ary Herlina. 2012: Dimensi Metrik Graf Gir, Universitas Hasanuddin Makassar. [6] Mudjiati,Titik. 2011. Dimensi Metrik Graf Kincir Dengan Daun Bervariasi, Institut Teknologi Surabaya. [7] Suardi, Nurfuaidah. 2012: Dimensi Metrik untuk Graf Halin Bintang Ganda, Universitas Hasanuddin Makassar.

*Penulis Koresponden E-mail : [email protected]