Vol. 16, No. 2,  199-207,  Januari  2020 DOI: 10.20956/jmsk.v%vi%i.8062
*Program Studi Pascasarjana (S2) Matematika, FMIPA-UNHAS Email : 1 ahmadsyukurd@gmail.com, 2 hasmaba97@gmail.com,
3 l.haryanto@unhas.ac.id, 4 budinurwahyu@unhas.ac.id

## Dimensi Partisi Graf Hasil Amalgamasi Siklus
Ahmad Syukur Daming 1* , Hasmawati Hasmawati 2* , Loeky Haryanto 3*
Budi Nurwahyu 4 *
Abstract
Let  be  a  connected  graph  G  and
-partition { } of end .  The
coordinat to is definition | . If |        | for every two vertices in , then is a called  k-resolving partition of . The minimum k such  that is  a  k-resolving  partition  of is  the  partition  dimension  of and  denoted  by .  In  this  paper,  we  show  that  the  partition  dimension  for  amlagamation  of  cycle  graph for and
To proof this results, we was used mathematical
induction method.
Keywords: Partition Dimention, Amalgamation, Cycle Graph

## Abstrak
Misalkan terdapat sebuah graf terhubung dan himpunan partisi { } dari dan . Koordinat terhadap didefinisikan sebagai | .  Jika |        | ,  untuk  setiap  dua  titik berbeda
, maka disebut -partisi pembeda dari . Nilai minimum sehingga merupakan -partisi  pembeda  dari adalah  dimensi  partisi  dari yang  dinotasikan dengan .  Dalam  makalah  ini  ditunjukkan  bahwa  dimensi  partisi  dari  amalgamasi  graf
siklus, untuk dan .  Metode  yang  digunakan  dalam mengbuktikan hasil tersebut adalah induksi matematika.
Kata kunci: Dimensi Partisi, Amalgamasi, Graf Siklus .

## 1. Pendahuluan
Graf  adalah  pasangan  himpunan  terurut
,  dan  ditulis  dengan  notasi
,  dengan adalah  himpunan  tidak  kosong  yang  anggotanya  disebut  titik  dan adalah  himpunan  pasangan–pasangan  tidak  terurut  dari  anggota yang  disebut  sisi. Salah  satu  kajian  dalam  teori  graf  yang  mendapat  perhatian  dari  beberapa  peneliti adalah dimensi partisi ( partition dimension ). Dimensi partisi pertama kali diperkenalkan oleh Chartrand dkk [4]. Mereka mengelompokkan semua titik di ke dalam sejumlah kelas partisi dan menentukan jarak setiap titik terhadap setiap kelas partisi tersebut. Terdapat  beberapa  hasil  tentang  dimensi  partisi  suatu  graf    yang  telah  diperoleh diantaranya dalam [5] dituliskan bahwa
jika dan hanya jika adalah graf lintasan dan menunjukkan bahwa graf mempunyai
jika dan hanya jika
Ahmad Syukur Daming, Hasmawati Hasmawati, Loeky Haryanto

## Budi Nurwahyu
adalah graf lengkap . Dalam makalah [9], disajikan batas atas dan bawah dimensi partisi  untuk  graf  pohon.  Sedangkan  makalah  [1],  menyajikan  dimensi  partisi  graf amalgamasi  bintang.  Dimensi  partisi  graf  amalgamasi  bintang  dan  lintasan  disajikan dalam  makalah  [2],  sedangkan  makalah  [6],  membahas  dimensi  partisi  untuk  graf persahabatan.  Dalam  makalah  ini  dibahas  penentuan  dimensi  partisi  untuk  graf amalgamasi  siklus.  Beberapa  metode  yang  disajikan  pada  makalah  [2]  dan  [5]  akan dikembangkan  untuk  digunakan  dalam  penentuan  dimensi  partisi  graf  Amalgamasi siklus.  Hasil  yang  diperoleh  dalam  penelitian  ini,  ditulis  dalam  bentuk  lema  dan proposisi, dan di akhir buktinya diberi tanda .

