J. Math. and Its Appl. E-ISSN: 2579-8936 P-ISSN: 1829-605X Vol. 15, No. 1, Maret 2018, 71-77

## Dimensi Metrik Graf Amal( )
Tri Utomo 1 , Novian Riskiana Dewi 2
1,2 Program Studi Matematika, Jurusan Sains, ITERA Lampung Selatan Indonesia e-mail : 1 tri.utomo@ma.itera.ac.id

## Abstrak
Salah  satu  topik  dalam  teori  graf  yang  menarik  sebagian  besar  para  peneliti  adalah tentang  dimensi  metrik,  yaitu  kardinalitas  minimum resolving  set yang  mungkin  dapat dibentuk  dari  suatu  graf.  Pada  paper  ini  dibahas  tentang  dimensi  metrik  graf  Amal( ), yaitu graf yang dibangun dari topologi jaringan komputer. Graf ini  dibentuk berdasarkan buah  jaringan  komputer  topologi  mesh  yang  dihubungkan  menjadi  satu-kesatuan  jaringan komputer  yang  lebih  besar  dengan  menggunakan  topologi  mesh.  Dengan  kata  lain,   buah graf  komplit dioperasikan  amalgamasi  dengan  graf  Komplit .  Graf  ini  dinotasikan sebagai  Amal( )  dengan
dan .  Dengan  menentukan  batas  bawah  dan  batas atas  kardinalitas resolving  set dari  Amal( )  didapatkan  bahwa  dimensi  metrik  dari  graf Amal( ) adalah
.
Kata Kunci : Resolving Set, Dimensi Metrik, Topologi Jaringan Komputer

## Abstract
One of the topic in graph theory that attract the researcher is metric dimension, that is the  minimum  cardinality  of  resolving  set  of  graph.  This  study  aim  to  find  the  metric dimension of Amal( ), that is the graph that obtained from computer network topology. This graph is   of computer network topology of mesh are merged being unity more bigger network  using  mesh  topology.  In  other  word,   of  complete  graph is  amalgamation  by complete graph . It is denoted by Amal( ), where and . By finding lower
bound  and  upper  bound  of  cardinality its  resolving  set  of  that  graphs, it  conclude  that  the metric dimension of Amal( ) is
.
Keywords: Resolving Set, Metric Dimension, Computer Network Topology

