## PELABELAN FUZZY PADA GRAF
Siti Rahmah Nurshiami, Suroto, dan Fajar Hoeruddin Universitas Jenderal Soedirman
email : oeytea10@gmail.com
ABSTRACT . This paper discusses fuzzy labeling graph and its properties. The properties discussed are fuzzy labeling subgraph, union graph, and fuzzy magic graph. The results showed  that  the  strength  of  connectedness  for  pair  of  vertices  in  a  graph  with  fuzzy labeling  is  always  greater  than  or  equal  to  the  strength  of  connectedness  for  pair  of vertices in its subgraph. In addition, union of two graph with fuzzy labeling will form a graph with fuzzy labeling. Meanwhile, on magic labeling there is always a fuzzy bridge on fuzzy magic graph.
Keywords: Fuzzy labeling, fuzzy bridge, fuzzy magic graph
ABSTRAK .  Pada  makalah  ini,  dibahas  pelabelan  fuzzy  dan  sifatnya.  Sifat  terkait  yang dibahas pada makalah ini adalah pelabelan fuzzy subgraf, gabungan dua graf, dan graf ajaib  fuzzy.  Hasil  menunjukkan  bahwa  kekuatan  keterhubungan  sepasang  simpul  pada sebuah  graf  dengan  label  fuzzy  selalu  lebih  besar  atau  sama  dengan  kekuatan keterhubungan  sepasang  simpul  tersebut  di  subgrafnya.  Selain  itu,  gabungan  dua  graf dengan label fuzzy akan membentuk sebuah graf dengan pelabelan fuzzy. Sementara itu, pada pelabelan yang bersifat ajaib selalu terdapat jembatan fuzzy pada graf ajaib fuzzy.
Kata kunci : Pelabelan fuzzy, jembatan fuzzy, graf ajaib fuzzy

## 1. PENDAHULUAN
Perkembangan  ilmu  pengetahuan  tidak  pernah  terlepas  dari  peran  serta matematika  sebagai  alat  untuk  berbagai  ilmu  pengetahuan.  Hal  ini  disebabkan karena  matematika  dapat  diaplikasikan  dalam  bidang  disiplin  ilmu  lain  dalam mengatasi  permasalahan  baik  dalam  bentuk  perumusan,  logika,  pemodelan  dan metode  matematika  lainnya. Salah  satu  pokok  bahasan  dari  matematika  yang memiliki banyak terapan sampai saat ini adalah teori graf. Dalam bidang kajian ilmu matematika,  graf  merepresentasikan  objek-objek  diskrit  dan  hubungan  antara  objek- objek tersebut. Representasi visual dari graf adalah dengan menyatakan objek sebagai simpul, sedangkan hubungan di antara objek dinyatakan dengan sisi.
Seiring  perkembangannya,  banyak  teori  yang  berkaitan  dengan  graf diperkenalkan  sebagai  penemuan  baru.  Salah  satu  yang  menjadi  perhatian  baru dewasa  ini  adalah  tentang  teori  graf  fuzzy  yang  merupakan  pengembangan  dari konsep  himpunan  fuzzy  dan  graf  klasik.  Sejarah  perkembangan  himpunan  fuzzy dimulai pada tahun 1965 oleh Lotfi A. Zadeh yang mengangkat tentang fenomena ketidakpastian  pada  situasi  kehidupan  nyata  yang  dijelaskan  dalam  kerangka matematis.  Teori  ini  lahir  akibat  banyaknya  permasalahan  yang  tidak  bisa diselesaikan  hanya  dengan  himpunan  tegas,  karena  tidak  semua  himpunan  yang dijumpai dalam kehidupan sehari-hari terdefinisi secara jelas, misalnya himpunan orang  miskin,  himpunan  orang  pandai,  himpunan  orang  tinggi,  dan  sebagainya. Kemudian,  Bede  (2013)  mendefinisikan  himpunan  fuzzy  sebagai  suatu  fungsi yang memetakan semua elemen semestanya ke dalam interval tutup   0,1 .
Selanjutnya  menurut  Sunitha  (2001),  pada  tahun  1973  Kaufmann memperkenalkan gagasan tentang definisi graf fuzzy yang didasarkan pada relasi fuzzy  yang  dikembangkan  oleh  Zadeh.  Definisi  yang  lebih  terperinci  diberikan oleh  Rosenfeld  pada  tahun  1975  yang  mendefinisikan  sebuah  graf  fuzzy  dengan himpunan  simpul  fuzzy  dan  himpunan  sisi  fuzzy.  Seiring  dengan  semakin banyaknya  penelitian  tentang  graf  fuzzy  maka  konsep-konsep  dasar  teori  graf fuzzy  banyak  ditemukan  sebagai  hasil  generalisasi  dari  teori  graf.  Di  antaranya penelitian yang dilakukan oleh Gani dan Subahashini (2012) dan Gani, dkk (2014) mengenai  pelabelan  fuzzy  pada  suatu  graf.  Dalam  makalah  ini  akan  dibahas mengenai pelabelan fuzzy pada suatu graf beserta sifatnya.

