## BEBERAPA SIFAT HIMPUNAN KRITIS PADA PELABELAN AJAIB GRAF BANANA TREE
Triyani dan Irham Taufiq Universitas Jenderal Soedirman trianisr@yahoo.com.au
ABSTRACT. A critical set in edge magic total labeling  on graph G is a subset label such  that  it  can  forms  the  edge  magic  total  labeling  uniquely.  This  paper  investigate critical  set  on  Banana  Tree  graph.  The  result  shows  some  properties  of  critical  set  on Banana Tree graph, such as  the size of it at least ( 1) n k  , where n is number of leaf and k is number of star, except the size of critical set on graph BT(1,1) is 2. Beside it, if x is the label of any leaf and y is the label of the edge adjacent to it then each critical set in λ must contain either x or y, not both.
Keywords : properties of critical set, edge magic total labeling, Banana Tree graph.
ABSTRAK. Sebuah  himpunan  kritis  pada  pelabelan  total  sisi  ajaib  pada  graf G merupakan subhimpunan label sedemikian sehingga label tersebut membangun pelabelan total  sisi-ajaib  secara  tunggal.    Pada  artikel  ini  diselidiki  semua  kemungkinan himpunan  kritis  pada  pelabelan  total  sisi  ajaib  graf Banana  Tree .  Hasil  penelitian menunjukkan  bahwa  terdapat  beberapa  sifat  himpunan  kritis  pada  graf Banana  Tree, yaitu  minimal  berukuran ( 1) n k  ,  dengan n menyatakan  banyaknya  daun  dari  graf bintang  dan k menyatakan  banyaknya  graf  bintang  kecuali  himpunan  kritis  pada  graf BT (1,1) berukuran 2. Selain itu, jika x adalah label dari titik daun dan y adalah label dari sisi yang bersisian dengan x , maka setiap himpunan kritis dalam λ harus memuat x atau y , tapi tidak keduanya.
Kata Kunci : Karakteristik himpunan kritis, pelabelan total sisi ajaib, graf Banana Tree

## 1. PENDAHULUAN
Sebuah  himpunan  kritis  pada  pelabelan  suatu  graf  adalah  subhimpunan label  dan  posisi  label  tersebut  yang  apabila  dilengkapi  akan  menghasilkan pelabelan  graf  secara  tunggal  (Imron  dkk.,  2007).  Salah  satu  konsep  dari himpunan  kritis  yaitu  penentuan  suatu  garis  pada  bidang  datar  (Sudarsana  dan Junaidi,  2008).  Penentuan  sebuah  garis  pada  bidang  datar  membutuhkan  paling sedikit dua buah titik sebagai dasar untuk mengetahui kemiringannya. Jika hanya
JMP : Volume 4 Nomor 2, Desember 2012, hal. 271 - 278
diberikan  sebuah  titik  maka  ada  tak  hingga  banyak  kemungkinan  persamaan garis yang dapat dibuat.
Menurut Baskoro (2007), masalah menentukan himpunan kritis dari suatu pelabelan  graf  merupakan  masalah  yang  tidak  mudah  karena  kemungkinan  dari subhimpunan  label  pada  graf  tersebut  sangat  banyak,  kemudian  masing-masing subhimpunan  tersebut  dicari  subhimpunan  label  yang  dapat  membangun pelabelan graf secara tunggal.
Salah  satu  jenis  dari  pelabelan  graf  adalah  pelabelan  total  sisi  ajaib. Pelabelan  total  sisi  ajaib  pada  graf G adalah  fungsi  bijektif    yang  memetakan setiap  titik  dan  sisi  ke  bilangan  bulat  positif  sedemikian  sehingga  jumlah  label dua buah titik dan sebuah sisi  yang bersisian dengan kedua titik tersebut  adalah sama.  Graf  yang  dapat  dilabeli  dengan  pelabelan  total  sisi  ajaib  selanjutnya disebut graf sisi ajaib.
Beberapa  kajian  tentang  himpunan  kritis  pada  pelabelan  total  sisi  ajaib telah dilakukan antara lain: himpunan kritis dalam pelabelan total sisi ajaib pada graf Star (Baskoro,  2005)  dan  himpunan  kritis  dalam  pelabelan  total  sisi  ajaib pada graf Caterpilar (Imron dkk., 2007).
Pada  artikel  ini  akan  dibahas  tentang  sifat-sifat  himpunan  kritis  pada pelabelan total sisi ajaib graf Banana Tree . Graf Banana Tree adalah graf pohon yang dibentuk dari gabungan terpisah graf bintang dengan menambahkan sebuah titik baru yang terhubung dengan sebuah titik daun dari setiap graf bintang.
Adapun sistematika penulisan artikel ini adalah bagian pertama  pendahuluan yang  menguraikan  latar  belakang  masalah,    rumusan  masalah,  beberapa  hasil kajian  yang  telah  dilakukan  dan  tujuan  penulisan.  Bagian  ke  dua  membahas himpunan  titik  dan  sisi  pada  graf Banana  Tree yang  meliputi  pendefinisian  dan kardinalitas himpunan titik dan sisi pada graf Banana Tree .  Pada bagian ke tiga membahas  pelabelan  total  sisi  ajaib  graf Banana  Tree yang  menguraikan  lemma dan teorema yang digunakan dalam penulisan artikel. Bagian ke empat membahas beberapa sifat himpunan kritis pada pelabelan graf Banana Tree . Bagian  ke lima pada  artikel  ini  adalah  kesimpulan  yang  menguraikan  simpulan  dari  bagian sebelumnya.
272                                                                                                           Triyani dan Irham Taufiq