## 1    Pendahuluan
Graf  adalah  himpunan  simpul  dan  sisi  yang  berhingga,  didefinisikan  sebagai , dengan adalah  himpunan  tak  kosong  simpul  dan adalah  himpunan  sisi.  Setiap  sisi menghubungkan  satu  simpul  dengan  simpul  yang  lain,  dan  setiap  simpul  dapat  mempunyai banyak  sisi  yang  menghubungkannya  dengan  simpul  lainnya.  Beberapa  permasalahan  pada disiplin  ilmu  dapat  dimodelkan  dalam  bentuk  graf.  Sebagai  contoh  pada  [1]  graf  digunakan sebagai  model  dari  kompetisi  antara  spesies  berbeda  pada  ekologi  lingkungan,  siapa  yang mempengaruhi atau siapa yang berada pada himpunan kelas yang sama. Selain itu pada  [2] [3],
graf  digunakan  untuk  mengilustrasikan  jaringan  lalu  lintas,  jaringan  komputer  [4]  [5],  dan sebagainya.  Pada  paper  ini  graf  digunakan  sebagai  representasi  dari  jaringan  komputer,  yaitu dengan  mengilustrasikan  komputer  sebagai  simpul  dan  jaringan  yang  menghubungkan  antar komputer sebagai sisi. Ada beberapa jenis topologi jaringan komputer, diantaranya topologi bus, ring, star, dan mesh. Pada penelitian ini dibahas tentang dimensi metrik suatu graf yang dibangun dari  kombinasi  topologi  jaringan  komputer  tersebut.  Yang  dimaksudkan  kombinasi  dalam penelitian  ini  yaitu  beberapa  jaringan  komputer  (sub  jaringan  komputer)  digabungkan  menjadi satu-kesatuan membentuk jaringan komputer yang lebih besar (jaringan komputer utama), dalam hal ini topologi mesh dengan topologi mesh, perhatikan Gambar 1.
Gambar 1 Ilustrasi 6 buah jaringan komputer bertopologi mesh (sub jaringan) dihubungkan menjadi satu-kesatuan membentuk jaringan komputer yang lebih besar menggunakan topologi mesh
Permasalahan  dimensi  metrik  pertama  kali  dikenalkan  oleh  Harary  dan  Melter  [6],  selain itu diteliti juga oleh Slater [7]. Misal adalah graf terhubung sederhana, dan , jarak  antara dua simpul   dan   dinotasikan sebagai
didefinisikan sebagai  panjang jalur terpendek  yang  menghubungkan  keduanya.  Misal
himpunan  simpul terurut  subset  ,  dan ,  representasi   terhadap dinotasikan  sebagai adalah  -
Sub Jaringan 2 Sub Jaringan 1
Sub Jaringan 5 Sub Jaringan 3 Sub Jaringan 6 Jaringan Utama Sub Jaringan 4
tupel . dinamakan resolving  set jika  setiap  simpul  pada mempunyai representasi yang berbeda terhadap . Resolving set dengan kardinalitas minimum disebut  sebagai resolving  set minimum,  sedangkan  kardinalitas  dari resolving  set ini  disebut sebagai dimensi metrik dari graf  , dinotasikan sebagai Dim( ).
Dimensi  metrik  merupakan  salah  satu  topik  pada  teori  graf  yang  menarik  bagi  para peneliti, beberapa hasi telah didapatkan, misalnya [6] mendapatkan hasil sebagai berikut:
Teorema 1 [6] Misal   graf terhubung dengan orde
, maka
1. Dim( ) jika dan hanya jika 2. Dim( ) jika dan hanya jika
3. Untuk
, maka Dim( )
Sedangkan  [8]  membahas  dimensi  metrik  graf  yang  dihasilkan  dari  operasi  perkalian lexicographic, selain itu [9] membahas dimensi metrik lokal dari graf yang memiliki -pendant, [10] membahas dimensi metrik pada beberapa graf reguler infinit, [11] membahas graf-graf yang memuat sikel  dan  yang  memiliki  dimensi  metrik  konstan,  dan  [12]  membahas  dimensi  metrik  dari pengembangan graf kincir.

## Gambar 2 Metodologi Penelitian