## 2. METODE PENELITIAN
Metode  yang  digunakan  adalah  studi  literatur  mengenai  definisi  pelabelan fuzzy  yang  telah  dikaji  oleh  Gani  dan  Subahashini  (2012).  Adapun  langkah- langkah  dalam  melakukan  pelabelan  fuzzy  pada  sebuah  graf  dasar G adalah dengan  memberikan  fungsi  bijektif   yang  memetakan  seluruh  himpunan simpul  ke  himpunan   0,1 A  dan  fungsi  bijektif   yang  memetakan  seluruh himpunan sisi ke himpunan   0,1 . B  Selanjutnya, diberikan proposisi dan sifat
2                                                                                                          Siti Rahmah Nurshiami, dkk
yang berkaitan dengan pelabelan fuzzy dan contohnya. Dalam penelitian ini juga dibahas mengenai pelabelan fuzzy ajaib beserta sifat dan contohnya.

## 3. HASIL DAN PEMBAHASAN
Definisi 1. Misal V adalah himpunan simpul tak kosong dan E adalah himpunan sisi  pada  graf *( , ). G V E   Pelabelan  fuzzy  adalah  fungsi  bijektif   dan ,   dengan   memetakan simpul di  G * ke   0,1 A  dan   memetakan sisi di G * ke   0,1 B  sedemikian  sehingga  nilai fungsinya berbeda untuk semua titik dan
sisi, serta memenuhi ( , ) ( ) ( ) u v u v         untuk setiap , . u v V 
Contoh Misal  diberikan  graf * ( , ) G V E dengan   1 2 3 4 , , , V v v v v  dan   1 2 1 3 2 3 3 4 1 4 ( , ), ( , ), ( , ), ( , ), ( , ) . E v v v v v v v v v v  Selanjutnya,  diberikan  fungsi  bijektif
  dan   yang mengaitkan setiap simpul v x di G * dengan fungsi
1 ( ) 2 x v x    dan 2 2 1 ( , ) . ( ) x y v v x y     Graf ( , ) G       yang  merupakan  hasil  pelabelan fuzzy dari graf * G dapat direpresentasikan dalam Gambar 1.
Gambar 1 Graf ( , ) G       0,5 2 v 4 v 3 v 1 v 0,02 0,04 0,077 0,056 0,25 0,167 0,125
0,1
Pelabelan Fuzzy pada Graf                                                                                                             3
Definisi  2. Misalkan  graf ( , ) G       adalah  graf  dengan  pelabelan  fuzzy.
Graf ( , ) H       disebut  subgraf  dengan  pelabelan  fuzzy  dari  G  jika
memenuhi ( ) ( ) u u      untuk setiap u V  dan ( , ) ( , ) u v u v      untuk setiap
, . u v V 
Proposisi  3. Jika ( , ) H       adalah  subgraf  dengan  pelabelan  fuzzy  dari
( , ) G       maka ( , ) ( , ) u v u v        untuk setiap , . u v V  Bukti. Misalkan ( , ) G       adalah  sembarang  graf  dengan  pelabelan  fuzzy dan ( , ) H       adalah  subgraf  dengan  pelabelan  fuzzy  dari G  sehingga
berlaku ( , ) ( , ) u v u v      untuk  setiap  , . u v V  Ambil  sembarang  lintasan  di H  yang  menghubungkan  titik u dan v dengan  panjang  lintasan n misalkan lintasan 1 2 1 ( ) , , ,..., , n u v u v v v v    . Kekuatan  keterhubungan  diantara  dua  titik u dan v dapat dirumuskan sebagai
  ( , ) sup ( , ) | 1, 2,3,... k u v u v k n    
  
