## ALGORITMA PELABELAN GRACEFUL UNTUK GRAF BINTANG MULTI-LEVEL

## GRACEFUL LABELING ALGORITHM FOR MULTI-LEVEL STAR GRAPH
Regina N. Pakpahan 1 , Maria Y. Manuel 2

## A BSTRACT
Graph theory is a topic in mathematics that is still relatively new and developing rapidly. Graph  theory  is  used  to  simplify  and  solving  problems  like  connection,  networking, travelling  or  flow.  One  of  the  very  interesting  topics  in  graph  theory  is  graph  labeling. 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.  The  Graceful  Tree Conjecture  (GTC)  posits  that  all  trees  can  be  gracefully  labeled,  a  hypothesis  still unproven. The quest for graceful labeling, particularly for specific types of trees, continues to be an active zona of research. One of the graph that already proven can be labeled with graceful labeling is  star  graph.  Now  we  gonna prove  graceful labeling for star  graph,  if each leaf in the star graph is connected to m new leaves. We call it multi-level star graph. Exploring these  methods aims  to extend  the concept to other  graphs,  contributing  to the identification of more gracefully labeled trees.
Keywords : graph labeling, graceful labeling, star graph

## 1. PENDAHULUAN
Pelabelan graceful diperkenalkan oleh Rosa [1] pertama kali dengan nama pelabelan β. Pelabelan β selanjutnya dikenal dengan istilah pelabelan graceful. Pelabelan graceful 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).  GTC mengatakan  bahwa  semua  graf  pohon  adalah graceful.  Namun  sampai  saat  ini, konjektur  tersebut masih  belum  bisa  dibuktikan,  dan  menjadi open problem bagi para peneliti. Salah satu jenis pohon yang sudah dibuktikan merupakan graceful yaitu graf bintang. Graf bintang adalah pohon dengan banyaknya simpul n + 1, memiliki satu simpul pusat v 0 yang terhubung dengan n simpul daun. [4] . Graf bintang sudah dibuktikan merupakan graceful . Kali ini kita akan  membuktikan  pelabelan  graceful  untuk  graf  bintang  jika  masing-masing  daun  di  graf  bintang dihubungkan dengan m daun baru, yang selanjutnya akan kita sebut graf bintang multi-level.

## 2. KAJIAN PUSTAKA

## A. Jenis-Jenis Graf
Menurut  Sugeng,  dkk [4] ,  graf  bintang  (S n )  adalah  graf  pohon  dengan  banyaknya  simpul n +1, memiliki satu simpul pusat v 0 yang terhubung dengan n simpul daun. Dalam graf bintang, terdapat istilah simpul  pusat  v 0 dan n simpul  daun. Simpul  pusat  (v 0 ) adalah  simpul  yang  berada  di  tengah,  dan
1 Universitas Negeri Manado Tondano, Sulawesi Utara, Indonesia regina.natalia@unima.ac.id
2 Universitas Negeri Manado Tondano, Sulawesi Utara, Indonesia mariamanuel@unima.ac.id
terhubung  dengan  semua  simpul-simpul  daun  pada  graf  bintang.  Sedangkan simpul  daun adalah simpul-simpul pada graf bintang yang terhubung dengan simpul pusat.
Graf  lengkap  adalah  graf  sederhana  di  mana  setiap  pasangan  simpul  saling  bertetangga.  Graf lengkap dengan n simpul dilambangkan dengan K n. [5]
Gambar 1. (a) Graf Bintang S 6 , (b) Graf Lengkap K 6

## B. Operasi Pada Graf
Komplemen ̅ dari  graf G adalah  salah satu  operasi  dalam  graf. ̅ memiliki  himpunan simpul yang sama dengan graf G , dimana simpul x dan y bertetangga di ̅ jika dan hanya jika kedua simpul tersebut tidak bertetangga di G. {6]
Dalam  graf,  terdapat juga  operasi komposisi.  Komposisi  adalah  salah  satu  dari  banyak  operasi yang  dapat  dilakukan  pada  graf  untuk  menghasilkan  graf  baru  dari  dua  atau  lebih  graf  yang  ada. Misalkan  graf  G 1 =(V 1 ,  E 1 )  dan  G 2 =(V 2 ,  E 2 )  adalah  2  graf  dengan  himpunan  simpul  V 1 dan  V 2 dan himpunan busur E 1 dan E 2 . Graf komposisi G 1 ○ G 2 adalah graf yang memiliki himpunan simpul yang merupakan pasangan terurut dari simpul-simpul G 1 dan G 2 . [7]

## C. Pelabelan Graceful
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 bintang.
Haviar, dkk [8] telah membuktikan dalam artikelnya bahwa graf bintang adalah graceful. Pelabelan graf  bintang  dimulai  dengan  memberi  label  0  pada  simpul  pusatnya,  dilanjutkan  dengan  melabeli n simpul  daunnya  dimulai  dari  label  1  hingga  label n .  Berikut  adalah  contoh  graf  bintang  yang  telah dilabeli.
Gambar 2. Graf Bintang yang telah dilabeli
Berikutnya, akan didefinisikan graf baru yang merupakan multi-level dari graf bintang, dan akan dibuktikan merupakan graceful.

