MEMBANDINGKAN DIMENSI METRIK DAN DIMENSI METRIK BINTANG

Mei 2016 

PROSIDING || Seminar Nasional || Menyiapkan Pendidikan Matematika Dalam Menghadapi MEA
14 Mei 2016 || ISBN: 978-979-8559-72-3
Penerbit : Universitas PGRI Adi Buana Surabaya

Penulis 1: Ninik Mutianingsih
Penulis 2: Uzlifah Asrining Ummah

PDF

ABSTRAK

Diberikan graf terhubung  dengan himpunan simpul  dan u. Jarak antara  dan, dinotasikan, didefinisikan sebagai panjang lintasan terpendek dari  ke pada . Jika  adalah himpunan bagian dari  dan , maka representasi  terhadap  adalah   . Jika  untuk setiap  berbeda, maka  disebut sebagai himpunan pembeda (resolving set) dari . Jika simpul-simpul di  membentuk graf bintang, maka himpunan pembeda  disebut himpunan pembeda bintang (star resolving set). Dimensi metrik bintang (star metric dimension) adalah kardinalitas minimum dari himpunan pembeda bintang dan dinotasikan dengan . Penelitian ini yaitu membandingkan dimensi metrik dan dimensi metrik bintang. Hasil penelitian diperoleh perbedaan karakteristik dari dimensi metrik dan dimensi metrik bintang.

Kata kunci: dimensi metrik, dimensi metrik bintang, himpunan pembeda, himpunan pembeda bintang

 

Abstract

Let a connected graph  with vertex set  and . The distance between  and , denoted by , is defined as the length of the shortest path from  to  in . If  is a subset of  and , then the representation of  with respect to  is . If  for every  are different, then  is a resolving set of . If the vertices in  to form star graph, then resolving set    is a star resolving set. Star metric dimension is a minimum cardinality from star resolving set and denoted by . This study is comparing dimensional metric and star metric dimensions. The research to find out by differences for characteristics of metric dimensions and star metric dimensions.

 

Key words: metric dimension, star metric dimension, resolving set, star resolving set.

 

PENDAHULUAN

Latar Belakang

Teori Graf mulai dikenal pada saat seorang matematikawan bangsa Swiss, bernama Leonhard Euler melalui tulisannya yang berisi tentang upaya pemecahan masalah jembatan Konigsberg yang sangat terkenal di Eropa. berhasil mengungkapkan Misteri Teka-Teki Jembatan Konigsberg pada tahun 1736 (sekarang bernama Kaliningrad) (Ibrahim dkk, 2013). Buku pertama yang menulis tentang teori graf adalah “Therie der endlichen und unendlichen Graphen” oleh Konig pada tahun 1936. Jembatan Konigsberg ditunjukkan pada Gambar 1.1 (a), sedangkan untuk representai dari jembatan ditunjukkan pada Gmbar 1.1 (b).

(a) (b)

Gambar 1.1 (a) Jembatan Konigsberg (b) Graf yang merepresentasikan Jembatan Konigsberg (Dewi, 2013)

 

Dalam tulisannya, Euler mencoba solusi atas permasalahan bagaimana menyeberangi semua jembatan itu tepat satu kali dari tempat berangkat sampai kembali ke tempat semula. Pada permasalahan yang diungkapkan oleh Euler, simpul digunakan untuk mempresentasikan lokasi daratan yang dihubungkan oleh jembatan-jembatan. Sedangkan tiap jembatan dipresentasikan dengan sisi. Hasil dari penelitiannya tersebut adalah seseorang tidak mungkin berjalan melalui ketujuh jembatan masing-masing satu kali dan kembali ke tempat asal keberangkatan  (Dewi, 2013).

Suatu graf  terdiri atas dua himpunan, yaitu himpunan tak kosong  yang unsur-unsurnya disebut simpul (vertices) dan himpunan (mungkin kosong)  yang unsur-unsurnya disebut sisi (edges), sedemikian hingga setiap sisi  dalam  merupakan pasangan dari simpul-simpul di , yang dinotasikan (Ibrahim dkk, 2013).  adalah banyaknya simpul atau anggota  dari graf  (vertex-set) disebut order dari graf . |  adalah banyaknya sisi atau anggota  dari graf  (edge-set) disebut size dari graf .

Sebuah graf  dikatakan terhubung (connected) jika untuk sebarang dua simpul berbeda di  terdapat sebuah lintasan yang menghubungkan kedua simpul tersebut. Jarak antara simpul  dan  didefinisikan sebagai panjang lintasan terpendek dari  ke  dan dinotasikan . Diameter dari suatu graf  didefinisikan sebagai nilai    atau jarak terbesar dari sebarang dua simpul di  dan dinotasikan .

