JURNAL SAINS DAN SENI POMITS Vol. 2, No.1, (2013) 2337-3520 (2301-928X Print)
1
Pelabelan Super Sisi Ajaib pada Subkelas Pohon Rohmatul Izzah dan Darmaji Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Teknologi Sepuluh Nopember (ITS) Jl. Arief Rahman Hakim, Surabaya 60111 E-mail:
[email protected] Abstrak—Misalkan adalah graf dengan himpunan simpul dan himpunan sisi . Suatu pemetaan dari ke dimana adalah order dan adalah ukuran disebut pelabelan super sisi ajaib jika merupakaan pemetaan bijektif dan dipetakan ke sehingga dan sedemikian sehingga masingmasing sisi di berlaku , dengan konstanta yang disebut juga bilangan ajaib. Pada Tugas Akhir ini, dilakukan pelabelan pada caterpillar teratur , firecracker teratur dan banana tree teratur dengan dan bilangan bulat positif sehingga memenuhi syarat pelabelan super sisi ajaib. Setelah mendapatkan label, selanjutnya menentukan pola pelabelan pada simpul dan sisi tersebut sehingga diperoleh bilangan ajaib kemudian menganalisa bilangan ajaib yang diperoleh tersebut. Kata Kunci—Banana Tree, Caterpillar, Firecracker, Pelabelan Super Sisi Ajaib.
T
I. PENDAHULUAN
eori graf pertama kali dikenalkan oleh Leonhard Euler pada tahun 1736, ketika mendiskusikan bagaimana caranya agar dapat melewati empat daerah yang terhubung dengan tujuh jembatan di sungai Pregel di Konigsberg Rusia tanpa harus melewati satu jembatan lebih dari satu kali [1]. Dengan mengaji dan menganalisis model atau rumusan, teori graf dapat ditunjukkan peranan dan kegunaannya dalam memecahkan berbagai permasalahan salah satunya diselesaikan dengan pelabelan graf seperti masalah sektor sistem komunikasi, transportasi, navigasi geografis, radar, penyimpanan data komputer, dan juga desain sirkuit gabungan pada komponen elektronik [2]. Pelabelan pada suatu graf merupakan pemetaan unsur himpunan simpul atau unsur himpunan sisi ke bilangan asli yang disebut label. Studi dari pelabelan pada graf telah memfokuskan pada penemuan graf-graf tertentu yang memiliki pelabelan tertentu, sehingga ada banyak jenis pelabelan, di antaranya adalah pelabelan total sisi ajaib dan pelabelan super sisi ajaib. Penelitian pelabelan super sisi ajaib terus berkembang, hal tersebut dapat diketahui dari banyaknya artikel tentang pelabelan super sisi ajaib dalam beragam kelas graf. Pada tahun 2001 Selvam Avadayappan dkk., melakukan penelitian tentang pelabelan super sisi ajaib pada graf sikel ( ) dan diperoleh [3], kemudian Hikoe Enomoto dkk., melakukan penelitian tentang pelabelan super sisi ajaib pada graf bipartite lengkap untuk atau dan
diperoleh [4]. Sejauh ini pelabelan super sisi ajaib pada subkelas pohon belum banyak diteliti. Dengan merujuk pada [5], pada Tugas Akhir ini dilakukan penelitian pelabelan super sisi ajaib pada caterpillar teratur , firecracker teratur dan banana tree teratur . II. PENGERTIAN GRAF Graf didefinisikan sebagai pasangan himpunan , ditulis dengan notasi , dengan adalah himpunan tak kosong dari simpul-simpul, dan adalah himpunan sisi yang menghubungkan sepasang simpul [6]. Graf terhubung yang tidak mengandung sikel dinamakan pohon [7]. Caterpillar diperoleh dengan menghubungkan simpul pusat dari graf bintang secara berurutan [8]. Firecracker diperoleh dengan menghubungkan satu simpul anting dari graf bintang secara berurutan [9]. Banana Tree adalah sebuah graf yang didapat dengan menghubungkan satu simpul anting dari setiap buah salinan graf bintang ke sebuah simpul baru yang disebut simpul akar [9].
(a)
Gambar 1. (a) Caterpillar
(b)
(c) , (b) Firecracker
, (c) Banana Tree
Pelabelan total sisi ajaib pada suatu graf dengan order dan ukuran adalah fungsi bijektif dari ke sehingga untuk masing-masing sisi di berlaku , dengan konstanta. Konstanta disebut juga bilangan ajaib (magic sum) [3].
Gambar 2. Pelabelan Total Sisi Ajaib
Pelabelan super sisi ajaib adalah pelabelan total sisi ajaib pada graf dan dipetakan ke himpunan sehingga dan [3].
JURNAL SAINS DAN SENI POMITS Vol. 2, No.1, (2013) 2337-3520 (2301-928X Print)
Gambar 3. (a) Pelabelan Super Sisi Ajaib (b) Bukan Pelabelan Super Sisi Ajaib
Misalkan adalah pelabelan super sisi ajaib dari graf dengan konstanta . Maka didapat persamaan [5] :
2
Karena adalah bilangan bulat maka merupakan bilangan bulat, sehingga mod mod mod merupakan
juga
)
sisa . Dari pola pelabelan sebelumnya
disubstitusikan ke
menjadi
sisa . Maka
Sehingga diperoleh III. PELABELAN SUPER SISI AJAIB PADA CATERPILLAR TERATUR A. Pelabelan Super Sisi Ajaib Pada Caterpillar Teratur Caterpillar teratur adalah pohon yang memenuhi pelabelan super sisi ajaib dengan pola pelabelan sebagai berikut:
Untuk Masing-masing sisi di berlaku , dengan bilangan ajaib, maka diperoleh
Teorema 1 Jika dengan adalah caterpillar teratur dengan 2 simpul backbone dan simpul anting, maka adalah pohon yang memenuhi pelabelan super sisi ajaib dengan bilangan ajaib . Bukti: Caterpillar teratur
Simpul dan diperoleh,
dan .
Pada proses pelabelan karenanya dan pada Persamaan (2) diperoleh . Jadi terbukti bahwa adalah pohon yang memenuhi pelabelan super sisi ajaib dengan bilangan ajaib Contoh pelabelan super sisi ajaib pada caterpillar teratur dengan seperti pada Gambar 4.
(a) Gambar 4. (a)
dengan
(b)
(b) dengan
B. Pelabelan Super Sisi Ajaib Pada Caterpillar Teratur Caterpillar teratur adalah pohon yang memenuhi pelabelan super sisi ajaib dengan pola pelabelan sebagai berikut:
mempunyai
merupakan simpul backbone karenanya untuk . Simpul untuk merupakan simpul anting karenanya Dengan menggunakan Persamaan (1)
Untuk Masing-masing sisi di berlaku , dengan konstanta ajaib, maka diperoleh
Teorema 2 Jika dengan adalah caterpillar teratur dengan 3 simpul backbone dan simpul anting, maka adalah pohon yang memenuhi pelabelan super sisi ajaib dengan bilangan ajaib . Bukti: Caterpillar teratur
Simpul karenanya
,
, mempunyai simpul dan sisi yaitu
dan
merupakan simpul backbone , .
JURNAL SAINS DAN SENI POMITS Vol. 2, No.1, (2013) 2337-3520 (2301-928X Print) Simpul untuk merupakan simpul anting karenanya menggunakan Persamaan (1) diperoleh,
3
dan . Dengan Teorema 3 Jika dengan adalah firecracker teratur dengan 2 simpul backbone, 2 simpul pusat dan simpul anting, maka adalah pohon yang memenuhi pelabelan super sisi ajaib dengan bilangan ajaib . Bukti: Firecracker teratur
mempunyai
Simpul
Karena adalah bilangan bulat maka juga merupakan bilangan bulat. Sehingga mod mod
)
sisa
. Dari pola pelabelan
sebelumnya disubstitusikan ke
menjadi
merupakan
sisa Sehingga diperoleh
dan merupakan simpul backbone karenanya untuk . Simpul dan merupakan simpul pusat karenanya untuk dan Simpul untuk dan merupakan simpul anting karenanya . Dengan menggunakan Persamaan (1) diperoleh,
. maka dan
Pada proses pelabelan sebelumnya karenanya sedangkan Persamaan (3) diperoleh . Jadi terbukti bahwa adalah pohon yang memenuhi pelabelan super sisi ajaib dengan bilangan ajaib Contoh pelabelan super sisi ajaib pada caterpillar teratur dengan seperti pada Gambar 5.
Karena
adalah
bilangan
bulat
juga merupakan bilangan bulat. mod mod sisa
merupakan
. Dari pelabelan
sebelumnya disubstitusikan ke sisa (a) Gambar 5. (a)
dengan
(b)
(b) dengan
IV. PELABELAN SUPER SISI AJAIB PADA FIRECRACKER TERATUR
A. Pelabelan Super Sisi Ajaib Pada Firecracker Teratur Firecracker teratur adalah pohon yang memenuhi pelabelan super sisi ajaib dengan pola pelabelan sebagai berikut:
Untuk dan Masing-masing sisi di berlaku , dengan bilangan ajaib, maka diperoleh
maka
Sehingga diperoleh
menjadi
. Maka
dan
Pada proses pelabelan sebelumnya oleh karenanya sedangkan pada Persamaan (4) diperoleh . Jadi terbukti bahwa adalah pohon yang memenuhi pelabelan super sisi ajaib dengan Contoh pelabelan super sisi ajaib pada firecracker teratur dengan seperti pada Gambar 6.
(a) Gambar 6. (a)
(b) dengan
(b)
dengan
JURNAL SAINS DAN SENI POMITS Vol. 2, No.1, (2013) 2337-3520 (2301-928X Print)
B. Pelabelan Super Sisi Ajaib Pada Firecracker Teratur Firecracker teratur adalah pohon yang memenuhi pelabelan super sisi ajaib dengan pola pelabelan sebagai berikut:
4
merupakan pelabelan
sisa sebelumnya
.
disubstitusikan
menjadi
Dari ke
sisa
.
Maka
dan Sehingga diperoleh
Pada proses pelabelan sebelumnya diperoleh oleh karenanya sedangkan pada Persamaan (5) diperoleh . Jadi terbukti bahwa adalah pohon yang memenuhi pelabelan super sisi ajaib dengan Contoh pelabelan super sisi ajaib pada firecracker teratur dengan seperti pada Gambar 7.
Untuk dan Masing-masing sisi di berlaku , dengan konstanta ajaib, maka diperoleh
Teorema 4 Jika dengan adalah firecracker teratur dengan 3 simpul backbone, 3 simpul pusat dan simpul anting, maka adalah pohon yang memenuhi pelabelan super sisi ajaib dengan bilangan ajaib . Bukti: Firecracker teratur
Simpul karenanya dan
,
untuk karenanya (1) diperoleh
(a) Gambar 7. (a)
(b) dengan
(c) (b)
dengan
V. PELABELAN SUPER SISI AJAIB PADA BANANA TREE TERATUR
, mempunyai
dan
merupakan simpul – simpul backbone , . Simpul , merupakan simpul – simpul pusat karenanya untuk dan Simpul dan merupakan simpul anting . Dengan menggunakan Persamaan
A. Pelabelan Super Sisi Ajaib Pada Banana Tree Teratur Banana Tree teratur adalah pohon yang memenuhi pelabelan super sisi ajaib dengan pola pelabelan sebagai berikut:
Untuk dan Masing-masing sisi di berlaku , dengan bilangan ajaib, maka diperoleh
Karena
adalah
bilangan
bulat
maka
juga merupakan bilangan bulat. Sehingga
Teorema 5 Jika dengan adalah banana tree teratur dengan 2 salinan graf bintang dan simpul anting, maka adalah pohon yang memenuhi pelabelan super sisi ajaib dengan bilangan ajaib Bukti: Banana tree teratur
mempunyai
mod mod
Simpul Simpul
merupakan simpul akar karenanya . dan merupakan simpul batang karenanya untuk . Simpul dan merupakan simpul pusat karenanya untuk . Simpul
JURNAL SAINS DAN SENI POMITS Vol. 2, No.1, (2013) 2337-3520 (2301-928X Print) untuk dan simpul anting karenanya menggunakan Persamaan (1) diperoleh,
5
merupakan . Dengan
Untuk dan Masing-masing sisi di berlaku , dengan konstanta ajaib, maka diperoleh
Karena
adalah
bilangan juga
bulat
maka
merupakan
bilangan
bulat. Sehingga
mod
sisa merupakan pola pelabelan sebelumnya disubstitusikan ke menjadi , sehingga diperoleh
. Dari sisa
.
dan
Pada proses pelabelan sebelumnya diperoleh oleh karenanya sedangkan pada Persamaan (6) diperoleh . Jadi terbukti bahwa adalah pohon yang memenuhi pelabelan super sisi ajaib dengan Contoh pelabelan super sisi ajaib pada banana tree teratur seperti pada Gambar 8. dengan
(a) Gambar 8. (a)
Bukti: Banana Tree teratur
, mempunyai
mod
)
Maka
Teorema 6 Jika dengan adalah banana tree teratur dengan 3 salinan graf bintang dan simpul anting, maka adalah pohon yang memenuhi pelabelan super sisi ajaib dengan bilangan ajaib .
(b) dengan
(b)
dengan
B. Pelabelan Super Sisi Ajaib Pada Banana Tree Teratur Banana tree teratur adalah pohon yang memenuhi pelabelan super sisi ajaib dengan pola pelabelan sebagai berikut:
Simpul merupakan simpul akar karenanya . Simpul , dan merupakan simpul batang karenanya untuk . Simpul , dan simpul merupakan simpul pusat karenanya untuk . Simpul untuk dan merupakan simpul anting karenanya . Dengan menggunakan Persamaan (1) diperoleh,
JURNAL SAINS DAN SENI POMITS Vol. 2, No.1, (2013) 2337-3520 (2301-928X Print) Karena
adalah
bilangan
bulat
6
maka
juga merupakan bilangan bulat. Sehingga
Untuk 2. Firecracker teratur adalah pohon yang memenuhi pelabelan super sisi ajaib dengan untuk dan pola pelabelan sebagai berikut:
mod mod
)
merupakan pola pelabelan
sisa . Dari disubstitusikan ke
sebelumnya menjadi
maka Sehingga diperoleh
sisa
.
dan
Untuk dan 3. Banana tree teratur adalah pohon yang memenuhi pelabelan super sisi ajaib dengan untuk dan pola pelabelan sebagai berikut:
Pada proses pelabelan sebelumnya diperoleh oleh karenanya sedangkan pada Persamaan (7) diperoleh . Jadi terbukti bahwa adalah pohon yang memenuhi pelabelan super sisi ajaib dengan Contoh pelabelan super sisi ajaib pada banana tree teratur dengan seperti pada Gambar 9.
Untuk
dan DAFTAR PUSTAKA
[1] [2] (a) Gambar 9. (a)
(b) dengan
(b)
dengan
Dalam hal adalah pohon yang memenuhi pelabelan super sisi ajaib dengan bilangan ajaib dan mempunyai pola pelabelan sebagai berikut:
[3] [4] [5]
[6] [7]
Pelabelan banana Tree Teratur
terlihat pada Gambar 10.
[8]
[9]
Gambar 10.
dengan
=19
VI. SIMPULAN Dari analisa dan pembahasan yang telah dilakukan diperoleh kesimpulan sebagai berikut: 1. Caterpillar teratur adalah pohon yang memenuhi pelabelan super sisi ajaib dengan untuk dan pola pelabelan sebagai berikut:
Cunningham, D. (2004). “Vertex Magic”. Electronic Journal of Undergraduate Mathematics. Vol 9, Hal 1-20. Fuman University. Irawati, N. dan Heri, R. (2010). “Pelabelan Total Titik Ajaib Pada Complete graf dengan Ganjil”.Jurnal Matematiaka Vol. 13 No. 3, Hal. 136-142. Semarang: Universitas Diponegoro. Avadayappan, S. dkk. (2001). “Super Magic Strenght of a Graf”. Indian J. Pure Appl. Math Vol. 32 No. 11, Hal 1621-1630. Enomoto, H. dkk. (1998). “Super Edge-Magic Grafs”. SUT Journal of Mathematics Vol. 34 No. 2, Hal 105-109. Swaminathan, V. And Jeyanthi P. (2006). “Super Edge-Magic Strenght of Firecrackers, Banana Trees and Unicyclic Grafs ”. Discrete Mathematics 306, Hal 1624-1636. Yulianti, Kartika. (2008). “Hand Out Mata Kuliah Teori Graf (MT 424) Jilid Satu”. Bandung: Universitas Pendidikan Indonesia. Bondy, J.A. and Murty, U.S.R. (1976). “Graf Theory with Applications”. Great Britain: The Macmillan Press Ltd. Weisstein, Eric W. "Caterpillar." From MathWorld -- A Wolfram Web Resource. http://mathworld.wolfram.com/Caterpillar.html Diakses tanggal 27 Maret 2013 Gallian, Joseph A. (2009). “A Dynamic Survey of Graf Labeling”. The Electronic Journal of Combinatoric 16.