(1)
dengan
    1 1 2 2 3 1
( , ) sup ( , ) ( , ) ( , ) ... ( , ) , k k u v u v v v v v v v                
disebut  kekuatan  lintasan  dengan  panjang k. Perhatikan  kembali  bahwa  untuk sembarang titik u dan v berlaku ( , ) ( , ) u v u v      sehingga diperoleh 1 1 ( , ) ( , ), u v u v      1 2 1 2 ( , ) ( , ), v v v v      2 3 2 3 ( , ) ( , ), v v v v      1 1 ( , ) ( , ). n n v v v v     
 
Akibatnya,
1 1 2 1 1 1 2 1 ( , ) ( , ) ... ( , ) ( , ) ( , ) ... ( , ). n n u v v v v v u v v v v v                     
4                                                                                                          Siti Rahmah Nurshiami, dkk
Selanjutnya,
    1 1 2 2 3 1 1 1 2 2 3 1 ( , ) sup ( , ) ( , ) ( , ) ... ( , ) sup ( , ) ( , ) ( , ) ... ( , ) ( , ) k k k k u v u v v v v v v v u v v v v v v v u v         

         
 
         

Kemudian,  dengan  mensubtitusikan  pertidaksamaan ( , ) ( , ) k k u v u v      ke
persamaan (1) diperoleh

   ( , ) sup ( , ) | 1, 2,3,... sup ( , ) | 1, 2,3,... ( , ) k k u v u v k u v k u v              

## 
Jadi, terbukti bahwa untuk setiap  , u v V  berlaku ( , ) ( , ). u v u v       
Proposisi 4. Gabungan dari dua graf dengan label fuzzy 1 G  dan 2 G  merupakan graf dengan pelabelan fuzzy, jika nilai fungsi untuk setiap simpul dan sisi 1 G  dan
2 G  berbeda.
Bukti. Misal 1 1 1 ( , ) G   
   dan 2 2 2 ( , ) G   
   adalah  dua  graf  dengan pelabelan  fuzzy  yang  memiliki  nilai  fungsi  berbeda  untuk  setiap  sisi  antara 1 G  dan 2 . G 
Dengan demikian,
1 1 2 2 ( ) ( ), u u      1 1 2 2 2 ( ) ( , ), u u v      1 1 1 2 2 ( , ) ( ), u v u      dan 1 1 1 2 2 2 ( , ) ( , ) u v u v      untuk  setiap 1 1 1 , u v V  dan 2 2 2 , . u v V  Gabungan dari 1 G  dan 2 G  adalah graf ( , ) G       dengan   1 1 2 1 2 2 2 1 1 2 1 2 ( ),      untuk ( )( ) ( ),     untuk maks ( ), ( )  untuk x x V V x x x V V
x x x V V     
            
  
     

dan
  1 1 2 1 2 2 2 1 1 2 1 2 ( ),      untuk ( )( ) ( ),     untuk
maks ( ), ( )  untuk x x E E x x x E E x x x E E     
                       Selanjutnya, akan dibuktikan bahwa fungsi 1 2         adalah fungsi bijektif.
Untuk  membuktikan  sifat  injektif,  maka  harus  ditunjukkan  bahwa  jika , u v 
maka ( ) ( ) u v      untuk setiap 1 2 , . u v V V
  Ambil sembarang 1 2 , u v V V  
