## BEBERAPA ALGORITMA PELABELAN GRACEFUL UNTUK GRAF CATERPILLAR

## SOME GRACEFUL LABELING ALGORITHM FOR CATERPILLAR GRAPHS
Regina N. Pakpahan 1 , Patricia V. J. Runtu 2 , Meidy A. Kuron 3
A BSTRACT
Graceful  labeling,  first  introduced  by  Rosa  as  β - labeling.  A  graceful  labeling  (or  β - labeling) on a graph G involves assigning labels to its set of vertices, forming an injective function f that  maps  each vertex  to  the  set  of  non-negative integers  {0,  1,  2,  ...,  |E(G)|}, where  |E(G)|  denotes the number  of  edges in  G.  This  induces a  bijective function f* that maps  the  edges  of  G  to  the  set  of  positive  integers  {1,2,...,|E(G)|}  which  the  edges  label obtained by absolute number of the subtraction between 2 neighboring vertex labels. One renowned  conjecture  proposed  by  Kotzig-Ringel-Rosa,  known  as  the  Graceful  Tree Conjecture  (GTC),  posits  that  all  trees  are  graceful.  To  this  day,  this  remains  an  open problem,  challenging  researchers  to  substantiate  its  validity.  The  quest  for  graceful labeling, particularly for specific types of trees, continues to be an active zona of research. Notably, caterpillar graphs have been established as graceful. It is worth noting that not all  graphs  possess  a  unique  labeling.  For  instance,  in  the  case  of  graceful  labeling  for caterpillar  graphs,  there  exist  four  distinct  methods,  which  will  be  elucidated algorithmically in this article. By demonstrating various approaches to labeling caterpillar graphs, it is hoped that this concept can be extended to other graceful labelings, ultimately contributing to the identification of more graceful trees
Keywords : graph labeling, graceful labeling, caterpillar graph

## 1. PENDAHULUAN
Pelabelan graceful diperkenalkan oleh Rosa [1] pertama kali dengan nama pelabelan β. Pelabelan β selanjutnya dikenal dengan istilah pelabelan graceful. Pelabelan graceful (atau pelabelan β ) pada graf G  adalah  pelabelan  pada  himpunan  simpul  dengan  ketentuan  membentuk  fungsi f injektif  yang memetakan setiap simpul pada elemen himpunan bilangan bulat {0, 1, 2, ..., |E(G)|} dengan |E(G)| adalah banyaknya  busur  yang  ada  pada  graf  G,  sedemikian  sehingga  menginduksi  fungsi f *  bijektif  dimana fungsi f * adalah fungsi yang memetakan busur-busur yang ada pada graf G pada himpunan bilangan asli {1,2,...,|E(G)|} dengan ketentuan label busur yang diperoleh adalah mutlak dari pengurangan antara 2 label simpul yang bertetangga [2] . Salah satu konjektur terkenal yang dikemukakan oleh Kotzig-Ringel- Rosa [3] , yang dikenal dengan Graceful Tree Conjecture (GTC) mengatakan bahwa semua graf pohon adalah graceful. Konjektur ini sampai sekarang masih menjadi masalah terbuka bagi para peneliti untuk membuktikan  kebenarannya,  dan  pencarian  pelabelan  graceful  untuk  beberapa  jenis  pohon  tertentu masih menjadi subjek penelitian aktif. Salah satu jenis pohon yang sudah dibuktikan merupakan graceful yaitu graf caterpillar. Graf caterpillar adalah pohon yang jika semua simpul berderajat satu dihapus maka yang  tertinggal  adalah  suatu  lintasan [4] .  Tidak  selamanya  pelabelan  suatu  graf  itu  tunggal.    Seperti contoh, pada pelabelan graceful untuk graf caterpillar. Ada 4 cara berbeda pelabelan graceful untuk graf caterpillar yang akan dibuktikan dalam bentuk algoritma pada artikel ini. Dengan menunjukkan beragam cara  berbeda  untuk  melabeli  graf  caterpillar,  diharapkan  selanjutnya  konsep  yang  sama  bisa dikombinasikan untuk pelabelan-pelabelan graceful lainnya, agar semakin banyak graf pohon yang bisa dibuktikan merupakan graceful.
1 Universitas Negeri Manado Tondano, Sulawesi Utara, Indonesia regina.natalia@unima.ac.id
2 Universitas Negeri Manado Tondano, Sulawesi Utara, Indonesia patricia_runtu@unima.ac.id
3 Universitas Negeri Manado Tondano, Sulawesi Utara, Indonesia meidykuron@unima.ac.id

