MAGIC STRENGTH PADA GRAF PATH, BISTAR, DAN CYCLE GANJIL
DIMAS ENGGAR SATRIA
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2013
PERNYATAAN MENGENAI SKRIPSI DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Magic Strength pada Graf Path, Bistar, dan Cycle Ganjil adalah benar karya saya dengan arahan dari komisi 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, Desember 2013 Dimas Enggar Satria NIM G54080049
ii
ABSTRAK DIMAS ENGGAR SATRIA. Magic Strength pada Graf Path, Bistar, dan Cycle Ganjil. Dibimbing oleh TEDUH WULANDARI MAS’OED dan MUHAMMAD ILYAS. Karya ilmiah ini membuktikan teorema-teorema untuk memperoleh magic strength pada graf path, graf bistar, dan graf cycle ganjil. Magic strength pada suatu graf adalah nilai minimum dari semua bilangan konstan yang diperoleh dari semua magic labeling pada graf tersebut. Magic labeling pada suatu graf merupakan pelabelan total pada simpul dan sisi suatu graf dengan labelnya adalah bilangan asli, dimana jumlah label-label pada sebuah sisi yang incident dengan dua simpul adalah suatu bilangan konstan. Terdapat empat pembuktian teorema yang dibahas dalam karya ilmiah ini. Misalkan n merupakan suatu bilangan asli. Teorema pertama membuktikan bahwa nilai magic strength dari graf path berderajat 2n adalah 5n+1. Teorema kedua membuktikan bahwa nilai magic strength dari graf path berderajat 2n+1 adalah 5n+3. Teorema ketiga membuktikan bahwa nilai magic strength dari graf bistar berderajat n adalah 5n+6. Teorema keempat membuktikan bahwa nilai magic strength dari graf cycle berderajat 2n+1 adalah 5n+4. Kata kunci: graph labeling, magic labeling, magic strength
ABSTRACT DIMAS ENGGAR SATRIA. Magic Strength in Path, Bistar, and Odd-Cycle Graphs. Supervised by TEDUH WULANDARI MAS’OED and MUHAMMAD ILYAS. This manuscript proves theorems to obtain magic strength; a minimum of all constant number that has been attained from all magic labeling in that graph, in path, bistar, and odd-cycle graphs. Magic labeling in the graph is defined as a total of labeling two vertices and one edge which is incident with it. The label is natural number and the total of labeling is a constant number. There are four theorems discussed in this paper. Suppose n is a natural number. The first theorem proves that magic strength value of a path graph with degree 2n is 5n+1. The second theorem proves that magic strength value of a path graph with degree 2n+1 is 5n+3. The third theorem proves that magic strength value of a bistar graph with degree n is 5n+6. The fourth theorem proves that magic strength value of a cycle graph with degree 2n+1 is 5n+4. Keywords: graph labeling, magic labeling, magic strength
MAGIC STRENGTH PADA GRAF PATH, BISTAR, DAN CYCLE GANJIL
DIMAS ENGGAR SATRIA
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 2013
vii
Judul Skripsi : Magic Strength pada Graf Path, Bistar, dan Cycle Ganjil Nama : Dimas Enggar Satria NIM : G54080049
Disetujui oleh
Teduh Wulandari Mas’oed, MSi Pembimbing I
Muhammad Ilyas, MSc Pembimbing II
Diketahui oleh
Dr Toni Bakhtiar, MSc Ketua Departemen
Tanggal Lulus:
viii
PRAKATA Puji dan syukur penulis panjatkan kepada Allah subhanahu wa ta’ala atas segala rahmat dan karunia-Nya serta shalawat dan salam kepada Nabi Muhammad SAW sehingga penelitian ini berhasil diselesaikan. Tema yang dipilih dalam penelitian ini ialah Magic Labeling dengan judul Magic Strength pada Graf Path, Bistar, dan Cycle Ganjil. Terima kasih penulis ucapkan kepada Ibu Teduh Wulandari Mas’oed, MSi dan Bpk Muhammad Ilyas, MSc selaku pembimbing. Ungkapan terima kasih juga disampaikan kepada ayah, ibu, kakak serta Astriani, atas segala doa dan saran kepada penulis dalam penyusunan skripsi ini. Terima kasih juga disampaikan untuk rekan kerja penelitian saya, yaitu Rahmalia Yuliarni dan Pipin Urip atas segala saran dan masukan terkait penelitian. Selain itu, tidak lupa rasa terima kasih sebesar-besarnya kepada teman-teman di Departemen Matematika IPB angkatan 45. Semoga karya ilmiah ini bermanfaat bagi dunia ilmu pengetahuan khususnya dalam bidang matematika dan dapat menjadi inspirasi bagi penelitian-penelitian selanjutnya.
Bogor, Desember 2013
Dimas Enggar Satria
ix
DAFTAR ISI
DAFTAR GAMBAR
vi
PENDAHULUAN
1
Latar Belakang
1
Tujuan
1
LANDASAN TEORI
2
Teori Graf
2
Pelabelan Graf
5
PEMBAHASAN Graf Path Derajat 2n
7 7
Graf Path Derajat 2n + 1
11
Graf Bistar Derajat n
15
Graf Cycle Derajat 2n + 1
21
SIMPULAN DAN SARAN
24
Simpulan
24
Saran
24
DAFTAR PUSTAKA
25
RIWAYAT HIDUP
26
DAFTAR GAMBAR 1 Graf G = (V, E). 2 Graf J tak terhubungkan 3 Cycle dengan 3 simpul. 4 Graf Bistar dengan 2 simpul pusat dan 6 simpul cabang. 5 Graf G taktrivial dengan 3 simpul. 6 Graf cycle ber-order 6. 7 Graf path P3. 8 Magic labeling pada graf path P3. 9 Graf path P6. 10 Magic labeling pada graf path P6. 11 Graf path P7. 12 Magic labeling pada graf path P7. 13 Graf bistar B5,5. 14 Magic labeling pada graf bistar B5,5. 15 Graf cycle C3. 16 Magic labeling pada graf cycle C3.
2 3 4 4 5 5 6 7 8 9 11 13 15 17 21 22
PENDAHULUAN Latar Belakang Cabang ilmu dalam bidang matematika yang diperkenalkan pertama kali oleh seorang ahli matematika asal Swiss, Leonardo Euler pada tahun 1736, salah satunya adalah “Teori Graf”. Saat itu Euler memperkenalkan teori graf untuk menyelesaikan masalah jembatan Königsberg yang merupakan salah satu masalah transportasi yang terjadi di kota Kaliningrad, Rusia. Sejak saat itu teori graf mulai mendapat banyak perhatian sehingga teori tersebut terus dikembangkan dan memiliki banyak terapan, diantaranya 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 menandai suatu simpul dan sisi, sedemikian sehingga setiap simpul dan sisi yang saling adjacent memiliki tanda yang berbeda. Ada beberapa metode yang dapat digunakan untuk menandai suatu simpul/sisi, salah satunya adalah metode pelabelan. Pelabelan pada suatu graf merupakan fungsi injektif yang memetakan setiap unsur himpunan simpul (vertex) dan setiap unsur himpunan sisi (edge) ke bilangan asli yang disebut label (Gallian 2009). Pelabelan pada graf terdiri dari pelabelan simpul, pelabelan sisi, dan pelabelan total. Pelabelan simpul adalah pelabelan dengan domain himpunan simpul, pelabelan sisi adalah pelabelan dengan domain himpunan sisi, dan pelabelan total adalah pelabelan dengan domain gabungan himpunan simpul dan sisi. Ada banyak jenis pelabelan pada graf yang telah dikembangkan, diantaranya adalah pelabelan graceful, pelabelan harmoni, pelabelan total, magic labeling, dan pelabelan anti ajaib (antimagic). Magic labeling pada suatu graf merupakan pelabelan total pada simpul dan sisi suatu graf dengan labelnya adalah bilangan asli, dengan jumlah label-label pada sebuah sisi dan dua simpul ujungnya adalah suatu bilangan konstan. Pada magic labeling, jumlah label-label pada sebuah sisi dan dua simpul ujungnya menghasilkan suatu konstanta ajaib. Nilai terkecil dari konstanta ajaib yang didapat dari magic labeling tersebut adalah magic strength. Dalam karya ilmiah ini akan dibuktikan beberapa teorema untuk memperoleh magic strength pada graf path, graf bistar, dan graf cycle. Sumber utama dalam karya ilmiah ini adalah artikel berjudul “Magic Strength of a Graph” yang ditulis Selvan Avadayappan, Vasuki, dan Jeyanthi pada tahun 2000.
Tujuan Tujuan dari penulisan karya ilmiah ini adalah membuktikan teorema-teorema untuk memperoleh nilai konstanta ajaib terkecil (magic strength) pada graf path Pn, graf bistar Bn,n, dan graf cycle C2n+1.
2
LANDASAN TEORI Pada bab ini akan dijelaskan beberapa definisi dalam teori graf dan pelabelan graf yang akan digunakan dalam penyusunan karya ilmiah ini. Teori Graf Definisi 1 (Graf) Suatu graf G adalah pasangan terurut (V, E) dengan V adalah himpunan takkosong dan berhingga dan E adalah himpunan pasangan takterurut yang menghubungkan elemen-elemen V. Graf G dinotasikan G = (V, E). Elemen V disebut simpul (vertex) sedangkan elemen E disebut sisi (edge). Himpunan dari simpul-simpul pada graf G dinotasikan dengan V(G), sedangkan himpunan dari sisi-sisi pada graf G dinotasikan dengan E(G). (Foulds 1992) Contoh graf G dapat dilihat pada Gambar 1. Himpunan simpul dan himpunan sisi graf pada Gambar 1 adalah V(G) = {a, b, c, d, e, f} E(G) = {{a, b}, {b, c}, {b, d}, {d, e}, {e, f}} G:
a
c
e
b
d
f
Gambar 1 Graf G = (V, E). Definisi 2 (Order dan Size) Misalkan diberikan graf G. Banyaknya simpul pada graf G disebut order dan banyaknya sisi pada graf G disebut size. Order dari graf G dinotasikan dengan |V(G)| dan size dari graf G dinotasikan dengan |E(G)|. (Chartrand & Oellermann 1993) Pada Gambar 1, nilai dari |V(G)| = 6 dan |E(G)| = 5. Definisi 3 (Incident dan adjacent) Misalkan diberikan graf G. Jika e = {u, v} ∈ E(G) dengan u, v ∈ V(G) maka u dan v dikatakan adjacent di G dan e dikatakan incident dengan u dan v. (Chartrand & Oellermann 1993) Pada Gambar 1, misalkan e = {a, b} ∈ E(G) maka a dan b dikatakan adjacent di G dan e dikatakan incident dengan a dan b.
3
Definisi 4 (Degree) Derajat (degree) dari suatu simpul v pada graf G adalah banyaknya sisi yang incident dengan v dan dinotasikan dengan deg(v). (Chartrand & Oellermann 1993) Pada Gambar 1, derajat setiap simpulnya ialah deg(a) = 1, deg(b) = 3, deg(c) = 1, deg(d) = 2, deg(e) = 2, dan deg(f ) = 1. Definisi 5 (Walk) Suatu walk pada graf G adalah suatu barisan simpul dan sisi dari graf G dengan bentuk {v1, {v1, v2}, v2, {v2, v3}, v3, … , {vn-1, vn}, vn} dan dapat dituliskan sebagai {v1, v2, … , vn} atau v1, v2, … , vn. Suatu walk yang menghubungkan v1 dengan vn dikatakan tertutup jika v1 = vn. Jika v1 ≠ vn maka walk tersebut dikatakan terbuka. (Foulds 1992) Pada Gambar 1, terdapat walk terbuka yaitu walk {a, {a, b}, b, {b, d}, d, {d, e}, e, {e, f}, f}. Definisi 6 (Path) Path pada suatu graf G adalah suatu walk dengan semua simpulnya berbeda. Graf ber-order n ≥ 1 yang berbentuk path disebut graf path ber-order n, dituliskan Pn. (Chartrand & Oellermann 1993) Pada Gambar 1, {a, b, d, e, f} merupakan salah satu contoh path. Definisi 7 (Graf Terhubungkan) Graf G dikatakan terhubungkan jika setiap 2 simpul yang berbeda pada graf G dihubungkan oleh suatu path dan dikatakan tak terhubungkan jika ada 2 simpul yang berbeda, tidak ada path yang menghubungkan kedua simpul tersebut. (Foulds 1992) Contoh graf terhubungkan dapat dilihat pada Gambar 1, sedangkan contoh graf tak terhubungkan dapat dilihat pada Gambar 2. J: e c f
a
b
d
Gambar 2 Graf J tak terhubungkan
4
Definisi 8 (Cycle) Cycle pada graf G adalah walk tertutup yang mengandung setidaknya tiga simpul berbeda. (Foulds 1992) Contoh cycle dapat dilihat pada Gambar 3. a c b Gambar 3 Cycle dengan 3 simpul. Definisi 9 (Tree) Tree adalah suatu graf terhubung yang tidak mempunyai cycle. (Foulds 1992) Gambar 1 merupakan contoh tree dengan 6 simpul. Definisi 10 (Graf Bistar) Graf G disebut graf bistar, dinotasikan Bn,n, jika pada graf G terdapat 2 salinan tree K1,n dimana setiap tree K1,n terdiri dari 1 simpul pusat dan simpul cabang sebanyak n, simpul pusat dari masing-masing tree K1,n dihubungkan oleh suatu sisi. (Avadayappan et. al. 2000) Contoh bistar dapat dilihat pada Pada Gambar 4 merupakan salah satu contoh bistar dimana terdiri dari 2 simpul pusat yaitu a dan e yang mana masing-masing dari simpul pusat memiliki 3 simpul cabang secara berurut yaitu b, c, d dan f, g, h. B3,3 :
f
b a
c
d
e
g
h
Gambar 4 Graf Bistar dengan 2 simpul pusat dan 6 simpul cabang. Definisi 11 (Graf Taktrivial) Suatu graf G disebut graf taktrivial jika suatu graf G memiliki order paling sedikit dua. (Chartrand & Oellermann 1993)
5
Berikut ini diberikan contoh graf taktrivial ber-order 3 G: a
b
c
Gambar 5 Graf G taktrivial dengan 3 simpul. Definisi 12 (Graf Cycle) Suatu graf ber-order n dengan n ≥ 3 yang membentuk sebuah cycle disebut graf cycle dan dinotasikan dengan Cn. (Chartrand & Oellermann 1993) Berikut ini diberikan contoh graf cycle ber-order 6. C6 :
f
e
a d b c Gambar 6 Graf cycle ber-order 6.
Pelabelan Graf Karya ilmiah ini membahas suatu magic labeling untuk mencari nilai konstanta ajaib terkecil pada graf path, graf n-bistar, dan graf cycle. Berikut dijelaskan beberapa definisi tentang pelabelan graf. Definisi 13 (Pelabelan) Pelabelan pada graf merupakan fungsi injektif yang memetakan untuk setiap unsur himpunan simpul (vertex) dan untuk setiap unsur himpunan sisi (edge) ke bilangan asli yang disebut label. (Gallian 2009) Pada tahun 1970, Kotzig dan Rosa menuliskan definisi mengenai magic labeling, definisi tersebut digunakan juga oleh Avadayappan, Vasuki, dan Jeyanthi dalam penulisan jurnalnya pada tahun 2000. Definisi 14 (Magic Labeling) Misalkan G graf dengan himpunan simpul V dan himpunan sisi E. Magic labeling pada graf G adalah suatu fungsi bijektif f : V ∪ E → {1, 2, 3, … , v + ɛ}, sehingga untuk setiap sisi xy, nilai penjumlahan f(x) + f(y) + f(xy) = c(f), dimana c(f) merupakan konstanta ajaib dari fungsi bijektif f. (Avadayappan et. al. 2000)
6
Definisi 15 (Graf Magic) Graf magic adalah graf yang memiliki magic labeling. (Gallian 2009) Definisi 16 (Magic Strength) Misalkan G graf magic dengan himpunan simpul V dan himpunan sisi E. Magic strength pada graf G, m(G), didefinisikan sebagai nilai minimum dari semua c(f). Artinya, m(G) = min{c(f) : f adalah magic labeling dari G}. (Avadayappan et. al. 2000) Berikut ini diberikan contoh magic strength pada suatu graf. Misalkan diberikan graf path P3 seperti pada Gambar 7. Banyaknya simpul ialah 3 dan banyaknya sisi 2, simpul dan sisi dari graf path P3 masing-masing akan diberi label 1, 2, 3, 4, dan 5. P3 :
u1
u2
u3
Gambar 7 Graf path P3. Misalkan simpul-simpul dan sisi-sisi pada graf path P3 diberi 3 pelabelan yang berbeda, yaitu untuk pelabelan pertama, misalnya f(u1) = 1 f(u1u2) = 4 f(u2) = 5 f(u2u3) = 3 f(u3) = 2 maka akan diperoleh penjumlahan label dari tiap sisi yang incident terhadap 2 simpul ujungnya : f(u1) + f(u2) + f(u1u2) = 1 + 5 + 4 = 10 f(u2) + f(u3) + f(u2u3) = 5 + 2 + 3 = 10 sehingga didapat nilai c(f) = 10 dan dapat digambarkan seperti Gambar 8 (a). Pelabelan kedua, misalnya f(u1) = 1 f(u1u2) = 5 f(u2) = 3 f(u2u3) = 4 f(u3) = 2 maka akan diperoleh penjumlahan label dari tiap sisi yang incident terhadap 2 simpul ujungnya : f(u1) + f(u2) + f(u1u2) = 1 + 3 + 5 = 9 f(u2) + f(u3) + f(u2u3) = 3 + 2 + 4 = 9 sehingga didapat nilai c(f) = 9 dan dapat digambarkan seperti Gambar 8 (b). Pelabelan ketiga, misalnya f(u1) = 3 f(u1u2) = 4 f(u2) = 1 f(u2u3) = 5 f(u3) = 2 maka akan diperoleh penjumlahan label dari tiap sisi yang incident terhadap 2 simpul ujungnya : f(u1) + f(u2) + f(u1u2) = 3 + 1 + 4 = 8 f(u2) + f(u3) + f(u2u3) = 1 + 2 + 5 = 8 sehingga didapat nilai c(f) = 8 dan dapat digambarkan seperti Gambar 8 (c).
7
(a) 1
5
2 3
4 (b) 1
3 5
2 4
(c) 3
1 4
2 5
Gambar 8 Magic labeling pada graf path P3. Dari ketiga pelabelan graf di atas, didapat nilai c(f) berturut-turut adalah 10, 9, dan 8. Jadi, untuk magic strength dari graf P3, m(P3) = min{10, 9, 8} = 8. Lema 1 Jika G adalah graf magic, maka untuk memperoleh magic strength akan diberikan kisaran nilai sebagai berikut v + ɛ + 3 ≤ m(G) ≤ 2v + 2ɛ dengan v adalah banyaknya simpul dan ɛ adalah banyaknya sisi. (Avadayappan et. al. 2000)
PEMBAHASAN Karya ilmiah ini membahas teorema-teorema mengenai magic strength pada graf path, graf n-bistar, dan graf cycle. Permasalahan utama dalam karya ilmiah ini adalah bagaimana memperoleh nilai konstanta ajaib terkecil dari suatu magic labeling pada graf-graf tersebut. Magic labeling tidak hanya dilakukan satu kali melainkan dilakukan beberapa kali hingga diperoleh beberapa nilai konstanta ajaib. Semua nilai konstanta ajaib tersebut akan diambil nilai konstanta ajaib terkecil yang mana nilai konstanta ajaib terkecil yang didapat merupakan magic strength pada graf tersebut. Graf Path Derajat 2n Misalkan G graf dengan himpunan vertex V dan himpunan edge E. Path pada suatu graf G adalah suatu walk dengan semua simpulnya berbeda. Graf berorder m ≥ 1 yang berbentuk path disebut graf path ber-order m, dituliskan Pm. Berikut akan diperlihatkan contoh magic labeling untuk mencari magic strength pada graf path P2n sebelum membuktikan teorema 1. Misalkan diberikan graf path P6 dengan bentuk seperti pada Gambar 9.
8
P6 : u1
u2
u3
u4
u5
u6
Gambar 9 Graf path P6. Pada graf path P6 diatas terdapat 6 simpul dan 5 sisi sehingga kisaran nilai untuk membantu memperoleh magic strength adalah 6 + 5 + 3 ≤ m(G) ≤ (2)(6) + (2)(5) 14 ≤ m(G) ≤ 22 Misalkan simpul-simpul dan sisi-sisi pada graf path P6 diberi 4 pelabelan yang berbeda, yaitu untuk pelabelan pertama, misalnya f(u1) = 10 f(u1u2) = 3 f(u2) = 4 f(u2u3) = 8 f(u3) = 5 f(u3u4) = 11 f(u4) = 1 f(u4u5) = 7 f(u5) = 9 f(u5u6) = 6 f(u6) = 2 maka akan diperoleh penjumlahan label dari tiap sisi yang incident terhadap 2 simpul ujungnya : f(u1) + f(u2) + f(u1u2) = 10 + 4 + 3 = 17 f(u2) + f(u3) + f(u2u3) = 4 + 5 + 8 = 17 f(u3) + f(u4) + f(u3u4) = 5 + 1 + 11 = 17 f(u4) + f(u5) + f(u4u5) = 1 + 9 + 7 = 17 f(u5) + f(u6) + f(u5u6) = 9 + 2 + 6 = 17 sehingga didapat nilai c(f) = 17 dan dapat digambarkan seperti Gambar 10 (a). Pelabelan kedua, misalnya f(u1) = 6 f(u1u2) = 4 f(u2) = 8 f(u2u3) = 9 f(u3) = 1 f(u3u4) = 7 f(u4) = 10 f(u4u5) = 3 f(u5) = 5 f(u5u6) = 11 f(u6) = 2 maka akan diperoleh penjumlahan label dari tiap sisi yang incident terhadap 2 simpul ujungnya : f(u1) + f(u2) + f(u1u2) = 6 + 8 + 4 = 18 f(u2) + f(u3) + f(u2u3) = 8 + 1 + 9 = 18 f(u3) + f(u4) + f(u3u4) = 1 + 10 + 7 = 18 f(u4) + f(u5) + f(u4u5) = 10 + 5 + 3 = 18 f(u5) + f(u6) + f(u5u6) = 5 + 2 + 11 = 18 sehingga didapat nilai c(f) = 18 dan dapat digambarkan seperti Gambar 10 (b). Pelabelan ketiga, misalnya f(u1) = 11 f(u1u2) = 1 f(u2) = 4 f(u2u3) = 10 f(u3) = 2 f(u3u4) = 9 f(u4) = 5 f(u4u5) = 8 f(u5) = 3 f(u5u6) = 6 f(u6) = 7
9
maka akan diperoleh penjumlahan label dari tiap sisi yang incident terhadap 2 simpul ujungnya : f(u1) + f(u2) + f(u1u2) = 11 + 4 + 1 = 16 f(u2) + f(u3) + f(u2u3) = 4 + 2 + 10 = 16 f(u3) + f(u4) + f(u3u4) = 2 + 5 + 9 = 16 f(u4) + f(u5) + f(u4u5) = 5 + 3 + 8 = 16 f(u5) + f(u6) + f(u5u6) = 3 + 7 + 6 = 16 sehingga didapat nilai c(f) = 16 dan dapat digambarkan seperti Gambar 10 (c). Pelabelan keempat, misalnya f(u1) = 1 f(u1u2) = 11 f(u2) = 4 f(u2u3) = 10 f(u3) = 2 f(u3u4) = 9 f(u4) = 5 f(u4u5) = 8 f(u5) = 3 f(u5u6) = 7 f(u6) = 6 maka akan diperoleh penjumlahan label dari tiap sisi yang incident terhadap 2 simpul ujungnya : f(u1) + f(u2) + f(u1u2) = 1 + 4 + 11 = 16 f(u2) + f(u3) + f(u2u3) = 4 + 2 + 10 = 16 f(u3) + f(u4) + f(u3u4) = 2 + 5 + 9 = 16 f(u4) + f(u5) + f(u4u5) = 5 + 3 + 8 = 16 f(u5) + f(u6) + f(u5u6) = 3 + 6 + 7 = 16 sehingga didapat nilai c(f) = 16 dan dapat digambarkan seperti Gambar 10 (d). (a)
4
10
8
3 (b)
8
6 4
(c)
1
11
11 7 6
8 3
5 9
2
3
5
2 10
5 3
9
10 4
1
7
2 6
7 10
2
4
11
9
1 11
9
1 (d)
5
8
6 7
Gambar 10 Magic labeling pada graf path P6. Dari keempat pelabelan graf di atas, didapat nilai c(f) secara berturut-turut adalah 17, 18, 16, 16. Jadi, untuk magic strength dari graf P6, m(P6) = min {17, 18, 16, 16 } = 16. Cara pelabelan tersebut merupakan salah satu contoh magic labeling pada graf path P2n. Berikut akan dibuktikan teorema 1 yang akan digunakan untuk menentukan magic strength pada graf path P2n.
10
Teorema 1 Misalkan P2n adalah suatu graf path dengan n ϵ N. Nilai magic strength dari P2n adalah m(P2n) = 5n + 1 Bukti : Misalkan P2n adalah graf path dengan banyaknya simpul 2n maka P2n memiliki |E(P2n)| = |V(P2n)| - 1 dengan |V(P2n)| = 2n. Akan dibuktikan m(P2n) = 5n + 1. Pembuktian m(P2n) = 5n + 1 dilakukan dengan 2 tahap. (i)
Akan dibuktikan m(P2n) ≥ 5n + 1. Misalkan P2n memiliki pelabelan magic f dengan konstanta c(f) dan memiliki sisi sebanyak 2n – 1 dengan setiap sisi yang incident terhadap 2 simpul ujungnya. Sehingga jumlah konstanta yang diperoleh dari semua sisinya dapat dirumuskan sebagai berikut. c(f) c(f) c(f) ⁞ c(f)
= = = =
f(v1) f(v2) f(v3) ⁞ f(vɛ)
ɛc(f)
=
𝑣𝜖𝑉
+ + +
f(v2) f(v3) f(v4) ⁞ f(vɛ + 1)
+
+ + +
f(v1v2) f(v2v3) f(v3v4) ⁞ f(vɛvɛ + 1)
+
𝑑𝑒𝑔(𝑣) 𝑓(𝑣)
+
𝑒𝜖𝐸
𝑓(𝑒)
Karena ɛ(P2n) = 2n – 1 , maka (2n – 1) c(f)
=
2𝑛 – 1 𝑖 = 2 2𝑓(𝑣𝑖 )
=
2𝑛 𝑖 = 1 𝑓(𝑣𝑖 )
2𝑛 – 1 𝑖 = 1 𝑓(𝑒𝑖 )
+ f(v1) + f(v2n) + 2𝑛 – 1 𝑖 = 1 𝑓(𝑒𝑖 )
+
+
2𝑛 – 1 𝑖 = 2 𝑓(𝑣𝑖 )
Karena ɛ + v = 4n – 1 , maka = (1 + 2 + … + 4n – 1) + = (4n – 1) (2n) +
2𝑛 – 1 𝑖 = 2 𝑓(𝑣𝑖 )
2𝑛 – 1 𝑖 = 2 𝑓(𝑣𝑖 )
Sehingga, c(f)
=
(4𝑛 – 1) (2𝑛) (2𝑛 – 1)
+ 1
2𝑛 – 1 𝑖 = 2 𝑓(𝑣𝑖 )
(2𝑛 – 1)
≥ 4n + 1 + (2𝑛 – 1) + = 4n + 1 +
(2 + 3 + … + 2𝑛 – 1) (2𝑛 – 1)
(1 + 2 + 3 + … + 2𝑛 – 1) (2𝑛 – 1)
= (4n – 1) + 2 +
(1 + 2 + 3 + … + 2𝑛 – 2 + 2𝑛 – 1)
˃ (4n – 1) + 2 +
(1 + 2 + 3 + … + 2𝑛 – 2)
(2𝑛 – 1)
(2𝑛 – 1)
= (4n – 1) + 2 + (n – 1) = 5n
+
11
Akibatnya c(f) ˃ 5n Sehingga c(f) ≥ 5n + 1 Karena m(P2n) merupakan nilai minimum dari semua kemungkinan nilai c(f) maka m(P2n) pasti memenuhi ketaksamaan m(P2n) ≥ 5n + 1. (ii)
Akan dibuktikan m(P2n) ≤ 5n + 1 dengan menunjukan eksistansi konstanta c(f) pada graf P2n. Misalkan v1, v2, v3, …, v2n adalah simpul terurut dari P2n dan e1, e2, e3, …, e2n-1 adalah sisi terurut dari P2n. Artinya, ei = vivi+1 untuk 1 ≤ i ≤ 2n – 1. Pilih fungsi label : f (v2i – 1) = i untuk 1 ≤ i ≤ n, f (v2i) = n + i untuk 1 ≤ i ≤ n, f (ei) = 4n – i untuk 1 ≤ i ≤ 2n – 1. Akibatnya diperoleh konstanta c(f) sebagai berikut. c(f) = f(x) + f(y) + f(xy) + f (v2i) + f (e2i - 1) = f (v2i – 1) = i + n+i + 4n – (2i – 1) = i + n+i + 4n – 2i + 1 = 5n + 1 Karena c(f) = 5n + 1 merupakan salah satu nilai konstanta ajaib yang didapat maka m(P2n) ≤ 5n + 1.
Dari tahap (i) dan (ii) dapat dibuktikan m(P2n) ≤ 5n + 1 dan m(P2n) ≥ 5n + 1, maka dapat diperoleh bahwa m(P2n) = 5n + 1. Dengan demikian dapat dibuktikan bahwa setiap graf path P2n memiliki nilai magic strength yaitu 5n + 1. ■ Terbukti
Graf Path Derajat 2n + 1 Berikut akan diperlihatkan contoh magic labeling untuk memperoleh magic strength pada graf path P2n+1 sebelum membuktikan teorema 2. Misalkan diberikan graf path P7 dengan bentuk seperti pada Gambar 11. P7 : u1
u2
u3
u4
u5
u6
u7
Gambar 11 Graf path P7. Pada graf path P7 diatas terdapat 7 simpul dan 6 sisi sehingga kisaran nilai untuk membantu memperoleh magic strength adalah 7 + 6 + 3 ≤ m(G) ≤ (2)(7) + (2)(6) 16 ≤ m(G) ≤ 30
12
Misalkan simpul-simpul dan sisi-sisi pada graf path P7 diberi 4 pelabelan yang berbeda, yaitu untuk pelabelan pertama, misalnya f(u1) = 4 f(u1u2) = 13 f(u2) = 1 f(u2u3) = 12 f(u3) = 5 f(u3u4) = 11 f(u4) = 2 f(u4u5) = 10 f(u5) = 6 f(u5u6) = 9 f(u6) = 3 f(u6u7) = 8 f(u7) = 7 maka akan diperoleh penjumlahan label dari tiap sisi yang incident terhadap 2 simpul ujungnya : f(u1) + f(u2) + f(u1u2) = 4 + 1 + 13 = 18 f(u2) + f(u3) + f(u2u3) = 1 + 5 + 12 = 18 f(u3) + f(u4) + f(u3u4) = 5 + 2 + 11 = 18 f(u4) + f(u5) + f(u4u5) = 2 + 6 + 10 = 18 f(u5) + f(u6) + f(u5u6) = 6 + 3 + 9 = 18 f(u6) + f(u7) + f(u6u7) = 3 + 7 + 8 = 18 sehingga didapat nilai c(f) = 18 dan dapat digambarkan seperti Gambar 12 (a). Pelabelan kedua, misalnya f(u1) = 11 f(u1u2) = 2 f(u2) = 6 f(u2u3) = 12 f(u3) = 1 f(u3u4) = 13 f(u4) = 5 f(u4u5) = 10 f(u5) = 4 f(u5u6) = 8 f(u6) = 7 f(u6u7) = 9 f(u7) = 3 maka akan diperoleh penjumlahan label dari tiap sisi yang incident terhadap 2 simpul ujungnya : f(u1) + f(u2) + f(u1u2) = 11 + 6 + 2 = 19 f(u2) + f(u3) + f(u2u3) = 6 + 1 + 12 = 19 f(u3) + f(u4) + f(u3u4) = 1 + 5 + 13 = 19 f(u4) + f(u5) + f(u4u5) = 5 + 4 + 10 = 19 f(u5) + f(u6) + f(u5u6) = 4 + 7 + 8 = 19 f(u6) + f(u7) + f(u6u7) = 7 + 3 + 9 = 19 sehingga didapat nilai c(f) = 19 dan dapat digambarkan seperti Gambar 12 (b). Pelabelan ketiga, misalnya f(u1) = 1 f(u1u2) = 13 f(u2) = 5 f(u2u3) = 12 f(u3) = 2 f(u3u4) = 11 f(u4) = 6 f(u4u5) = 10 f(u5) = 3 f(u5u6) = 9 f(u6) = 7 f(u6u7) = 8 f(u7) = 4 maka akan diperoleh penjumlahan label dari tiap sisi yang incident terhadap 2 simpul ujungnya : f(u1) + f(u2) + f(u1u2) = 1 + 5 + 13 = 19 f(u2) + f(u3) + f(u2u3) = 5 + 2 + 12 = 19 f(u3) + f(u4) + f(u3u4) = 2 + 6 + 11 = 19
13
f(u4) + f(u5) + f(u4u5) = 6 + 3 + 10 = 19 f(u5) + f(u6) + f(u5u6) = 3 + 7 + 9 = 19 f(u6) + f(u7) + f(u6u7) = 7 + 4 + 8 = 19 sehingga didapat nilai c(f) = 19 dan dapat digambarkan seperti Gambar 12 (c). Pelabelan keempat, misalnya f(u1) = 6 f(u1u2) = 4 f(u2) = 10 f(u2u3) = 1 f(u3) = 9 f(u3u4) = 8 f(u4) = 3 f(u4u5) = 12 f(u5) = 5 f(u5u6) = 13 f(u6) = 2 f(u6u7) = 7 f(u7) = 11 maka akan diperoleh penjumlahan label dari tiap sisi yang incident terhadap 2 simpul ujungnya : f(u1) + f(u2) + f(u1u2) = 6 + 10 + 4 = 20 f(u2) + f(u3) + f(u2u3) = 10 + 9 + 1 = 20 f(u3) + f(u4) + f(u3u4) = 9 + 3 + 8 = 20 f(u4) + f(u5) + f(u4u5) = 3 + 5 + 12 = 20 f(u5) + f(u6) + f(u5u6) = 5 + 2 + 13 = 20 f(u6) + f(u7) + f(u6u7) = 2 + 11 + 7 = 20 sehingga didapat nilai c(f) = 16 dan dapat digambarkan seperti Gambar 12 (d). (a)
4
1
(b)
11
12
6 4
6
9
10 1
4 10
11
12
3 9
7
4 8
9 5
12
8
8
10
7
7
3
3 8
9
10
13
3
6
5
2
5
1 13
(d)
1
6 2
(c)
11
12
13
2
5
11
2 13
7
Gambar 12 Magic labeling pada graf path P7. Dari 4 pelabelan graf di atas, didapat nilai c(f) secara berturut-turut adalah 18, 19, 20, 20. Jadi, untuk magic strength dari graf P6, m(P6) = min{18, 19, 19, 20 } = 18. Cara pelabelan tersebut merupakan salah satu contoh magic labeling pada graf path P2n+1. Berikut akan dibuktikan teorema 2 yang akan digunakan untuk menentukan magic strength pada graf path P2n+1. Teorema 2 Misalkan P2n+1 adalah suatu graf path dengan n ϵ N. Nilai magic strength dari P2n+1 adalah m(P2n+1) = 5n + 3
14
Bukti : Misalkan P2n+1 adalah graf path dengan banyaknya simpul 2n+1 maka P2n+1 memiliki |E(P2n+1)| = |V(P2n+1)| - 1 dengan |V(P2n+1)| = 2n+1. Akan dibuktikan m(P2n+1) = 5n + 3. Pembuktian m(P2n+1) = 5n + 3 dilakukan dengan 2 tahap. (i)
Akan dibuktikan m(P2n+1) ≥ 5n + 3. Misalkan P2n+1 memiliki pelabelan magic g dengan konstanta c(g) dan memiliki sisi sebanyak 2n dengan setiap sisi yang incident terhadap 2 simpul ujungnya. Sehingga jumlah konstanta yang diperoleh dari semua sisinya dapat dirumuskan sebagai berikut. g(v1) + g(v2) + g(v1v2) c(g) = c(g) = g(v2) + g(v3) + g(v2v3) c(g) = g(v3) + g(v4) + g(v3v4) ⁞ ⁞ ⁞ ⁞ c(g) = g(vɛ) + g(vɛ + 1) + g(vɛvɛ + 1) + ɛc(g)
=
𝑣𝜖𝑉
𝑑𝑒𝑔(𝑣) 𝑔(𝑣)
+
𝑒𝜖𝐸
𝑔(𝑒)
Karena ɛ(P2n + 1) = 2n , maka (2n) c(g)
=
2𝑛 𝑖 = 2 2𝑔(𝑣𝑖 )
+ g(v1) + g(v2n) +
=
2𝑛 + 1 𝑖 = 1 𝑔(𝑣𝑖 )
+
2𝑛 𝑖 = 1 𝑔(𝑒𝑖 )
+
2𝑛 𝑖 = 1 𝑔(𝑒𝑖 ) 2𝑛 𝑖 = 2 𝑔(𝑣𝑖 )
Karena ɛ + v = 4n + 1 , maka 2𝑛 𝑖 = 2 𝑔(𝑣𝑖 )
= (1 + 2 + … + 4n + 1) +
2𝑛 𝑖 = 2 𝑔(𝑣𝑖 )
= (4n + 1) (2n + 1) + Sehingga, c(g)
=
(4𝑛 + 1) (2𝑛 + 1) (2𝑛) 1
+
≥ 4n + 3 + (2𝑛) + = 4n + 3 +
2𝑛 𝑖 = 2 𝑔(𝑣𝑖 )
(2𝑛 )
(2 + 3 + … + 2𝑛) (2𝑛)
(1 + 2 + 3 + … + 2𝑛)
= (4n + 1) + 2 + ˃ (4n + 1) + 2 +
(2𝑛) (1 + 2 + 3 + … + 2𝑛 – 1 + 2𝑛) (2𝑛 ) (1 + 2 + 3 + … + 2𝑛 – 1) (2𝑛) 1
= (4n + 1) + 2 + (n – 2) 5
= 5n + 2 5
Akibatnya c(g) ˃ 5n + 2 Sehingga c(g) ≥ 5n + 3 Karena m(P2n+1) merupakan nilai minimum dari semua kemungkinan nilai c(g) maka m(P2n+1) pasti memenuhi ketaksamaan m(P2n+1) ≥ 5n + 3.
15
(ii)
Akan dibuktikan m(P2n+1) ≤ 5n + 3 dengan menunjukan eksistansi konstanta c(g) pada graf P2n+1. Misalkan v1, v2, v3, …, v2n+1 adalah simpul terurut dari P2n+1 dan e1, e2, e3, …, e2n adalah sisi terurut dari P2n+1. Artinya, ei = vivi+1 untuk 1 ≤ i ≤ 2n. Pilih fungsi label : g (v2i – 1) = i untuk 1 ≤ i ≤ n, g (v2i) = n + i untuk 1 ≤ i ≤ n + 1, g (ei) = 4n + 2 – i untuk 1 ≤ i ≤ 2n. Akibatnya diperoleh konstanta c(g) sebagai berikut. c(g) = g(x) + g(y) + g(xy) = g (v2i) + g (v2i - 1) + g (e2i - 1) = i + n+i + 4n + 2 – (2i – 1) = i + n+i + 4n + 2 – 2i + 1 = 5n + 3 Karena c(g) = 5n + 3 merupakan salah satu nilai konstanta ajaib yang didapat maka m(P2n+1) ≤ 5n + 3.
Dari tahap (i) dan (ii) dapat dibuktikan m(P2n+1) ≤ 5n + 3 dan m(P2n+1) ≥ 5n + 3, maka dapat diperoleh bahwa m(P2n+1) = 5n + 3. Dengan demikian dapat dibuktikan bahwa setiap graf path P2n+1 memiliki nilai magic strength yaitu 5n + 3. ■ Terbukti
Graf Bistar Derajat n Misalkan G graf dengan himpunan vertex V dan himpunan edge E. Graf G disebut graf bistar, dinotasikan Bn,n, jika pada graf G terdapat 2 salinan tree K1,n dimana setiap tree K1,n terdiri dari 1 simpul pusat dan simpul cabang sebanyak n, simpul pusat dari masing-masing tree K1,n dihubungkan oleh suatu sisi. Berikut akan diperlihatkan contoh magic labeling untuk memperoleh magic strength pada graf bistar Bn,n sebelum membuktikan teorema 3. Misalkan diberikan graf bistar B5,5 dengan bentuk seperti pada Gambar 13. B5,5 :
u1
v1 v2
u2 vv1
uu1
vv2
uu2 u
u3
uu3 uu4 u4 u5
uv
v
v3
vv3 vv4
uu5
vv5
v4 v5
Gambar 13 Graf bistar B5,5.
16
Pada graf bistar B5,5 diatas terdapat 12 simpul dan 11 sisi sehingga kisaran nilai untuk membantu memperoleh magic strength adalah 12 + 11 + 3 ≤ m(G) ≤ (2)(12) + (2)(11) 26 ≤ m(G) ≤ 46 Misalkan simpul-simpul dan sisi-sisi pada graf bistar B5,5 diberi 2 pelabelan yang berbeda, yaitu untuk pelabelan pertama, misalnya f(u) = 7 f(uv) = 9 f(v) = 6 f(uu1) = 23 f(u1) = 1 f(uu2) = 22 f(u2) = 2 f(uu3) = 21 f(u3) = 3 f(uu4) = 20 f(u4) = 4 f(uu5) = 19 f(u5) = 5 f(vv1) = 12 f(v1) = 13 f(vv2) = 11 f(v2) = 14 f(vv3) = 10 f(v3) = 15 f(vv4) = 9 f(v4) = 16 f(vv5) = 8 f(v5) = 17 maka akan diperoleh penjumlahan label dari tiap sisi yang incident terhadap 2 simpul ujungnya : f(u) + f(v) + f(uv) = 7 + 6 + 18 = 31 f(u) + f(u1) + f(uu1) = 7 + 1 + 23 = 31 f(u) + f(u2) + f(uu2) = 7 + 2 + 22 = 31 f(u) + f(u3) + f(uu3) = 7 + 3 + 21 = 31 f(u) + f(u4) + f(uu4) = 7 + 4 + 20 = 31 f(u) + f(u5) + f(uu5) = 7 + 5 + 19 = 31 f(v) + f(v1) + f(vv1) = 6 + 13 + 12 = 31 f(v) + f(v2) + f(vv2) = 6 + 14 + 11 = 31 f(v) + f(v3) + f(vv3) = 6 + 15 + 10 = 31 f(v) + f(v4) + f(vv4) = 6 + 16 + 9 = 31 f(v) + f(v5) + f(vv5) = 6 + 17 + 8 = 31 sehingga didapat nilai c(f) = 31 dan dapat digambarkan seperti Gambar 14 (a). Pelabelan kedua, misalnya f(u) = 1 f(uv) = 18 f(v) = 12 f(uu1) = 19 f(u1) = 11 f(uu2) = 20 f(u2) = 10 f(uu3) = 21 f(u3) = 9 f(uu4) = 22 f(u4) = 8 f(uu5) = 23 f(u5) = 7 f(vv1) = 13 f(v1) = 6 f(vv2) = 14 f(v2) = 5 f(vv3) = 15 f(v3) = 4 f(vv4) = 16 f(v4) = 3 f(vv5) = 17 f(v5) = 2
17
maka akan diperoleh penjumlahan label dari tiap sisi yang incident terhadap 2 simpul ujungnya : f(u) + f(v) + f(uv) = 1 + 12 + 18 = 31 f(u) + f(u1) + f(uu1) = 1 + 11 + 29 = 31 f(u) + f(u2) + f(uu2) = 1 + 10 + 20 = 31 f(u) + f(u3) + f(uu3) = 1 + 9 + 21 = 31 f(u) + f(u4) + f(uu4) = 1 + 8 + 22 = 31 f(u) + f(u5) + f(uu5) = 1 + 7 + 23 = 31 f(v) + f(v1) + f(vv1) = 12 + 6 + 13 = 31 f(v) + f(v2) + f(vv2) = 12 + 5 + 14 = 31 f(v) + f(v3) + f(vv3) = 12 + 4 + 15 = 31 f(v) + f(v4) + f(vv4) = 12 + 3 + 16 = 31 f(v) + f(v5) + f(vv5) = 12 + 2 + 17 = 31 sehingga didapat nilai c(f) = 31 dan dapat digambarkan seperti Gambar 14 (b). (a)
1
13
23
12
14
2
11
22 7
3
21
6 18
20 19
9
8
16
4
(b)
5
17
11
6 5
10 19
13 14
20 1
9
18
12
4
15
21 22 8
15
10
23
17
16 3
2 7 Gambar 14 Magic labeling pada graf bistar B5,5. Dari kedua pelabelan graf di atas, didapat nilai c(f) secara berturut-turut adalah 31 dan 31. Jadi, untuk magic strength dari graf bistar B5,5, m(B5,5) = min{31, 31} = 31. Cara pelabelan tersebut merupakan salah satu contoh magic labeling pada graf bistar Bn,n. Berikut akan dibuktikan teorema 3 yang akan digunakan untuk menentukan magic strength pada graf bistar Bn,n.
18
Teorema 3 Misalkan Bn,n adalah suatu graf bistar dengan n ϵ N. Nilai magic strength dari Bn,n adalah m(Bn,n) = 5n + 6 Bukti : Misalkan Bn,n adalah graf bistar dengan banyaknya simpul 2n+2 maka Bn,n memiliki |E(Bn,n)| = |V(Bn,n)| - 1 dengan |V(Bn,n)| = |V(K1,n)| + |V(K1,n)| = (n+1) + (n+1) = 2n + 2. Akan dibuktikan m(Bn,n) = 5n + 6. Pembuktian m(Bn,n) = 5n + 6 dilakukan dengan 2 tahap. (i)
Akan dibuktikan m(Bn,n) ≥ 5n + 6. Misalkan Bn,n memiliki pelabelan magic f dengan konstanta c(f) dan memiliki sisi sebanyak 2n + 1 dengan setiap sisi yang incident terhadap 2 simpul ujungnya. Sehingga jumlah konstanta yang diperoleh dari semua sisinya dapat dirumuskan sebagai berikut. c(f) = f(u) + f(u1) + f(uu1) c(f) = f(u) + f(u2) + f(uu2) c(f) = f(u) + f(u3) + f(uu3) ⁞ ⁞ ⁞ ⁞ c(f) = f(u) + f(un) + f(uun) c(f) = f(v) + f(v1) + f(vv1) c(f) = f(v) + f(v2) + f(vv2) c(f) = f(v) + f(v3) + f(vv3) ⁞ ⁞ ⁞ ⁞ c(f) = f(v) + f(vn) + f(vvn) c(f) = f(u) + f(v) + f(uv) + n c(f) + n c(f) + c(f)
= (n f(u) + n f(v) + f(u)) 𝑛 𝑛 𝑖 = 1 𝑓(𝑢𝑖 ) + 𝑖 = 1 𝑓(𝑣𝑖 ) + f(v)) ( 𝑛𝑖= 1 𝑓(𝑢𝑢𝑖 ) + 𝑛𝑖= 1 𝑓(𝑣𝑣𝑖 ) + f(uv)) f(u) + f(u) + 𝑛𝑖= 1 𝑓(𝑢𝑖 ) + n f(v) + f(v) 𝑛 𝑛 𝑖 = 1 𝑓(𝑣𝑖 )) + ( 𝑖 = 1 𝑓(𝑢𝑢𝑖 )
+ ( + (n + n + 1) c(f)
= (n + +
ɛ c(f)
𝑛 𝑖 = 1 𝑓(𝑣𝑣𝑖 )
=
𝑣𝜖𝑉
+ f(uv))
𝑑𝑒𝑔(𝑣) 𝑓(𝑣)
+
Karena ɛ(Bn,n) = 2n + 1 , maka (2n + 1) c(f)
𝑛 𝑖 = 1 𝑓(𝑢𝑖 )
= (1 + n) f(u) +
=
+
𝑛 𝑖 = 1 𝑓(𝑣𝑖 )
+
𝑛 𝑖 = 1 𝑓(𝑣𝑣𝑖 ) 𝑛 𝑖 = 1 𝑓(𝑢𝑖 )
+
+
+ (1 + n) f(v) +
+ (1 + n) f(v)
𝑛 𝑖 = 1 𝑓(𝑢𝑢i )
+ f(uv) 𝑛 𝑖 = 1 𝑓(𝑣𝑖 ) 𝑒𝜖𝐸
𝑓(𝑒)
+ (1 + n) f(u)
𝑒𝜖𝐸
𝑓(𝑒)
19
=
𝑛 𝑖 = 1 𝑓(𝑢𝑖 )
+ n f(v) +
+ n f(v) + 𝑣𝜖𝑉
𝑒𝜖𝐸
𝑛 𝑖 = 1 𝑓(𝑣𝑖 )
𝑒𝜖𝐸
𝑓(𝑣) +
+ f(u) + n f(u) + f(v)
𝑓(𝑒)
𝑛 𝑖 = 1 𝑓(𝑢𝑖 )
= f(u) +
=
+
𝑛 𝑖 = 1 𝑓(𝑣𝑖 )
+ f(v) +
+ n f(u)
𝑓(𝑒) 𝑒𝜖𝐸
𝑓(𝑒) + n f(u) + n f(v)
Karena ɛ + v = 4n + 3 , maka = (1 + 2 + … + 4n + 3) + n f(u) + n f(v) =
(4𝑛 + 3) (4𝑛 + 4) 2
Sehingga, c(f) =
+ n f(u) + n f(v)
(4𝑛 + 3) (4𝑛 + 4)
+
2 (2𝑛 + 1) (4𝑛 + 3) (4𝑛 + 4)
=
+
(4𝑛 + 2)
=
4n + 5 +
=
4n + 5 +
=
4n + 5 +
2 (4𝑛 + 2) 1 (2𝑛 + 1)
(𝑛 𝑓(𝑢 ) + 𝑛 𝑓(𝑣)) (2𝑛 + 1) 𝑛 (𝑓(𝑢 ) + 𝑓(𝑣)) (2𝑛 + 1)
+ +
𝑛 (𝑓(𝑢) + 𝑓(𝑣)) (2𝑛 + 1) 𝑛 (𝑓(𝑢) + 𝑓(𝑣)) (2𝑛 + 1)
1 + 𝑛 (𝑓(𝑢) + 𝑓(𝑣)) (2𝑛 + 1)
Karena c(f) merupakan bilangan bilangan bulat, 1 + 𝑛 (𝑓(𝑢) + 𝑓(𝑣)) maka juga merupakan bilangan (2𝑛 + 1) bulat sehingga 1 + 𝑛 (𝑓(𝑢) + 𝑓(𝑣)) ≡ 0 mod (2n+1) menjadi, 𝑛 (𝑓(𝑢) + 𝑓(𝑣)) 𝑓(𝑢) + 𝑓(𝑣)
≡ 2n mod (2n + 1) ≡ (2n) (n-1) mod (2n + 1)
Karena n x (2n - 1)
≡ 1 mod (2n + 1)
maka n-1
≡ (2n - 1) mod (2n + 1)
sehingga mengakibatkan, 𝑓(𝑢) + 𝑓(𝑣)
≡ (2n) (2n - 1) mod (2n + 1)
𝑓(𝑢) + 𝑓(𝑣)
≡ (4n2 - 2n) mod (2n + 1)
𝑓(𝑢) + 𝑓(𝑣)
≡ 2 mod (2n + 1)
20
maka
𝑓(𝑢) + 𝑓(𝑣) ≥ 2n + 3
Sehingga c(f) ≥ 4n + 5 +
𝑛 (2𝑛 + 3) + 1 (2𝑛 + 1)
= 5n + 6
Karena m(Bn,n) merupakan nilai minimum dari semua kemungkinan nilai c(f) maka m(Bn,n) pasti memenuhi ketaksamaan m(Bn,n) ≥ 5n + 6. (ii)
Akan dibuktikan m(Bn,n) ≤ 5n + 6 dengan menunjukan eksistansi konstanta c(f) pada graf Bn,n. Misalkan u, v, u1, u2, . . . , un, v1, v2, . . . . . . . , vn adalah simpul terurut dari Bn,n dan uv, uu1, uu2, . . . , uun, vv1, vv2, . . . , vvn adalah sisi terurut dari Bn,n. Pilih fungsi label : f (u) = n + 2, f (v) = n + 1, f (uv) = 3n + 3, f (ui) = i untuk 1 ≤ i ≤ n, f (vi) = 2n + 2 + i untuk 1 ≤ i ≤ n, f (uui) = 4n + 4 – i untuk 1 ≤ i ≤ n, f (vvi) = 2n + 3 – i untuk 1 ≤ i ≤ n. Akibatnya diperoleh konstanta c(f) sebagai berikut. untuk u dan ui yang adjacent di K1,n dan uui incident dengan u dan ui , maka c1(f)
= f(x) + = f (u) + = n+2 + = 5n + 6 untuk v dan vi yang adjacent di maka
f(y) f (ui) i
+ + +
f(xy) f (uui) 4n + 4 – i
K1,n dan vvi incident dengan v dan vi ,
c2(f)
= f(x) + f(y) + f(xy) f (vi) + f (vvi) = f (v) + = n+1 + 2n + 2 + i + 2n + 3 – i = 5n + 6 untuk u dan v adjacent di Bn,n dan uv incident dengan u dan v, maka c3(f)
= f(x) + f(y) + f(xy) f (v) + f (uv) = f (u) + = n+2 + n+1 + 3n + 3 = 5n + 6 Karena setiap graf terhubung di Bn,n memiliki nilai c(f) = 5n + 6 yang merupakan salah satu nilai konstanta ajaib yang didapat maka m(Bn,n) ≤ 5n + 6. Dari tahap (i) dan (ii) dapat dibuktikan m(Bn,n) ≤ 5n + 6 dan m(Bn,n) ≥ 5n + 6, maka dapat diperoleh bahwa m(Bn,n) = 5n + 6. Dengan demikian dapat dibuktikan bahwa setiap graf bistar Bn,n memiliki nilai magic strength yaitu 5n + 6. ■ Terbukti
21
Graf Cycle Derajat 2n + 1 Misalkan G graf dengan himpunan vertex V dan himpunan edge E. Graf G disebut graf cycle, dinotasikan Cm, jika graf G ber-order m dengan m ≥ 3 dan membentuk sebuah cycle. Berikut akan diperlihatkan contoh magic labeling untuk memperoleh magic strength pada graf cycle C2n+1 sebelum membuktikan teorema 4. Misalkan diberikan graf cycle C3 dengan bentuk seperti pada Gambar 15. C3 :
u1
u3
u2
Gambar 15 Graf cycle C3. Pada graf cycle C3 diatas terdapat 3 simpul dan 3 sisi sehingga kisaran nilai untuk membantu memperoleh magic strength adalah 3 + 3 + 3 ≤ m(G) ≤ (2)(3) + (2)(3) 9 ≤ m(G) ≤ 12 Misalkan simpul-simpul dan sisi-sisi pada graf cycle C3 diberi 4 pelabelan yang berbeda, yaitu untuk pelabelan pertama, misalnya f(u1) = 6 f(u1u2) = 1 f(u2) = 5 f(u2u3) = 3 f(u3) = 4 f(u3u1) = 2 maka akan diperoleh penjumlahan label dari tiap sisi yang incident terhadap 2 simpul ujungnya : f(u1) + f(u2) + f(u1u2) = 6 + 5 + 1 = 12 f(u2) + f(u3) + f(u2u3) = 5 + 4 + 3 = 12 f(u3) + f(u1) + f(u3u1) = 4 + 6 + 2 = 12 sehingga didapat nilai c(f) = 12 dan dapat digambarkan seperti Gambar 16 (a). Pelabelan kedua, misalnya f(u1) = 5 f(u1u2) = 2 f(u2) = 3 f(u2u3) = 6 f(u3) = 1 f(u3u1) = 4 maka akan diperoleh penjumlahan label dari tiap sisi yang incident terhadap 2 simpul ujungnya : f(u1) + f(u2) + f(u1u2) = 5 + 3 + 2 = 10 f(u2) + f(u3) + f(u2u3) = 3 + 1 + 6 = 10 f(u3) + f(u1) + f(u3u1) = 1 + 5 + 4 = 10 sehingga didapat nilai c(f) = 10 dan dapat digambarkan seperti Gambar 16 (b). Pelabelan ketiga, misalnya f(u1) = 3 f(u1u2) = 4 f(u2) = 2 f(u2u3) = 6 f(u3) = 1 f(u3u1) = 5
22
maka akan diperoleh penjumlahan label dari tiap sisi yang incident terhadap 2 simpul ujungnya : f(u1) + f(u2) + f(u1u2) = 3 + 2 + 4 = 9 f(u2) + f(u3) + f(u2u3) = 2 + 1 + 6 = 9 f(u3) + f(u1) + f(u3u1) = 1 + 3 + 5 = 9 sehingga didapat nilai c(f) = 9 dan dapat digambarkan seperti Gambar 16 (c). Pelabelan keempat, misalnya f(u1) = 4 f(u1u2) = 5 f(u2) = 2 f(u2u3) = 3 f(u3) = 6 f(u3u1) = 1 maka akan diperoleh penjumlahan label dari tiap sisi yang incident terhadap 2 simpul ujungnya : f(u1) + f(u2) + f(u1u2) = 4 + 2 + 5 = 11 f(u2) + f(u3) + f(u2u3) = 2 + 6 + 3 = 11 f(u3) + f(u1) + f(u3u1) = 6 + 4 + 1 = 11 sehingga didapat nilai c(f) = 11 dan dapat digambarkan seperti Gambar 16 (d). (a)
6 2 4
1 5
3
(b)
5 4 1
2 3
6
(c)
3 4
5 1
2
6
(d)
4 1
5
6
2 3 Gambar 16 Magic labeling pada graf cycle C3. Dari 4 pelabelan graf di atas, didapat nilai c(f) secara berturut-turut adalah 12, 10, 9, 11. Jadi, untuk magic strength dari graf cycle C3, m(C3) = min{12, 10, 9, 11} = 9.
23
Cara pelabelan tersebut merupakan salah satu contoh magic labeling pada graf cycle C2n+1. Berikut akan dibuktikan teorema 4 yang akan digunakan untuk menentukan magic strength pada graf cycle C2n+1. Teorema 4 Misalkan C2n + 1 adalah suatu graf cycle dengan n ϵ N. Nilai magic strength dari C2n + 1 adalah m(C2n + 1) = 5n + 4 Bukti : Misalkan C2n + 1 adalah graf cycle dengan banyaknya simpul 2n+1 maka C2n+1 memiliki |E(C2n+1)| = |V(C2n+1)| dengan |V(C2n+1)| = 2n+1. Akan dibuktikan m(C2n+1) = 5n + 4. Pembuktian m(C2n+1) = 5n + 4 dilakukan dengan 2 tahap. (i)
Akan dibuktikan m(C2n + 1) ≥ 5n + 4. Misalkan C2n+1 memiliki pelabelan magic g dengan konstanta c(g) dan memiliki sisi sebanyak 2n + 1 dengan setiap sisi yang incident terhadap 2 simpul ujungnya. Sehingga jumlah konstanta yang diperoleh dari semua sisinya dapat dirumuskan sebagai berikut. g(v1) + g(v2) + g(v1v2) c(g) = c(g) = g(v2) + g(v3) + g(v2v3) c(g) = g(v3) + g(v4) + g(v3v4) ⁞ ⁞ ⁞ ⁞ g(vɛ - 1) + g(vɛ) + g(vɛ - 1vɛ) c(g) = c(g) = g(vɛ) + g(v1) + g(vɛv1) + ɛc(g)
=
𝑣𝜖𝑉
𝑔(𝑣)
+
𝑒𝜖𝐸
𝑔(𝑒)
+
𝑣𝜖𝑉
Karena ɛ(C2n + 1) = 2n + 1 , maka (2n + 1) c(g)
𝑔(𝑣) +
=
𝑣𝜖𝑉
=
2𝑛 + 1 𝑖 = 1 𝑔(𝑣𝑖 )
𝑒𝜖𝐸
+
𝑔(𝑒) 2𝑛 + 1 𝑖 = 1 𝑔(𝑒𝑖 )
𝑔(𝑣)
Karena ɛ + v = 4n + 2 , maka = (1 + 2 + … + 4n + 2) + ≥
(4𝑛 + 2)(4𝑛 + 3) 2
𝑣𝜖𝑉
𝑔(𝑣)
+ (1 + 2 + … + 2n + 1)
= (2n + 1) (4n + 3) + (2n + 1) (n + 1) = ((4n + 3) + (n + 1)) (2n + 1) = (2n + 1) (5n + 4) Akibatnya (2n + 1) c(g) ≥ (2n + 1) (5n + 4) Sehingga c(g) ≥ 5n + 4 Karena m(C2n+1) merupakan nilai minimum dari semua kemungkinan nilai c(g) maka m(C2n+1) pasti memenuhi ketaksamaan m(C2n+1) ≥ 5n + 4.
24
(ii)
Akan dibuktikan m(C2n + 1) ≤ 5n + 4 dengan menunjukan eksistansi konstanta c(g) pada graf C2n + 1. Misalkan v1, v2, v3, …, v2n+1 adalah simpul terurut dari C2n+1 dan e1, e2, e3, …, e2n+1 adalah sisi terurut dari C2n+1. Artinya, ei = vivi+1 untuk 1 ≤ i ≤ 2n - 1. Kemudian pilih fungsi label dimana fungsi label berikut adalah magic labeling dari C2n+1 : g (v2i+1) = 1 + i untuk 0 ≤ i ≤ n, g (v2i+2) = n + i + 2 untuk 0 ≤ i ≤ n - 1, g (vi+1vi+2) = 4n + 2 – (i + 1) untuk 0 ≤ i ≤ 2n – 1, g (v2n+1v1) = 4n + 2. Akibatnya diperoleh konstanta c(g) sebagai berikut. c(g) = g(x) + g(y) + g(xy) = g (v2i + 1) + g (v2i + 2) + g (v2i + 1v2i + 2) = 1+i + n + i + 2 + 4n + 2 – (2i + 1) = 5n + 4 Untuk v2n + 1v1 c(g)
= g(x) + g(y) + g(xy) = g (v2n + 1) + g (v1) + g (v2n + 1v1) + 1 + 4n + 2 = 1+n = 5n + 4 Karena c(g) = 5n + 4 maka nilai minimum dari semua kemungkinan nilai c(g) akan kurang atau sama dengan 5n + 4. Dari tahap (i) dan (ii) dapat dibuktikan m(C2n+1) ≤ 5n + 4 dan m(C2n+1) ≥ 5n + 4, maka dapat diperoleh bahwa m(C2n+1) = 5n + 4. Dengan demikian dapat dibuktikan bahwa setiap graf cycle C2n+1 memiliki nilai magic strength yaitu 5n + 4. ■ Terbukti
SIMPULAN DAN SARAN Simpulan Dalam karya ilmiah ini telah dibuktikan bahwa graf path Pn, graf bistar Bn,n, dan graf cycle C2n+1 memiliki nilai konstanta ajaib terkecil (magic strength). Adapun nilai konstanta dari graf path Pn, graf bistar Bn,n, dan graf cycle C2n+1 bergantung pada degree dari suatu simpul v pada graf-graf tersebut. Saran Dalam karya ilmiah ini telah dibahas magic strength pada suatu graf yang difokuskan pada graf path Pn, graf n-bistar Bn,n, dan graf cycle C2n+1. Bagi yang berminat membuat karya ilmiah yang berhubungan dengan magic strength dapat mencari super magic strength pada graf path, graf star, graf cycle atau pada graf lainnya.
25
DAFTAR PUSTAKA Avadayappan S, Vasuki R, Jeyanthi P. 2000. Magic Strength of A Graph. Indian J. Pure Appl. Math. 31(7):873-883. Chartrand G, Oellermann OR. 1993. Applied and Algorithmic Graph Theory. New York: McGraw-Hill. Foulds LR. 1992. Graph Theory Applications. New York: Spinger-Verlag. Gallian JA. 2009. A dynamic survey of graph labeling. The Electronic Journal Combinatorics 16:7-65.
RIWAYAT HIDUP Penulis dilahirkan di Bekasi pada tanggal 24 Agustus 1990 dari pasangan Bapak Sukino Riyanto dan Ibu Isnaningsih. Penulis merupakan putra ketiga dari tiga bersaudara. Tahun 2008 penulis lulus dari SMA Negeri 44 Jakarta dan pada tahun yang sama penulis lulus seleksi masuk Institut Pertanian Bogor (IPB) melalui jalur Penelusuran Minat dan Kemampuan (PMDK) dan diterima di Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama mengikuti perkuliahan, penulis pernah aktif sebagai Ketua Biro Found Rising Departemen Keuangan LDK Al-Hurriyah, Ketua Divisi Sosial dan Politik Dewan Perwakilan Mahasiswa (DPM) FMIPA IPB dan Ketua Umum Dewan Perwakilan Mahasiswa (DPM) FMIPA IPB. Selain itu, penulis aktif dalam berbagai kepanitiaan, diantaranya panitia Open House IPB, Masa Perkenalan Kampus Mahasiswa Baru (MPKMB), Masa Perkenalan Fakultas (MPF), dan Masa Perkenalan Departemen (MPD). Penulis juga aktif sebagai staf pengajar matematika di beberapa bimbingan belajar wilayah Bogor dan Bekasi pada tahun 2012-2013.