## 2. Tinjauan Pustaka
Graf adalah  pasangan  himpunan
dimana adalah  himpunan berhingga  tak  kosong  yang  anggota-anggotanya  disebut  titik,  dan adalah  sebuah himpunan  (mungkin  kosong)  dari  pasangan-pasangan  titik  yang  disebut  sisi.  Misalkan sisi {    } , maka dikatakan bahwa sisi terkait dengan titik dan titik , sedangka  titik dan  titik disebut  titik-titik  yang  bertetangga.  Untuk  kepentingan penghematan  dalam  penulisan  selanjutnya,  sisi {    } hanya  ditulis . Graf disebut  graf  terhubung  (connected),  jika  untuk  setiap  dua  titik  yang  berbeda dan di terdapat  suatu  lintasan  dari ke [3].  Panjang  suatu  lintasan  adalah banyaknya sisi yang ada pada lintasan tersebut.
Misalkan adalah  graf  sederhana  dan .  Jarak  antara  titik dan dinotasikan dengan adalah { | Dalam  maalah  [8]  disebutkan  bahwa  graf  lintasan
adalah  graf  dengan
himpunan titik { } dan himpunan sisi { } , dengan  setiap untuk .  Graf  lintasan  yang  berorder dinotasikan dengan dengan . Jika adalah suatu graf lintasan berorde dan , maka graf siklus adalah graf dengan himpunan titik dan himpunan  sisi { } .  Graf  siklus memiliki titik  dan sisi dengan setiap titiknya berderajat dua.
Misalkan { |    {            }} untuk dan ,  merupakan  kumpulan  graf
berhingga  dan  masing–masing memiliki  titik  tetap yang  disebut  terminal. Amalgamasi
adalah graf yang dibentuk dengan mengambil semua dan menyatukan  terminalnya  [9].  Graf  yang  akan  di  diteliti  dalam  penelitian  ini  adalah dengan untuk  setiap , dan .  Untuk
penyederhanaan  penulisan  dalam  penelitian  ini
dinotasikan  dengan .  Himpunan  titik { |                       } dan himpuan  sisi { |         }   { |
} .
Misalkan  terdapat  sebuah  graf  terhubung dengan
adalah  himpunan  titik- titiknya,
dan ,  jarak  antara dengan yang  dinotasikan
didefinisikan  sebagai {       |     } Misalkan  terdapat  sebuah  graf
Ahmad Syukur Daming, Hasmawati Hasmawati, Loeky Haryanto

## Budi Nurwahyu
terhubung dan  koleksi  himpunan { } ,  dengan adalah  partisi  dari Himpunan { } disebut himpunan  partisi dan disebut kelas partisi. Misalkan .  Koordinat terhadap didefinisikan  sebagai |
(
) .
Himpunan  partisi dikatakan -partisi  pembeda ( resolving  partition )  jika - vektor | untuk setiap , berbeda. Nilai minimum agar terdapat -partisi pembeda  dari adalah dimensi  partisi dari ,  dinotasikan  dengan
[5]. Dalam [6], ditunjukkan bahwa {
Dalam penentuan dimensi partisi untuk graf
diperlukan beberapa sifat seperti yang disajikan pada definisi, lema, dan proposisi berikut.
Definisi 2.1. Diberikan suatu graf terhubung dan . Titik dan disebut titik-titik yang setara dalam graf apabila memenuhi salah satu sifat berikut:
a. untuk setiap {    } ,
b. Untuk  setiap {    } ,  terdapat  titik sehingga
.
Lema  2.1. Diberikan  suatu  graf  terhubung G dengan  partisi  pembeda dari , untuk .  Jika untuk  setiap {    } ,  maka dan merupakan unsur yang berada pada kelas partisi yang berbeda di .
Lema 2.2. Diberikan suatu graf terhubung dan
merupakan titik-titik yang setara.  Misalkan  pula
, dan { } merupakan  partisi pembeda dari . Jika , maka dan merupakan unsur yang berada pada kelas partisi yang berbeda di
Bukti. Misalkan {
} , . Karena dan adalah titik-titk yang setara, maka untuk setiap {    } atau untuk setiap {    } , terdapat  titik sehingga
.  Mengingat { } adalah  partisi  pembeda, =1  dan dengan {    } ,  untuk dan ,  maka  mestilah  terdapat {          } sehingga dan
.  Dalam  hal  ini,
dan ( ) .
Teorema  2.1. Diberikan graf  terhubung  dengan  order
,  maka jika dan hanya jika
.
Ahmad Syukur Daming, Hasmawati Hasmawati, Loeky Haryanto

## Budi Nurwahyu
Gambar 1. Graf Hasil Amalgamasi Siklus (

## 2.1 Dimensi Partisi
Batas  atas  dimensi  partisi dapat  diperoleh  dengan  mengkonstruksi partisi pembeda pada graf .
a. Misalkan =4  dengan  himpunan  titik dan  himpunan  sisi .  Tulis { }   { } ⋃{ } , dengan { } dan { } dan = { }   { } . Pilih  himpunan  partisi { } dengan { } , { } ,  dan { } .  Representasi  setiap  titik  di
terhadap
adalah sebagai berikut:
|
( | ) , jika ⌊ ⌋
( | ) ⌊ ⌋ ;
( ( | ) ; jika ⌊ ⌋ )
( | )
( | )
( | )
( | ) = ( ( | ) )
Ahmad Syukur Daming, Hasmawati Hasmawati, Loeky Haryanto

## Budi Nurwahyu
Hasil observasi menunjukkan semua titik mempunyai representasi yang berbeda,  sehingga merupakan  partisi  pembeda  dari dengan  kardinalitas | | . Jadi, . ...(3.1) Untuk  batas  bawah  dari  dimensi  partisi dapat  merujuk  pada  Proposisi 2.1 menyatakan bahwa jika dan hanya jika . Graf , maka  dapat  dipastikan  batas  bawah  dari  dimensi  partisi    graf adalah . ...(3.2) Berdasarkan  persamaan  (3.1),  dan  (3.2)  diperoleh  batas  bawah  dan  atas  yaitu .  Jadi  dimensi  partisi  graf adalah b. Misalkan =  5  dengan  himpunan  titik dan  himpunan  sisi . Tulis { }   { } ⋃{ } , dengan { } dan { } dan = { { } { } } . Pilih  himpunan  partisi { } dengan { } { } , { } { } ,  dan { } .  Refresentasi setiap titik di terhadap adalah sebagai berikut:
|
( | ) ; jika ⌊ ⌋
( | ) ; jika ⌊ ⌋
( | ) ;  jika ⌊ ⌋ untuk
( | )
( | )
( | ) ; jika ⌊ ⌋
( | ) ; jika ⌊ ⌋ dan
( | )
Hasil  observasi  menunjukkan  bahwa  semua  titik mempunyai representasi  yang  berbeda,  sehingga merupakan  partisi  pembeda  dari dengan kardinalitas | | . Jadi, . ...(3.3) Untuk  batas  bawah  dari  dimensi  partisi dapat  merujuk  pada  Proposisi 2.1 menyatakan bahwa jika dan hanya jika . Graf , maka  dapat  dipastikan  batas  bawah  dari  dimensi  partisi    graf adalah . ...(3.4) Berdasarkan  persamaan  (3.3)  dan  (3.4)  diperoleh  batas  bawah  dan  atas  yaitu .  Jadi  dimensi  partisi  graf adalah
Ahmad Syukur Daming, Hasmawati Hasmawati, Loeky Haryanto

## Budi Nurwahyu
2.2. Dimensi partisi Penentuan dimensi partisi dimulai dengan . a. Misalkan { }   { } ⋃{ } ⋃{ } dengan { } , { } , { } dan { } Pilih  himpunan  partisi { } dengan { } , { } ,  dan { } .  Representasi  setiap  titik  di terhadap adalah sebagai berikut:
| ( | )
( | ) ;
( | )
( | )
( | )
( | ) ;
( | )
( | ) ;

## ( | )
Hasil  observasi  menunjukkan  semua  titik mempunyai  representasi yang  berbeda  terhadap ,  sehingga merupakan  partisi  pembeda  dari dengan  kardinalitas | | .  Jadi,
.  Menurut  Proposisi  2.1, . Jadi b. Misalkan { }   { } ⋃{ } ⋃{ } dengan { } , { } , { } dan
= { } {
}
{ } Pilih  himpunan  partisi { } dengan { } , { } ,  dan { } .  Refresentasi  setiap  titik  di terhadap adalah sebagai berikut:
Ahmad Syukur Daming, Hasmawati Hasmawati, Loeky Haryanto

## Budi Nurwahyu
Untuk  representasi  titik dan dimana dan sama  dengan
representasi  titik  pada  graf
,  sedangkan  titik dan  titik untuk , dan adalah ( | ) ( | ) ; ( | )    ( | )
( | )
( | ) ; jika ⌊ ⌋
( | ) ; jika ⌊ ⌋
( | )
Hasil observasi menunjukkan semua titik
mempunyai representasi yang berbeda,  sehingga merupakan  partisi  pembeda  dari dengan  kardinalitas | | .  Jadi, .  Serupa  dengan  batas  bawah bahwa menurut Proposisi 2.1, diperoleh . Jadi Dengan  cara  yang  serupa  dapat  ditunjukkan  bahwa dan adalah  3  untuk .  Graf dan dapat dilihat pada Gambar 2.
Gambar 2. Partisi Pembeda (a)
dan (b)
Berdasarkan  hasil  pada  Subbab 2.1 dan 2.2 ,  dirumuskan  perumuman  partisi  dimensi graf untuk dalam bentuk teorema seperti berikut. Proposisi 2.2: Jika dan , maka . Bukti:
Pembuktian Proposisi 2.2 menggunakan metode induksi matematika, yaitu:
1) Berdasarkan hasil pada Subbab 2.1 dan 2.2 diperoleh :
a. Untuk dan , b. Untuk dan , c. Untuk dan , d. Untuk dan ,
(b) (a)
Ahmad Syukur Daming, Hasmawati Hasmawati, Loeky Haryanto

## Budi Nurwahyu
2) Asumsikan  bahwa  untuk , adalah  benar  jika ,  yaitu dengan  partisi  pembeda  minimum  adalah { } , { |             } , { |             } , dan { |             } . Dalam hal ini, { }   { } ⋃   ⋃{ } dan { } 3)  Selanjutnya  akan  ditunjukkan  bahwa  proposisi  juga  benar  untuk ,  yaitu jika maka . Graf merupakan graf dengan penambahan satu titik sebut pada sisi [    ] di graf . Untuk  menentukan  dimensi  partisi dapat  diperoleh  dengan mengkonstruksi  partisi  pembeda  graf .  Misalkan { }
sedemikian sehingga :
a. Untuk ,
{ |             }   { } { } , { |             }   { } { } , dan { } Representasi setiap titik di terhadap adalah sebagai berikut:
|
( |  ) ; jika ⌊ ⌋
( |  ) ; jika ⌊ ⌋ untuk , karena . ( | )
( |  )
( |  )
( |  ) ; jika ⌊ ⌋
( |  ) ; jika ⌊ ⌋ dan ( |  )
( |  )
b. Untuk tulis { } { } , { } , dan { |             }   { } { |             } { }
untuk setiap Karenanya, representasi titik dan dimana dan sama dengan representasi titik pada graf . Sedangkan titik dimana dan titik adalah sebagai berikut:
( |   )
Ahmad Syukur Daming, Hasmawati Hasmawati, Loeky Haryanto
Budi Nurwahyu
( |   ) ; jika ⌊ ⌋
( |   ) ; jika ⌊ ⌋
( |   ) ; jika ⌊ ⌋ dan ( |   )
( |   )
Terlihat  bahwa  representasi  setiap  titik  graf
,  untuk terhadap  himpunan  partisi adalah  berbeda.  Dengan  demikian  himpunan  partisi merupakan  partisi  pembeda  untuk  graf ,  dengan .  Jadi | |   | | ,  jika .  Menurut  Proposisi  2.1, .  Jadi untuk  setiap dan