## 2. KAJIAN PUSTAKA
Pelabelan  graceful  pertama  kali  diperkenalkan  oleh  Rosa [1] dengan  nama  pelabelan β .  Dalam papernya Rosa memperkenalkan 4 pelabelan graf: pelabelan α, pelabelan β , pelabelan σ , pelabelan ρ. Hirarki Rosa adalah hirarki dari keempat pelabelan tersebut, yaitu sebagai berikut:
Pelabelan α  Pelabelan β  Pelabelan σ  Pelabelan ρ
Sebagai contoh, tiap pelabelan α juga merupakan pelabelan β , pelabelan σ , dan pelabelan ρ . Tetapi pelabelan β belum  tentu  merupakan  pelabelan α .  Lebih  jelasnya,  Rosa  mendefinisikan  misalkan  O G adalah pelabelan dari graf G dengan n busur ( a i adalah label dari simpul v i di O G ) dan memenuhi syarat- syarat berikut:
a)
⊂ {0, 1, … , };
b) ⊂ {0, 1, … , 2 };
c) ≡ {1, 2, … , }; d) ≡ { , , … , } , dimana x i = i atau x i = 2n + 1 – i,
e) Ada x , dengan x ∈ {0, 1, … , n }, sedemikian sehingga untuk sebarang busur ( v i , v j ) dari graf G, salah satu syarat a i ≤ x, a j > x, atau a i > x, a j ≤ x berlaku.
Pelabelan yang memenuhi syarat:
(a), (c), (e) disebut pelabelan α (a), (c) disebut pelabelan β (b), (c) disebut pelabelan σ (b), (d) disebut pelabelan ρ
Salah satu konjektur terkenal yang sampai saat ini menjadi open problem dalam topik pelabelan graf  dikenal  dengan  Kotzig-Ringel-Rosa [3] ,  yaitu Graceful  Tree  Conjecture (GTC). Graceful  Tree Conjecture mengatakan  bahwa  semua  graf  pohon  adalah  graceful.  Dalam  upaya  untuk  membuktikan konjektur  ini,  para  peneliti  telah  membuktikan  berbagai  macam  graf  pohon  adalah  graceful.  Salah satunya adalah graf caterpillar.
Menurut Haviar, M., Ivaska, M [5] , graf caterpillar adalah graf pohon yang jika simpul-simpul daun (simpul berderajat 1) dihapus, akan menghasilkan graf lintasan. Sedangkan Md Momin Al Aziz dkk [6] mengatakan bahwa graf caterpillar adalah graf lintasan dengan 2 daun atau graf pohon dimana semua simpul berderajat 1 atau 2. Graf lintasan yang dimaksud disebut backbone dari graf caterpillar. Dalam graf caterpillar, terdapat istilah simpul daun dan simpul akar. Simpul daun adalah simpul berderajat 1 pada graf caterpillar. Sedangkan simpul akar adalah simpul-simpul pada graf lintasan yang terbentuk jika simpul-simpul daun dihapus. [7] . Gambar 1 di bawah ini merupakan contoh dari graf caterpillar.
Gambar 1. Graf Caterpillar
Rosa [1] telah  membuktikan  dalam  artikelnya  bahwa  graf  caterpillar  adalah  graceful.  Selain  itu, Haviar, M., Ivaska, M [5] juga telah membuktikan dalam artikelnya bahwa graf caterpillar adalah graceful seperti di bawah ini.
Simpul Akar
Simpul Daun
Teorema 1. ( Haviar, M., Ivaska, M [5] )
Graf G berukuran m adalah caterpillar jika dan hanya jika terdapat barisan pelabelan (j 1 , j 2 , … , j m ) dari G sedemikian sehingga
0 ≤ − ≤ 1 untuk setiap ∈ {1, 2, … , − 1}

