J. Math. and Its Appl. E-ISSN: 2579-8936 P-ISSN: 1829-605X Vol. 15, No. 2, Nopember 2018, 89-96

## Aplikasi Dimensi Metrik Untuk Meminimalkan Pemasangan Sensor Kebakaran Sebuah Gedung

## Suhud Wahyudi
Departemen Matematika ITS Surabaya Indonesia e - mail : suhud@matematika.its.ac.id
Abstrak
Diberikan himpunan terurut
} , , , { 2 1 k w w w W   ) ( G V  dan untuk setiap vertex ) ( G V v  ,  representasi  dari v terhadap W adalah k  –  tuple )) , ( , ), , ( ), , ( ( ) | ( 2 1 k w v d w v d w v d W v r   , dimana d ( x , y )    merepresentasikan jarak  antara vertex x dan y . J ika ) | ( W v r untuk  setiap vertex ) ( G V v  berbeda, maka W disebut himpunan resolving dari ) ( G V . Himpunan resolving dengan kardinalitas minimum disebut himpunan resolving minimum, dan kardinalitas tersebut dinamakan dimensi metrik dari G dinotasikan dengan ) dim( G .
Pada  penelitian  ini  dibahas  salah  satu  aplikasi  dimensi  metrik  graf  yaitu  untuk meminimalkan  pemasangan  sensor  kebakaran  sebuah  gedung.  Dalam  suatu  gedung,  ruangan dapat  direpresentasikan  sebagai vertex dan  dinding  atau  lantai  antara  ruangan  yang  satu  dengan lainnya  sebagai edge dari  suatu  graf G sehingga  dapat  dibuat  graf  terhubung  yang  mewakili gedung  tersebut.  Studi  kasus  yang  diambil  adalah sebuah  gedung  yang  mempunyai  12 ruangan. Dari  analisa  yang  dilakukan,  sensor  kebakaran  yang  harus  dipasang  di  gedung  hanya  di  tiga ruangan saja.
Kata kunci : himpunan resolving, kardinalitas minimum , dimensi metrik, sensor kebakaran.

## Abstract
Given  an  ordered  set } , , , { 2 1 k w w w W   ) ( G V  and  a  vertex ) ( G V v  ,  the representation of v with respect to W is the k – tuple )) , ( , ), , ( ), , ( ( ) | ( 2 1 k w v d w v d w v d W v r   , where d ( x , y )  represents  the  distance  between  the  vertexs x and y .    If ) | ( W v r have  distinct representations,  then W is  called  the  resoving  set  of ) ( G V .  The  resolving  set  with  minimum cardinality is called minimum  resolving set, and the cardinality is called the metric dimension of G denoted by ) dim( G
In  the  research  we  examine  one  application  of  the  metric  dimension  of  graph  that  is  to minimize  the  installation  of  a  fire  sensor  in  a  building.  In  a  building,  rooms  building  can  be interpreted as a vertex and a wall or floor associated with the room interpreted as an  edge wich connecting  the  vertexs.  Case  study  is  taken  in  building  wich  has  12  rooms.  From  the  analysis carried out, the sensor should be installed in the building just in three rooms only.
Keyword : resolving set, minimum cardinality, metric dimension, fire sensor.

## 1.  Pendahuluan
Teori  graf  pertama  kali  diperkenalkan  oleh  Leonhard  Euler  pada  tahun  1736  ketika mendiskusikan  tentang  persoalan  yang  terjadi  di  kota  Kaliningrad  Rusia,  yaitu  bagaimana caranya  agar  seseorang  dapat  menyeberang  ke  semua  jembatan  tanpa  harus  melewati  satu
jembatan  lebih  dari  satu  kali.  Publikasi  dari  masalah  ini  dan  usulan  solusinya  dikenal  sebagai masalah  dari  teori  graf.    Sejak  saat  itu,  teori  graf  terus  berkembang  seiring  dengan  penemuan- penemuan  baru  yang  terkait  dengan  graf.  Saat  ini  teori  graf  telah  dapat  memberikan  kerangka dasar  bagi  banyak  persoalan  yang  berhubungan  dengan  struktur  dan  hubungan  antara  suatu obyek diskrit dalam bentuk apapun. Pemakaian teori graf telah dapat diterapkan dalam berbagai cabang ilmu pengetahuan seperti ilmu komputer, ekonomi, psikologi, ilmu sosial, genetika, riset operasional.  Misalnya  pada  [1]  menggunakan  graf  untuk  memodelkan  kompetisi  antar  spesies yang    berbeda  pada  suatu  ekologi  lingkungan,  dengan  menganalisa  siapa  yang  mempengaruhi atau  siapa  yang  berada  pada  himpunan  kelas  yang  sama,  [2]  menggunakan  graf  untuk mengilustrasikan jaringan lalu lintas, dan lain lain. Pada paper ini diaplikasikan konsep dimensi metrik  graf  tersebut  untuk  meminimumkan  jumlah  pemasangan  sensor  kebakaran  pada  suatu gedung.
Belum  diketahui  secara  spesifik  kapan  bahasan  dimensi  partisi  ini  pertama  kali  ada.  Ide dimensi  metrik  muncul  dari  himpunan resolving (dan  himpunan resolving minimum)  yang diperkenalkan oleh Slater [3] pada tahun 1975. Slater mengutarakan konsep himpunan locating untuk menyatakan himpunan resolving seperti yang dikenal saat ini. Ia menyatakan kardinalitas minimum  himpunan resolving graf G sebagai location  number dinotasikan  dengan  loc( G ). Kemudian  Melter  dan  Harary  [4]  pada  tahun  1976  mengutarakan  konsep  dimensi  metrik  suatu graf seperti  yang dikenal saat ini. Dimensi metrik adalah kardinalitas minimum  dari himpunan resolving.  Sampai  saat  ini,  dimensi  metrik  terus  dipelajari  dan  dikembangkan  diantaranya  oleh G .  Cartrand  [5]  yang  mendapatkan  hasil  bahwa  untuk  graf  terhubung G dengan  orde 𝑛 ≥ 2 maka dim( G ) = 1 jika dan hanya jika 𝐺 = 𝑃 𝑛 , Rinurwati dkk.[6] membahas dimensi metrik dan dimensi  metrik  lokal  dari  graf  yang  memiliki m -  pendant,  Suhud  Wahyudi  dkk.[7]  membahas dimensi metrik Pengembangan Graf Kincir Pola K 1 +mK 3 , dan lain lain.
Misalkan 𝐺(𝑉, 𝐸) adalah  graf  tak  berarah  dan  terhubung  dengan  ( V ,  E)  berturut  –  turut menunjukkan (banyaknya vertex , banyaknya edge ) di G , dan 𝑢, 𝑣 𝜖 𝑉 , jarak antara dua vertex u dan v di G , ) , ( v u d didefinisikan  sebagai  panjang  lintasan  terpendek  diantara  keduanya.  Untuk himpunan terurut } , , , { 2 1 k w w w W   dari vertex-vertex dalam graf terhubung G dan untuk setiap vertex ) ( G V v  , representasi dari v terhadap W adalah k - tuple
)) , ( , ), , ( ), , ( ( ) | ( 2 1 k w v d w v d w v d W v r   .
Jika ) | ( W v r untuk  setiap vertex ) ( G V v  berbeda,  maka W disebut  himpunan resolving dari ) ( G V . Himpunan resolving dengan kardinalitas minimum disebut himpunan resolving minimum, dan kardinalitas tersebut dinamakan dimensi metrik dari G dinotasikan dengan ) dim( G [8].
[4] menunjukkan bahwa untuk setiap pasangan integer n,k dengan 1 ≤ k ≤ n − 1, terdapat suatu graf dimensi k orde n. Kemudian [5] menunjukkan bahwa selain graf path P n , dimensi metriknya minimal 2.
Contoh  berikut  diberikan  untuk  memberikan  gambaran  mendapatkan  himpunan resolving, himpunan resolving minimum dan dimensi metrik dari sebuah graf terhubung.
Diberikan graf terhubung G dengan 5 vertex dan 6 edge seperti ditunjukkan pada Gambar 1 , dan akan ditentukan himpunan resolving dari graf G tersebut.
Gambar 1 Graf terhubung dengan 5 vertex dan 6 edge
Pembahasan :
Misalkan ) ( 1 u W  .    Representasi vertex-vertex di  graf G terhadap 1 W adalah ) 0 ( ) | ( 1  W u r , ) 1 ( ) | ( 1  W v r , ) 1 ( ) | ( 1  W y r , ) 2 ( ) | ( 1  W x r , ) 2 ( ) | ( 1  W z r .
Karena 1 ) | ( ) | ( 1 1   W y r W v r dan 2 ) | ( ) | ( 1 1   W z r W x r maka 1 W bukan  himpunan resolving dari  graf G .  Kemudian  misalkan } , , { 2 y v u W  .  Maka  representasi vertex-vertex di  graf  G terhadap 2 W adalah ) 1 , 1 , 0 ( ) | ( 2  W u r , ) 2 , 0 , 1 ( ) | ( 2  W v r , ) 0 , 2 , 1 ( ) | ( 2  W y r , ) 1 , 1 , 2 ( ) | ( 2  W x r , ) 2 , 1 , 2 ( ) | ( 2  W z r .  Karena  representasi vertex-vertex di  graf G terhadap 2 W berbeda,  maka 2 W adalah  himpunan resolving dari G .  Akan  tetapi 2 W bukan  himpunan resolving minimum  dari ) ( G V , karena 3 W berikut  mempunyai  kardinalitas  lebih  kecil  dari 2 W .  Misalkan } , { 3 y u W  . Maka  representasi vertex-vertex di  graf G terhadap 3 W adalah ) 1 , 0 ( ) | ( 3  W u r , ) 2 , 1 ( ) | ( 3  W v r , ) 2 , 2 ( ) | ( 3  W z r , ) 0 , 1 ( ) | ( 3  W y r ) 1 , 2 ( ) | ( 3  W x r .  Karena  representasi vertex-vertex di  graf G terhadap 3 W berbeda,  maka 3 W adalah  himpunan resolving dari ) ( G V . 3 W adalah  himpunan resolving minimum  dari ) ( G V karena  tidak  ada  lagi  himpunan resolving yang  kardinalitasnya lebih kecil dari 2. Jadi graf  diatas mempunyai dimensi 2 atau 2 ) dim(  G .
2.  Metode Penelitian
u v x y z
Penelitian  ini  bertujuan  untuk  mengembangkan  aplikasi  teori  graf.  Dalam  hal  ini  adalah dimensi  metrik  graf  yang  di  aplikasikan  untuk  meminimumkan  banyaknya  sensor  kebakaran yang  harus  di  pasang  dalam  sutu  gedung.  Dimensi  metrik  graf  yang  dimaksud  disini  adalah dimensi metrik dari graf yang terhubung.
Dalam  pengerjaan  penelitian  ini,  pertama  kali  dilakukan  analisa  dimensi  metrik  graf  secara umum,  kemudian  mengkonstruksi  graf  yang  sesuai  untuk  sebuah  gedung  yang  diberikan.  Dari graf yang terbentuk tersebut ditentukan himpunan resolving dan dimensi metriknya.

## 3.  Hasil dan Pembahasan
Dalam suatu gedung , ruangan dapat direpresentasikan sebagai vertex dan dinding atau lantai antara ruangan  yang satu  dengan lainnya sebagai edge dari suatu  graf G sehingga dapat  dibuat graf  terhubung  yang  mewakili  gedung  tersebut.  Dalam  hal  ini  dimensi  metrik  dari  graf  sebuah gedung yang diperoleh dari himpunan resolving minimum dapat digunakan sebagai dasar untuk meminimalkan  pemasangan  sensor  kebakaran  sebuah  gedung.  Dengan  memilih  salah  satu  dari himpunan resolving minimum  dapat  ditentukan  ruangan  mana  saja  yang  harus  diberi  sensor untuk mendeteksi asal adanya api sehingga dapat meminimalkan pemasangan sensor kebakaran sebuah gedung.
Misalkan  sebuah  gedung  yang  memiliki  12  ruangan  dengan  masing-masing  ruang  diberi label  nama 𝑅 1 , 𝑅 2 , 𝑅 3 , 𝑅 4 , 𝑅 5 , 𝑅 6 , 𝑅 7 , 𝑅 8 , 𝑅 9 , 𝑅 10 , 𝑅 11 , 𝑅 12 dengan  hubungan  antara  ruang  satu dengan yang lainnya seperti ditunjukkan pada Gambar 2. Jarak antara ruang 𝑅 3 dan 𝑅 4 adalah 1, 𝑅 2 dan 𝑅 3 adalah  1, 𝑅 2 dan 𝑅 5 adalah  2, 𝑅 2 dan 𝑅 12 adalah  1, 𝑅 2 dan 𝑅 8 adalah  3  dan seterusnya. Sedangkan jarak antara suatu ruang dengan dirinya sendiri adalah 0. Misalkan akan dipasang  sensor  deteksi  adanya  api  dengan  warna  merah  pada  salah  satu  ruang.  Jika  ada  api disuatu  ruang,  maka  sensor  akan  mendeteksi  jarak  dari  ruang  adanya  api  dengan  ruang  yang dipasang  sensor  merah.  Sebagai  contoh,  misalkan  sensor  diletakkan  di 𝑅 2 .  Jika  api  muncul  di 𝑅 3 , maka sensor mengidentifikasikan bahwa api muncul dari ruang yang berjarak 1 dari 𝑅 2 , dan ruang yang berjarak 1 dari 𝑅 2 ada 4 yaitu 𝑅 1 , 𝑅 3 , 𝑅 11 dan 𝑅 12 sehingga tidak dapat diketahui dengan pasti api berasal dari ruang yang mana. Sebaliknya apabila semua ruang dipasang sensor maka  dengan  pasti  dapat  diketahui  asal  adanya  api.  Akan  tetapi  hal  ini  bukanlah  yang diharapkan.  Persoalannya  adalah  minimal  berapa  banyak  sensor  yang  dibutuhkan  dan  ruang mana  saja  yang  harus  dipasang  sensor  sehingga  apabila  muncul  api  dari  ruang  manapun  akan dapat  diketahui  dengan  tepat  sumber  adanya  api.  Dengan  demikian  kebakaran  yang  lebih  luas dapat dicegah. Berikut adalah analisa yang dilakukan untuk gedung Gambar 2.
Gambar 2 Sebuah gedung dengan 12 ruangan Graf  yang  mewakili  Gambar  2 adalah  graf  terhubung G dengan  12 vertex dan  30 edge seperti yang diperlihatkan pada Gambar 3.

## Gambar 3 Representasi graf G Gambar 2
Karena graf G pada Gambar 3 bukan graf Path , maka dimensi metriknya 2  [5]. Sehingga penyelidikan  himpunan resolving untuk  Graf G Gambar  3 dimulai  dari  himpunan  terurut W dengan  anggota  2 vertex di G. Dalam  kasus  ini  ada  sebanyak  66  macam  himpunan  terurut W . Dari  penyelidikan  yang  dilakukan,  tidak  terdapat  himpunan  terurut W yang  menghasilkan huimpunan resolving ,  sehingga  dimensi  metrik  graf G Gambar  3 adalah ≠  2.  Dalam  hal  ini, sebagai  contoh  diambil  3  kasus  saja.  Misalnya  diambil 𝑊 1 = (𝑅 1 , 𝑅 2 ) , 𝑊 2 = (𝑅 2 , 𝑅 3 ) , 𝑊 3 =
R 12 R 4 R 1 R 3 R 2 R 11 R 9 R 5 R 6 R 10 R 8 R 7
(𝑅 6 , 𝑅 11 ) .    Representasi vertex-vertex di  graf G pada  Gambar  3 terhadap 𝑊 1 , 𝑊 2 , 𝑊 3 adalah sebagai berikut :
1. 𝑊 1 = (𝑅 1 , 𝑅 2 )
Representasi vertex-vertex di graf G terhadap 𝑊 1 adalah 𝑟(𝑅 1 |𝑊 1 ) = (0,1) , 𝑟(𝑅 2 |𝑊 1 ) = (1,0) , 𝑟(𝑅 3 |𝑊 1 ) = (1,1) , 𝑟(𝑅 4 |𝑊 1 ) = (1,2) , 𝑟(𝑅 5 |𝑊 1 ) = (1,2) , 𝑟(𝑅 6 |𝑊 1 ) = (2,3) , 𝑟(𝑅 7 |𝑊 1 ) = (2,3) , 𝑟(𝑅 8 |𝑊 1 ) = (2,3) , 𝑟(𝑅 9 |𝑊 1 ) = (1,2) , 𝑟(𝑅 10 |𝑊 1 ) = (2,2) , 𝑟(𝑅 11 |𝑊 1 ) = (1,1) , 𝑟(𝑅 12 |𝑊 1 ) = (2,1) .
Disini  terlihat  bahwa 𝑟(𝑅 3 |𝑊 1 ) = (𝑅 11 |𝑊 1 ) = (1,1) , 𝑟(𝑅 4 |𝑊 1 ) = (𝑅 5 |𝑊 1 ) = 𝑟(𝑅 9 |𝑊 1 ) = (1,2) , dan 𝑟(𝑅 6 |𝑊 1 ) = 𝑟(𝑅 7 |𝑊 1 ) = 𝑟(𝑅 8 |𝑊 1 ) = (2,3) . Jadi 𝑊 1 = (𝑅 1 , 𝑅 2 ) bukan himpunan resolving .
2. 𝑊 2 = (𝑅 2 , 𝑅 3 )
Representasi vertex-vertex di graf G terhadap 𝑊 2 adalah 𝑟(𝑅 1 |𝑊 2 ) = (1,1) , 𝑟(𝑅 2 |𝑊 2 ) = (0,1) , 𝑟(𝑅 3 |𝑊 2 ) = (1,0) , 𝑟(𝑅 4 |𝑊 2 ) = (2,2) , 𝑟(𝑅 5 |𝑊 2 ) = (2,2) , 𝑟(𝑅 6 |𝑊 2 ) = (3,2) , 𝑟(𝑅 7 |𝑊 2 ) = (3,3) , 𝑟(𝑅 8 |𝑊 2 ) = (3,2) , 𝑟(𝑅 9 |𝑊 2 ) = (2,1) , 𝑟(𝑅 10 |𝑊 2 ) = (2,1) , 𝑟(𝑅 11 |𝑊 2 ) = (1,1) , 𝑟(𝑅 12 |𝑊 2 ) = (1,2) .
Disini  terlihat  bahwa 𝑟(𝑅 1 |𝑊 2 ) =  𝑟(𝑅 11 |𝑊 2 ) = (1,1) , 𝑟(𝑅 4 |𝑊 2 ) = 𝑟(𝑅 5 |𝑊 2 ) = (2,2) , 𝑟(𝑅 6 |𝑊 2 ) = 𝑟(𝑅 8 |𝑊 2 ) = (3,2) ,  dan 𝑟(𝑅 9 |𝑊 2 ) = 𝑟(𝑅 10 |𝑊 2 ) = (2,1) .  Jadi 𝑊 2 = (𝑅 2 , 𝑅 3 ) bukan himpunan resolving .
3. 𝑊 3 = (𝑅 6 , 𝑅 11 )
Representasi vertex-vertex di graf G terhadap 𝑊 3 adalah 𝑟(𝑅 1 |𝑊 3 ) = (2,1) , 𝑟(𝑅 2 |𝑊 3 ) = (3,1) , 𝑟(𝑅 3 |𝑊 3 ) = (2,1) , 𝑟(𝑅 4 |𝑊 3 ) = (1,2) , 𝑟(𝑅 5 |𝑊 3 ) = (1,1) , 𝑟(𝑅 6 |𝑊 3 ) = (0,2) , 𝑟(𝑅 7 |𝑊 3 ) = (1,3) , 𝑟(𝑅 8 |𝑊 3 ) = (1,2) , 𝑟(𝑅 9 |𝑊 3 ) = (1,1) , 𝑟(𝑅 10 |𝑊 3 ) = (2,1) , 𝑟(𝑅 11 |𝑊 3 ) = (2,0) , 𝑟(𝑅 12 |𝑊 3 ) = (3,1) .
Disini  terlihat  bahwa 𝑟(𝑅 1 |𝑊 3 ) = 𝑟(𝑅 3 |𝑊 3 ) = 𝑟(𝑅 10 |𝑊 3 ) = (2,1) , 𝑟(𝑅 2 |𝑊 3 ) = 𝑟(𝑅 12 |𝑊 3 ) = (3,1) , 𝑟(𝑅 4 |𝑊 3 ) = 𝑟(𝑅 8 |𝑊 3 ) = (1,2) ,  dan 𝑟(𝑅 5 |𝑊 3 ) = 𝑟(𝑅 9 |𝑊 3 ) = (1,1) . Jadi 𝑊 3 = (𝑅 6 , 𝑅 11 ) bukan himpunan resolving .
Selanjutnya  penyelidikan  dilakukan  untuk  himpunan  terurut W dengan  anggota  3 vertex di G . Dalam kasus ini ada sebanyak 220 macam himpunan terurut W .  Dari proses perhitungan yang dilakukan, terdapat 14 himpunan resolving untuk graf G pada Gambar 3 yaitu 𝑊 1 = (𝑅 1 , 𝑅 3 , 𝑅 6 ) , 𝑊 2 = (𝑅 1 , 𝑅 7 , 𝑅 9 ) , 𝑊 3 = (𝑅 1 , 𝑅 9 , 𝑅 12 ) , 𝑊 4 = (𝑅 2 , 𝑅 3 , 𝑅 5 ) , 𝑊 5 = (𝑅 2 , 𝑅 3 , 𝑅 6 ) , 𝑊 6 = (𝑅 2 , 𝑅 3 , 𝑅 9 ) , 𝑊 7 = (𝑅 2 , 𝑅 3 , 𝑅 10 ) , 𝑊 8 = (𝑅 2 , 𝑅 3 , 𝑅 12 ) , 𝑊 9 = (𝑅 2 , 𝑅 5 , 𝑅 12 ) , 𝑊 10 = (𝑅 3 , 𝑅 5 , 𝑅 7 ) , 𝑊 11 = (𝑅 3 , 𝑅 6 , 𝑅 7 ) , 𝑊 12 = (𝑅 3 , 𝑅 6 , 𝑅 11 ) , 𝑊 13 = (𝑅 4 , 𝑅 6 , 𝑅 10 ) , 𝑊 14 = (𝑅 6 , 𝑅 10 , 𝑅 11 ) .
Misalkan dipilih ) , , ( 12 5 2 9 R R R W  . Maka representasi vertex-vertex di graf G terhadap 1 W adalah ) 2 , 1 , 1 ( ) | ( 9 1  W R r , ) 2 , 0 , 2 ( ) | ( 9 5  W R r , ) 2 , 1 , 2 ( ) | ( 9 9  W R r , ) 1 , 2 , 0 ( ) | ( 9 2  W R r , ) 3 , 1 , 3 ( ) | ( 9 6  W R r , ) 1 , 2 , 2 ( ) | ( 9 10  W R r , ) 2 , 2 , 1 ( ) | ( 9 3  W R r , ) 3 , 2 , 3 ( ) | ( 9 7  W R r , ) 1 , 1 , 1 ( ) | ( 9 11  W R r , ) 3 , 2 , 2 ( ) | ( 9 4  W R r , ) 2 , 2 , 3 ( ) | ( 9 8  W R r , ) 0 , 2 , 1 ( ) | ( 9 12  W R r .  Karena  semua representasi vertex G terhadap 9 W berbeda,  maka ) , , ( 12 5 2 9 R R R W  adalah  himpunan resolving . Jadi  dimensi  graf G adalah 3. Hal  ini berakibat bahwa  apabila akan  dipasang sensor kebakaran  pada  gedung  Gambar  2,  maka  minimal  dipasang  3  sensor  pada  gedung  tersebut. Pemasangan  sensor  haruslah  pada  himpunan resolving. Andaikan  yang  dipilih  adalah ) , , ( 12 5 2 9 R R R W  . Misalnya dipasang sensor warna merah di 𝑅 2 , sensor warna biru di 𝑅 5 , dan sensor  warna  kuning  di 𝑅 12 .  Apabila  muncul  api  di  salah  satu  ruang  gedung  tersebut,  maka secara tepat dapat ditentukan asal adanya api karena setiap ruang mempunyai representasi  yang berbeda terhadap ) , , ( 12 5 2 R R R . Sebagai contoh, misalnya muncul api di 𝑅 9 , maka sensor merah mengidentifikasikan  api  berasal  dari  ruang  yang  berjarak  2  terhadap 𝑅 2 ,  sensor  biru mengidentifikasikan  api  berasal  dari  ruang  yang  berjarak  1  terhadap 𝑅 5 ,  dan  sensor  kuning mengidentifikasikan api berasal dari ruang yang berjarak 2 terhadap 𝑅 12 , atau secara singkat api berasal  dari  ruang  dengan  jarak  (2,1,2)  dari
) , , ( 12 5 2 R R R .  Dan  satu-satunya  ruang  dengan identifikasi seperti ini adalah 𝑅 9 . Jadi  dengan tepat dapat disimpulkan bahwa api berasal dari 𝑅 9 . Meskipun dimensi metrik graf G pada Gambar 3 adalah 3 sehingga minimal 3 sensor yang harus  dipasang  di  gedung  Gambar  2 tersebut,  akan  tetapi  kalau  kita  tidak  tepat  memilih  3 ruangan yang dipasang sensor tersebut, maka hal ini akan mengakibatkan kita tidak dapat secara tepat  menentukan  asal  adanya  api.    Misalnya  dipilih  ruang  yang  dipasang  sensor  adalah ) , , ( 9 2 1 R R R ,  maka  apabila  muncul  api 𝑅 3 ,  sensor  mengidentifikasikan  api  berasal  dari  ruang dengan jarak terhadap ) , , ( 9 2 1 R R R adalah (1,1,1). Disisi lain jarak 𝑅 11 terhadap ) , , ( 9 2 1 R R R juga (1,1,1).  Jadi  kita  tidak  dapat  menentukan  dengan  tepat  apakah  api  berasal  dari 𝑅 3 atau 𝑅 11 . Demikian pula dengan 𝑅 7 dan 𝑅 8 yang mempunyai jarak yang sama terhadap ) , , ( 9 2 1 R R R yaitu
(2,3,2). Hal ini dikarenakan bahwa ) , , ( 9 2 1 R R R bukan himpunan resolving dari graf G Gambar 3 diatas. Hal ini dapat diuraikan sebagai berikut :
) , , ( 9 2 1 R R R W n  ,  maka  representasi vertex-vertex di  graf G terhadap n W adalah ) 1 , 1 , 0 ( ) | ( 1  n W R r , ) 1 , 2 , 1 ( ) | ( 5  n W R r , ) 0 , 2 , 1 ( ) | ( 9  n W R r , ) 2 , 0 , 1 ( ) | ( 2  n W R r , ) 1 , 3 , 2 ( ) | ( 6  n W R r , ) 1 , 2 , 2 ( ) | ( 10  n W R r , ) 1 , 1 , 1 ( ) | ( 3  n W R r ) 2 , 3 , 2 ( ) | ( 7  n W R r , ) 1 , 1 , 1 ( ) | ( 11  n W R r , ) 2 , 2 , 1 ( ) | ( 4  n W R r , ) 2 , 3 , 2 ( ) | ( 8  n W R r ) 2 , 1 , 2 ( ) | ( 12  n W R r .  Karena
) | ( 3 n W R r = ) 1 , 1 , 1 ( ) | ( 11  n W R r dan ) | ( 7 n W R r = ) 2 , 3 , 2 ( ) | ( 8  n W R r , maka ) , , ( 9 2 1 R R R W n  bukan himpunan resolving .

## 4.  Simpulan
Dimensi  metrik  suatu  graf  yang  diperoleh  dari  denah  ruang  suatu  gedung  dapat direpresentasikan  sebagai  minimal  banyaknya  sensor  api  kebakaran  yang  harus  dipasang  pada gedung  tersebut,  sedangkan  himpunan resolving dengan  kardinalitas  minimum  menunjukkan ruangan  mana  saja  yang  harus  dipasang  sensor  tersebut.  Dari  analisa  yang  dilakukan,  sensor kebakaran yang harus dipasang di gedung hanya di tiga ruangan saja .

## DAFTAR PUSTAKA
[1] S. Allesina and J. M. Levine, “A competitive network theory of species diversity,” Proc. Natl. Acad. Sci. U. S. A. , 2011.
[2] M. B. Hu, R. Jiang, Y. H. Wu, W. X. Wang, and Q. S. Wu, “Urban traffic from the perspective of dual graph,” Eur. Phys. J. B , 2008.
[3] Peter J. Slater, “Leaves of Trees,” in Proceeding of International Conference On Research, Implementation And Education Of Mathematics And SciencesProceeding of the 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing,
Congressus Numerantium , 1975, pp. 549–559.
[4] F. Harary and R. A. Melter, “On the Metric Dimension of a Graph,” Ars Comb. , vol. 2, pp. 191–195, 1976.
[5] G. Chartrand, L. Eroh, M. A. Johnson, and O. R. Oellermann, “Resolvability in graphs and the metric dimension of a graph,” Discret. Appl. Math. , 2000.
[6] Rinurwati, Slamin, and H. Suprajitno, “On (local) metric dimension of graphs with m - pendant points,” J. Phys. Conf. Ser. , vol. 855, no. 1, p. 12035, 2017.
[7] S. Wahyudi, S. Sumarno, and S. Sanjaya, “Dimensi metrik pengembangan graf kincir pola K1 + mK3,” Limits J. Math. Its Appl. , vol. 8, no. 2, p. 17, Nov. 2011.
[8] G. Chartrand and P. Zhang, “The theory and applications of resolvability in graphs: A survey,” Congr. Numer. , vol. 160, 2003.