## DIMENSI METRIK GRAF DUAL PRISMA
Fenny Fitriani 1
1 Universitas PGRI Adi Buana Surabaya, fenny_f@unipasby.ac.id
Abstract. The form of a graph which formed from a graph has no intersecting side is  called  a  dual  graph.  One  graph  that  can  be  formed  as  a  dual  graph  is  a  prism graph. Prism graph ( ) is a graph formed from the results of a cartesian product of a cycle graph with a line graph. In this paper we discuss the metric dimension of a dual prism graph ( ). The metric dimension of a dual prism graph is divided into two states, when and .
Keywords : Dual graph, prism graph, metric dimension.
Abstrak. Bentuk  graf  yang  dibentuk  dari  graf  yang  tidak  memiliki  sisi  yang berpotongan disebut sebagai graf dual. Salah satu graf yang dapat dibentuk sebagai graf dual adalah graf prisma. Graf prisma ( ) merupakan graf yang terbentuk dari hasil  produk  kartesian  graf  sikel  dengan  graf  garis.  Dalam  paper  ini  dibahas mengenai dimensi metrik dari graf dual prisma (
). Dimensi metrik dari graf dual prisma terbagi dalam dua keadaan yaitu pada saat dan .
Kata Kunci : Graf dual, graf prisma, dimensi metrik .

## 1 Pendahuluan
Salah  satu  bentuk  dari  graf  adalah  graf  dengan  sisi  yang  tidak  saling berpotongan  atau  disebut  juga  sebagai  graf  planar.  Contoh  dari  bentuk  graf tersebut  adalah  graf  pohon,  graf  prisma,  dan  graf  antiprisma.  Dari  graf  planar tersebu dapat dibentuk suatu graf baru yang disebut dengan graf dual. Simpul dari graf dual merupakan region r pada graf planar.  Dua simpul pada graf dual dapat dihubungkan dengan suatu sisi jika dan hanya jika dua region yang diwakili oleh kedua  simpul  tersebut  dipisahkan  oleh  sisi  pada  graf  palanar  pembentuknya  [1]. Beberapa  penelitan  yang  telah  dilakukan  dengan  menggunakan  graf  dual  antara lain penggunaan graf dual sebagai dasar pewarnaan peta kotamadya [6], sifat dari graf  euler  jika  dihubungkan  dengan  graf  dual  [7],  penandaan  jaringan  sosial berdasarkan graf dual [12], dan karakteristik dari graf dual parsial [5]
Salah  satu  subjek  yang  dipelajari  dalam  teori  graf  adalah  dimensi  metrik  dari graf.  Jika  dimisalkan  suatu  graf ,  maka  dimensi  metrik dari  graf merupakan  nilai  kardinalitas  minimum  dari  himpunan  pembeda .  Himpunan pembeda merupakan himpunan simpul dimana representasi  relatif simpul terhadap dapat dituliskan sebagai ( ) dengan merupakan panjang lintasan  minimum  antara  simpul dengan  simpul untuk  setiap . Himpunan  pembeda merupakan  himpunan  pembeda  dari  graf jika  untuk

## Unisda Journal of Mathematics and Computer Science
sebarang  simpul  dalam memenuhi dengan dan [3]. Beberapa penelitian mengenai dimensi metrik antara lain dimensi metrik graf dengan [4], dimensi metrik dan dimensi partisi dari famili graf tangga [9], dimensi metrik graf pohon bentuk tertentu [8], analisis dimensi  metrik dengan himpunan pembeda  terhubung pada  graf khusus  keluarga pohon dikaitkan keterampilan berpikir tingkat tinggi [10], dan dimensi metrik graf amal (nKm) [11].
Dari penjabaran diatas, dalam artikel ini dibahas mengenai dimensi metrik dari graf  dual  yang  dibangun  dari  salah  satu  graf  planar.  Graf  planar  yang  dimaksud adalah  graf  prisma yang  merupakan  hasil  dari cartesian  product antara
.

## 2 Pembahasan
Sebelum  menemukan  nilai  dimensi  metrik  dari  graf  dual  yang  dibentuk  dari graf  prisma,  maka  diperlukan  bentuk  umum  dari  graf  dual  prisma.  Dari  bentuk umum tersebut kemudian dicari dimensi metrik dari graf yang terbentuk.