## 3. METODE PENELITIAN
Metode  penelitian  yang  digunakan  dalam  penelitian  ini  adalah  metode  penelitian kepustakaan. Menurut Sugiyono [8] penelitian  kepustakaan  merupakan  kajian  teoritis,  referensi  serta  literatur  ilmiah lainnya  yang  berkaitan  dengan  budaya,  nilai  dan  norma  yang  berkembang  pada  situasi  sosial  yang diteliti.
Jenis  penelitian  yang  digunakan  dalam  penelitian  ini  adalah  penelitian  studi  literatur.  Metode studi literatur adalah serangkaian kegiatan yang berkenaan dengan metode pengumpulan data pustaka, membaca dan mencatat, serta mengelolah bahan penelitian. [9]
Menurut  Kuhlthau  dalam  Mirzaqon  dan  Purwoko [10] ,  langkah-langkah  metode  penelitian kepustakaan adalah sebagai berikut:
1. Pemilihan topik
2. Eksplorasi informasi
3. Menentukan fokus penelitian
4. Pengumpulan sumber data
5. Persiapan penyajian data
6. Penyusunan laporan

## 4. HASIL DAN PEMBAHASAN
Dalam  penelitian  ini,  peneliti  akan  membahas  4  cara  berbeda  untuk  melabeli  graf  caterpillar dengan pelabelan graceful. Misalkan sebuah graf G, memiliki:
a x : Simpul-simpul akar pada graf G, dengan x = 1, 2, … , p , dimana p adalah banyaknya simpul akar. Ketentuan urutan simpul-simpul akar dilihat dari kiri ke kanan atau dari atas ke bawah.
: Simpul-simpul daun pada graf G, dengan x adalah indeks dari simpul akar dimana simpul daun tersebut terhubung dengan q x adalah banyaknya simpul daun dari simpul akar x .
n : banyaknya simpul di graf G. ( n = p + q 1 + q 2 + … + q p )
k :
l :
Maka:
Algoritma 1. top down dengan simpul 0 berada di simpul akar pertama.
1. Beri label a 1 dengan 0.
2. Beri label a x dengan − ∑ ( + 1) , dengan x bilangan genap, dan x ≤ p. 3. Beri label a x dengan ∑ ( + 1) , dengan x bilangan ganjil, x > 1, dan x ≤ p .
4. Beri label d x untuk x bilangan genap dan x < p berurutan dimulai dengan label terkecil yang belum dipilih.
Untuk kasus q 2 ≠ 0, maka pelabelan dimulai d 2 dari angka 1, 2, … , q 2 , dan dilanjutkan dengan melabeli d x dimulai dari a x-1 + 1, … , a x-1 + q x , x > 2 Untuk  kasus q 2 =  0,  maka  pelabelan  dimulai  dari  d 4 dari  angka  2,  3,    …, q 4 untuk  p  >  3,  dan dilanjutkan dengan melabeli d x dimulai dari a x-1 + 1, … , a x -1 + q x , x > 4.
5. Beri  label d x dengan x bilangan  ganjil  dan x <  p  berurutan  dimulai  dengan  label  terbesar  yang belum dipilih, n , n – 1, … , n – q 1 , dan dilanjutkan dengan melabeli d x dimulai dari a x-1 – 1, … , a x -1 – q x , x > 1.
6. Beri label d p dengan: untuk p bilangan ganjil dimulai dari a p + 1, … , a p + q p . untuk p bilangan genap dimulai dari a p – 1, … , a p – q p .
Algoritma 2. top down dengan simpul n berada di simpul akar pertama.
1. Beri label a 1 dengan n.
2. Beri label a x dengan ∑ ( + 1) , dengan x bilangan genap, dan x ≤ p.
3. Beri label a x dengan − ∑ ( + 1) , dengan x bilangan ganjil, x > 1, dan x ≤ p.
4. Beri label d x untuk x bilangan genap dan x < p berurutan dimulai dari a x-1 – 1, … , a x -1 – q x . 5. Beri label d x dengan x bilangan ganjil dan x < p berurutan dimulai dengan label terkecil 0, 1, … Untuk kasus q 1 ≠ 0, maka pelabelan dimulai d 1 dari angka 0, 1, … , q 1 – 1, dan dilanjutkan dengan melabeli d x dimulai dari a x-1 + 1, … , a x-1 + q x , x > 1 Untuk  kasus q 1 =  0,  maka  pelabelan  dimulai  dari  d 3 dari  angka  1,  2,  …, q 3 untuk  p  >  3,  dan dilanjutkan dengan melabeli d x dimulai dari a x-1 + 1, … , a x -1 + q x , x > 3 6. Beri label d p dengan: untuk p bilangan ganjil dimulai dari a p – 1, …, a p – q p untuk p bilangan genap dimulai dari a p + 1, …, a p + q p
Algoritma 3. bottom up dengan simpul 0 berada di simpul akar terakhir.
1. Beri label a p dengan 0.
Untuk p ganjil:
2. Beri label a x dengan ∑ ( + 1) − ∑ ( + 1) , dengan x bilangan ganjil.
3. Beri label a x dengan + ∑ ( + 1) , dengan x bilangan genap 4. Beri label d x untuk x bilangan ganjil dan x < p dimulai dari a 1 + 1, …, a 1 + q 1 , dan dilanjutkan dengan melabeli d x dimulai dari a x-1 + 1, … , a x-1 + q x , x > 1.
5. Beri label d x dengan x bilangan genap dan x < p berurutan dimulai dari a x-1 – 1, …, a x – q x 6. Beri label d p dimulai dari label terbesar n , n – 1, …, n – q p .
Untuk p genap:
2. Beri label a x dengan ∑ ( + 1) − ∑ ( + 1) , dengan x bilangan genap
3. Beri label a x dengan + ( + 1) + ∑ ( + 1) , dengan x bilangan ganjil
4. Beri label d x untuk x bilangan ganjil dan x < p dimulai dari a 1 – 1, …, a 1 – q 1 , dan dilanjutkan dengan melabeli d x dimulai dari a x-1 – 1, … , a x-1 – q x , x > 1.
5. Beri label d x dengan x bilangan genap dan x < p berurutan dimulai dari a x-1 + 1, … , a x-1 + q x , x >1. 6. Beri label d p dimulai dari label terbesar n , n – 1, …, n - q p
Algoritma 4. bottom up dengan simpul n berada di simpul akar terakhir.
1. Beri label a p dengan n.
Untuk p ganjil:
2. Beri label a x dengan ( ∑ ( + 1)) − ( ∑ ( + 1)) − 1 , dengan x bilangan genap 3. Beri label a x dengan + ( + 1) + ∑ ( + 1) , dengan x bilangan ganjil.
4. Beri label d x untuk x bilangan ganjil dan x < p dimulai dari a 1 – 1, …, a 1 – q 1 , dan dilanjutkan dengan melabeli d x dimulai dari a x-1 – 1, … , a x-1 – q x , x > 1.
5. Beri label d x dengan x bilangan genap dan x < p berurutan dimulai dari a x-1 + 1, …, a x + q x 6. Beri label d p dimulai dari label terkecil 0, 1, … q p – 1.
Untuk p genap:
2. Beri label a x dengan ( ∑ ( + 1)) − ( ∑ ( + 1)) − 1 , dengan x bilangan ganjil 3. Beri label a x dengan + ( + 1) + ∑ ( + 1) , dengan x bilangan genap
4. Beri label d x untuk x bilangan ganjil dan x < p dimulai dari a 1 + 1, …, a 1 + q 1 , dan dilanjutkan dengan melabeli d x dimulai dari a x-1 + 1, … , a x-1 + q x , x > 1 5. Beri label d x dengan x bilangan genap dan x < p berurutan dimulai dari a x-1 – 1, … , a x-1 – q x , x >1. 6. Beri label d p dimulai dari label terkecil 0, 1, … q p – 1.