## 2. HIMPUNAN TITIK DAN SISI PADA GRAF BANANA TREE
Graf Banana  Tree dinotasikan  dengan
1 2 ( , ,..., ) k BT n n n merupakan  graf pohon  yang  terdiri  dari  gabungan  terpisah  graf  bintang  dengan  menambahkan sebuah  titik  yang  terhubung  dengan  sebuah  titik  daun  dari  setiap  graf  bintang. Notasi n i menyatakan  banyaknya  titik  daun  dari  graf  bintang  ke- i dan k menyatakan banyaknya graf bintang.
... ... a k1 a 13 a k2 ... c 2 c k a ... a 12 a 11 a 23 a 22 a 21 a k3 c 1 1 1 n a 2 2 n a k kn a
Gambar 1. Graf Banana Tree
Himpunan  titik  pada  graf Banana  Tree 1 2 ( , ,..., ) k BT n n n didefinisikan dengan 1 2 ( ( , ,..., )) { } { 1 } { 1 ;1 } k i ij i V BT n n n a c i k a i k j n          ,  dan
himpunan sisinya didefinisikan dengan
1 2 1 ( ( , ,..., )) { 1 } { 1 ;1 } k i i ij i E BT n n n aa i k c a i k j n         .  Notasi c i menyatakan titik pusat pada  graf  bintang  ke- i , a menyatakan  sebuah titik baru, dan ij a menyatakan    titik    daun    ke- j pada  graf    bintang  ke- i .    Banyaknya  titik pada 1 2 ( , ,..., ) k BT n n n adalah  sebuah titik  ditambah  dengan  banyaknya titik dari setiap  graf  bintang.  Jika  graf  bintang  ke- i dinotasikan  sebagai i n S ,  maka banyaknya titik pada graf Banana Tree adalah
1 2 1 2 ( ( , ,..., )) 1 ( ) ( ) ... ( ) k k n n n V BT n n n V S V S V S      1 1 ( 1) k i i n      1 1 . k i i k n     
Karena graf Banana Tree merupakan graf pohon, maka banyaknya sisi pada graf Banana Tree adalah
1 2 1 2 ( ( , ,..., )) ( ( , ,..., )) 1 k k E BT n n n V BT n n n   1 . k i i k n    
Akibatnya,  banyaknya  bilangan  positif  yang  dibutuhkan  untuk  melabeli  titik  dan sisi pada graf Banana Tree
1 2 ( , ,..., ) k BT n n n adalah
1 2 1 2 1 1 1 ( ( , ,..., )) ( ( , ,..., )) 1 =1+2( ) k k k k i i i i k i i V BT n n n
E BT n n n k n k n
k n             

