PELABELAN SUPER GRACEFUL PADA GRAPH Griselda Afrian Y, Purwanto, dan Lucky Tri Oktoviana Universitas Negeri Malang ABSTRAK: Pelabelan pada suatu graph adalah pemetaan yang memetakan unsur-unsur graph yaitu himpunan titik, himpunan sisi maupun himpunan titik dan sisi ke suatu bilangan (biasanya bilangan bulat positif atau non negatif) yang disebut label. Pelabelan super graceful pada graph , adalah pemetaan bijektif 1,2, … , sedemikian | . Pada penulisan ini sehingga masing-masing sisi uv mendapat label | ditunjukkan bahwa graph !" dapat dilabeli dengan pelabelan super graceful karena !" adalah graph super graceful. Graph !" adalah graph caterpillar graph regular dengan semua titik yang bergantung disetiap titik pada lintasan mempunyai jumlah sama. Pembuktian dilakukan dengan cara mengkontruksikan himpunan pelabelan titik dan himpunan pelabelan sisinya. Kemudian diberikan beberapa contoh pelabelan super graceful pada graph !" . Dari pembahasan diperoleh bahwa pelabelan pada graph !" untuk # $ 1 dan $ 1 merupakan pelabelan super graceful dengan himpunan pelabelan titik dan sisinya, % 1,2, … ,2 # 1 1 1 . Semua himpunan label titik mempunyai nilai ganjil dan himpunan label sisi mempunyai nilai genap. Pelabelan pada graph !" dikerjakan dengan cara melabeli titik terlebih dahulu kemudian dilanjutkan dengan melabeli sisi. Kata Kunci: graph, pelabelan, pelabelan super graceful, graph
!"
Teori graph adalah salah satu cabang dari ilmu matematika yang penting dan banyak manfaatnya karena teori-teorinya dapat diterapkan dalam kehidupan seharihari. Salah satu contoh penerapan teori graph adalah pelabelan graph. Joseph A. Gallian dalam jurnal yang berjudul A Dynamic Survey of Graph Labelling (2011) menjelaskan bahwa pelabelan graph adalah suatu pemberian nilai pada titik atau sisi dari graph atau keduanya sehingga memenuhi kondisi tertentu. Dalam jurnal tersebut juga menjelaskan bahwa pelabelan graph pertama kali diperkenalkan pada akhir tahun 1960. Sebagian besar metode pelabelan graph diperkenalkan oleh Rosa, kemudian yang lainnya oleh Graham dan Sloane pada tahun 1980. Terdapat beberapa macam dalam pelabelan graph, salah satunya adalah pelabelan graceful. Dalam jurnal yang berjudul Super Graceful Labeling for Some Simple Graph (Perumal dkk,2012:35), mendefinisikan tipe baru pelabelan yakni pelabelan super graceful. Pelabelan super graceful didefinisikan sebagai pemetaan bijektif 1,2, … , pada graph G (p,q) sedemikian sehingga & ' . f ( u ) − f ( v ) untuk setiap sisi
Yang sering digunakan saat ini adalah pelabelan ajaib, baik pelabelan sisi ajaib maupun pelabelan total ajaib. Masih sedikit skripsi yang mengkaji mengenai pelabelan graceful yakni Pelabelan Graceful Ganjil pada Graph Pn ∪ Cm oleh Dewi Kurniantini (2012). Berdasarkan uraian diatas maka akan dibahas teori tipe pelabelan baru, yakni pelabelan super graceful yang telah dibuktikan dalam jurnal Super Graceful Labeling for Some Simple Graph (Perumal dkk,2012:35) pada beberapa
1
graph salah satunya Graph !" , sehingga disusunlah skripsi yang berjudul “Pelabelan Super Graceful pada Graph !" ”. Dari penulisan yang dilakukan diharapkan memperoleh tujuan yaitu antara lain : (1) Menunjukkan dan memamahami bahwa pelabelan pada !" adalah pelabelan graph super graceful, (2) Menunjukkan bahwa semua himpunan label titik mempunyai nilai ganjil dan himpunan label sisi mempunyai nilai genap, (3) Memahami cara pengerjaan pelabelan super graceful pada graph !" . KAJIAN PUSTAKA Graph Dalam jurnal yang ditulis oleh Perumal dkk (2012) yang berjudul Super Graceful labeling for some simple graphs dijelaskan bahwa sebuah graph terhubung yang tidak mempunyai sikel disebut pohon, sebuah pohon T disebut caterpillar, jika penghapusan semua titik yang bergantung akan tetap menghasilkan lintasan. Jika jumlah titik yang bergantung pada tiap titik di lintasan berjumlah sama, maka graph tersebut disebut graph caterpillar regular, dan dinotasikan dengan atau !" . Secara umum Graph # !1 mempunyai jumlah titik sebanyak # 1 1 titik dan # 1 1 1 sisi. Sehingga jumlah titik dan sisinya |=2 # 1 adalah | 1 1 dengan #, bilangan asli. & Pelabelan Wallis dkk (2000:178) menyatakan bahwa “pelabelan pada suatu graph adalah pemetaan yang memetakan unsur-unsur pada suatu graph (titik atau sisi) ke bilanganbilangan (biasanya ke bilangan bulat positif atau bilangan bulat non negatif). Jika domain dari pemetaan adalah titik, maka pelabelannya disebut pelabelan titik (vertex labeling). Jika domainnya adalah sisi maka pelabelannya disebut pelabelan sisi (edge labeling), dan jika domainnya adalah titik dan sisi maka pelabelannya disebut pelabelan total (total labeling). Selanjutnya dalam jurnal yang berjudul A Dynamic Survey of Graph Labeling (Gallian, 2011) dijelaskan terdapat beberapa macam pelabelan pada graph, diantaranya adalah pelabelan graceful dan pelabelan ajaib. Dalam jurnal Perumal dkk, (2012:35), Rosa mendefinisikan pelabelan graceful pada graph G dengan sisi merupakan pemetaan injektif dari himpunan titik di G ke himpunan 0,1,2, … sedemikian sehingga masing-masing sisi uv mendapat label | |, menghasilkan label sisi yang berbeda semua. Kotzig dan Rosa dalam Joseph A. Gallian (2011:77) mendefinisikan pelabelan ajaib dari suatu graph , | , sehingga untuk masingadalah fungsi bijektif dari ke 1,2,3, … , | masing sisi *+di berlaku * + *+ % ,, dengan , konstanta. PEMBAHASAN Dalam jurnal Super Graceful labeling for some simple graphs (Perumal,dkk 2012) telah membuktikan bahwa Graph !" adalah graph Super Graceful, !" untuk membuktikan hal tersebut maka perlu dibuktikan bahwa Graph dapat dilabeli dengan pelabelan super graceful.
2
Teorema : !" adalah graph super graceful untuk # $ 1 dan $ 1. Bukti : Misal - , " , . , … , adalah titik dari lintasan . Dengan titik yang bergantung /," , /,. , … , /,0 tepat di masing-masing / , 0 1 2 1 #. Sehingga | !" | % # 1 1 dan | !" | % # 1 1 1 Kemudian definisikan fungsi pelabelannya !" & !" 1,2, … , 2 # 1 1 1 sebagai berikut : % 2 # 1 1 1 1 2# 2 2 1, 0 1 2 1 #, 2 4 0 #562 8 / % 3 1 2 1 1, 0 1 2 1 #, 2 4 1 #562 . Untuk 0 1 2 1 # dan 2 4 0 #562 , 9 /,: ; % 1 2 2< 1, 1 1 < 1 dan Untuk 0 1 2 1 # dan 2 4 1 #562 , 9 /,: ; % 1 2# 3 2 2< 1 , 1 1 < 1 Sehingga dari pelabelan titik-titik tersebut dapat dikontruksikan himpunan pelabelan titiknya sebagai berikut : 1. Himpunan titik-titik untuk v> genap "
%
% atau
%
/4/4-
?
/
/@AB.
1 2#
?
/@AB.
1 2#
2
1,
2
2
1
1 2#
1, … ,
1 #
2
1
% 1 2# 2 1, 1 2# 1, … , 1 # 3 1 Sehingga himpunan titik-titik / untuk 0 1 2 1 # dengan 2 4 0 #56 2 !" adalah 1 2# 2 1, 1 2# dalam pelabelan grap 1, … , 1 # 2 1 untuk # yang bernilai genap atau 1 2# 2 1, 1 2# 1, … , 1 # 3 1 untuk # yang bernilai ganjil. 2. Himpunan titik-titik untuk / ganjil .
%
%
(atau)
?
/@" /4" AB. /4"
% 2
% 2
?
/@" AB.
1
1
/
1 2
1, 4
1, 4
1
1
1
1
1, 6
1
1, 6
1
3
1, … , #
1, … , #
1
1
1
1
1
Sehingga himpunan titik-titik / untuk 1 1 2 1 # dengan 2 4 1 #56 2 dalam pelabelan grap !" adalah 2 1 1, 4 1 1, 6 1 1, … , # 1 1 untuk # yang bernilai genap atau 2 1 1, 4 1 1, 6 1 1, … , # 1 1 1 untuk # yang bernilai ganjil. 3. Himpunan titik-titik /,: yang bergantung pada / genap H
%
% %
?
I?J 9
?
I?
/@/4AB. /@/4AB. /4-
0
?
:@" 0
:@"
/@AB .
/,: ;KL
1 2 1 2
% 1,3,5, … ,2 1 2 1 2 1 4 1 2 1 …,# 1 2
1, 2
1
4 …
1
1L
1 2
1
3,
1, 2 1 1, 4 # 1
1 2
1
5, … ,
3, 2 1 3, 4 1, # 1
1
1 2
2
5, …, 1 5, …, 3, # 1
1 5,
% 1,3,5, … ,2 1 2 1 1, 2 1 3, 2 1 5, …, 2 1 2 1 … # 1 1 1, # 1 1 3, # 1 1 5, … , # 1 1 2 1 Sehingga himpunan titik-titik / untuk 0 1 2 1 # dengan 2 4 0 #56 2 dalam pelabelan grap !" adalah 1,3,5, … ,2 1 2 1 1, 2 1 3, 2 1 5, … , 2 1 2 1 4 1 1, 4 1 3, 4 1 5, … ,4 1 2 1 … # 1 1, # 1 3, # 1 5, … , # 1 2 1 untuk # yang bernilai genap atau 1,3,5, … ,2 1 2 1 1, 2 1 3, 2 1 5, … , 2 1 2 1 … # 1 1 1, # 1 1 3, # 1 1 5, …, # 1 1 2 1 untuk # yang bernilai ganjil. 4. Himpunan titik-titik /,: yang bergantung pada / ganjil (atau)
N
%
%
0
?
I?J 9
?
I?
/@" /4" AB. /@" /4" AB.
:@" 0
:@"
/,: ;KL
1 2#
3
4
2
2<
1 L
%
?
1 2#
/@/4AB .
%
2
3,
1 2#
3
2
5, … , 1 2# 3 2 2 1 2 3, 1 2# 2 5, … , 1 2# 2 2 1 2# 3, 1 2# 5, … , 1 2# 2 1 1 # 4 3, 1 # 4 5, … , 1 # 4 2 1
1 2#
1
… (atau) %
3
1 2# 2 3, 1 2# 2 5, … , 1 2# 2 2 1 1 2# 3, 1 2# 5, … , 1 2# 2 1 … 1 # 3 3, 1 # 3 5, … , 1 # 3 2 1 Sehingga himpunan titik-titik / untuk 1 1 2 1 # dengan 2 4 1 #56 2 dalam pelabelan grap !" adalah 1 2# 2 3, 1 2# 2 5, … , 1 2# 2 2 1 1 2# 3, 1 2# 5, … , 1 2# 2 1 … 1 # 4 3, 1 # 4 5, … , 1 # 4 2 1 untuk # yang bernilai genap atau 1 2# 2 3, 1 2# 2 5, … , 1 2# 2 2 1 1 2# 3, 1 2# 5, … , 1 2# 2 1 … 1 # 3 3, 1 # 3 5, … , 1 # 3 2 1 untuk # yang bernilai ganjil. 1. Himpunan pelabelan sisi dimana / genap dan /O" ganjil "
P"
%
?
% %
?
/@/4AB . P"
/4-
%
% % Atau
/@/4AB . P"
/ /O"
|
/
|
/O"
JQ9
1 2#
2
2
1;
?
|
1 2#
2
2
2
?
|
1 2#
22 |
?
|2
?
/@AB . P"
/4-
/@AB . P"
/@/4AB . P" /4-
/@AB .
% 2
1 #, 2
1 #
2 |
1 #
2 ,2 5
9
1 2
2
1;QK
2 |
1 #
4 , … ,4
1
% 2
1 #, 2
1 #
2 ,2
1 #
4 , … ,2
1
Jadi himpunan sisi untuk / genap dan /O" ganjil adalah 2 1 #, 2 1 # 2 ,2 1 # 4 , … ,4 1 untuk m bernilai genap atau 2 1 #, 2 1 # 2 ,2 1 # 4 , … ,2 1 untuk m bernilai ganjil. 2. Himpunan pelabelan sisi dimana / ganjil dan /O" genap .
%
%
P"
?
/@" /4" AB . P"
?
|
?
JQ9
?
|
1 2
?
|
1 22
/4"
%
/@" AB . P"
/@" /4" AB . P"
% %
/4"
/@" AB . P"
/4"
% 2
/ /O"
/@" AB .
/
1 2
1 #
|
/O"
1
1;
1
1 ,2
1 2#
2#
2
2# | % 1 #
2
/4"
P"
2
2
1
1 QK
1 |
?
/@" AB .
3 ,…,2
|2
1
2 |
1 #
% 2 1 # 1 ,2 1 # 3 ,…,4 1 Jadi himpunan sisi untuk / ganjil dan /O" genap adalah 2 1 #, 2 1 # 2 ,2 1 # 4 , … ,2 1 untuk m bernilai genap atau 2 1 #, 2 1 # 2 ,2 1 # 4 , … ,4 1 untuk m bernilai ganjil. 3. Himpunan pelabelan sisi untuk sisi yang bergantung pada / genap Atau
H
%
% %
/4-
?
/@AB .
0
I?J 9 :@" 0
?
I?JQ
?
I?JQ9
/@/4AB . /@/4AB .
:@" 0
:@"
/ /,: ;KL /
9
/,: ;QKL
1 2#
2
6
2
2;
9
1 2
2<
1;QKL
% % % %
?
I? |
1 2#
?
I? 2
1 #
?
I? 2|
1 #
1
2
<| L
?
I?J29
1 #
1
2
1;, 29
1
2
/@/4AB .
/4/4-
0
/@AB . /@AB . /@AB .
/4-
:@" 0
:@" 0
:@" 0
:@"
2;, … , 2
% 29
2 1
22 2
1 #
2<| L 2< L
1 #
1
2
KR
1 # 1 1;, 29 1 # 1 2;, … , 2 1 # 1 J29 1 # 1 1;, 29 1 # 1 2;, … , 29 ;K … J29 1 # 3 1;, 29 1 # 3 1 # 1 2;, … , 29 1 # 3 ;K … 2 , 2 2, … , 2
% 29
1 # 1 1;, 29 1 # 1 2;, … , 2 1 # 1 29 1 # 1 1;, 29 1 # 1 2;, … , 2 1 # 1 … 4 2,4 , 4 2, … , 2 4 1 # Jadi himpunan sisi yang bergantung pada / genap adalah J29 1 1;, 29 1 # 1 2;, … , 29 1 # 1 ;K J29 1 # 1 1;, 29 1 # 1 2;, … , 29 1 # 1 ;K … J29 1;, 29 1 # 3 2;, … , 29 1 # 3 ;K … 1 # 3 2 ,2 2, … , 2 untuk m bernilai genap atau J29 1 # 1 1;, 29 2;, … , 29 1 # 1 ;K J29 1 # 1 1;, 29 1 # 1 2;, … , 29 1 # 1 ;K … 4 2,4 , 4 2, … , 2 1 # 1 4 untuk m bernilai ganjil. 4. Himpunan pelabelan sisi yang bergantung pada / ganjil Atau
N
%
/4"
?
/@" AB .
0
I? J 9 :@"
/ /,: ;KL
7
% %
% % % % %
?
I? JQ
?
I? |
/@" /4" AB . /4"
/@" AB .
/4" /4"
0
:@"
0
9
/
:@"
/,: ;QKL
1 2
1
1
I? |
1 2
?
I? |
1 22
2#
?
I?
1 2#
2
22
?
I? 2
1 #
1
2
?
J29
2
1;, 29
/@" AB . /@" AB . /@" AB .
/@" /4" AB .
1 2#
2
2
2
2<| L
1
2<
1| R
?
/@" /4" AB . /4"
0
:@" 0
:@" 0
:@" 0
:@"
1 #
1
1
2#
2 2
1
2<| L 2< L 2< L 1 #
1
2
2;, … , 2 1 # 1 2 K % J29 1 # 1;, 29 1 # 2;, … , 29 1 # ;K 29 1 # 2; 1, 29 1 # 2; 2 , … , 29 1 # … 2 2 1 1 ,2 2 1 2 ,…,2 2 1
1 # 1;, 29 1 # 2;, … , 29 1 # ;K 1 # 2; 1, 29 1 # 2; 2 , … , 29 1 # 2; K … J29 1 1;, 29 1 2;, … , 29 1 ;K Jadi himpunan sisi yang bergantung pada / ganjil adalah J29 1 # 1;, 29 1 # 2;, … , 29 1 # ;K J29 1 # 2; 1, 29 1 # 2; 2 , … , 29 1 # 2; K … 2 2 1 1 ,2 2 1 2 ,…,2 2 1 untuk m bernilai genap atau J29 1 #
Atau
% J29 J29
2;
8
1;, 29 1 # 2;, … , 29 1 # ;K J29 1 # 2; 2 , … , 29 1 # 2; K … 2;, … , 29 1 ;K untuk m bernilai ganjil. Contoh -
"
-,"
-,.
23 22
1
","
",.
.,"
Gambar Graph
14
20
16
3
21
19
Gambar Graph
S
S
17
12
H,"
.,.
T
6
H,.
11
10
8
4
7
9
15
T
1
H
.
5
18
1 # 2; 1, 29 J29 1 1;, 29
2
13
dengan pelabelan super graceful
PENUTUP Kesimpulan Berdasarkan hasil penelitian dan pembahasan pada bab sebelumnya, dapat !" adalah graph super disimpulkan bahwa: (1) dapat diketahui bahwa graph graceful untuk # $ 1 dan $ 1 sehingga pelabelan pada graph !" merupakan pelabelan super graceful dengan himpunan pelabelan titik dan sisinya, % 1,2, … ,2 # 1 1 1 , (2) Semua himpunan label titik mempunyai nilai ganjil dan himpunan label sisi mempunyai nilai genap, (3) Pelabelan !" dikerjakan dengan cara melabeli titik terlebih super graceful pada graph dahulu, dan dilanjutkan dengan melabeli sisi. Saran Hasil dari penulisan yang telah dilakukan memberikan saran-saran kepada pembaca agar dapat mengembangkan penulisan ini dan menggunakannya sebagaimana mestinya. Adapaun saran-saran tersebut adalah: (1) Masih ada beberapa jenis graph lain yang dapat dikenakan pelabelan super graceful selain graph !" dalam jurnal yang ditulis oleh M.A Perumal, dkk (2012) yang berjudul super graceful labeling for some simple graphs, misalnya graph U0 , graph Coconut tree, graph ! ,0 dan graph lainnya yang sehingga disarankan bagi para pembaca untuk bisa lebih mengkajinya, (2) Selain pelabelan super graceful, masih ada jenis 9
pelabelan lain yang belum dibahas, misalnya pelabelan graceful genap yang dapat dikenakan pada beberapa jenis graph tertentu, sehingga disarankan bagi para pembaca untuk bisa lebih mengkajinya.
DAFTAR RUJUKAN Afianti. 2008. Pelabelan Total Ajaib pada sikel C dalam Graph Whell dengan Bilangan Ganjil. Skripsi tidak diterbitkan. Malang. Fakultas Ilmu Pengetahuan Alam dan Matematika. Universitas Negeri Malang. Aldous, Joan M. and Wilson, Robin J. 2004. Graph and Applications An Introductory Approach. Great Britain: Springer. Gallian, Joseph A. 2011. A Dynamic Survey of Graph Labeling. The Electronic Journal of Combinatorics, 18 (DS6). (online), (http://cs.anu.edu.au/publications /eljc/Survey/ds6.pdf), diakses 22 Agustus 2012. Hayati, Nurul. 2008. Pelabelan Sisi Ajaib pada Graph Tanpa Titik Pusat dan Titik Tergantung dengan Panjang Sikel 3 U V, 3 . Skripsi tidak diterbitkan. Malang. Fakultas Ilmu Pengetahuan Alam dan Matematika. Universitas Negeri Malang. Johnsonbaugh, Richard. 2001. Discrete Mathematics. United States of America: Prentice-Hall. Lorentz, Thereziea. 2009. Pelabelan Super Sisi Ajaib pada Graph Ulat (caterpillars) yang Mempunyai n Badan dan 2n Kaki dengan n Bilangan Asli. Skripsi tidak diterbitkan. Malang. Fakultas Ilmu Pengetahuan Alam dan Matematika. Universitas Negeri Malang. Perumal, M.A. , Navaneethakrishnan,S., and Nagarajan,A. 2012. Super Graceful Labeling for Some Simple Graphs. International Journal on Applications of mathematics and soft computing, (Online), (http://www.ijmsc.com/index.php/ ijmsc/article/view/63/pdf), diakses 9 agustus 2012. Rahmawati, Ika. 2009. Pelabelan Total Sisi Ajaib pada Graph 2 1 . . Skripsi tidak diterbitkan. Malang. Fakultas Ilmu Pengetahuan Alam dan Matematika. Universitas Negeri Malang. Wallis, W.D., Baskoro, Edy T., Miller, Mirka and Slamin. 2000. Edge-Magic Total Labeling. Australasian Journal of Combinatorics, (Online), 22 (1): 177-190, (http://ajc.maths.uq.edu.au/pdf/22/ocr-ajc-v22-p177.pdf), diakses 3 Maret 2012.
10
