SUPER EDGE MAGIC STRENGTH PADA GRAF FIRE CRACKERS DAN GRAF BANANA TREES ANDINI QASHRINA DARMANAGARI

SUPER EDGE MAGIC STRENGTH PADA GRAF FIRE CRACKERS DAN GRAF BANANA TREES

ANDINI QASHRINA DARMANAGARI

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2016

PERNYATAAN MENGENAI SKRIPSI DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Super Edge Magic Strength pada Graf Fire Crackers dan Graf Banana Trees adalah benar karya saya dengan arahan dari dosen pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam daftar pustaka di bagian akhir skripsi ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor. Bogor, Januari 2016 Andini Qashrina Darmanagari NIM G54110031

ABSTRAK ANDINI QASHRINA DARMANAGARI. Super Edge Magic Strength pada Graf Fire Crackers dan Graf Banana Trees. Dibimbing oleh TEDUH WULANDARI MAS’OED dan FARIDA HANUM. Karya ilmiah ini menjelaskan pembuktian teorema-teorema yang menyatakan bahwa graf Fire Crackers dan graf Banana Trees memiliki super edge magic strength. Suatu graf disebut super edge magic jika terdapat pemetaan satu-satu dari himpunan verteks ke himpunan bilangan bulat , dengan adalah banyaknya verteks dan pemetaan satu-satu dari himpunan edge ke himpunan bilangan bulat dengan adalah banyaknya edge sedemikian sehingga untuk setiap edge pada graf, jumlah label edge dan verteks yang incident dengan edge tersebut memiliki nilai yang sama dan disebut konstanta magic. Super edge magic strength adalah nilai minimum dari konstanta magic yang diperoleh dari semua pelabelan super edge magic pada graf tersebut. Kata kunci: graf Banana Trees, graf Fire Crackers, konstanta magic, super edge magic

ABSTRACT ANDINI QASHRINA DARMANAGARI. Super Edge Magic Strength of Fire Crackers and Banana Trees Graphs. Supervised by TEDUH WULANDARI MAS’OED and FARIDA HANUM. This manuscript proves theorems related to the super edge magic strength of fire crackers and banana trees graphs. A graph is called super edge magic labeling if there exist a bijection from vertices to the set of integers , where is the total number of vertices and a bijection from the edges to the set of integers }, where is the total number of edges, with the property that the sum of the label on an edge and the labels on the vertices that incident with that edge is constant for every edge in the graph. The constant is called the magic number. Super edge magic strength is defined as the minimum of magic number where the minimum is taken over all super edge magic labeling. Keywords: Banana Trees graph, Fire Crackers graph, magic number, super edge magic

SUPER EDGE MAGIC STRENGTH PADA GRAF FIRE CRACKERS DAN GRAF BANANA TREES

ANDINI QASHRINA DARMANAGARI

Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2016

Judul Skripsi : Super Edge Magic Strength pada Graf Fire Crackers dan Graf Banana Trees Nama : Andini Qashrina Darmanagari NIM : G54110031

Disetujui oleh

Teduh Wulandari Mas’oed, MSi Pembimbing I

Dra Farida Hanum, MSi Pembimbing II

Diketahui oleh

Dr Toni Bakhtiar, MSc Ketua Departemen

Tanggal Lulus:

PRAKATA Puji dan syukur penulis panjatkan kepada Allah SWT atas segala rahmat dan karunia-Nya serta sholawat dan salam kepada Nabi Muhammad SAW sehingga karya ilmiah ini berhasil diselesaikan. Penyusunan karya ilmiah ini juga tidak lepas dari bantuan berbagai pihak. Untuk itu, penulis mengucapkan terima kasih yang sebesarbesarnya kepada: 1 Keluarga tercinta Ayah, Mama, Abang Daffa, Adik Fauzy, dan seluruh keluarga besar yang selalu memberikan doa, dukungan, semangat, bimbingan, kasih sayang, dan motivasi, 2 Teduh Wulandari Mas’oed, MSi dan Dra Farida Hanum, MSi selaku dosen pembimbing, serta Drs Prapto Tri Supriyo, MKom selaku dosen penguji yang telah memberikan ilmu, motivasi, kesabaran, bimbingan, saran, dan bantuannya selama penulisan skripsi ini, 3 Nopi Elida selaku kakak tingkat penulis sejak TPB yang telah mendengarkan curahan hati selama penulisan skripsi ini, yang selalu memberikan motivasi, semangat, serta saran, 4 Intan, Kiki, Lidya, Sifa, Hanna, Alfi, Riefdah, Putri, Atikah, Resty selaku sahabat yang menemani penulis selama masa kuliah dan memberikan motivasi, doa, serta dukungan, 5 Teman-teman Matematika angkatan 48 yang selalu memberikan keceriaan, dukungan, doa, dan segala bantuan yang telah diberikan, 6 Kakak-kakak Matematika angkatan 47, adik-adik Matematika angkatan 49, keluarga besar LDK Al Hurriyyah IPB, keluarga besar Puskomnas Al Hurriyyah IPB, keluarga besar FSLDK IPB, penghuni Asrama Putri A2 lorong IV TPB IPB tahun 2011/2012, dan semua keluarga besar alumni SMA Negeri 4 Kota Bekasi yang berada di IPB yang telah memberikan doa, semangat, dan dukungannya. Semoga karya ilmiah ini dapat bermanfaat bagi dunia ilmu pengetahuan khususnya matematika dan menjadi inspirasi bagi penelitian-penelitian selanjutnya.