## 3.   PELABELAN TOTAL SISI AJAIB PADA GRAF BANANA TREE
Bentuk khusus dari pelabelan total sisi ajaib adalah pelabelan super total sisi ajaib,  yaitu  pelabelan  total  sisi  ajaib  yang  label  titiknya  adalah  bilangan  positif terurut  1,  2,  …, ( ) V G .  Lemma  berikut  dapat  digunakan  sebagai  acuan  dalam menentukan sifat dalam himpunan kritis pada pelabelan graf.
Lemma  3.1 (Figueroa-Centeno  dkk.,  2001).  Sebuah  graf G dengan ( ) V G
menyatakan banyaknya titik  pada graf G dan ( ) E G menyatakan banyaknya sisi pada  graf G adalah  graf  super  total  sisi  ajaib  jika  dan  hanya  jika  terdapat  fungsi bijektif   : ( ) 1, 2,..., ( ) V G V G   sedemikian sehingga   ( ) ( ) ( ) S x y xy E G     
adalah sebuah himpunan yang terdiri dari bilangan bulat berturutan.  Selanjutnya,  disebut    pelabelan  super  total  sisi  ajaib  dari  graf G dengan  konstanta  ajaib
( ) ( ) h V G E G s
   dengan min{ } s z z S   dan   ( ) ( ) ( ) S x y xy E G
    
        ( ) 1 , ( ) 2 ,..., ( ) ( ) . h V G h V G h V G E G       
274                                                                                                           Triyani dan Irham Taufiq
Teorema  3.2. (Hussain,  dkk.,  2009).
1 2 ( , ,..., ) k G BT n n n  dikatakan  graf  super
total sisi ajaib jika 1 2 ... k n n n n     dan 1 2 k n k          .

