MEMBANDINGKAN DIMENSI METRIK DAN DIMENSI METRIK BINTANG
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
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:
- Studi Literatur
Pada tahap ini, dilakukan studi literatur dari buku, jurnal, dan penelitian sebelumnya mengenai dimensi metrik dan dimensi metrik bintang.
- Analisis
Kegiatan yang dilakukan antara lain:
- Mendapatkan himpunan pembeda dan himpunan pembeda bintang.
- 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 .
- 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.
- 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:
- Simpul-simpul bukan elemen yaitu:
- 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:
- 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 .
- 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.