## 3. METODE PENELITIAN
Metode  penelitian  yang  digunakan  dalam  penelitian  ini  adalah  metode  penelitian kepustakaan. Menurut Sugiyono [9] 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. [10]
Menurut Kuhlthau (2002) dalam Mirzaqon dan Purwoko [11] , 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  memberikan  algoritma  serta pembuktian  pelabelan  graceful untuk graf bintang multi-level.
Definisi  1. Graf  Bintang  Multi-Level.  Graf  bintang  multi-level  adalah  graf  bintang,  yang dikomposisikan dengan komplemen dari graf lengkap K m . Dengan kata lain, masing-masing daunnya dihubungkan dengan m simpul baru ( ∘ ).
Gambar 3. Graf Bintang Multi-Level ∘
Teorema 1. Graf Bintang Multi-Level adalah graceful.
Sebelum menuliskan algoritma dan membuktikannya, pertama-tama akan disepakati terlebih dahulu keterangan berikut.
Simpul pusat (v 0 ) : simpul yang berada ditengah, yang menjadi pusat dari graf bintang Simpul daun dalam ( T i )  : simpul daun dari graf bintang awal, dengan i = 1, 2, … , n
Simpul daun luar ( T ij )  : simpul daun baru yang dihubungkan pada masing-masing simpul daun dalam, dengan j = 1, 2, … , m
Algoritma.
1. Labeli simpul pusat ( v 0 ) dengan 0.
2. Labeli m simpul daun luar yang terhubung pada salah satu simpul daun dalam dengan 1, 2, … , m .
3. Labeli simpul daun dalam yang simpul daun luarnya belum diberi label dengan m +1.
4. Lanjutkan dengan melabeli m simpul daun luar yang terhubung pada salah satu simpul daun dalam yang belum diberi label dengan m +2, m+ 3, …, 2 m +1.
5. Labeli simpul daun dalam yang simpul daun luarnya belum diberi label dengan 2 m +2.
6. Lakukan pelabelan secara selang seling hingga pasangan T i dan T ij yang bersesuaian hanya salah satunya yang memiliki label. Jika n ganjil, maka hingga melabeli simpul daun luar dengan
+ , +
+ 1, … , + . Jika n genap, maka hingga melabeli simpul daun dalam dengan + .
7. Jika n ganjil, maka labeli simpul daun dalam yang bersesuaian dengan simpul daun luar yang
terakhir dilabeli dengan
+ . Jika n genap, maka labeli simpul daun luar yang
bersesuaian dengan simpul daun dalam yang terakhir dilabeli dengan
+ , + +
1, … , + 1 + .
8. Lakukan kembali pelabelan secara selang seling simpul daun dalam dan simpul daun luar yang bersesuaian secara mundur, mulai dari label terbesar ke label terkecil.
Berikut adalah contoh graf bintang yang diperbesar setelah diberi pelabelan graceful.
Gambar 4. Graf bintang multi-level yang telah dilabeli secara graceful

## 5. KESIMPULAN
Graf  bintang  multi-level  merupakan  graf  yang  mempunyai  pelabelan  graceful.  Pelabelan dilakukan  selang  seling  dimulai  dari  simpul  daun  luar  kemudian  simpul  daun  dalam  sesuai  dengan algoritma yang telah diberikan. Penelitian ini diharapkan bisa berkontribusi 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 pohon lainnya, terutama yang berhubungan dengan graf bintang multi-level, jika ada penambahan level lagi lebih dari 2 level, atau jika daun-daun baru yang ditambahkan tidak harus berjumlah sama.

## 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]  Sugeng, K.A., Slamet, S., Silaban, D.R. (2014). Teori Graf dan Aplikasinya . Depok: Departemen Matematika FMIPA UI.
[5]  Gladkov, L. (2018). Topics in graph theory. AMS/MAA Textbooks. , DOI: 10.1090/text/041/13
[6]  Godsil, C., Royle, G. (2001). Algebraic Graph Theory . New York: Springer. pp 5–6
[7]  Bondy, J., & Murty, U. (2008). Graph Theory , 1-582. DOI: 10.1007/978-1-84628-970-5.
[8]  Haviar,  M.,  Ivaska,  M.  (2014). Vertex  Labellings  of  Simple  Graph .  Research  and  Exposition  in Mathematics. Banska Bystrica (34) pp. 72–74.
[9]  Sugiyono. (2012). Metode Penelitian Kuantitatif, Kualitatif, dan R&D . Bandung: Alfabeta.
[10] Zed, M. (2008). Metode Penelitian Kepustakaan . Jakarta : Yayasan Obor Indonesia.
[11] Mirzaqon.  T,  A  dan  Budi  Purwoko.  (2017). Studi  Kepustakaan  Mengenai  Landasan  Teori  dan Praktik Konseling Expressive Writing . Jurnal BK Unesa, 8(1).