Bogor, Januari 2016 Andini Qashrina Darmanagari

DAFTAR ISI

DAFTAR GAMBAR

vii

DAFTAR LAMPIRAN

vii

PENDAHULUAN

1

Latar Belakang

1

Tujuan Penelitian

2

TINJAUAN PUSTAKA

2

HASIL DAN PEMBAHASAN

7

Graf Fire Crackers

7

Graf Banana Trees

21

SIMPULAN DAN SARAN

26

Simpulan

26

Saran

27

DAFTAR PUSTAKA

27

LAMPIRAN

28

RIWAYAT HIDUP

45

DAFTAR GAMBAR 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Graf Cycle 3-regular graph Graf 6-star Graf Fire Crackers F(3,2) Graf Banana Trees BT(2,3,4) Pelabelan super edge magic pada graf Fire Crackers F(2,1) pada graf Fire Crackers pada graf Fire Crackers pada graf Fire Crackers pada graf Banana Trees pada graf Banana Trees pada graf Banana Trees pada graf Banana Trees

2 3 3 4 4 5 6 9 9 9 22 22 22 23

DAFTAR LAMPIRAN 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Bukti teorema yang berlaku pada tree Graf Fire Crackers dengan F(3,3), c(f) = 34 Graf Fire Crackers dengan F(3,3), c(f) = 35 Graf Fire Crackers dengan F(3,4), c(f) = 40 Graf Fire Crackers dengan F(3,4), c(f) = 41 Graf Fire Crackers dengan F(2,1), c(f) = 16 Graf Banana Trees dengan BT(2,3), c(f) = 20 Graf Banana Trees dengan BT(2,3), c(f) = 22 Graf Banana Trees dengan BT(2,4), c(f) = 22 Graf Banana Trees dengan BT(3,1), c(f) = 18 Graf Banana Trees dengan BT(3,1), c(f) = 19 Graf Banana Trees dengan BT(3,3), c(f) = 22 Graf Banana Trees dengan BT(3,3), c(f) = 23 Graf Banana Trees dengan BT(3,3), c(f) = 25 Graf Banana Trees dengan BT(1,2,3), c(f) = 25

28 29 30 31 32 33 34 35 36 37 39 40 42 43 44

PENDAHULUAN Latar Belakang Teori graf merupakan salah satu cabang matematika yang banyak berperan dalam pengembangan matematika terapan dan telah mengalami perkembangan sejak tahun 1920-an. Pada awalnya, teori graf diperkenalkan oleh Leonhard Euler sebagai solusi permasalahan mungkin tidaknya melewati ketujuh jembatan di kota Königsberg (sekarang dikenal sebagai Kaliningrad, Rusia) dan kembali ke tempat asal semula tepat satu kali. Kemudian, Leonhard Euler memodelkan permasalahan tersebut ke dalam model matematika berupa bagan yang terdiri dari titik dan garis. Titik merepresentasikan kota yang dihubungkan oleh jembatan dan garis sebagai jembatan yang menghubungkan kota. Model ini kemudian dikenal sebagai “Teori Graf”. Mengikuti perkembangan zaman, teori graf terus dikembangkan dan memiliki banyak terapan, di antaranya model jaringan komunikasi, ilmu komputer, penjadwalan, riset operasi, dan sebagainya. Hal itu disebabkan teori graf memiliki cakupan model yang luas. Salah satu permasalahan utama dalam teori graf adalah bagaimana melabelkan suatu verteks dan edge sedemikian sehingga setiap verteks dan edge yang saling terhubung memiliki label yang berbeda. Suatu pelabelan pada graf dengan banyaknya verteks v dan banyaknya edge adalah pemetaan satu-satu dari himpunan ke himpunan bilangan bulat positif Pelabelan ini disebut pelabelan total (Ngurah & Baskoro 2003). Pelabelan pada graf terdiri dari pelabelan verteks, pelabelan edge, dan pelabelan total. Pelabelan verteks adalah pelabelan dengan domain himpunan verteks, pelabelan edge adalah pelabelan dengan domain himpunan edge, dan pelabelan total adalah pelabelan dengan domain gabungan himpunan verteks dan edge. Ada banyak jenis pelabelan pada graf yang telah dikembangkan, di antaranya adalah pelabelan graceful, pelabelan harmoni, pelabelan total, pelabelan ajaib (magic), dan pelabelan antiajaib (antimagic). Dalam pengembangan pelabelan ajaib (magic), dikenal pula pelabelan vertex magic, pelabelan super vertex magic, pelabelan edge magic, dan pelabelan super edge magic. Salah satu contoh penerapan dari sebuah pelabelan pada graf adalah pemberian alamat pada suatu komputer yang ada dalam suatu jaringan. Pelabelan ajaib (magic) pada suatu graf merupakan pelabelan total pada verteks dan edge suatu graf dengan labelnya adalah bilangan asli, dengan jumlah label-label pada sebuah edge dan dua verteks ujungnya adalah suatu bilangan konstan atau disebut konstanta magic (Kotzig dan Rosa 1970). Pelabelan super edge magic adalah pelabelan graf yang himpunan serta himpunan edgenya dipetakan ke verteksnya dipetakan ke dengan adalah banyaknya verteks dan adalah banyaknya edge pada suatu graf (Enomoto et al. 1998). Terdapat 2 graf yang akan dibahas pada penelitian ini yaitu graf Fire Crackers dan graf Banana Trees. Karya ilmiah ini akan menjelaskan teorema-teorema yang menyatakan bahwa graf Fire Crackers dan graf Banana Trees merupakan graf yang memiliki super edge magic strength (Swaminathan & Jeyanthi 2006).