dengan . u v  Terdapat  tiga  kemungkinan  dalam  pengambilan  sembarang
1 2 , , u v V V   yakni  untuk
1 u V  dan 2 , v V  untuk u V  dan 1 2 , v V V   dan 1 2 , . u v V V   Jika 1 u V  dan 2 , v V  maka
1 ( ) ( ) u u     
2 ( ) v    ( ) v    sehingga diperoleh ( ) ( ). u v      Jika u V  dan 1 2 , v V V   maka 1 ( ) ( ) u u        1 2 maks ( ), ( ) v v        1 2 ( ) v       ( ) v    sehingga diperoleh ( ) ( ). u v      Jika 1 2 , , u v V V   maka
  1 2 ( ) maks ( ), ( ) u u u          1 2 maks ( ), ( ) v v        1 2 ( ) v
     
( ) v   
6                                                                                                          Siti Rahmah Nurshiami, dkk
sehingga  diperoleh ( ) ( ). u v     
Jadi,  fungsi 1 2         bersifat  injektif.
Selanjutnya,  misalkan  fungsi  untuk  simpul  didefinisikan
  1 1 1 : 0,1 , V A  
 
  2 2 2 : 0,1 , V A     dan   1 2 1 2 : ( ) ( ) 0,1 . V V A A A        Kemudian, akan ditunjukkan bahwa 1 2         bersifat surjektif. Artinya, untuk setiap a A 
selalu  terdapat 1 2 , u V V   sehingga ( ) . u a    Untuk 1 , a A  selalu  terdapat
1 1 u V  sedemikian  sehingga 1 1 ( ) . u a    Demikian  pula  untuk 2 , a A  selalu terdapat 2 2 u V  sedemikian  sehingga 2 2 ( ) . u a    Dengan  demikian,  terbukti bahwa 1 2         bersifat  surjektif.  Lebih  lanjut,  karena
1 2        
bersifat  injektif  sekaligus  surjektif,  maka
1 2         bijektif.  Dengan  cara yang sama, akan dibuktikan bahwa  fungsi
1 2         adalah fungsi  bijektif. Untuk membuktikan sifat injektif, maka harus ditunjukkan terlebih dahulu bahwa jika ( , ) ( , ), u v c d  maka berlaku ( , ) ( , ) u v c d      untuk setiap
1 2 ( , ), ( , ) . u v c d E E   Ambil sembarang 1 2 ( , ), ( , ) u v c d E E   dengan ( , ) ( , ). u v c d  Terdapat  tiga  kemungkinan  dalam  pengambilan  sembarang
1 2 ( , ), ( , ) , u v c d E E   yakni untuk 1 ( , ) u v E  dan 2 ( , ) c d E  maka 1 ( , ) ( , ) u v u v      2 ( , ) c d    ( , ) c d    sehingga  diperoleh ( , ) ( , ). u v c d      Untuk 1 ( , ) u v E  dan 1 2 ( , ) , c d E E   maka 1 ( , ) ( , ) u v u v        1 2 maks ( , ), ( , ) c d c d        1 2 ( , ) c d       ( , ) c d   
Pelabelan Fuzzy pada Graf                                                                                                             7
sehingga diperoleh ( , ) ( , ). u v c d     
Untuk 1 2 ( , ), ( , ) , u v c d E E   maka
  1 2 ( , ) maks ( , ), ( , ) u v u v u v          1 2 maks ( , ), ( , ) c d c d        1 2 ( , ) c d      
( , ) c d    sehingga  diperoleh
( , ) ( , ). u v c d      Jadi,  fungsi
1 2         bersifat
injektif.  Selanjutnya,  fungsi  untuk  sisi  didefinisikan  dengan
  1 1 1 : 0,1 , E B    
  2 2 2 : 0,1 , E B     dan   1 2 1 2 : ( ) ( ) 0,1 . E E B B B        Kemudian, akan  ditunjukkan  bahwa 1 2         bersifat  surjektif.  Artinya,  untuk  setiap b B  selalu  terdapat 1 2 ( , ) , u v E E   sehingga ( , ) . u v b    Untuk 1 , b B 