## Daftar Pustaka
[1] Asmiati.  2012.  Partition  Dimension  of  Amalgamation  of  Stars. Bulletin  of Mathematics . 02(04): 161-167.
[2] Asmiati. 2016. Dimensi Partisi Graf Amalgamasi Bintang yang Dihubungkan Suatu Lintasan. Jurnal  Matematika,  Fakultas  Matematika  dan  Ilmu  Pengetahuan  Alam Universitas Lampung . 19(3): 93-95.
[3] Chartrand, G., dan Oellermann, O. R. 1993. Applied and Algorithmic Graph Theory . McGraw–Hill, Inc, New York–St. Louis–San Francisco.
[4] Chartrand, G., Salehi, E., dan Zang, P. 1998. On The Partition Dimension of Graph. Congressus Numerantium . Vol. 130: 157-168.
[5] Chartrand,  G.,  Salehi,  E.,  dan  Zang,  P.  2000.  The  Partition  Dimension  of  Graph. Aequationes Mathematicae . 59: 45-54.
[6] Darmaji. 2011. Dimensi Partisi Graf Multipartit dan Graf Hasil Korona Dua Graf Terhubung. Disertasi . Bandung: Institut Teknologi Bandung, Indonesia.
[7] Diestel  R.  2005. Graph  Theory ,  Third  Edition.  Springer-Verlag  Heidelberg.  New York.
[8] Fitriani, D., Salman, A. N. M. 2016. Rainbow connection number of amalgamation of some graphs. AKCE International journal of graphs and combinatorics . 13 : 90– 99.
[9] Juan, R., Yero, I. G., dan Lemanska, M. 2014. On the Partition Dimension of Trees. Discrete Applied Mathematics . 166: 204-209.