## 4. BEBERAPA SIFAT HIMPUNAN KRITIS PADA PELABELAN AJAIB GRAF BANANA TREE
Menurut Imron dkk (2007), Sebuah himpunan kritis pada pelabelan suatu graf adalah subhimpunan label dan posisi label tersebut yang jika dilengkapi akan menghasilkan  pelabelan  tersebut  secara  tunggal.  Secara  sederhana  jika  diberikan subhimpunan  label  suatu  graf  dan  posisinya,  apakah  himpunan  tersebut  hanya membangun  graf  yang  sama  dengan  pelabelannya  secara  tunggal?  Jika  ya  maka himpunan tersebut adalah himpunan kritis.
Sebelum  menguraikan  sifat  himpunan  kritis  pada  graf
1 2 ( , ,..., ) k BT n n n , berikut  diberikan  contoh  label  posisi  (gambar  2a)  dan  pelabelan  graf  total  sisi ajaib  pada  graf BT( 1,1)  (gambar  2b).    Himpunan  pasangan  terurut  dari  label posisi  dan  pelabelan  total  sisi  ajaib  pada  graf BT(1,1) dapat  ditulis  sebagai  
(1, 4),(2,8),(3,1),(4,9),(5,3),(6,7),(7, 2),(8,6),(9,5) .  Setiap  satu  elemen  dari himpunan  pasangan  terurut  ini  bukan  merupakan  himpunan  kritis,  sebab  jika dipunyai  hanya  sebuah  pasangan  terurut  ini,  selalu  dapat  dikonstruksi  pelabelan super total sisi ajaib lain yaitu dengan menukar label titik daun dengan label sisi daun  yang bersisian dengan titik tersebut.   Akan tetapi jika dipunyai dua elemen yang  merupakan  kombinasi  dari  9  pasangan  terurut,  misal  (5,3)  dan  (9,5),  maka tidak  dapat  dikonstruksi  pelabelan  lain  selain  pelabelan  .  Hal  ini  berarti subhimpunan pasangan terurut {(5,3),(9,5)} merupakan himpunan kritis minimal. Beberapa  himpunan  kritis  minimal  pada  graf BT( 1,1)  yang  lain  adalah {(5,3),(8,6)},  dan  {(4,9),(9,5)}.  Subhimpunan  {(5,3),(1,4)}  bukan  himpunan kritis.  Karena  dengan  menukar  (8,6)  dengan  (8,5)  dan  (9,5)  dengan  (9,6)  ,  dapat dikonstruksi  pelabelan total  sisi  ajaib lain selain pelabelan total  sisi  ajaib λ  yaitu sebuah himpunan pasangan terurut  dari label  posisi  dan pelabelan total  sisi ajaib
Beberapa Sifat Himpunan Kritis                                                                                                275
baru {(1,4), (2,8), (3,1), (4,9), (5,3), (6,7), (7,2), (8,5), (9,6)}. Jadi himpunan kritis minimal pada graf BT(1,1) minimal anggotanya sebanyak 2.
1 4 5 2 3 6 7 8 9 1 2 3 4 5 6 7 8 9 (b) (a)
Gambar 2. Label posisi dan pelabelan total sisi ajaib pada graf BT(1,1)
Berdasarkan  hal  ini,  diperoleh  beberapa  sifat  himpunan  kritis  dalam pelabelan total sisi ajaib pada graf
1 2 ( , ,..., ) k BT n n n sebagai berikut:
Sifat 1. Himpunan    kritis   pada   graf Banana   Tree
1 2 ( , , ..., ) k BT n n n dengan n 1 = n 2 = … = n k = n, n  2 , k  2 minimal  anggotanya  sebanyak ( n -1 ) k dengan n menyatakan banyaknya titik daun dari graf bintang  dan k menyatakan banyaknya graf bintang.
Bukti: Misal λ menyatakan pelabelan total sisi ajaib pada graf
1 2 ( , ,..., ) k BT n n n , dan Q λ adalah himpunan kritis pada pelabelan λ. Andaikan ( 1) Q n k    artinya banyaknya  elemen  dalam Q λ kurang  dari  banyaknya  titik  daun  pada  graf
1 2 ( , , ..., ) k BT n n n . Akibatnya terdapat i dan j sedemikian hingga pasangan terurut ( c , x ij ) dan ( d , y ij ) dengan c, d menyatakan label posisi dan x ij , y ij masing-masing menyatakan  label  titik  daun  dan  label  sisi  daun  yang  bersisian  dengan  titik tersebut,  keduanya  tidak  berada  di Q λ .  Oleh  karena  itu,  pelabelan  total  sisi  ajaib yang  dapat  dikonstruksi  dari Q λ tidak  tunggal,  yaitu  dengan  menukar  pasangan terurut ( , ) dengan ( , ) ij ij c x c y dan ( , ) dengan ( , ) ij ij d y d x .  Hal  ini  kontradiksi dengan definisi himpunan kritis. Oleh karena itu, haruslah ( 1) Q n k    .
Sifat  2. Jika x adalah  label  dari  titik  daun v dan y adalah  label  dari  sisi  yang bersisian dengan v , maka setiap himpunan kritis dalam λ harus memuat x atau y , tapi tidak keduanya.
Bukti: Misalkan   12 13 , ,..., kn a a a adalah  himpunan  semua  titik  daun  dari  graf
Banana  Tree 1 2 ( , ,..., ) k BT n n n dan   12 13 , ,..., kn e e e adalah  himpunan  semua  sisi yang  bersisian  dengan  titik  daun.  Misal ( ) ij ij a x   menyatakan  label  titik  daun dan ( ) ij ij e y   menyatakan  label  sisi  daun  yang  bersisian  dengan  titik  daun a ij ,
dengan 1, 2,...,  dan 2, 3,..., i k j n   ,  sehingga ( , ) ij a x menyatakan  label x ij pada posisi a , dan ( , ) ij b y menyatakan label y ij pada posisi b . Akan ditunjukkan bahwa setiap  himpunan  kritis  dalam  pelabelan  harus  memuat    memuat ( , ) atau ( , ) ij ij a x b y , tapi tidak keduanya. Andaikan terdapat himpunan kritis yang memuat ( , ) dan ( , ) ij ij a x b y .  Berdasarkan  sifat  1  maka  terdapat  sedikitnya  sebuah titik v dan  sisi  daun  yang  bersisian  dengan v yang  tidak  termuat  di Q λ .  Dengan kata lain terdapat s dan t , sedemikian hingga ( c , x st ) dan ( d , y st ) keduanya tidak berada di himpunan kritis Q λ . Oleh karena itu, dapat dikonstruksi pelabelan total sisi  ajaib  λ’  dengan  cara  menukar  pasangan  terurut ( , ) dengan ( , ) st st c x c y dan
( , ) dengan ( , ) st st d y d x .  Akibatnya  pelabelan  total  sisi  ajaib  yang  dapat dikonstruksi  dari Q λ tidak tunggal. Hal  ini  kontradiksi dengan definisi himpunan kritis. Oleh karena itu, haruslah setiap himpunan kritis dalam pelabelan λ memuat
( , ) atau ( , ) ij ij a x b y , tapi tidak keduanya.