selalu  terdapat 1 1 1 ( , ) u v E  sedemikian  sehingga 1 1 1 ( , ) . u v b    Demikian  pula
untuk 2 , b B  selalu  terdapat 2 2 u V  sedemikian  sehingga 2 2 2 ( , ) . u v b    Dengan demikian, terbukti bahwa 1 2         bersifat surjektif. Lebih lanjut,
karena 1 2         bersifat  injektif  sekaligus  surjektif,  maka
1 2        
bijektif.Selanjutnya,  akan  ditunjukkan  bahwa  untuk  setiap , u v V  berlaku
1 2 1 2 1 2 ( )( , ) ( )( ) ( )( ). u v u v                  Jika  memperhatikan  asal  sisi
dari  setiap  sisi  di , G  maka  terdapat  tiga  kasus  berbeda  yang  harus  diselidiki,
yakni untuk 1 2 ( , ) , u v E E   2 1 ( , ) , u v E E   dan 1 2 ( , ) . u v E E   Kasus I: untuk 1 2 ( , ) . u v E E  
Jika  memperhatikan  asal  simpul  dari  setiap  sisi  di G  dengan 1 2 ( , ) . u v E E   maka terdapat tiga subkasus yakni
a. untuk 1 2 , u v V V   1 2 1 ( )( , ) ( , ) u v u v
       
1 1 ( ) ( ) u v
     
8                                                                                                          Siti Rahmah Nurshiami, dkk
1 2 1 2 ( )( ) ( )( ) u v            
b. untuk 1 2 u V V   dan 1 2 v V V     1 2 1 1 2 1 2 1 2 ( )( , ) ( ) ( ) ( )
( )( ) ( )( ) u v u v v
u v              
           
c. untuk
1 2 , u v V V       1 2 1 2 1 2 1 2 1 2 ( )( , ) ( ) ( )
( ) ( )
( )( ) ( )( ) u v u u v v u v                
            
Kasus II: untuk 2 1 ( , ) , u v E E  
Jika  memperhatikan  asal  simpul  dari  setiap  sisi  di G  dengan 2 1 ( , ) , u v E E  
maka terdapat tiga subkasus yakni
a. untuk 2 1 , u v V V   1 2 2 2 2 1 2 1 2 ( )( , ) ( , ) ( ) ( )
( )( ) ( )( ) u v u v u v
u v                          
b. untuk 2 1 u V V   dan 1 2 v V V     1 2 2 1 2 1 2 1 2 ( )( , ) ( ) ( ) ( ) ( )( ) ( )( ) u v u v v
u v                          
c. untuk
1 2 , u v V V       1 2 1 2 1 2 1 2 1 2 ( )( , ) ( ) ( ) ( ) ( ) ( )( ) ( )( ) u v u u v v u v          
   
 
        
   
Kasus III: untuk 1 2 ( , ) u v E E  
Jika  memperhatikan  asal  simpul  dari  setiap  sisi  di G  dengan
1 2 ( , ) u v E E  
maka hanya terdapat satu kemungkinan yakni untuk
1 2 , u v V V  
Pelabelan Fuzzy pada Graf                                                                                                             9
        1 2 1 2 1 1 2 2 1 2 1 2 1 2 1 2 ( )( , )