## Bukti.
Untuk membuktikan bahwa graf adalah graceful, maka harus ditunjukkan:
(1) Ada fungsi f injektif yang memetakan setiap simpul pada elemen himpunan bilangan bulat {0, 1, 2, ..., |E(G)|} dengan |E(G)| adalah banyaknya busur yang ada pada graf G
(2) Ada fungsi f * bijektif dimana fungsi f * adalah fungsi yang memetakan busur-busur yang ada pada graf G pada himpunan bilangan asli {1,2,...,|E(G)|} dengan ketentuan label busur yang diperoleh adalah mutlak dari pengurangan antara 2 label simpul yang bertetangga.

## Pada Algortima 1:
Pembuktian  (1)  jelas  dari  algoritma,  karena  pelabelan  dimulai  dari a 1 dengan  label  0,  kemudian dilanjutkan dengan melabeli dengan 1, 2, … n . Untuk kasus p ganjil, maka dimulai dari a 1 , d 2 , a 3 , d 4 , …, d p-1 , a p , dp , a p-1 , d p-2 , … , d 1 . Sedangkan untuk kasus p genap, maka dimulai dari a 1 , d 2 , a 3 , d 4 , …, a p-1 , d p , a p , d p-2 untuk d 2 , a 3 , … , d p .
Pembuktian (2) pelabelan akan menghasilkan pasangan-pasangan dimana a x akan berpasangan dengan d x+1 . Dimulai dari a 1 dan d 1 , dimana a 1 = 0, dan d 1 yang dimulai dari bilangan terbesar n (Langkah 5) akan menghasilkan label busur terbesar, n , yang akan menurun hingga pada a p dan d p , dimana langkah keenam jelas menunjukkan label busur terkecil yaitu 1.