## 2    Metode Penelitian
Dalam mengerjakan penelitian ini, dilakukan kontruksi graf berdasarkan topologi jaringan komputer.  Setelah  itu  dilakukan  observasi  mengenai  dimensi  metrik  dari  graf  yang  telah
Penelitian yang dilakukan
Jaringan Komputer yang Lebih Kompleks (beberapa jaringan komputer dihubungkan menjadi satu-kesatuan membentuk jaringan komputer yang lebih besar
didapatkan  pada  tahapan  sebelumnya.  Dalam  menentukan  dimensi  metrik  ini  diperlukan  batas bawah dan batas atas dimensi metrik dari graf tersebut.
Berdasarkan  bagan pada Gambar 2,  langkah-langkah  yang dilakukan dalam  penelitian ini dapat dirumuskan sebagai berikut:
1. Membentuk suatu graf berdasarkan topologi jaringan komputer
2. Menentukan batas bawah dimensi metrik.
3. Menentukan batas atas dimensi metrik.
4. Menentukan  nilai  eksak  dimensi  metrik  bedasarkan  batas  bawah  dan  batas  atas  dimensi metrik.

## 3    Hasil dan Pembahasan
3.1. Amalgamasi  -Graf Komplit
Graf  yang  dibahas  pada  paper  ini  terinspirasi  dari  topologi  jaringan  komputer,  dengan mengilustrasikan  komputer  sebagai  simpul,  dan  jaringan  yang  menghubungkan  komputer sebagai sisi. Ada beberapa jenis topologi pada jaringan komputer, yaitu topologi bus, ring, star, dan mesh, sama halnya dengan graf garis, cycle, graf bintang, and graf komplit pada teori graf. Pada  paper  ini  dibentuk  suatu  jaringan  komputer  yang  lebih  besar  dengan  mengkombinasikan topologi-topologi  tersebut,  dalam  hal  ini  topologi  mesh  dengan  topologi  mesh,  topologi  mesh pada  masing-masing  sub  jaringan  komputer  dan  topologi  mesh  pada  jaringan  komputer  utama, perhatikan Gambar 1 .
Gambar 3 Contoh graf Amal( ), yaitu 5 buah graf diamalgamasikan dengan
graf
Simpul Tepi
Simpul Tengah
Kombinasi  dari  topologi  mesh  dengan  topologi  mesh  mempunyai  arti    bahwa  terdapat beberapa  jaringan  komputer  bertopologi  mesh  (sub  jaringan  komputer)  dihubungkan  menjadi satu-kesatuan  membentuk  jaringan  komputer  yang  lebih  besar  (jaringan  komputer  utama) menggunakan topologi mesh. Ini mengilustrasikan bahwa,   buah graf komplit dioperasikan amalgamasi  dengan  graf  komplit ,  dengan  cara  menyatukan  simpul  server  pada  setiap tepat  satu  dengan  tiap  simpul  pada
.  Graf  ini  kemudian  dinotasikan  sebagai  Amal( ), dengan dan ,  perhatikan Gambar 3 .  Untuk  keperluan  selanjutnya,  didefinisikan  dua jenis  simpul  pada  Amal( ),  yaitu  simpul  tepi  dan  simpul  tengah.  Simpul  tepi mengilustrasikan  komputer  client  pada  setiap  topologi  mesh .  Sedangkan  simpul  tengah mengilustrasikan  komputer  server  pada  setiap  topologi  mesh yang  disatukan  dengan
komputer pada topologi mesh .
3.2. Dimensi Metrik Amal( )
Misal   adalah  Amal( )  seperti  yang  sudah  didefinisikan  sebelumnya,  maka  graf adalah graf terhubung sederhana.
Teorema  2 Batas  bawah:  Misal   adalah  Amal( )  dengan dan ,  maka
Dim( )
Bukti: Misal   adalah Amal( ) dengan
dan , adalah resolving set, dan merupakan  simpul  tepi  dari   dengan and .  Simpul  tepi dengan
pada pertama,  mempunyai  jarak  yang  sama  terhadap simpul lainya pada  . Ini mengartikan bahwa simpul-simpul tersebut memiliki representasi yang sama terhadap , maka salah satu dari simpul-simpul ini haruslah berada di luar , atau dapat ditulis  sebagai .  Dengan  cara  yang  sama  untuk  simpul-simpul  tepi  pada lainya, dapat  ditunjukkan  bahwa .  Akibatnya, haruslah  setidaknya  memuat
, dan ini jelas bawah where and merupakan simpul-simpul yang berbeda. sehingga , dan . Teorema  3 Batas  atas:  Misal adalah  Amal( )  dengan
dan ,  maka Dim( ) Bukti: Misal adalah Amal( ) dengan dan , dengan ,  dan adalah  simpul  tepi  dari .  Karena dengan dan merupakan  simpul-simpul  yang
berbeda,  maka
.  selanjutnya  akan  ditunjukkan  bahwa merupakan  resolving set.
Pertama, representasi dari simpul tengah terhadap akan selalu 2, kecuali simpul tengah yang  adjacent  dengan  simpul  tepi  pada  .  Representasi  simpul  tengah  yang  adjacent  dengan simpul  tepi  pada   terhadap adalah  1.  Ini  mengakibatkan  representasi  simpul  tengah  akan berbeda pada peletakan urutan 1 dan 2. Kedua, simpul tepi pada dengan dan mempunyai representasi terhadap sama dengan 0 dengan dirinya sendiri, dan  akan  selalu  1  dengan  simpul  tepi  pada   yang  adjacent  dengan  simpul  tengah  yang  sama, dan  selainnya  akan  selalu  mempunyai  representasi  terhadap sama  dengan  3.  Ini mengakibatkan representasi simpul tepi akan berbeda pada peletakan urutan 0,1, dan 3.  Karena representasi setiap simpul  pada   terhadap berbeda, dapat  disimpulkan bahwa merupakan resolving set.
Dari penjelasan sebelumnya dikatakan bahwa minimal memuat dengan , dan ,  jadi  tidak  mungkin  dibentuk resolving  set sehingga . Sehingga dapat disimpulkan bahwa merukan minimum resolving set yang dapat dibentuk.
Teorema  4 Dimensi  metrik:  Misal   adalah  Amal( )  dengan dan ,  maka Dim( )
Bukti: Misal   adalah  Amal( )  dengan dan
,  dari  penjelasan  diatas  kita ketahui  bahwa  batas  bawah  dimensi  metrik   adalah ,  dinotasikan  sebagai  Dim( ) ,  dan  batas  atas  dimensi  metrik   adalah
,  dinotasikan  sebagai  Dim( )
. Maka dapat disimpulkan bahwa dimensi metrik   adalah .

## 4    Simpulan
Berdasarkan  penjelasan  di  atas  dapat  disimpulkan  bahwa,  dimensi  metrik  Amal(
) dengan dan , dinotasikan sebagai Dim(Amal( )) adalah .

## 5 Daftar Pustaka
[1] S. Allesina dan J. M. Levine, “A Competitive Network Theory of Species Diversity,” PNAS, vol. 108, pp. 5638-5642, 4 February 2010.
[2]   A. Benjamin, G. Chartrand and P. Zhang, The Fascinating World of Graph Theory, United
Kingdom: Princeton University Press, 2015.
[3]   R. Jiang, Y. H. Wu, W. X. Wang dan Q. S. Wu, “Urban Traffic from The Perspective of Dual Graph,” The European Physical Journal B, pp. 127-133, May 2008.
[4]   B. Baranidharan dan B. Shanthi, “A New Graph Theory based Routing Protocol for Wireless Sensor Networks,” International Journal on Applications of Graph Theory in Wireless Ad Hoc Networks and Sensor Networks, vol. 3, no. 4, pp. 15-26, 2011.
[5]   M. N. Shah, “Implementation of Graph Theory in Computer Networking to Find an Efficient Routing Algorithm,” International Journal of Innovative Research in Computer and Communication Engineering, vol. 4, no. 1, pp. 12-20, 2016.
[6]   G. Chartrand, L. Eroh, M. A. Jhnson dan O. R. Oellermann, “Resolvability in Graphs and The Metric Dimension of a Graph,” Discrete Applied Mathematics, vol. 105, pp. 99-113, 2000.
[7]   P. J. Slater, “Leaves of Trees,” Proc. 6th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, vol. 14, pp. 549-559, 1975.
[8]   S. W. Saputro, R. Simanjuntak, S. Uttunggadewa, H. Assiyatun, E. T. Baskoro, A. N. M. Salman dan M. Baca, “The Metric Dimension of The Lexicographic Product of Graph,” Discrete Mathematics, vol. 313, pp. 1045-1051, 2013.
[9]   Rinurwati, Slamin dan H. Suprajitno, “On (Local) Metric Dimension of Graphs with m- Pendant Points,” International Conference on Mathematics Education, Theory and Application, vol. 855, 2017.
[10]  I. Tomescu dan M. Imran, “On Metric and Partition Dimensions of Some Infinite Regular Graphs,” Bull. Math. Soc. Sci. Math. Roumanie , no. 4, pp. 461-472, 2009.
[11]  M. Ali, G. Ali, U. Ali dan M. T. Rahim, “On Cycle Related Graphs with Constant Metric Dimension,” Open Journal of Discrete Mathematics, vol. 2, pp. 21-23, 2012.
[12]  S. Wahyudi, Sumarno dan Suharmadi, “Dimensi Metrik Pengembangan Graf Kincir Pola K1+mK3,” Limits: Journal of Mathematics and Its Applications, vol. 8, no. 2, pp. 17-22, 2011.