## 5. KESIMPULAN
Berdasarkan  penentuan  himpunan  kritis,  diperoleh  sifat  banyaknya anggota  minimal  dari  himpunan  kritis  pada  pelabelan  total  sisi  ajaib  graf
1 2 ( , ,..., ) k BT n n n adalah ( 1) n k  dengan n menyatakan banyaknya titik daun dari graf  bintang  dan k menyatakan  banyaknya  graf  bintang,  kecuali  himpunan  kritis pada graf BT( 1,1) , banyaknya anggota minimal adalah 2.  Setiap himpunan kritis
dalam pelabelan total sisi ajaib pada graf
1 2 ( , ,..., ) k BT n n n tidak memuat label titik daun  sekaligus  label  sisi  daun  yang  bersisian  dengan  titik  tersebut,  tetapi  harus salah  satu,  yaitu  memuat  label  titik  daun  atau  label  sisi  daun  yang  bersisian dengan titik tersebut.

## DAFTAR PUSTAKA
Baskoro,  E.  T.  2005. Critical  Sets  in  Edge-Magic  Total  Labellings,  Journal  of Combinatorial Mathematics and Combinatorial Computing, 55(1), 33-42 .
Baskoro,  E.  T.  2007. Mengenalkan  Indonesia  Melalui  Teori  Graf .  Pidato  Ilmiah Guru Besar ITB. Bandung.
Figueroa-Centeno, R. M., Ichisima, R., dan Muntaner-Batle, F. A 2001. The place of  super  edge-magic  labeling  among  other  classes  of  labeling,  Discreate Math . 231, 153-168.
Hussain,  M.,  Baskoro,  E.  T.,  dan  Slamin.  2009. On  super  edge-magic  total labeling of Banana Trees. Utilitas Math., Vol 79, 243-251.
Imron,  C.,  Setiyono,  B.,  Simanjuntak,  R.,  dan  Baskoro,  E.  T.  2007. Critical  Set  of Caterpillar Graph  for Secret Sharing Scheme, Proceeding IGGTIS, ITB-Bandung , 10-15.
Sudarsana,  I.  W.  dan  Junaidi.  2008. Secret  Sharing  Scheme  Based  on  Magic Labeling of  Star , Proceeding  of  International Converence and  Workshop  on Basic and Aplied Science (ICOWOBAS). UNAIR-Surabaya,  244-249.
278                                                                                                           Triyani dan Irham Taufiq