2 Tujuan Penelitian Tujuan dari penulisan karya ilmiah ini adalah menjelaskan pembuktian teoremateorema yang menyatakan bahwa graf Fire Crackers dan graf Banana Trees memiliki super edge magic strength.

TINJAUAN PUSTAKA Graf adalah pasangan terurut dengan himpunan takkosong dan Suatu graf berhingga dan himpunan pasangan tak terurut yang menghubungkan elemen-elemen Graf dinotasikan dengan Elemen disebut verteks sedangkan elemen disebut edge. Himpunan dari verteks-verteks pada graf dinotasikan dengan sedangkan edge-edge pada graf dinotasikan dengan (Foulds 1992). Contoh graf dapat dilihat pada gambar berikut ini.

Gambar 1 Graf Himpunan verteks dan himpunan edge pada Gambar 1 adalah

dan

Order dan Size Misalkan diberikan graf Banyaknya verteks pada graf disebut order dan banyaknya edge pada graf disebut size dari graf Order dari graf dinotasikan dengan , sedangkan size dari graf dinotasikan dengan (Chartrand & Oellermann 1993). Pada Gambar 1, nilai dari = 5 dan nilai dari = 5. Adjacent dan Incident Misalkan diberikan graf G. Jika dengan maka dan dikatakan adjacent di dan dikatakan incident dengan dan (Chartrand & Oellermann 1993). Pada Gambar 1, misalkan maka dan dikatakan adjacent di dan dikatakan incident dengan dan Degree Derajat (degree) dari suatu verteks pada graf adalah banyaknya edge yang incident dengan dan dinotasikan dengan deg (Chartrand & Oellermann 1993). Pada Gambar 1, derajat setiap verteksnya ialah deg deg deg deg dan deg

3 Walk, Cycle, Tree, Path Suatu walk pada graf adalah suatu deretan berhingga dari verteks dan edge secara bergantian yang diawali dan diakhiri dengan verteks, sedemikian sehingga setiap edge, incident dengan dua verteks yang berdekatan. Contohnya dan dapat dituliskan sebagai atau Suatu walk yang menghubungkan dengan dikatakan tertutup jika Jika maka walk tersebut dikatakan terbuka (Foulds 1992). Pada Gambar . Cycle pada suatu graf adalah 1, terdapat walk terbuka yaitu walk walk tertutup yang mengandung setidaknya tiga verteks dan semua verteks berbeda (Foulds 1992). Pada Gambar 2, terdapat cycle pada graf yang terdiri atas tiga verteks yaitu

Gambar 2 Cycle Tree adalah suatu graf terhubung yang tidak mempunyai cycle (Foulds 1992). Path pada suatu graf adalah suatu walk dengan semua verteksnya berbeda. Graf ber-order yang berbentuk path disebut graf path ber-order dituliskan (Chartrand & Oellermann 1993). Pada Gambar 1, merupakan salah satu contoh path. Regular Graph Graf yang setiap verteksnya mempunyai derajat yang sama disebut graf teratur. Apabila derajat setiap verteks adalah maka graf tersebut disebut sebagai graf teratur derajat ( -regular graphs) (Chartrand & Oellermann 1993). Pada Gambar 3, terdapat 3regular graphs dengan derajat setiap verteks adalah 3.

Gambar 3 3-regular graph Star Graph Graf star (star graph) atau dikenal dengan -star adalah tree yang memiliki verteks dengan satu verteks mempunyai derajat verteks ini dinamakan verteks pusat dan verteks lain mempunyai derajat 1, verteks ini dinamakan verteks pendant (Chartrand & Oellermann 1993). Contoh graf 6-star ditunjukkan pada Gambar 4.

4