Dimensi metrik pertama kali dikenalkan oleh Harary dan Melter pada tahun 1966, kajian tentang dimensi metrik menjadi sebuah NP.complete problem artinya tidak mudah untuk mendapatkan dimensi metrik dari suatu graf bentuk tertentu. Oleh karena itu, untuk mendapatkan dimensi metrik bentuk graf tertentu ataupun kelas tertentu dilakukan analisis dari subkelas terlebih dahulu agar lebih mudah mencari dimensi metrik dari graf secara umum (Permana, 2012).

Beberapa aplikasi dari himpunan pembeda pada ilmu kimia yaitu untuk mempresentasikan senyawa kimia (Chartrand, 2000). Contoh aplikasi dari dimensi metrik lainnya adalah untuk meminimalkan pemasangan sensor kebakaran di sebuah gedung, seperti pada penelitian Wahyudi (2012).

Penelitian terdahulu tentang dimensi metrik yaitu oleh Chartrand, dkk dengan judul “Resolvability in Graph and The Metric Dimension of a Graph”  tahun 2000 dan Saputro, dkk dengan judul “The Metric Dimension of A Complete -Partite Graph and Its Products”. Selain itu ada juga penelitian dimensi metrik yang dilakukan oleh Bangkit Joko Widodo dengan judul Dimensi Metrik pada Graf Sun, Graf Helm, dan Graf Double Cones, oleh Wildan Habibi dengan judul Dimensi Metrik Graf Kincir dan oleh Johanes Arief Puromo dengan judul Dimensi Metrik Pada Pengembangan Graph Kincir. Penelitian tentang dimensi metrik bintang yaitu oleh Ninik Mutianingsih dengan judul Dimensi Metrik Bintang dari Graf Serupa Roda. Berdasarkan ulasan dari berbagai penelitian yang telah dilakukan, maka pada penelitian ini yaitu membandingkan dimensi metrik dan dimensi metrik bintang.

 

Rumusan Pertanyaan

Berdasarkan uaraian latar belakang, masalah yang dikaji adalah membandingkan dimensi metrik dan dimensi metrik bintang.

 

Tujuan Penelitian

Tujuan dari penelitian ini, yaitu memperoleh perbedaan karakteristik dari dimensi metrik dan dimesi metrik bintang.

 

Manfaat Penelitian

Manfaat dari penulisan tesis ini, yaitu sebagai acuan penelitian selanjutnya tentang graf, khususnya dimensi metrik dan dimensi metrik bintang.

 

METODE PENELITIAN

Metode penelitian untuk mendapatkan perbedaan karakteristik dari dimensi metrik dan dimensi metrik bintang adalah sebagai berikut:

  1. Studi Literatur

Pada tahap ini, dilakukan studi literatur dari buku, jurnal, dan penelitian sebelumnya mengenai dimensi metrik dan dimensi metrik bintang.

  1. Analisis

Kegiatan yang dilakukan antara lain:

  1. Mendapatkan himpunan pembeda dan himpunan pembeda bintang.
  2. Mendapatkan dimensi metrik dan dimensi metrik Pada tahap ini diperoleh batas atas dan batas bawah, jika batas atas dan batas bawah sama, maka bisa didapatkan dimensi metrik dan dimensi metrik bintang .
  3. Melakukan evaluasi terhadap analisis yang sudah dilakukan yaitu dari hasil pada tahap sebelumnya akan dbuktikan menggunakan kajian dimensi metrik bintang dan teorema dimensi metrik bintang.
  4. Penarikan simpulan dari hasil penelitian yang dilakukan.

 

HASIL PENELITIAN

Dari hasil kajian yang sudah dilakukan, diperoleh perbedaan karakteristik dari dimensi metrik dan dimensi metrik bintang yaitu pada tahap mendapatkan himpunan pembedanya.

 

PEMBAHASAN

Dimensi Metrik

Diberikan suatu graf terhubung . Misalkan dua simpul  dan  adalah simpul-simpul pada graf terhubung . Jarak antara dua simpul  dan  didefinisikan sebagai panjang lintasan terpendek dari  ke  pada  dan dinotasikan . Jika diberikan suatu himpunan terurut yaitu    dari simpul-simpul dalam graf terhubung  dan simpul  di  maka representasi dari simpul  terhadap  adalah:

Jika  untuk setiap simpul  berbeda atau jika representasi di  berbeda antara simpul satu dengan simpul yang lainnya, maka  dikatakan sebagai himpunan pembeda dari . Himpunan pembeda dengan kardinalitas) minimum disebut himpunan pembeda minimum. Kardinalitas minimum dari himpunan pembeda disebut dimensi metrik dari  dan dinotasikan  (Chartrand, dkk., 2000). Dengan demikian dimensi metrik dari graf  adalah kardinalitas minimum dari himpunan pembeda .

Sebagai contoh untuk mendapatkan dimensi metrik Sebagai contoh, diberikan sebuah graf gir  dengan  yang diberikan pada Gambar 1.2. Untuk mendapatkan dimensi metrik pada graf gir , maka harus menentukan batas atas dan batas bawah dimensi metric dari graf tersebut. Berikut akan dibahas dimenis metric dari graf gir .

Gambar 1.2 Graf Gir

Untuk mendapatkan batas atas dimensi metrik , misalkan  diperoleh representasi:

  1. Simpul-simpul bukan elemen yaitu:
  1. Simpul-simpul elemen yaitu  dan

Terlihat dari hasil diatas bahwa semua simpul yang bukan elemn  mempunyai representasi yang berbeda. Sedangkan simpul  dan  yang merupakan elemen dari  pasti memiliki representasi yang berbeda, yang membedakan adalah posisi  pada representasinya. Akan tetapi  belim tentu memiliki kardinalitas yang minimum. Oleh karena itu, dapat dikatakan sebagai batas atas dimensi metrik  atau dapat ditulis .

Untuk batas bawah,  kurang dari 2 misalkan . Chartrand dkk (2000) telah membuktikan bahwa  jika dan hanya jika . Oleh karena  bukan lintasan, maka . Oleh karena , maka dapat dikatakan .

 

Graf Bintang

Sebelum membahas tentang dimensi metrik bntang terlebih dahulu kita membahas tentang graf bintang. Graf bintang  adalah graf dengan  simpul. Memiliki satu simpul pusat  yang terhubung dengan  simpul lainnya (Darmaji, 2012). Gambar 1.3 adalah contoh dari graf bintang.

(a) (b) (c) (d)

Gambar 1.3 (a) Graf Bintang  atau graf Trivial (b) Graf Bintang (c) Graf Bintang  (d) Graf Bintang

 

Dimensi Metrik Bintang

Pengembangan dimensi metrik dapat dilakukan dengan menambahkan syarat tertentu pada himpunan pembeda . Pada penelitian ini dibahas syarat yang harus terpenuhi pada himpunan . Jika simpul-simpul di  membentuk graf bintang, maka himpunan pembeda  dinamakan himpunan pembeda bintang dan dinotasikan dengan . Himpunan pembeda bintang dengan banyak anggota minimum disebut dimensi metrik bintang dan dinotasikan  (Mutia, 2015). Dengan demikian, dimensi metrik bintang  adalah banyak anggota minimum dari himpunan pembeda bintang .

Contoh dari dimensi metrik bintang yaitu diberikan sebuah graf gir  dengan  seperti pada Gambar 1.2. Untuk mendapatkan dimensi metrik bintang pada graf gir , maka harus menetukan batas atas dan batas bawah dimensi metrik bintang dari graf tersebut. Dimensi metrik bintang mensyaratkan bahwa semua simpul elemen  harus membentuk bintang dan  memiliki kardinalitas yang minimum. Berikut akan dibahas dimensi metrik bintang pada graf gir .

Untuk mendapatkan batas atas dimensi metrik bintang , misalkan  dan ditunjukkan bahwa semua simpul di  mempunyai representasi yang berbeda terhadap . Berikut adalah hasil observasi dari graf . Simpul-simpul yang bukan elemen  adalah  dan  diperoleh representasi simpul sebagai berikut:

 

Terlihat dari hasil observasi diatas bahwa semua simpul yang bukan elemen  mempunyai representasi yang berbeda. Sedangkan simpul  yang merupakan elemen dari  memiliki representasi yang bebeda dan yang membedakan adalah posisi  pada representasi ketiga simpul tersebut, yaitu     . Jadi  merupakan himpunan pembeda bintang dengan kardinalitas  sama dengan  dan simpul-simpul elemen  membentuk graf bintang . Akan tetapi,  belum tentu memiliki kardinalitas yang minimum. Oleh karena itu, dapat dikatakan sebagai batas atas dimensi metrik bintang  atau dapat ditulis .