## Pada Algortima 2:
Pembuktian  (1)  jelas  dari  algoritma,  karena  pelabelan  dimulai  dari a 1 dengan  label  0,  kemudian dilanjutkan dengan melabeli dengan 1, 2, … n . Untuk kasus p ganjil, maka dimulai dari a 1 , d 2 , a 3 , d 4 , …, d p-1 , a p , dp , a p-1 , d p-2 , … , d 1 . Sedangkan untuk kasus p genap, maka dimulai dari a 1 , d 2 , a 3 , d 4 , …, a p-1 , d p , a p , d p-2 untuk d 2 , a 3 , … , d p .
Pembuktian (2) pada algoritma 2 sama dengan algoritma 1, karena nilai mutlak dari hasil pengurangan 2 simpul yang bertetangga akan bernilai sama. Artinya label busur algoritma 1 dan algoritma 2 sama.

## Pada Algortima 3:
Pembuktian  (1)  jelas  dari  algoritma,  karena  pelabelan  dimulai  dari a 1 dengan  label  0,  kemudian dilanjutkan dengan melabeli dengan 1, 2, … n . Untuk kasus p ganjil, maka dimulai dari a 1 , d 2 , a 3 , d 4 , …, d p-1 , a p , dp , a p-1 , d p-2 , … , d 1 . Sedangkan untuk kasus p genap, maka dimulai dari a 1 , d 2 , a 3 , d 4 , …, a p-1 , d p , a p , d p-2 untuk d 2 , a 3 , … , d p .
Pembuktian (2) pelabelan akan menghasilkan pasangan-pasangan dimana a x akan berpasangan dengan d x+1 . Dimulai dari a 1 dan d 1 , dimana langkah keempat jelas menunjukkan label terkecil, label busur akan membesar hingga pada a p dan d p dimana a p = 0 dan d p dimulai dengan label terbesar n (Langkah 6) akan menghasilkan label busur terbesar n .