Gambar 4 Graf 6-star Graf Fire Crackers Misalkan adalah graf -star dengan . Misalkan adalah salah satu verteks pendant dari graf dan adalah salah satu verteks pendant dari graf Misalkan adalah verteks yang adjacent dengan untuk merupakan verteks pendant yang adjacent dengan untuk Misalkan Tree yang diperoleh dengan menghubungkan dan untuk disebut graf Fire Crackers dan dinotasikan dengan (Swaminathan & Jeyanthi 2006). Notasi menyatakan banyaknya graf star yang ada pada graf Fire Crackers dan menyatakan banyaknya verteks pendant yang menempel pada setiap graf star yang ditunjukkan pada Gambar ada pada graf Fire Crackers. Contoh graf Fire Crackers 5.

Gambar 5 Graf Fire Crackers Berdasarkan definisi, graf Fire Crackers pada Gambar 5 memiliki nilai dan Pada Gambar 5, diberikan notasi dan Notasi terdiri dari verteks-verteks penghubung (menghubungkan antara 2 graf star yang ada pada graf Fire Crackers) yaitu dan atau secara umum dituliskan dengan Selanjutnya notasi terdiri dari verteks-verteks pusat yaitu dan atau secara umum dituliskan dengan dan notasi terdiri dari verteks pendant yaitu dan atau secara umum dituliskan dengan Akibatnya, pada Gambar 5 diperoleh himpunan verteks dari graf Fire Crackers sebagai berikut,