Untuk mendaptkan batas bawah, akan ditunjukkan bahwa jika  kurang dari , misalkan  maka pasti terdapat sedikitnya dua simpul yang mempunyai representasi sama. Perhatikan dua kasus berikut:

  1. Simpul elemen adalah simpul pusat dan simpul tepi. Jika demikian, maka terdapat sedikitnya dua simpul yang memiliki representasi sama. Tanpa mengurangi keumuman, misalkan  maka sedikitnya terdapat dua simpul yang mempunyai representasi sama, yaitu    dan  .
  2. Simpul elemen adalah simpul tepi dan simpul tambahan. Jika demikian, maka terdapat sedikitnya dua simpul yang memiliki representasi sama. Tanpa mengurangi keumuman, misalkan  maka sedikitnya  terdapat dua simpul dengan representasi yang sama, yaitu   .

Dari kasus i dan ii menunjukkan bahwa  dengan  bukan merupakan himpunan pembeda bintang. Oleh karena itu, batas bawah dimensi metrik bintang .

Oleh karena batas atas dan batas bawah dimensi metrik bintang . Jadi dimensi metrik bintang . Graf bintang yang dibentuk oleh himpunan pembeda bintang  adalah graf bintang , seperti pada Gambar 1.3.

Gambar 1.3 Graf Bintang

 

SIMPULAN

Dari hasil kajian yang sudah dilakukan dapat diambil kesimpulan bahwa perbedaan yang diperoleh yaitu pada tahap menentukan himpunan pembeda. Yaitu untuk mendapatkan dimensi metrik  kita bisa menentukan himpunan pembeda disemua titik tanpa harus membentuk graf bintang, sedangkan untuk mendapatkan dimensi metrik bintang  kita harus menentukan himpunan pembeda bintang yang terhubung dan membentuk graf bintang .

 

SARAN

Dimensi metrik dan dimensi metrik bintang untuk sebarang graf terhubung adalah masalah terbuka. Untuk mendapatkan dimensi metrik dan dimensi metrik bintang bisa  diperoleh pada sebarang graf terhubung.

 

Daftar Pustaka

Amalia, R. (2012). Dimensi Partisi pada Graf Serupa Roda dengan Penambahan Anting. Tugas Akhir, Jurusan Matematika FMIPA Institut Teknologi Sepuluh Nopember (ITS), Surabaya.

Chartrand, G., Eroh, L., Johnson, M., & Oellermann, O. (2000). Resolving in Graph and The Metric Dimension of a Graph. Discrete Applied Mathematics(105), 99-113.

Darmaji. (2012). Dimensi Partisi Graph Multipartit dan Graph Hasil Corona Dua Graph Terhubung. Disertasi, Institut Teknologi Bandung (ITB), Bandung.

Dewi, N. R. (2013). Pelabelan Total Super (a, d) Sisi Antimagic pada Graf Siput. Skripsi, FKIP Universitas Jember, Jember.

Gross, J., & Yellen, J. (2006). Graph Theory and Its Aplications (second edition). Chapman & Hall/CRC Taylor & Francis Graph, New York.

Habibi,W. (2011). Dimensi Metrik Garf Kincir. Skirpsi, Jurusan Matematika Fakultas Sains dan Teknologi Universitas Islam Negeri Maulana Malik Ibrahim, Malang.

Harraay, F., & Melter, R. (1976). On The Metric Dimension of a Graph. Ars combin. 2 1076, 191-195.

Ibrahim, N. (2013). Pengantar Kombinatorika & Teori Graf. Graha Ilmu, Yogyakarta.

Mutia, N. (2015). Dimensi Metrik Bintang dari Graf Serupa Roda. Tesis, Jurusan Matematika FMIPA Institut Teknologi Sepuluh Nopember (ITS), Surabaya.

Permana, A. (2012). Dimensi Metrik Graf Pohon Bentuk Tertentu. Jurnal Politeknik Pomits, 1(1), 1-4.

P. A. Johanes. (). Dimensi Metrik pada Pengembangan Graph Kincir dengan Pola Tugas Akhir, Jurusan Matematika FMIPA Institut Teknologi Sepuluh Nopember (ITS), Surabaya.

Slamin. (2009). DESAIN JARINGAN Pendekatan Teori Graf. Jember University Press, Jember.

Wahyudi, S. (2012). Dimensi Metrik Pengembangan Graf Kincir Pola K1+mK6 dan aplikasi Dimensi Metrik untuk Meminimumkan Pemasangan Sensor Kebakaran Sebuah Gedung. Seminar Nasional Pascasarjana (SNPS XII) ITS, Surabaya, 12 Juli 2012.

Widodo, B. (2013). Dimensi Metrik pada Graf Sun, Graf Helm, dan Graf Double Cones. Skripsi, Fakultas Matematika dan Ilmu Pengetahuan Alam Universias Sebelas Maret, Surakarta.

, , ,