( , ) ( , )
< ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) (
)( ) ( )( ) u v u v u v u u v v u u v v u v                                              
Dengan demikian, terbukti bahwa
1 2 1 2 1 2 ( )( , ) ( )( ) ( )( ) u v u v                 
sehingga graf G  juga merupakan graf dengan pelabelan fuzzy.
Definisi 5. Graf dengan pelabelan fuzzy pada graf dikatakan graf ajaib fuzzy jika
( ) ( , ) ( ) u u v v         memiliki  nilai  konstanta  ajaib  yang  sama  untuk  setiap
, u v V  yang dinotasikan dengan 0 ( ). m G
Proposisi  6. Jika G  adalah  graf  dengan  pelabelan  fuzzy  ajaib,  maka G  setidaknya memiliki satu jembatan fuzzy.
Bukti. Misal G  adalah  graf  dengan  pelabelan  fuzzy  ajaib.  Pilih  sebuah  sisi ( , ) x y yang  memiliki  label  tertinggi  dari  himpunan V. Dengan  demikian,  untuk setiap  simpul , u v V  pasti  memenuhi ( , ) ( , ). u v x y      Kekuatan keterhubungan antara simpul x dan y adalah
  1 2 3 ( , ) sup ( , ), ( , ), ( , )... ( , ) k x y x y x y x y x y                 1 1 1 1 2 1 ( , ), sup ( , ) ( , ) ,..., sup sup ( , ) ( , ) ... ( , ) k x y x y y y x y y y y y               

         
( , ) x y   
Selanjutnya,  jika  sisi ( , ) x y dihilangkan  sehingga ( , ) 0. x y    Misal    kekuatan keterhubungan antara simpul x dan y adalah
1 1
' ( , ) ' ( , ) x y u v       untuk suatu
1 1 , , u v V  maka
10                                                                                                       Siti Rahmah Nurshiami, dkk
1 1 ' ( , ) ' ( , ) ( , ) ( , ) x y u v x y x y             
Dengan demikian, kekuatan keterhubungan  antara simpul x dan y menjadi  lebih kecil  dari  sebelumnya  atau ' ( , ) ( , ). x y x y       
Karena  penghapusan  sisi
( , ) x y pada  graf G mengurangi  kekuatan  keterhubungan  antara  simpul x dan y , maka  sisi ( , ) x y adalah  jembatan  fuzzy.  Dengan  demikian,  terbukti  bahwa  untuk sembarang graf ajaib selalu terdapat minimal satu jembatan fuzzy.

## 4. KESIMPULAN DAN SARAN

## 4.1 Kesimpulan
Berdasarkan  hasil  dan  pembahasan,  maka  diperoleh  kesimpulan    bahwa pelabelan fuzzy merupakan fungsi bijektif yang memetakan semua simpul dan sisi pada  graf  dasar G *  ke  himpunan   0,1 sedemikian  sehingga  label  sisinya  selalu lebih kecil dari minimum kedua simpul yang bersisian dengannya. Gabungan dari dua  graf  dengan  pelabelan  fuzzy  merupakan  graf  dengan  pelabelan  fuzzy  jika semua label simpul dan sisi di kedua graf tersebut berbeda. Graf dengan pelabelan fuzzy ( , ) G V E  dikatakan  graf  ajaib  fuzzy  jika ( ) ( , ) ( ) u u v v        
memiliki  nilai  yang  sama  untuk  setiap , . u v V  Selalu  terdapat  jembatan  fuzzy pada sembarang graf ajaib fuzzy.

## 4.2 Saran
Dari hasil penelitian ini, dapat dilakukan penelitian lebih lanjut mengenai graf ajaib fuzzy, menentukan formulasi konstanta ajaib fuzzy pada beberapa graf khusus, serta membahas aplikasi dari pelabelan fuzzy pada sebuah graf.
Pelabelan Fuzzy pada Graf                                                                                                            11

## DAFTAR PUSTAKA
Bede,  B.  (2013). Mathematics  of  Fuzzy  Sets  and  Fuzzy  Logic. New  York: Springer.
Gani, A. N. dan Subahashini, A. R. (2012). Properties of Fuzzy Labeling Graph. Applied Mathematical Sciences. 6(70):3461-3466.
Gani, A. N. Akram, M. dan Subahashini, A. R. (2014). Novel Properties of Fuzzy Labeling Graphs. Journal of Mathematics . 375135.
Sunitha, M. (2001). Studies On Fuzzy Graphs . Cochin: Cochin University
12                                                                                                       Siti Rahmah Nurshiami, dkk