5 Kemudian pada graf Fire Crackers terdapat 11 edge. Verteks dihubungkan dengan verteks untuk setiap maka akan didapatkan edge yaitu untuk setiap Edge berikutnya menghubungkan setiap verteks dan verteks dinotasikan dengan untuk setiap Edge selanjutnya menghubungkan setiap verteks dan verteks dinotasikan dengan { } untuk setiap dan Akibatnya diperoleh himpunan edge secara keseluruhan dari graf Fire Crackers sebagai berikut, = { Graf Banana Trees Misalkan adalah graf -star, -star sampai adalah salah satu verteks pendant dari graf . Misalkan juga star. Misalkan adalah sebuah verteks baru. Tree yang diperoleh dengan menghubungkan dengan setiap untuk disebut Banana Trees, dinotasikan oleh dan adalah sembarang bilangan bulat positif dan (Swaminathan & Jeyanthi 2006). Contoh graf Banana Trees ditunjukkan pada Gambar 6.

Gambar 6 Graf Banana Trees Berdasarkan definisi, graf Banana Trees pada Gambar 6 memiliki nilai Pada Gambar 6, diberikan notasi dan Notasi terdiri dari sebuah verteks baru. Verteks ini menghubungkan beberapa graf star, dinotasikan dengan Selanjutnya notasi terdiri dari beberapa verteks yaitu dan atau secara umum dituliskan dengan lambang Di notasi terdapat verteks-verteks berikutnya yaitu verteks pusat dan atau secara umum dituliskan dengan lambang dan juga di notasi terdapat enam verteks lainnya (verteks pendant) yaitu dan atau secara umum dituliskan dengan lambang Akibatnya, pada Gambar 6 diperoleh himpunan verteks dari graf Banana Trees adalah

6 Graf Banana Trees memiliki 12 edge. Edge yang didapatkan dari menghubungkan verteks dan verteks dinotasikan dengan Edge selanjutnya menghubungkan setiap verteks dan verteks dinotasikan dengan { untuk setiap Edge berikutnya menghubungkan setiap verteks dan verteks dinotasikan dengan { } untuk setiap dan Akibatnya diperoleh himpunan edge secara keseluruhan dari graf Banana Trees

Pelabelan Graf Pelabelan Total (Total Labeling) dengan banyaknya verteks v dan banyaknya edge Suatu pelabelan pada graf adalah pemetaan satu-satu dari himpunan ke himpunan bilangan bulat positif Pelabelan ini disebut pelabelan total (Ngurah & Baskoro 2003). Pelabelan Ajaib (Magic Labeling) Misalkan graf dengan himpunan verteks dan himpunan edge Magic labeling pada graf adalah suatu fungsi bijektif sehingga untuk setiap edge nilai penjumlahan dengan merupakan konstanta magic dari fungsi bijektif f (Avadayappan et al. 2000). Pelabelan Super Edge Magic Misalkan

graf dengan verteks dan edge, dan memiliki pelabelan edge magic dan maka disebut pelabelan Jika super edge magic (Enomoto et al. 1998). Contoh pelabelan super edge magic dapat dilihat pada Gambar 7.

Gambar 7 Pelabelan super edge magic pada graf Fire Crackers

Misalkan verteks-verteks pada graf Fire Crackers

.

diberi pelabelan:

7

Kemudian diberikan pelabelan untuk edge-edge pada graf Fire Crackers

maka akan diperoleh penjumlahan label dari tiap edge yang incident terhadap

verteks :

Dari semua penjumlahan label di atas terlihat bahwa pelabelan tersebut menghasilkan satu nilai saja atau disebut konstanta magic (magic number) yaitu Graf Super Edge Magic Suatu graf disebut super edge magic jika terdapat sebuah pelabelan super edge magic pada (Enomoto et al. 1998). Super Edge Magic Strength Misalkan graf dengan himpunan verteks dan himpunan edge Super edge magic strength pada graf dinotasikan dengan didefinisikan sebagai nilai artinya adalah pelabelan super edge minimum dari semua magic dari } (Swaminathan & Jeyanthi 2006).

HASIL DAN PEMBAHASAN Karya ilmiah ini membahas teorema-teorema mengenai super edge magic strength pada graf Fire Crackers dan graf Banana Trees Permasalahan utama dalam karya ilmiah ini adalah bagaimana menjelaskan pembuktian teorema-teorema yang menyatakan bahwa graf Fire Crackers dan graf Banana Trees memiliki super edge magic strength.

1. Graf Fire Crackers Teorema 1 Graf Fire Crackers memiliki pelabelan super edge magic jika, jika

ganjil

jika k genap.

8 Akan dibuktikan: i. Batas bawah dari pada graf Fire Crackers yaitu Bukti Misalkan himpunan verteks dan himpunan edge { } Total verteks yang ada pada graf dinotasikan dengan Karena terdapat star dan setiap star memiliki verteks pendant sehingga setiap star memiliki verteks akibatnya graf memiliki verteks, dapat dituliskan rumus sebagai berikut Graf dengan tree yang terhubung, mempunyai total verteks verteks sehingga total edge menjadi atau dapat (bukti dapat dilihat pada Lampiran 1). dituliskan rumus sebagai berikut Misalkan adalah salah satu pelabelan super edge magic dari graf dengan konstanta magic . Berikut penjabaran

⁞

⁞

⁞

∑

∑

Berikut diberikan rumus beserta penjelasannya. ∑

∑

Pada graf Fire Crackers ini akan dicari konstanta magic . Konstanta magic yang paling kecil (minimal) merepresentasikan bahwa graf Fire Crackers mempunyai didapat dengan cara menjumlahkan semua super edge magic strength. Nilai verteks dan edge yang ada. Derajat (degree) pada rumus di atas merepresentasikan bahwa setiap verteks akan digunakan sebanyak edge yang incident dengan verteks tersebut. ∑ ∑

∑ ∑

∑

∑

(

)

∑

Simbol melambangkan verteks dan simbol melambangkan edge. Simbol verteks terdiri atas beberapa simbol verteks yaitu simbol verteks dan dengan dan dan edge terdiri dari beberapa edge yaitu edge dan sehingga diperoleh: ∑ ∑

∑

∑

∑

∑

(

)+

Rumus di atas, dijelaskan menggunakan gambar. Pada Gambar 8 di bawah ini, dijelaskan setiap suku yang terdapat pada rumus tersebut.

9

Gambar 8 Verteks

pada graf Fire Crackers

Pada Gambar 8 di atas, setiap verteks minimal berderajat . Untuk sampai berderajat 3, secara umum penjumlahan label verteks dapat ∑ dituliskan sebagai berikut ∑

Gambar 9 Verteks


Untuk verteks dapat dilihat pada Gambar 9. Verteks mempunyai derajat (berasal dari verteks pendant yang menempel pada graf star) dan juga berderajat satu untuk verteks yang adjacent dengan . Dapat dituliskan penjumlahan label verteks oleh ∑ rumus sebagai berikut

Gambar 10 Verteks


Setiap verteks selalu berderajat , maka dapat dituliskan penjumlahan label verteks sebagai berikut ∑ ∑ ( ) ∑

∑

∑

∑

∑

(

∑

∑ ∑ ∑ ∑

∑ + ∑ ∑ + ∑

∑

∑

(

)

∑

∑

∑

∑

(

)

∑

∑

)+

10 Dengan memisahkan suku untuk setiap verteks dan edge yang ada, maka akan didapatkan deret aritmatika (4 suku pertama sama dengan banyaknya verteks dan edge pada graf sehingga penjumlahan label diperoleh ∑ ( ∑

∑

)

∑

+∑

∑

(

∑

∑

(

)

∑ ∑

∑

)

(

secara umum dapat dituliskan

) Karena

∑ ∑

∑ ∑

maka didapatkan hasil, ∑

∑ ∑

∑

Karena yang akan dicari adalah nilai minimum dari suatu konstanta magic (magic number), maka selanjutnya atur verteks yang berderajat tinggi dilabelkan dengan nilai terkecil, maka diperoleh,

(

)

2 2 2 2 2 2

( )

2

( )

(

)

2

{

2

{

–

}

2

{

–

}

2

{

Oleh karena itu,

–

}

}

(

)

11 2

{

}

(G) Karena maka

merupakan nilai minimum dari semua kemungkinan nilai pasti memenuhi ketaksamaan

ii. Batas atas dari pada graf Fire Crackers yaitu jika ganjil. Bukti Pembuktian batas atas didapatkan dengan menunjukkan konstanta magic ada pada pelabelan di graf Fire Crackers. Pelabelan Graf Fire Crackers Terbagi menjadi kasus yaitu, Kasus (i) : ganjil. Terdapat Kasus (ii) : genap Subkasus (i) : ganjil. Didefinisikan Untuk

{

{

Untuk

subkasus.

sebagai berikut:

yang

12

(

)

{ Pelabelan edge sebagai berikut,

{ (

)

{

Untuk

(

) {

 Pilih pelabelan untuk ganjil pada

Akibatnya diperoleh konstanta magic

 Pilih pelabelan untuk genap pada:

sebagai berikut.

13


sebagai berikut.

 Pilih pelabelan untuk ganjil pada


sebagai berikut.

+

 Pilih pelabelan untuk genap pada


sebagai berikut.

 Pilih pelabelan untuk ganjil, ganjil pada

( (

(

) )

Akibatnya diperoleh konstanta magic ( ) ( )

sebagai berikut.

)

(

)

14

 Pilih pelabelan untuk ganjil, genap pada

(

)

(

)

(

)

(

)

(

)

(

)

)

(

)


sebagai berikut.

 Pilih pelabelan untuk genap, ganjil pada

(

(

)

(

)

Akibatnya diperoleh konstanta magic c(f) sebagai berikut. (

)

(

)

 Pilih pelabelan untuk i genap, genap pada

( (

) )


sebagai berikut.

15 Karena

merupakan salah satu nilai konstanta magic yang

didapat maka jika ganjil dan ganjil. Contoh pelabelan super edge magic dengan ganjil dan ganjil dapat dilihat pada Lampiran 2 yaitu dengan dan Lampiran 3 yaitu dengan . Subkasus (ii): genap. Pelabelan untuk verteks Pelabelan verteks

(

)

dan

{

Untuk

(

)

{

Pelabelan edge adalah sebagai berikut: Untuk (

)

{

Untuk

(

) {  Pilih pelabelan untuk ganjil pada

adalah sama dengan subkasus (i). adalah sebagai berikut,

16


sebagai berikut.



sebagai berikut.

 Pilih pelabelan untuk i ganjil pada


sebagai berikut.

 Pilih pelabelan untuk i genap pada

Akibatnya diperoleh konstanta magic c(f) sebagai berikut.

17

 Pilih pelabelan untuk ganjil, ganjil pada

(

)

(

)

(

)

(

)

(

)

sebagai berikut.

 Pilih pelabelan untuk ganjil, genap pada

)

(

)

Akibatnya diperoleh konstanta magic (

)

(

sebagai berikut.

)

 Pilih pelabelan untuk genap, ganjil pada

(

(

)


(

)

)

(

(

(

) )

Akibatnya diperoleh konstanta magic c(f) sebagai berikut. ( ) ( )

18

 Pilih pelabelan untuk i genap, j genap pada

(

(

)

(

):

)

(

)

Akibatnya diperoleh konstanta magic c(f) sebagai berikut. ( ) ( )

Karena

merupakan salah satu nilai konstanta magic

, jika ganjil dan genap. Contoh yang didapat maka pelabelan super edge magic dengan ganjil dan genap dapat dilihat pada Lampiran 4 yaitu dengan dan Lampiran 5 yaitu dengan . Kasus (ii): genap. Misalkan Didefinisikan )

(

{

sebagai berikut:

(

)

{ ( ( (

)

) )

{

Adapun pelabelan edge adalah sebagai berikut :

{

19 (

)

{

 Pilih pelabelan untuk ganjil pada (

) (

)


)

(

)

sebagai berikut. (

)


)

(


(

)

sebagai berikut.

(

(

)

)

(

)

 Pilih pelabelan untuk ganjil pada pada ( (

) )


)

(

)


(

)

sebagai berikut. (

)

20


sebagai berikut.

)

(

(

)

)

 Pilih pelabelan untuk ganjil pada ( (

)

(

(

(

)

)

)

(

)

sebagai berikut. )

(

(

)

 Pilih pelabelan untuk genap pada (

(

(

)


(

)

)

(

)

(

)

)

(

)

)

Akibatnya diperoleh konstanta ( ) ( ( ( Karena

)

sebagai berikut. ) (

)

) merupakan salah satu nilai konstanta magic

yang didapat maka ( ) jika genap. Contoh pelabelan super edge magic dengan genap dapat dilihat pada Lampiran 6 yaitu dengan Dari tahap i dan ii dapat dibuktikan jika ganjil dan graf Fire Crackers

( ) jika genap. Jadi, secara umum maka pada memiliki super edge magic strength dengan jika (2k +

jika

ganjil genap.

21 2. Graf Banana Trees Teorema 2 Graf Banana Trees memiliki pelabelan super edge magic jika, dengan bulat positif, dan Akan dibuktikan: i. Batas bawah dari

adalah bilangan

pada graf Banana Trees yaitu

Bukti { } Misalkan himpunan verteks dan himpunan edge Total verteks yang ada pada graf dinotasikan dengan Total verteks pada graf Banana Trees didapatkan dari penjumlahan unsur pembentuk graf star, jumlah graf star yang ada pada graf Banana Trees dan satu verteks yang disebut dengan verteks baru. Dapat dituliskan dengan rumus sebagai berikut Graf dengan tree yang terhubung mempunyai total verteks verteks sehingga total edge menjadi edge atau dapat dituliskan rumus sebagai berikut . Berikut penjabaran

⁞

⁞

⁞

∑

∑

Berikut diberikan rumus dan penjelasannya. ∑

∑

Pada graf Banana Trees ini akan dicari konstanta magic Konstanta magic yang paling kecil (minimal) merepresentasikan bahwa graf Banana Trees mempunyai super edge magic strength. Nilai didapat dengan cara menjumlahkan semua verteks dan edge yang ada. Derajat (degree) pada rumus di atas mempresentasikan bahwa setiap verteks akan digunakan sebanyak edge yang incident dengan verteks tersebut. ∑ ∑

∑

∑ (

)

∑

22 Simbol melambangkan verteks dan simbol melambangkan edge. Simbol terdiri dari beberapa verteks lagi yaitu verteks , dan dengan dan dan edge w terdiri dari beberapa edge lagi yaitu dan ∑

∑

∑

∑

(

)

∑

Rumus di atas, dijelaskan menggunakan gambar. Pada gambar di bawah ini, dijelaskan masing masing suku yang membentuk rumus tersebut.

Gambar 11 Verteks

pada graf Banana Trees

Dapat dilihat pada Gambar 11, bahwa verteks a berderajat sebanyak graf star yang akan dibentuk atau dapat dituliskan dengan

Gambar 12 Verteks


Karena masing-masing berderajat 2, maka secara umum penjumlahan label verteks dapat dituliskan dengan rumus sebagai berikut ∑

Gambar 13 Verteks


23 Untuk verteks dapat dilihat pada Gambar 13. Verteks mempunyai derajat (berasal dari verteks yang membentuk graf star). Maka dari itu penjumlahan label ∑ verteks dapat dituliskan dengan rumus sebagai berikut

Gambar 14 Verteks


Setiap verteks selalu berderajat 1, maka penjumlahan label verteks sebagai berikut ∑ ∑ ( ) ∑

( ∑

∑

∑ ∑

∑

∑

) (

∑

)

∑ ∑ ) ∑

∑

(

∑

dapat dituliskan

(

∑

)

Dengan memisahkan suku untuk setiap verteks dan edge yang ada, maka akan didapatkan deret aritmatika (4 suku pertama sama dengan banyaknya verteks dan edge pada graf sehingga penjumlahan label diperoleh ∑

(

c(f) = c(f) =

∑

( ∑

∑

∑

) ∑

) ∑

(

)

∑

secara umum juga

dapat dituliskan ( Karena

∑

.

didapatkan hasil, ∑

(

)

∑

Karena yang akan dicari adalah nilai minimum dari suatu konstanta magic, maka atur verteks yang berderajat tinggi dilabelkan dengan nilai terkecil, maka diperoleh: (

( )

∑

∑

24 2

(

)

) )

)

Karena

maka, ) )

)

Karena

)

)

)

)

merupakan nilai minimum dari semua kemungkinan nilai pasti memenuhi ketaksamaan )

maka

ii. Batas atas dari pada graf Banana Trees yaitu Bukti Pembuktian batas atas didapatkan dengan menunjukkan konstanta magic yang ada pada pelabelan pada graf Banana Trees. Pelabelan Graf Banana Trees Didefinisikan

{

} adalah sebagai berikut :

25 Pelabelan edge adalah sebagai berikut: {

(

(

)

(

)

) {

 Pilih pelabelan untuk

pada



pada



sebagai berikut.

pada



sebagai berikut.

pada

:

sebagai berikut.

26

Akibatnya diperoleh konstanta magic c(f) sebagai berikut.


pada



sebagai berikut.

pada


sebagai berikut.

Karena

merupakan salah satu nilai konstanta magic yang didapat maka . Dari tahap i dan ii dapat dibuktikan pada graf Banana Trees memiliki super edge magic strength dengan Contoh pelabelan super edge magic pada Banana Trees dapat dilihat pada Lampiran 7 sampai dengan Lampiran 15.

SIMPULAN DAN SARAN Simpulan Karya ilmiah ini telah menjelaskan pembuktian teorema-teorema yang menyatakan bahwa graf Fire Crackers dan graf Banana Trees memiliki super edge magic strength. Pembuktian dilakukan dengan merekonstruksi rumus dan juga menunjukkan konstanta magic yang didapat dari pelabelan yang sudah ada.

27 Saran Dalam karya ilmiah ini telah dibahas teorema-teorema tentang super edge magic strength pada graf Fire Crackers dan graf Banana Trees Karya ilmiah ini dapat diperluas untuk penggunaan graf lainnya di antaranya unicyclic graph.

DAFTAR PUSTAKA Avadayappan S, Vasuki R, Jeyanthi P. 2000. Magic strength of a graph. Indian Journal of Pure and Applied Mathematics. 31(7): 873-883. Chartrand G, Oellermann OR. 1993. Applied and Algorithmic Graph Theory. New York (US): McGraw-Hill. Enomoto H, Llado AS, Nakamigawa T, Ringel G. 1998. Super edge-magic graph. SUT Journal of Mathematics. 34(2): 105–109. Foulds LR. 1992. Graph Theory Applications. New York (US): Springer-Verlag. Kotzig A, Rosa A. 1970. Magic valuations of finite graphs. Canadian Mathematical Bulletin. 13: 451–461. doi: 10.4153/CMB-1970-084-1. Ngurah AAG, Baskoro ET. 2003. On magic and antimagic total labeling of generalized Petersen graph. Utilitas Math. 63: 97-107. Swaminathan V, Jeyanthi P. 2006. Super edge–magic strength of fire crackers, banana trees and unicyclic graphs. Discrete Mathematics. 306(14): 1624-1636. doi: 10.1016/j.disc.2005.06.038.

28 Lampiran 1 Bukti teorema yang berlaku pada tree Teorema 3.1 Misalkan

tree yang mempunyai order

maka

juga mempunyai size

.

Bukti : Karena adalah suatu tree dengan order dan size hasilnya benar untuk Misalkan adalah suatu bilangan integer dan diasumsikan hasilnya benar untuk semua tree yang berorder . Misalkan adalah tree berorder dan size dan misalkan adalah sebuah edge dari Diketahui bahwa adalah penghubung (bridge) dari sehingga adalah forest (minimal ada dua komponen). Dinotasikan dua komponen dari yaitu dan dengan adalah tree berorder dan size Karena berdasarkan asumsi bahwa untuk Dan juga, karena dan maka

29 Lampiran 2 Contoh Pelabelan pada Graf Fire Crackers Pelabelan super edge magic dari dengan memiliki: Berdasarkan teorema,

Batas bawah

=

Batas atas

= = =

= = Super edge magic strength

terletak pada

30 Lampiran 3 Contoh Pelabelan pada Graf Fire Crackers Pelabelan super edge magic dari

dengan


Batas bawah

=

Batas atas

= = =

= = Super edge magic strength

terletak pada

32 Lampiran 5 Contoh Pelabelan pada Graf Fire Crackers Pelabelan super edge magic dari

dengan


Batas bawah

=

Batas atas

= = =

= = ,5 Super edge magic strength

terletak pada

34 Lampiran 7 Contoh Pelabelan pada Graf Banana Trees Pelabelan super edge magic dari dengan memiliki: Berdasarkan teorema,

Batas bawah

=

= = Batas atas = = = Super edge magic strength

terletak pada

35 Lampiran 8 Contoh Pelabelan pada Graf Banana Trees Pelabelan super edge magic dari

dengan

36 Lampiran 9 Contoh Pelabelan pada Graf Banana Trees Pelabelan super edge magic dari dengan memiliki : Berdasarkan teorema,

Batas bawah

=


terletak pada


Batas bawah

=


terletak pada

38 Contoh Pelabelan pada Graf Banana Trees Pelabelan super edge magic dari

dengan


dengan

40 Lampiran 12 Contoh Pelabelan pada Graf Banana Trees Pelabelan super edge magic dari dengan memiliki: Berdasarkan teorema,

Batas bawah

=


terletak pada

41 Contoh Pelabelan pada Graf Banana Trees Pelabelan super edge magic dari

dengan


dengan

.


dengan


Batas bawah

=


terletak pada

45

RIWAYAT HIDUP Penulis dilahirkan di Jakarta pada tanggal 29 Juli 1993 dari pasangan Isman Yahya dan Rini Usman. Penulis merupakan anak pertama dari tiga bersaudara. Tahun 2011 penulis lulus dari SMA Negeri 4 Kota Bekasi dan pada tahun yang sama lulus seleksi masuk Institut Pertanian Bogor (IPB) melalui jalur undangan dan diterima di Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama mengikuti perkuliahan, penulis pernah aktif di berbagai organisasi kemahasiswaan baik intra maupun ekstra kampus. Di antaranya sebagai Koordinator Putri Lembaga Dakwah Kampus (LDK) Masjid Al Hurriyyah IPB, Ketua Forum Keluarga Keputrian Forum Silaturrahim Lembaga Dakwah Kampus (FSLDK) IPB, Bendahara Komisi Internal Dewan Perwakilan Mahasiwa (DPM) TPB IPB, staf keLDK-an Forum Silaturrahim Lembaga Dakwah Kampus Indonesia. Selain itu juga, penulis juga lolos dalam program wirausaha dan mendapat hibah dana Career Development IPB, menerima beasiswa Super Semar 2012-2013 dan Karya Salemba Empat 2014-2015 dan menjadi asisten dosen mata kuliah Agama Islam serta pernah menjadi staf pengajar matematika di lembaga bimbingan belajar Spektrum.

SUPER EDGE MAGIC STRENGTH PADA GRAF FIRE CRACKERS DAN GRAF BANANA TREES ANDINI QASHRINA DARMANAGARI

Recommend Documents