## 2.1 Graf dual prisma
Bentuk umum dari graf dual yang dibentuk dari graf prisma dapat didefinisikan sebagai berikut:
Definisi  1. Graf merupakan  graf  dual  yang  dibentuk  dari  graf  prisma dengan . Himpunan simpul dari graf adalah ( )   { }   { dan } dan  himpunan  sisi  dari  graf dapat  dinyatakan  sebagai ( )   { }   { dan } { }   { dan } { } .  Dengan  kata  lain | ( )| dan | ( )| .
Gambar  1  merupakan  contoh  graf  dual yang  dibentuk  dari  graf  prisma
.  Himpunan  simpul  dari  graf
adalah ( )   { } dengan dan  himpunan  sisi  dari  graf adalah ( ) { |         }   { |                       } { |         }   { }          }   { |         }

## Unisda Journal of Mathematics and Computer Science
Gambar 1. Graf dual

## 2.2 Dimensi metrik graf dual prisma
Berikut  diberikan  lemma  yang  akan  digunakan  sebagai  pembuktian  dalam pembuktian dimensi metrik graf dual prisma
Lemma 2.1 Misalkan dan merupakan simpul  yang ada pada graf . Jika (1) simpul dan tidak  bertetangga  dan atau  (2)  simpul dan bertetangga  dan ,  maka  setiap  himpunan  pembeda  dari memuat paling sedikit salah satu dari simpul dan [2].
Dimensi metrik dari graf dual prisma didapatkan dalam dua keadaan yaitu pada  saat dan .  Berikut  diberikan  teorema  graf  dual  prisma dengan : Teorema 2.1 Jika adalah graf dual dari graf dengan , maka ( )   { ⌊ ⌋ (1)

## Bukti:
Dalam pembuktian ini dilakukan dalam 3 kasus yaitu:
Kasus  1 :  Ditunjukkan ( ) pada .  Untuk  batas  atas  jika dimisalkan  diambil { }    ( ) .  Dari tersebut  sedemikian hingga  didapatkan  hasil  representasi  jarak  antara  simpul terhadap berbeda, dengan  kata  lain  himpunan merupakan  himpunan  pembeda  dari
untuk sehingga ( ) .  Selanjutnya  untuk  batas  bawah  dimensi metrik,  simpul dan  simpul memiliki  simpul-simpul  ketetanggaan  yang sama, sehingga sesuai dengan Lemma 1 salah satu simpul dari simpul dan harus  masuk  kedalam  himpunan  pembeda
mengakibatkan ( ) .
Karena  graf bukan  graf  lintasan,  maka ( ) .  Untuk  simpul yang  ada  pada  sikel  memiliki  diameter  yang  sama  yaitu untuk .  Karena  setiap pada paling  sedikit  memuat  satu  dan  paling banyak  memuat  tiga  simpul  dari  graf ,  serta  paling  banyak  satu pada

## Unisda Journal of Mathematics and Computer Science
memua  tepat  tiga  simpul  maka ( ) .  Karena ( ) ,
maka ( ) untuk .
Kasus  2. Ditunjukkan ( ) pada .  Untuk  batas  atas  jika dimisalkan  diambil { }    ( ) .  Dari tersebut  sedemikian hingga  didapatkan  hasil  representasi  jarak  antara  simpul terhadap berbeda,
dengan  kata  lain  himpunan merupakan  himpunan  pembeda  dari untuk sehingga ( ) .  Selanjutnya  untuk  batas  bawah  dimensi metrik,  simpul dan  simpul memiliki  simpul-simpul  ketetanggaan  yang sama, sehingga sesuai dengan Lemma 1 salah satu simpul dari simpul dan
harus  masuk  kedalam  himpunan  pembeda mengakibatkan ( ) . Karena  graf bukan  graf  lintasan,  maka ( ) .  Untuk  simpul yang  ada  pada  sikel  memiliki  diameter  yang  sama  yaitu untuk .  Karena  setiap pada paling  sedikit  memuat  satu  dan  paling banyak  memuat  tiga  simpul  dari  graf ,  serta  paling  banyak  satu pada memua  tepat  tiga  simpul  maka ( ) .  Karena ( ) ,
maka ( ) untuk .
Kasus3: ditunjukkan ( )   ⌊ ⌋ pada .  Untuk  batas  atas, misalkan  pola  dari  pengambilan gap dapat  ditulis  dalam  barisan  berurutan { ⌊ ⌋ } dimana adalah  jumlah  simpul  yang  ada  pada gap .  Dari permisalan  tersebut  didapatkan  pola gap dari mengikuti  pola  pada {           } dengan  penambahan gap {   } sebanyak i dengan  pola pengulangan  pada .  Dari  pola  tersebut  dapat  dikonstruksikan sebagai berikut: a. Untuk atau 3 Misalkan atau , maka didapatkan ⌊ ⌋ dengan .  Sehingga  didapatkan { |         } { } .  Karena memuat simpul  dan  dengan  menggunakan ketentuan  yang  ada  pada  kasus  (1),  maka  untuk  setiap memiliki  representasi  yang  berbeda  terhadap ,  tetapi . b. Untuk 4 Misalkan ,  maka  didapatkan ⌊ ⌋ dengan . Sehingga  didapatkan { |         }   { } Karena memuat simpul  dan  dengan  menggunakan  ketentuan yang  ada  pada  kasus  (1),  maka  untuk  setiap memiliki representasi yang berbeda terhadap , tetapi . c. Untuk atau 1 Misalkan atau , maka didapatkan ⌊ ⌋ dengan . Sehingga didapatkan { |             } { } .  Karena memuat simpul  dan  dengan  menggunakan

## Unisda Journal of Mathematics and Computer Science
ketentuan  yang  ada  pada  kasus  (1),  maka  untuk  setiap memiliki  representasi  yang  berbeda  terhadap tetapi . Dari  ketiga  kasus  (a)-(c),  didapatkan ,  sehingga  salah  satu dari  simpul dan harus  masuk  kedalam .  Hal  tersebut  mengakibatkan
kardinalitas  minimum  dari adalah ⌊ ⌋ ,  dengan  kata
( )   ⌊ ⌋ .
Untuk  batas  bawah  dari  dimensi  metrik,  misalkan ( )   ⌊ ⌋ .  Jika ⌊ ⌋ simpul  berada  pada  sikel,  maka .  Jika
maka  akan  terdapat  representasi  yang  sama  untuk  simpul  yang  ada  pada  sikel.
Dari uraian tersebut didaptakan ⌊ ⌋ , dengan kata lain ( ) ⌊ ⌋ .  Karena ⌊ ⌋          ( )   ⌊ ⌋ ,  maka ( )
⌊ ⌋ untuk .
Sedangkan  untuk  dimensi  metrik  dari  graf  dual  prisma dengan diberikan pada teorema berikut:
Teorema  2.2 Jika adalah  graf  dual  dari  graf
dengan dan ,
maka
( )   { ⌈ ⌉ (2)

## Bukti:
Dalam pembuktian ini dilakukan dalam 2 kasus yaitu: Kasus  1 :  Ditunjukkan ( ) pada .  Untuk  batas  atas  jika dimisalkan  diambil { } .  Dari tersebut  sedemikian  hingga didapatkan  hasil  representasi  jarak  antara  simpul terhadap berbeda,  dengan kata lain merupakan himpunan pembeda dari
untuk sehingga
( ) .  Untuk  batas  bawah,  dengan  menggunakan  ketentuan  pada  batas atas dan karena pada tiap simpul  yang ada pada sikel pertama memiliki tetangga yang  mengakibatkan  jarak  tiap  simpul  pada  sikel  pertama  maksimal  adalah  2.
Untuk mudah  diketahui  bahwa ( ) ,  untuk dan karena  jarak  tiap  simpul  maksimal  2  mudah  diketahui  bahwa ( ) . Pada ,  hasil  representasi  simpul  sikel  pertama  yeng  tersisa  sama  dengan hasil  representasi  simpul , ( | ) ,  sehingga ( ) . Pada , hasil representasi simpul  sikel pertama  yang tersisa sama dengan  2 simpul  dari  sikel  kedua  yang  bertetangga  dengan  simpul  di , } untuk ,  sehingga ( ) .  Karena ( )
maka ( ) .

## Unisda Journal of Mathematics and Computer Science
Kasus 2: ditunjukkan ( )   ⌈ ⌉ pada . Untuk batas atas, misalkan
pola dari pengambilan gap dapat ditulis dalam barisan berurutan { ⌊ ⌋ } dimana adalah  jumlah  simpul  yang  ada  pada gap .  Dari permisalan  tersebut  didapatkan  pola gap dari mengikuti  pola  pada
{          } dengan  penambahan gap {   } sebanyak i dengan  pola pengulangan  pada .  Dari  pola  tersebut  dapat  dikonstruksikan sebagai berikut: d. Untuk atau 2 Misalkan atau ,  maka  didapatkan ⌈ ⌉ dengan .  Sehingga  didapatkan { |         } { } .  Karena memuat simpul  dan  dengan  menggunakan
ketentuan yang ada pada kasus (1), dimana nilai pada kasus (2) ini terdiri dari {                      } jika ,  maka  untuk  setiap memiliki representasi yang berbeda terhadap e. Untuk atau 4 Misalkan atau ,  maka  didapatkan ⌈ ⌉ dengan .  Sehingga  didapatkan { |         } { } Karena memuat simpul dan dengan menggunakan
ketentuan yang ada pada kasus (1), dimana nilai pada kasus (2) ini terdiri dari {                        } jika ,  maka  untuk  setiap memiliki representasi yang berbeda terhadap . f. Untuk
Misalkan ,  maka  didapatkan ⌈ ⌉ dengan .  Sehingga didapatkan { |             }   { } .  Karena memuat simpul  dan  dengan  menggunakan  ketentuan  yang  ada  pada kasus  (1),  dimana  nilai pada  kasus  (2)  ini  terdiri  dari { } jika ,  maka  untuk  setiap memiliki representasi yang berbeda terhadap .
Dari  ketiga  kasus  (a)-(c),  didapatkan  bahwa merupakan  himpunan  pembeda, sehingga ( )   ⌈ ⌉ .
Untuk  batas  bawah  dari  dimensi  metrik,  misalkan ( )   ⌈ ⌉ .  Jika ⌈ ⌉ simpul  berada  pada  sikel  pertama,  maka  terdapat  hasil  representasi simpul yang sama terhadap . Jika ⌈ ⌉ berada pada sekel, maka terdapat representasi  simpul  yang  sama  terhadapat .  Dari  uraian  tersebut  didaptakan ⌈ ⌉ ,  dengan  kata  lain ( )   ⌈ ⌉ .  Karena ⌈ ⌉      ( ) ⌈ ⌉ , maka ( )   ⌈ ⌉ untuk .

## 3 Kesimpulan
Berdasarkan  pembahasan  di  atas,  didapatkan  bahwa  dimensi  metrik  dari  graf dual prisma dapat dibagi dalam dua keadaan yaitu pada saat dan .  Dimensi  metrik  graf  dual  prisma  ketika adalah ( ) dengan
dan ( )   ⌊ ⌋ dengan .  Dimensi  metrik  graf dual  prisma  ketika adalah ( ) dengan dan ( )   ⌈ ⌉ dengan .

## 4 Daftar Pustaka
[1]  Bondy,  J.  A.,  &  Murty,  U.  (1976). Graph  Theory  with  Applications.  . Great Britain : The Macrniilan Press Ltd.
[2]  Bringham,  R.,  Chartrand,  G.,  Dutton,  R.  D.,  &  Zhang,  P.  (2003).  Resolving Domination In Graphs. Mathematica Bohemica, 128 (1), 25-36.
[3]  Chartrand,  G.,  Eroh,  L.,  Johnson,  M.  A.,  &  Oellermann,  O.  R.  (2000). Resolvability in graphs and the metric dimension of a graph. Discrete Applied Mathematic, 105 , 99-113.
[4]  Hindayani.  (2011,  Mei).  Dimensi  Metrik  Graf  Kr  +  mKs,  m,r,s  elemen  N. CAUCHY, 1 (4), 165-174.
[5] Lakshmi, S., & Saranya, N. (2014). Self-Dual and Characterization of Partial Dual Graphs. IOSR Journal of Mathematics (IOSR-JM), 10 (6), 14-25.
[6] Mussafi, N. S. (2015, April). Penerapan Greedy Coloring Algorithm Pada Peta Kotamadya  Yogyakarta  Berbasis  Four-Colour  Theorem. Kaunia,  XI (1),  19- 26.
[7] Pathak, R., & Kalita, B. (2012). Properties of Some Euler Graphs Constructed from  Euler  Diagram. Int.  Journal  of  Applied  Sciences  and  Engineering Research, I (2), 232-237.
[8]  Permana,  A.  B.,  &  Darmaji.  (2012).  Dimensi  Metrik  Graf  Pohon  Bentuk Tertentu. JURNAL TEKNIK POMITS, 1 (1), 1-4.
[9] Saifudin, I. (2016, Agustus). Dimensi Metrik dan Dimensi Partisi dari Famili Graf  Tangga. JUSTINDO,  Jurnal  Sistem  &  Teknologi  Informasi  Indonesia,
1 (2), 105-112.
[10]  Sulistio,  W.,  Slamin,  &  Dafik.  (2015,  Desember).  Analisis  Dimensi  Metrik Dengan  Himpunan  Pembeda  Terhubung  Pada  Graf  Khusus  Keluarga  Pohon Dikaitkan Keterampilan Berpikir Tingkat Tinggi. Kadikma, 6 (3), 26-35.
[11] Utomo, T., & Dewi, N. R. (2018, Maret). Dimensi Metrik Graf Amal (nKm). Limits: Journal Mathematics and Its Application, 15 (1), 71-77.
[12] Yuan, W., He, K., Guan, D., & Han, G. (2017). Edge-Dual Graph Preserving Sign Prediction for Signed Social Networks. IEEE Access, 5 , 19383-19392.