## Pada Algortima 4:
Pembuktian  (1)  jelas  dari  algoritma,  karena  pelabelan  dimulai  dari a 1 dengan  label  0,  kemudian dilanjutkan dengan melabeli dengan 1, 2, … n . Untuk kasus p ganjil, maka dimulai dari a 1 , d 2 , a 3 , d 4 , …, d p-1 , a p , dp , a p-1 , d p-2 , … , d 1 . Sedangkan untuk kasus p genap, maka dimulai dari a 1 , d 2 , a 3 , d 4 , …, a p-1 , d p , a p , d p-2 untuk d 2 , a 3 , … , d p .
Pembuktian (2) pada algoritma 4 sama dengan algoritma 3, karena nilai mutlak dari hasil pengurangan 2 simpul yang bertetangga akan bernilai sama. Artinya label busur algoritma 3 dan algoritma 4 sama.
Berikut  adalah  contoh  graf  caterpillar  yang  sudah  diberi  pelabelan  graceful  berbeda  sesuai  masing- masing algoritma
Gambar 2. (a) Pelabelan dengan algoritma 1, (b) Pelabelan dengan algoritma 2, (c) Pelabelan dengan algoritma 3, (d) Pelabelan dengan algoritma 4

## 5. KESIMPULAN
Graf  caterpillar  merupakah  graf  yang  mempunyai  pelabelan  graceful.  Cara  melabeli  graf caterpillar secara graceful ada 4 cara berbeda, yaitu dengan cara top down dengan simpul 0 berada di simpul  akar  pertama,  dengan  cara top  down dengan  simpul n berada  di simpul  akar pertama,  dengan cara bottom  up dengan  simpul  0  berada  di  simpul  akar  terakhir,  dan  dengan  cara bottom  up dengan simpul n berada di simpul akar terakhir. Penelitian ini diharapkan bisa berkontribusi untuk menunjukkan ada  beragam  cara  untuk  melabeli  graf  caterpillar,  dan  selanjutnya  bisa  dikombinasikan  dengan pelabelan-pelabelan graceful lainnya, agar semakin banyak graf pohon yang bisa dibuktikan merupakan graceful,  dalam  rangka  untuk  membuktikan Graceful Tree  Conjecture . Pada  penelitian  di  masa  yang akan datang, diharapkan peneliti selanjutnya bisa menemukan algoritma pelabelan graf caterpillar jika simpul 0 nya berada di sebarang simpul akar dari graf caterpillar atau sebarang simpul daun dari graf caterpillar.

## DAFTAR PUSTAKA
[1]   Rosa, A. (1967). On certain valuations of the vertices of a graph. Jurnal Theory of Graphs, Proc. Internat. Symposium,Rome, 1966, Gordonand Breach, N.Y. and Dunod Paris, pp. 349–355.
[2]   N. Parvathi & S. Vidyanandini (2014) Graceful Labeling of a Tree from Caterpillars , Journal of Information and Optimization Sciences, 35:4, 387-393, DOI: 10.1080/02522667.2014.961811
[3]  G,  Ringel.  (1963). Theory  of  graphs  and  its  applications ,  Proceedings  of  the  Symposium Smolenice. held in Smolenice in June, 1963. New York, pp. 85–90.
[4]  Hossain, F., Aziz, M.A., & Kaykobad, M. (2014) New Classes of Graceful trees , Journal of Discrete Mathematics, vol. 2014, Article ID 194759, 6 pages. DOI: 10.1155/2014/194759
[5]  Haviar,  M.,  Ivaska,  M.  (2014). Vertex  Labellings  of  Simple  Graph .  Research  and  Exposition  in Mathematics. Banska Bystrica (34) pp. 72–74.
[6]  M. M. Al Aziz, M. F. Hossain, T. Faequa and M. Kaykobad,. (2014). Graceful labeling of trees: Methods and applications . 17 th International Conference on Computer and Information Technology (ICCIT), Dhaka, Bangladesh, 2014. pp. 92-95. DOI: 10.1109/ICCITechn.2014.7073154.
[7]  Sugeng, K.A., Slamet, S., Silaban, D.R. (2014). Teori Graf dan Aplikasinya . Depok: Departemen Matematika FMIPA UI.
[8]  Sugiyono. (2012). Metode Penelitian Kuantitatif, Kualitatif, dan R&D . Bandung: Alfabeta.
[9]  Zed, M. (2008). Metode Penelitian Kepustakaan . Jakarta : Yayasan Obor Indonesia.
[10] Mirzaqon.  T,  A  dan  Budi  Purwoko.  (2017). Studi  Kepustakaan  Mengenai  Landasan  Teori  dan Praktik Konseling Expressive Writing . Jurnal BK Unesa, 8(1).