PELABELAN SUPER EDGE MAGIC PADA GRAF CYCLE DAN GRAF WHEEL
NURUL NUR INDAH SARI
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012 1
ABSTRAK NURUL NUR INDAH SARI. Pelabelan Super Edge Magic pada Graf Cycle dan Graf Wheel. Dibimbing oleh TEDUH WULANDARI MASโOED dan FARIDA HANUM. Karya ilmiah ini membuktikan bahwa graf cycle dan graf wheel memiliki pelabelan super edge magic. Pelabelan super edge magic pada suatu graf adalah pelabelan yang memiliki pelabelan edge magic dan himpunan simpulnya dipetakan ke {1, 2, โฆ , ๐} serta himpunan sisinya dipetakan ke {๐ + 1, ๐ + 2, โฆ , ๐ + ๐}, dengan ๐ adalah banyaknya simpul dan ๐ adalah banyaknya sisi pada suatu graf. Terdapat satu lema dan dua teorema yang dibahas dalam karya ilmiah ini. Lema ini digunakan untuk membuktikan kedua teorema. Teorema pertama membuktikan bahwa graf cycle ๐ถ๐ adalah super edge magic jika dan hanya jika ๐ ganjil. Teorema kedua membuktikan bahwa graf wheel ๐๐ dengan order ๐ bukan graf super edge magic, bahkan ๐๐ dengan ๐ โก 0 mod 4 bukan graf edge magic. Kata kunci: pelabelan edge magic, pelabelan super edge magic, graf cycle, graf wheel.
2
ABSTRACT NURUL NUR INDAH SARI. Super Edge Magic Labeling on Cycle Graph and Wheel Graph. Supervised by TEDUH WULANDARI MASโOED and FARIDA HANUM. This manuscript proves that cycle graph and wheel graph have a super edge magic labeling. Super edge magic labeling on a graph is labeling that has an edge magic labeling with a set of vertices were mapped in to {1, 2, โฆ , ๐} and a set of edges were mapped in to {๐ + 1, ๐ + 2, โฆ , ๐ + ๐}, in which ๐ is order and ๐ is size on the graph. There are one lemma and two theorems to be discussed. The lemma is used to prove the two theorems. The first theorem proves that cycle graph ๐ถ๐ is super edge magic if and only if ๐ is odd. The second theorem proves that wheel graph ๐๐ of order ๐ is not super edge magic. Moreover ๐๐ is not edge magic if ๐ โก 0 mod 4. Keywords: edge magic labeling, super edge magic labeling, cycle graph, wheel graph.
3
PELABELAN SUPER EDGE MAGIC PADA GRAF CYCLE DAN GRAF WHEEL
NURUL NUR INDAH SARI
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 2012
4
Judul Skripsi : Pelabelan Super Edge Magic pada Graf Cycle dan Graf Wheel Nama : Nurul Nur Indah Sari NIM : G54070039
Menyetujui, Pembimbing I,
Pembimbing II,
Teduh Wulandari Masโoed, M.Si. NIP. 19740915 199903 2 001
Dra. Farida Hanum, M.Si. NIP. 19651019 199103 2 002
Mengetahui: Ketua Departemen Matematika,
Dr. Berlian Setiawaty, M.S. NIP. 19650505 198903 2 004
Tanggal Lulus :
5
PRAKATA Puji dan syukur penulis panjatkan kepada Allah SWT atas segala rahmat dan karunia-Nya serta shalawat dan salam kepada Nabi Muhammad SAW sehingga karya ilmiah ini berhasil diselesaikan. Penyusunan karya ilmiah ini juga tidak lepas dari peranan berbagai pihak. Untuk itu penulis mengucapkan terima kasih yang sebesar-besarnya kepada: 1. keluarga tercinta: Ibu dan Bapak (terima kasih atas doa, dukungan secara moril maupun materiil, motivasi, dan kasih sayangnya), adik-adikku (terima kasih atas doa dan dukungannya), serta keluarga besar dari Ibu dan Bapak (terima kasih atas doanya), 2. Teduh Wulandari Masโoed, M.Si. selaku dosen pembimbing I (terima kasih atas semua ilmu, motivasi, kesabaran, dukungan, dan bantuannya selama penulisan karya ilmiah ini), 3. Dra. Farida Hanum, M.Si. selaku dosen pembimbing II (terima kasih atas semua ilmu dan sarannya), 4. Drs. Siswandi, M.Si. selaku dosen penguji (terima kasih atas semua ilmu dan sarannya), 5. segenap dosen Departemen Matematika terima kasih atas semua ilmu yang telah diberikan, 6. staf Departemen Matematika terima kasih atas bantuannya, 7. teman-teman Matematika angkatan 44: Selvie, Resha, Fany, Anis, Sari, Ipul, Dora, Tanty, Yuyun, Titi, Wewe, Deva, Ndep, Ima, Lingga, Ruhyat, Ayung, Melon, Rachma, Sri, Denda, Fajar, Rofi, Dian, Tyas, Della, Pandi, Lili, Ririh, Yuli, Nunuy, Iam, Lilis, Ayum, Wahyu, Fikri, Atik, Cita, Arina, Masay, Diana, Yogie, Aswin, Imam, Lugina, Yanti, Pepi, Aqil, Eka, Aze, Ali, Vianey, Nadiroh, Naโim, Dhika, Nurus, Phunny, Ab, Siska, Indin, Olih, Tita, Lina, Lukman, Endro, Tendy, Ikhsan, Puying, Zae, dan Copa (terima kasih atas doa, dukungan, bantuan, dan kebersamaannya), 8. kakak-kakak Matematika angkatan 42 dan 43 (terima kasih atas semua ilmu dan bantuannya), 9. adik-adik Matematika angkatan 45 ( terima kasih atas bantuan dan dukungannya), 10. teman-teman B26 ( terima kasih atas dukungan dan kebersamaannya), 11. sahabat-sahabat terdekat: Fina, Nia, Echa, Tika, Lujeng, Rinal, Ayu, Lely, Anis, Agus, dan lainnya ( terima kasih atas doa, dukungan, dan kebersamaannya), 12. teman- teman FOSMA IPB, FOSMA Bogor, SHOT Bogor, GEMA Bogor, dan FKA Bogor (terima kasih atas doa, dukungan, dan kebersamaannya), 13. teman-teman Pondok Malea Atas (terima kasih atas dukungan dan kebersamaannya), 14. semua pihak yang telah membantu dalam penyusunan karya ilmiah ini. Semoga karya ilmiah ini bermanfaat bagi dunia ilmu pengetahuan khususnya dalam bidang matematika dan menjadi inspirasi bagi penelitian-penelitian selanjutnya.
Bogor, Februari 2012
Nurul Nur Indah Sari
6
RIWAYAT HIDUP Penulis dilahirkan di Minahasa pada tanggal 8 Juli 1989 dari pasangan bapak Oyo Suhyono dan ibu Teti Rosmiati. Penulis merupakan putri pertama dari tiga bersaudara. Tahun 2007 penulis lulus dari SMA Negeri 1 Pangandaran dan pada tahun yang sama diterima sebagai mahasiswi IPB melalui jalur Undangan Seleksi Masuk IPB (USMI). Penulis memilih Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama mengikuti perkuliahan, penulis aktif di berbagai kegiatan kemahasiswaan, yaitu sebagai pengurus Gugus Mahasiswa Matematika (GUMATIKA) periode 2009, Organisasi Mahasiswa Daerah Ciamis (OMDA PMGC) dan FOSMA IPB. Selain itu, penulis juga aktif dalam berbagai kepanitiaan, di antaranya panitia Masa Perkenalan Departemen, try out Pengantar Matematika, dan training ESQ mahasiswa baru.
DAFTAR ISI Halaman DAFTAR GAMBAR ................................................................................................................. viii I
PENDAHULUAN ............................................................................................................. 1.1 Latar Belakang .......................................................................................................... 1.2 Tujuan .......................................................................................................................
1 1 1
II
LANDASAN TEORI ......................................................................................................... 2.1 Teori Graf .................................................................................................................. 2.2 Pelabelan Graf ...........................................................................................................
1 1 3
III
PEMBAHASAN ................................................................................................................
5
IV
SIMPULAN DAN SARAN ............................................................................................... 4.1 Simpulan ................................................................................................................... 4.2 Saran ..........................................................................................................................
14 14 15
DAFTAR PUSTAKA ................................................................................................................
15
LAMPIRAN ...............................................................................................................................
16
vii
DAFTAR GAMBAR Halaman 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
Graf ๐บ = (๐, ๐ธ) .................................................................................................................. Cycle .................................................................................................................................... Graf ๐บ nontrivial ................................................................................................................. Graf cycle ber-order 5 ......................................................................................................... Graf lengkap ber-order 5 .................................................................................................... Union dari 2 graf ................................................................................................................. Join dari 2 graf .................................................................................................................... Graf wheel ber-order 7 ........................................................................................................ Graf cycle ber-order 3 ......................................................................................................... Pelabelan edge magic pada graf ๐ถ3 ..................................................................................... Pelabelan super edge magic pada graf ๐ถ3 ........................................................................... Graf cycle ber-order 9 ........................................................................................................ Pelabelan super edge magic pada graf ๐ถ9 ........................................................................... Graf cycle ber-order 4 ......................................................................................................... Pelabelan edge magic pada graf ๐ถ4 ..................................................................................... Pelabelan edge magic pada graf ๐ถ5 ..................................................................................... Pelabelan super edge magic pada graf ๐ถ5 ........................................................................... Graf cycle ber-order 6 ......................................................................................................... Pelabelan edge magic pada graf ๐ถ6 ..................................................................................... Graf cycle ber-order 7 ......................................................................................................... Pelabelan edge magic pada graf ๐ถ7 ..................................................................................... Pelabelan super edge magic pada graf ๐ถ7 ........................................................................... Graf wheel ber-order 5 ........................................................................................................ Pelabelan edge magic pada graf ๐5 .................................................................................... Graf wheel ber-order 4 ........................................................................................................ Graf wheel ber-order 6 ........................................................................................................ Pelabelan edge magic pada graf ๐6 .................................................................................... Graf wheel ber-order 8 ........................................................................................................ Graf wheel ber-order 9 ........................................................................................................ Pelabelan edge magic pada graf ๐9 .................................................................................... Graf wheel ber-order 11 ..................................................................................................... Pelabelan edge magic pada graf ๐11 ................................................................................... Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 4, ๐ ๐ = 3, ๐(๐) = 2, ๐ ๐ = 1, dan ๐ ๐๐ = 8 . Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 4, ๐ ๐ = 3, ๐(๐) = 1, ๐ ๐ = 2, dan ๐ ๐๐ = 8 . Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 4, ๐ ๐ = 3, ๐(๐) = 2, ๐ ๐ = 1, dan ๐ ๐๐ = 7 . Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 4, ๐ ๐ = 3, ๐(๐) = 1, ๐ ๐ = 2, ๐ ๐๐ = 7, dan ๐ ๐๐ = 8 ................................................................................................................... Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 4, ๐ ๐ = 3, ๐(๐) = 2, ๐ ๐ = 1, dan ๐ ๐๐ = 6 . Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 4, ๐ ๐ = 3, ๐(๐) = 1, ๐ ๐ = 2, ๐ ๐๐ = 6, dan ๐ ๐๐ = 7 ................................................................................................................... Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 4, ๐ ๐ = 3, ๐(๐) = 2, ๐ ๐ = 1, dan ๐ ๐๐ = 5 . Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 4, ๐ ๐ = 3, ๐(๐) = 1, ๐ ๐ = 2, ๐ ๐๐ = 5, ๐ ๐๐ = 8, dan ๐ ๐๐ = 6 ................................................................................................ Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 1, ๐ ๐ = 2, ๐(๐) = 3, ๐ ๐ = 4, ๐ ๐๐ = 8, dan ๐ ๐๐ = 6 .................................................................................................................... Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 1, ๐ ๐ = 2, ๐(๐) = 4, ๐ ๐ = 3, ๐ ๐๐ = 8, ๐ ๐๐ = 5, dan ๐ ๐๐ = 7 ................................................................................................. Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 2, ๐ ๐ = 3, ๐(๐) = 4, ๐ ๐ = 1, ๐ ๐๐ = 6, dan ๐ ๐๐ = 8 ................................................................................................................... Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 2, ๐ ๐ = 3, ๐(๐) = 1, ๐ ๐ = 4, ๐ ๐๐ = 8, ๐ ๐๐ = 7, dan ๐ ๐๐ = 5 .................................................................................................
1 2 2 2 3 3 3 3 4 4 4 6 6 7 7 8 8 8 8 8 9 9 9 10 11 12 12 12 13 13 13 14 17 17 17 18 18 18 19 19 19 20 20 20
viii
I PENDAHULUAN 1.1 Latar Belakang Masalah jembatan Konigsberg adalah masalah yang pertama kali diselesaikan menggunakan graf. Masalah ini pertama kali dipecahkan pada tahun 1736 oleh Leonhard Euler seorang ahli matematika asal Swiss yang menemukan salah satu cabang dari matematika yang saat ini dikenal sebagai โTeori Grafโ. Teori graf merupakan pokok bahasan yang memiliki banyak terapan sampai saat ini, di antaranya dalam model jaringan transportasi, teknik elektro, kimia, sistem komunikasi, administrasi bisnis, sosiologi, marketing, desain arsitektur, dan masih banyak lagi terapan yang lainnya. Banyak permasalahan yang dapat diselesaikan dengan menggunakan graf. Sebagai contoh, permasalahan untuk merencanakan tempat pembuangan sampah pada suatu perumahan penduduk, diagnosa dalam jaringan komputer, dan masih banyak lagi permasalahan yang dapat diselesaikan dengan menggunakan graf. Pelabelan graf merupakan salah satu topik dalam graf. Pelabelan pada suatu graf adalah suatu pemetaan bijektif dari himpunan simpul dan himpunan sisi ke himpunan bilangan asli. Terdapat beberapa jenis pelabelan pada graf,
antara lain pelabelan graceful, pelabelan ajaib (magic), pelabelan anti ajaib, dan pelabelan yang lainnya. Dalam pengembangan pelabelan ajaib (magic), dikenal pula pelabelan vertex magic, pelabelan super vertex magic, pelabelan edge magic, dan pelabelan super edge magic. Pelabelan super edge magic pada suatu graf ๐บ yang memiliki ๐ simpul dan ๐ sisi adalah jika ๐บ memiliki pelabelan edge magic dan memenuhi syarat-syarat lain. Karya ilmiah ini akan membuktikan bahwa graf cycle dan graf wheel merupakan graf yang memiliki pelabelan graf yang super edge magic. Ada satu lema dan dua teorema yang digunakan untuk membuktikan bahwa graf cycle dan graf wheel merupakan pelabelan graf yang super edge magic. Sumber utama karya ilmiah ini adalah artikel yang ditulis Enomoto et al. pada tahun 1998. 1.2 Tujuan Tujuan dari penulisan karya ilmiah ini adalah untuk membuktikan bahwa graf cycle dan graf wheel memiliki pelabelan graf yang super edge magic.
II LANDASAN TEORI Pada bab ini akan dijelaskan beberapa definisi dalam teori graf dan pelabelan graf yang akan digunakan dalam penyusunan karya ilmiah ini.
sisinya tidak mempunyai arah. Contoh graf tak berarah dapat dilihat pada Gambar 1. ๐บ: a
2.1 Teori Graf Definisi 1 (Graf) Suatu graf ๐บ adalah pasangan terurut (๐, ๐ธ) dengan ๐ adalah himpunan takkosong dan berhingga dan ๐ธ adalah himpunan pasangan tak terurut yang menghubungkan elemen-elemen ๐. Graf ๐บ dinotasikan ๐บ = (๐, ๐ธ). Elemen ๐ disebut simpul (vertex) sedangkan elemen ๐ธ disebut sisi (edge). Himpunan dari simpul-simpul pada graf ๐บ dinotasikan dengan ๐(๐บ), sedangkan himpunan dari sisi-sisi pada graf ๐บ dinotasikan dengan ๐ธ(๐บ). (Foulds 1992) Graf yang dimaksud pada definisi tersebut adalah graf tak berarah artinya graf yang
c
b
d
e
Gambar 1 Graf ๐บ = (๐, ๐ธ). Himpunan simpul dan himpunan sisi graf pada Gambar 1 adalah ๐(๐บ) = {๐, ๐, ๐, ๐, ๐} ๐ธ ๐บ = { ๐, ๐ , ๐, ๐ , ๐, ๐ , ๐, ๐ , ๐, ๐ }.
ix
2
Definisi 2 (Order dan Size) Misalkan diberikan graf ๐บ. Banyaknya simpul pada graf ๐บ disebut order dan banyaknya sisi pada graf ๐บ disebut size. Order dari graf ๐บ dinotasikan dengan |๐ ๐บ | dan size dari graf ๐บ dinotasikan dengan |๐ธ ๐บ |. (Chartrand & Oellermann 1993) Pada Gambar 1, nilai dari ๐ ๐บ ๐ธ ๐บ = 5.
= 5 dan
Definisi 3 (Incident dan Adjacent) Misalkan diberikan graf ๐บ. 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 ๐. Definisi 4 (Degree) Derajat (degree) dari suatu simpul ๐ฃ pada graf ๐บ adalah banyaknya sisi yang incident dengan ๐ฃ dan dinotasikan dengan deg ๐ฃ. (Chartrand & Oellermann 1993) Pada Gambar 1, derajat setiap simpulnya ialah deg ๐ = 2, deg ๐ = 3, deg ๐ = 3, deg ๐ = 1, dan deg ๐ = 1. Definisi 5 (Walk) Suatu walk pada graf ๐บ adalah suatu barisan simpul dan sisi dari graf ๐บ dengan bentuk {๐ฃ1 , ๐ฃ1 , ๐ฃ2 , ๐ฃ2 , ๐ฃ2 , ๐ฃ3 , ๐ฃ3 , โฆ , ๐ฃ๐ โ1 , ๐ฃ๐ , ๐ฃ๐ } dan dapat dituliskan sebagai {๐ฃ1 , ๐ฃ2 , โฆ , ๐ฃ๐ } atau ๐ฃ1 , ๐ฃ2 , โฆ , ๐ฃ๐ . Suatu walk yang menghubungkan ๐ฃ1 dengan ๐ฃ๐ dikatakan tertutup jika ๐ฃ1 = ๐ฃ๐ . Jika ๐ฃ1 โ ๐ฃ๐ maka walk tersebut dikatakan terbuka. (Foulds 1992)
a
c
b
Gambar 2 Cycle. Definisi 7 (Graf Nontrivial) Suatu graf ๐บ disebut graf nontrivial jika suatu graf ๐บ memiliki order paling sedikit dua. (Chartrand & Oellermann 1993) Berikut ini diberikan contoh graf nontrivial ber-order 3. ๐บ:
Gambar 3 Graf ๐บ nontrivial. Definisi 8 (Graf Cycle) Suatu graf ber-order ๐ dengan ๐ โฅ 3 yang membentuk sebuah cycle disebut graf cycle dan dinotasikan dengan ๐ถ๐ . (Chartrand & Oellermann 1993) Berikut ini diberikan contoh graf cycle berorder 5. ๐ถ5 :
a
b
e
c
d
Pada Gambar 1, terdapat walk terbuka yaitu walk {๐, ๐, ๐ , ๐, {๐, ๐}, ๐, {๐, ๐}, ๐}.
Gambar 4 Graf cycle ber-order 5.
Definisi 6 (Cycle) Cycle pada suatu graf ๐บ adalah walk tertutup yang mengandung setidaknya tiga simpul dan semua simpulnya berbeda. (Foulds 1992)
Definisi 9 (Graf Lengkap) Graf ber-order ๐ yang setiap dua simpulnya adjacent disebut graf lengkap (complete graph) dan dinotasikan dengan ๐พ๐ . (Chartrand & Oellermann 1993)
Pada Gambar 1 terdapat cycle pada graf ๐บ yang terdiri atas tiga simpul, yaitu
Berikut diberikan contoh graf lengkap berorder 5 seperti pada Gambar 5.
3
๐พ5 :
๐ถ4 + ๐พ1 :
Gambar 5 Graf lengkap ber-order 5. Gambar 7 Join dari 2 graf. Definisi 10 (Union dari 2 Graf) Misalkan ๐บ1 dan ๐บ2 adalah graf dengan himpunan simpul yang disjoint, maka union dari ๐บ1 dan ๐บ2 , dituliskan ๐บ1 โช ๐บ2 , adalah graf yang memiliki ๐ ๐บ1 โช ๐บ2 = ๐(๐บ1 ) โช ๐(๐บ2 ) dan ๐ธ ๐บ1 โช ๐บ2 = ๐ธ(๐บ1 ) โช ๐ธ(๐บ2 ). (Chartrand & Oellermann 1993) Berikut diberikan contoh union dari 2 graf. ๐พ3 โช 3๐พ1 :
Definisi 12 (Graf Wheel) Untuk ๐ โฅ 4, graf wheel ๐๐ dengan order ๐ adalah join dari graf cycle ๐ถ๐โ1 ber-order ๐ โ 1 dan graf lengkap (complete graph) ๐พ1 ber-order 1. (Fukuchi 2001) Berikut diberikan contoh graf wheel ber-order 7. ๐7 :
v1
v2
v0
v6
v3
Gambar 6 Union dari 2 graf. Definisi 11 (Join dari 2 Graf) Misalkan ๐บ1 dan ๐บ2 adalah graf dengan himpunan simpul yang disjoint, maka join dari ๐บ1 dan ๐บ2 , dituliskan ๐บ1 +๐บ2 , adalah graf ๐บ1 โช ๐บ2 dimana setiap simpul di ๐บ1 adjacent dengan setiap simpul di ๐บ2 ditambah semua sisi bertipe ๐ฃ1 ๐ฃ2 dengan ๐ฃ1 โ ๐(๐บ1 ) dan ๐ฃ2 โ ๐(๐บ2 ). (Chartrand & Oellermann 1993)
v5
v4
Gambar 8 Graf wheel ber-order 7. 2.2 Pelabelan Graf Karya ilmiah ini membahas pelabelan super edge magic pada graf cycle dan graf wheel. Berikut dijelaskan beberapa definisi tentang pelabelan graf.
Berikut diberikan contoh join dari 2 graf. ๐ถ4 :
๐พ1 :
Definisi 13 (Pelabelan Edge Magic) Misalkan ๐บ graf dengan ๐ simpul dan ๐ sisi. Suatu pemetaan bijektif ๐ dari himpunan simpul gabung himpunan sisi ke himpunan {1, 2, โฆ , ๐ + ๐) disebut sebagai pelabelan edge magic pada ๐บ jika ada konstanta ๐ โ โ (disebut magic number ๐) sehingga ๐(๐ข) + ๐(๐ฃ) + ๐(๐ข๐ฃ) = ๐ untuk setiap ๐ข๐ฃ โ ๐ธ(๐บ). (Enomoto et al. 1998) Berikut ini diberikan contoh pelabelan edge magic. Misalkan diberikan graf seperti pada Gambar 9. Banyaknya simpul ialah 3 dan banyaknya sisi juga 3, maka masing-masing berlabel 1, 2, 3, 4, 5, dan 6.
4
๐ถ3 : a
b
c
Gambar 9 Graf cycle ber-order 3. Misalkan simpul-simpul pada graf ๐ถ3 dipadankan dengan suatu nilai, yaitu ๐ ๐ =4 ๐ ๐ =6 ๐ ๐ =2 Dipilih ๐ = 11, maka diperoleh label sisi, sehingga ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 4 + 6 + 1 = 11 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 4 + 2 + 5 = 11 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 6 + 2 + 3 = 11 dan dapat digambarkan seperti Gambar 10 (a). Sedangkan untuk ๐ = 12 dan misalkan simpul-simpulnya dipadankan dengan suatu nilai ๐ ๐ =6 ๐ ๐ =5 ๐ ๐ =4 sehingga diperoleh ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 6 + 5 + 1 = 12 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 6 + 4 + 2 = 12 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 5 + 4 + 3 = 12 dan dapat digambarkan seperti Gambar 10 (b). (a)
Dari dua pelabelan tersebut, dapat dilihat bahwa pelabelan edge magic tidak tunggal. Nilai ๐ dapat berubah-ubah dengan memperhatikan label simpulnya. Pada dasarnya proses pelabelan edge magic pada graf cycle diperoleh dengan mencoba-coba semua kemungkinan label yang ada. Definisi 14 (Pelabelan Super Edge Magic) Misalkan ๐บ graf dengan ๐ simpul dan ๐ sisi, dan ๐บ memiliki pelabelan edge magic ๐. Jika ๐: ๐ ๐บ โ {1, 2, โฆ , ๐} dan ๐: ๐ธ ๐บ โ {๐ + 1, ๐ + 2, โฆ , ๐ + ๐} maka ๐ disebut pelabelan super edge magic. (Enomoto et al. 1998) Berikut ini diberikan contoh pelabelan super edge magic. Diberikan graf seperti pada Gambar 9. Berdasarkan definisi pelabelan super edge magic, maka ๐: ๐ ๐ถ3 โ {1, 2, 3} dan ๐: ๐ธ ๐ถ3 โ {4, 5, 6}. Misalkan simpulsimpul pada graf ๐ถ3 dipadankan dengan suatu nilai, yaitu ๐ ๐ =1 ๐ ๐ =3 ๐ ๐ =2 Dipilih ๐ = 9, maka diperoleh label sisi, sehingga ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 1 + 3 + 5 = 9 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 1 + 2 + 6 = 9 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 3 + 2 + 4 = 9 dan dapat digambarkan sebagai berikut 1
4 5
1
5 3
6
3
2
(b)
1
2 3
4
2
Gambar 11 Pelabelan super edge magic pada graf ๐ถ3 . Definisi 15 (Graf Super Edge Magic) Suatu graf ๐บ disebut super edge magic jika terdapat sebuah pelabelan super edge magic dari ๐บ. (Enomoto et al. 1998)
6
5
6
4
Gambar 10 Pelabelan edge magic pada graf ๐ถ3 .
Gambar 11 merupakan contoh graf super edge magic karena memiliki pelabelan super edge magic.
5
III PEMBAHASAN Karya ilmiah ini membahas lema dan teorema-teorema yang membuktikan bahwa graf cycle dan graf wheel memiliki pelabelan super edge magic. Misalkan diberikan graf seperti pada Gambar 9. Banyaknya simpul dan sisi ialah 3. Graf tersebut dilabeli dengan ๐: ๐ ๐ถ3 โ {1, 2, 3} dan ๐: ๐ธ ๐ถ3 โ {4, 5, 6}, sehingga diperoleh graf seperti pada Gambar 11. Berikut ini diberikan lema yang akan digunakan untuk membuktikan teorema selanjutnya. Lema 3.1 Jika ๐บ graf nontrivial yang super edge magic, maka |๐ธ ๐บ | โค 2|๐ ๐บ | โ 3. (Enomoto et al. 1998) Bukti : Misalkan ๐บ graf nontrivial yang super edge magic. Akan dibuktikan bahwa |๐ธ ๐บ | โค 2|๐ ๐บ | โ 3. Misalkan ๐บ memiliki ๐ simpul dan ๐ sisi. Karena ๐บ graf yang super edge magic artinya ada konstanta ๐ sehingga ๐(๐ข) + ๐(๐ฃ) + ๐(๐ข๐ฃ) = ๐ dan ๐: ๐(๐บ) โ {1, 2, โฆ , ๐}, ๐: ๐ธ(๐บ) โ {๐ + 1, ๐ + 2, โฆ , ๐ + ๐}. Maka akan dilihat nilai ๐ yang maksimum dan minimum, karena untuk melabeli suatu graf harus dilihat kemungkinan ๐ yang maksimum dan minimumnya. (i) Akan dilihat nilai ๐ yang maksimum. Pilih ๐ข, ๐ฃ โ ๐(๐บ) maka magic number yang maksimum yaitu ๐ ๐ข = ๐, karena magic number yang maksimum ๐ maka kemungkinan yang maksimum untuk ๐(๐ฃ) ialah ๐ โ 1, sehingga diperoleh ๐ ๐ข +๐ ๐ฃ =๐+ ๐โ1 = ๐ ๐บ + (|๐ ๐บ | โ 1) Karena simpul yang maksimumnya ๐ maka ๐ ๐ข๐ฃ = ๐ + 1 = |๐ ๐บ | + 1 Ini berarti ๐ = ๐ ๐ข + ๐ ๐ฃ + ๐ ๐ข๐ฃ = ๐ ๐บ + ๐ ๐บ โ1 +(|๐ ๐บ | + 1) (ii) Akan dilihat nilai ๐ yang minimum. Untuk melakukan pelabelan, pilih magic number yang minimum yaitu ๐ ๐ข = 1 dan untuk ๐ ๐ข๐ฃ pilih magic number yang maksimum yaitu ๐ ๐ข๐ฃ = ๐ + ๐. Karena ๐ ๐ข = 1 maka paling tidak sisi yang minimumnya yaitu ๐ ๐ฃ = 1 + 1 = 2, sehingga diperoleh
๐ = ๐ ๐ข + ๐ ๐ฃ + ๐ ๐ข๐ฃ = 1 + 2 + (๐ + ๐) =1+2+( ๐ ๐บ + ๐ธ ๐บ ) Dari (i) dan (ii) dapat diperoleh 1+2+ ๐ ๐บ + ๐ธ ๐บ โค๐ โค ๐ ๐บ + ๐ ๐บ โ1 + (|๐ ๐บ | + 1) 3 + |๐ ๐บ | + |๐ธ ๐บ | โค 3|๐ ๐บ | |๐ธ ๐บ | โค 3|๐ ๐บ | โ 3 โ |๐ ๐บ | ๐ธ ๐บ | โค2 ๐ ๐บ |โ3 โ Berikut ini diberikan ilustrasi Lema 3.1. Ilustrasi pertama, akan ditunjukkan graf yang super edge magic dan memenuhi |๐ธ ๐บ | โค 2|๐ ๐บ | โ 3. Misalkan diberikan graf ๐ถ3 seperti pada Gambar 9, banyaknya simpul dan sisi ialah 3. Jadi ๐ธ ๐บ | = ๐ ๐บ | = 3 dan ๐ธ ๐บ |=3โค2 ๐ ๐บ |โ3 =2 3 โ3 = 3. Graf ๐ถ3 merupakan graf super edge magic dan pertaksamaan pada Lema 3.1 dipenuhi. Ilustrasi kedua, akan ditunjukkan graf yang bukan super edge magic dan memenuhi |๐ธ ๐บ | โค 2|๐ ๐บ | โ 3. Misalkan diberikan graf ๐ถ4 seperti pada Gambar 14, banyaknya simpul dan sisi pada graf ๐ถ4 adalah 4. Jadi ๐ธ ๐บ | = ๐ ๐บ | = 4 dan ๐ธ ๐บ |=4โค2 ๐ ๐บ |โ3 =2 4 โ3 =5 Graf ๐ถ4 bukan graf super edge magic (bukti dapat dilihat dilampiran) dan pertaksamaan pada Lema 3.1 dipenuhi. Ilustrasi ketiga, akan ditunjukkan graf yang bukan super edge magic dan tidak memenuhi |๐ธ ๐บ | โค 2|๐ ๐บ | โ 3. Misalkan diberikan graf ๐5 seperti pada Gambar 23, banyaknya simpul adalah 5 dan banyaknya sisi adalah 8. Jadi |๐ธ ๐บ | = 8, |๐ ๐บ | = 5, dan ๐ธ ๐บ |=8โค2 ๐ ๐บ |โ3 =2 5 โ3 =7 Graf ๐5 bukan graf super edge magic karena pertaksamaan pada Lema 3.1 tidak dipenuhi sehingga Lema 3.1 tidak dipenuhi. Lema 3.1 akan digunakan untuk menunjukkan graf cycle dan graf wheel memiliki pelabelan super edge magic. Sebelum membuktikan Teorema 3.2 akan diperlihatkan contoh cara pelabelan super edge magic pada suatu graf cycle. Misalkan diberikan graf cycle ber-order 9 dengan bentuk seperti pada Gambar 12.
6
๐ถ9 :
Teorema 3.2 Cycle ๐ถ๐ adalah super edge magic jika dan hanya jika ๐ ganjil. (Enomoto et al. 1998)
a b
i
c
h
g
d
f
e
Gambar 12 Graf cycle ber-order 9. Graf ๐ถ9 tersebut akan dilabeli dengan ๐: ๐ ๐ถ9 โ {1, 2, 3, 4, 5, 6, 7, 8, 9} dan ๐: ๐ธ ๐ถ9 โ {10, 11, 12, 13, 14, 15, 16, 17, 18} sehingga menjadi graf super edge magic. Misalkan simpul-simpul pada graf ๐ถ9 dipadankan dengan suatu nilai, yaitu ๐ ๐ =1 ๐ ๐ =8 ๐ ๐ =6 ๐ ๐ =4 ๐ ๐ =2 ๐ ๐ =9 ๐ ๐ =7 ๐ ๐ =5 ๐ ๐ =3 Dipilih ๐ = 24, maka diperoleh label sisi, sehingga ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 1 + 6 + 17 = 24 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 6 + 2 + 16 = 24 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 2 + 7 + 15 = 24 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 7 + 3 + 14 = 24 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 3 + 8 + 13 = 24 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 8 + 4 + 12 = 24 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 4 + 9 + 11 = 24 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 9 + 5 + 10 = 24 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 1 + 5 + 18 = 24 dan dapat digambarkan sebagai berikut 1 18
17 6
5 10
16 2
9
15
11
7
4 12
14 3
13
8
Gambar 13 Pelabelan super edge magic pada graf ๐ถ9 . Cara pelabelan tersebut merupakan salah satu contoh cara pelabelan super edge magic pada suatu graf cycle. Cara ini juga digunakan untuk membuktikan Teorema 3.2. Berikut akan dibuktikan Teorema 3.2 yang menyatakan bahwa graf ๐ถ๐ memiliki pelabelan super edge magic.
Bukti : (โน) Misalkan cycle ๐ถ๐ adalah graf super edge magic. Akan dibuktikan ๐ bilangan ganjil. Bukti : Misalkan ๐ถ๐ adalah graf super edge magic artinya ada pelabelan super edge magic ๐ dengan ๐ sebagai magic number. Artinya ada konstanta ๐ sehingga ๐(๐ข) + ๐(๐ฃ) + ๐(๐ข๐ฃ) = ๐ dan ๐ ๐ ๐ถ๐ โ {1, 2, โฆ , ๐}, ๐ ๐ธ ๐ถ๐ โ {๐ + 1, ๐ + 2, โฆ , ๐ + ๐}. Karena setiap ๐ข๐ฃ โ ๐ธ(๐ถ๐ ) berlaku ๐ = ๐(๐ข) + ๐(๐ฃ) + ๐(๐ข๐ฃ) akibatnya ๐ ๐ =
๐ ๐ข + ๐ ๐ฃ + ๐ ๐ข๐ฃ ๐ข๐ฃ โ๐ธ ๐ถ๐
=2
๐(๐ฃ) + ๐ฃโ๐(๐ถ๐ )
๐(๐ข๐ฃ) ๐ข๐ฃ โ๐ธ(๐ถ๐ )
= 2 1+2+โฏ+๐ +( ๐ +1 +(๐ + 2) + โฏ + (๐ + ๐)) ๐
=2
2๐
๐+ ๐=1 ๐
=2
๐ ๐=๐+1 2๐
๐+ ๐=1
๐
๐โ ๐=1
๐ ๐=1
๐ ๐+1 =2 2 2๐(2๐ + 1) ๐(๐ + 1) + โ 2 2 ๐ ๐+1 =2 2 4๐2 + 2๐ โ ๐2 โ ๐ + 2 ๐(๐ + 1) 3๐2 + ๐ =2 + 2 2 ๐(3๐ + 1) = ๐(๐ + 1) + 2 Ini berarti ๐(3๐ + 1) ๐(๐ + 1) = ๐ ๐ โ 2 3๐ + 1 ๐(๐ + 1) = ๐ ๐ โ 2 3๐ + 1 ๐+1=๐ โ 2 3๐ + 1 =๐ โ๐โ1 2 Karena ๐ dan ๐ adalah bilangan bulat 3๐+1 maka bilangan bulat, sehingga 2
7
3๐ + 1 haruslah genap. Akibatnya 3๐ ganjil, maka ๐ bilangan ganjil. โ (โธ) Misalkan ๐ adalah bilangan ganjil. Akan dibuktikan cycle ๐ถ๐ adalah graf super edge magic. Bukti : Misalkan ๐ = 2๐ + 1 adalah bilangan ganjil dan diberikan graf cycle ๐ถ๐ . Dimisalkan juga ๐ ๐ถ๐ = {๐ฃ0 , ๐ฃ1 , โฆ , ๐ฃ๐ โ1 } ๐ธ ๐ถ๐ = {๐ฃ0 ๐ฃ1 , ๐ฃ1 ๐ฃ2 , โฆ , ๐ฃ๐ โ2 ๐ฃ๐ โ1 , ๐ฃ๐ โ1 ๐ฃ0 }. Didefinisikan ๐+2 ; ๐ genap 2 ๐(๐ฃ๐ ) = ๐+3 ๐+ ; ๐ ganjil 2 ๐(๐ฃ๐โ1 ๐ฃ0 ) = 2๐ ๐(๐ฃ๐ ๐ฃ๐+1 ) = 2๐ โ 1 โ ๐ dengan 0 โค ๐ โค ๐ โ 2. Ambil sembarang ๐ฃ๐ ๐ฃ๐+1 dengan 0 โค ๐ โค ๐ โ 2 dan ๐ ganjil maka ๐ = ๐ ๐ฃ๐ + ๐ ๐ฃ๐+1 + ๐ ๐ฃ๐ ๐ฃ๐+1 (๐ + 1) + 2 ๐+3 + = ๐+ 2 2 +(2๐ โ 1 โ ๐) ๐+3 ๐+3 + + 2๐ โ 1 โ ๐ =๐+ 2 2 = ๐ + ๐ + 3 + 2๐ โ 1 โ ๐ = ๐ + 2๐ + 2 ๐โ1 = + 2๐ + 2 2 ๐ โ 1 + 4๐ + 4 = 2 5๐ + 3 = 2 dan untuk ๐ฃ๐ โ1 ๐ฃ0 ๐ = ๐(๐ฃ๐โ1 ) + ๐(๐ฃ0 ) + ๐(๐ฃ๐โ1 ๐ฃ0 ) (๐ โ 1) + 2 0+2 + + 2๐ = 2 2 ๐+3 = + 2๐ 2 ๐ + 3 + 4๐ = 2 5๐ + 3 = 2 Karena ๐ ganjil maka 5๐ ganjil, sehingga 5๐ + 3 haruslah genap. 5๐ +3 Akibatnya bilangan bulat, maka ๐ 2 bilangan bulat. Jadi, ๐ adalah pelabelan super edge magic dengan magic 5๐+3 number ๐ = . 2 โ
Berikut ini diberikan ilustrasi untuk lebih memahami Teorema 3.2. Ada beberapa ilustrasi yang akan diberikan. Pada dasarnya proses pelabelan edge magic dan pelabelan super edge magic pada graf cycle diperoleh dengan mencoba-coba semua kemungkinan label yang ada. Ilustrasi pertama, misalkan diberikan graf ๐ถ4 dengan banyaknya simpul 4 dan banyaknya sisi 4, dengan bentuk graf seperti pada Gambar 14. ๐ถ4 : a
b
d
c
Gambar 14 Graf cycle ber-order 4. Untuk memperoleh pelabelan edge magic maka simpul dan sisi berlabel 1, 2, 3, 4, 5, 6, 7, 8. Misalkan simpul-simpul pada graf ๐ถ4 dipadankan dengan suatu nilai, yaitu ๐ ๐ =6 ๐ ๐ =3 ๐ ๐ =7 ๐ ๐ =8 Dipilih ๐ = 15, maka diperoleh label sisi, sehingga ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 6 + 7 + 2 = 15 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 7 + 3 + 5 = 15 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 3 + 8 + 4 = 15 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 6 + 8 + 1 = 15 dan dapat digambarkan sebagai berikut 6 2
1
7
8 5
4 3
Gambar 15 Pelabelan edge magic pada graf ๐ถ4 . Ilustrasi kedua, misalkan diberikan graf ๐ถ5 dengan banyaknya simpul 5 dan banyaknya sisi 5, dengan bentuk graf seperti pada Gambar 4. Untuk memperoleh pelabelan graf edge magic maka simpul dan sisi berlabel 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Misalkan simpulsimpul pada graf ๐ถ5 dipadankan dengan suatu nilai, yaitu
8
๐ ๐ = 10 ๐ ๐ =8 ๐ ๐ =6 ๐ ๐ =4 ๐ ๐ =2 Dipilih ๐ = 17, maka diperoleh label sisi, sehingga ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 10 + 6 + 1 = 17 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 6 + 2 + 9 = 17 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 2 + 8 + 7 = 17 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 8 + 4 + 5 = 17 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 10 + 4 + 3 = 17 dan dapat digambarkan sebagai berikut
๐ถ6 :
b
3
6
4 9
5
2
8
7
Gambar 16 Pelabelan edge magic pada graf ๐ถ5 . Sedangkan untuk memperoleh pelabelan super edge magic maka dilabeli dengan ๐: ๐ ๐ถ5 โ {1, 2, 3, 4, 5} dan ๐: ๐ธ ๐ถ5 โ {6, 7, 8, 9, 10}. Misalkan simpul-simpul pada graf ๐ถ5 dipadankan dengan suatu nilai, yaitu ๐ ๐ =1 ๐ ๐ =2 ๐ ๐ =3 ๐ ๐ =4 ๐ ๐ =5 Karena graf ๐ถ5 ber-order 5 dan 5 merupakan bilangan ganjil maka berdasarkan Teorema 3.2 diperoleh graf ๐ถ5 super edge magic maka 5๐+3 berlaku ๐ = = 14 dan diperoleh label 2 sisi, sehingga ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 1 + 3 + 10 = 14 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 3 + 5 + 6 = 14 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 5 + 2 + 7 = 14 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 2 + 4 + 8 = 14 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 1 + 4 + 9 = 14 dan dapat digambarkan sebagai berikut 1 9
10 3
4 8
6 5
7
Ilustrasi ketiga, misalkan diberikan graf ๐ถ6 dengan banyaknya simpul 6 dan banyaknya sisi 6, dengan bentuk graf seperti pada Gambar 18.
d
Gambar 18 Graf cycle ber-order 6. Untuk memperoleh pelabelan edge magic maka simpul dan sisi berlabel 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Misalkan simpul-simpul pada graf ๐ถ6 dipadankan dengan suatu nilai, yaitu ๐ ๐ =7 ๐ ๐ =6 ๐ ๐ =2 ๐ ๐ =5 ๐ ๐ = 10 ๐ ๐ = 12 Dipilih ๐ = 20, maka diperoleh label sisi, sehingga ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 7 + 2 + 11 = 20 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 2 + 10 + 8 = 20 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 10 + 6 + 4 = 20 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 6 + 5 + 9 = 20 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 5 + 12 + 3 = 20 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 7 + 12 + 1 = 20 dan dapat digambarkan sebagai berikut 7
12
1
3
11 2
5 8
9 10
4
6
Gambar 19 Pelabelan edge magic pada graf ๐ถ6 . Ilustrasi keempat, misalkan diberikan graf ๐ถ7 dengan banyaknya simpul 7 dan banyaknya sisi 7, dengan bentuk graf sebagai berikut ๐ถ7 : a
2
Gambar 17 Pelabelan super edge magic pada graf ๐ถ5 .
e
c
10 1
f
a
b
g
c
f
d
e
Gambar 20 Graf cycle ber-order 7.
9
Untuk memperoleh pelabelan edge magic maka simpul dan sisi berlabel 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14. Misalkan simpulsimpul pada graf ๐ถ7 dipadankan dengan suatu nilai, yaitu ๐ ๐ = 14 ๐ ๐ = 10 ๐ ๐ =6 ๐ ๐ =3 ๐ ๐ =5 ๐ ๐ =7 ๐ ๐ =4 Dipilih ๐ = 22, maka diperoleh label sisi, sehingga ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 14 + 6 + 2 = 22 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 6 + 5 + 11 = 22 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 5 + 4 + 13 = 22 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 4 + 10 + 8 = 22 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 10 + 3 + 9 = 22 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 3 + 7 + 12 = 22 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 14 + 7 + 1 = 22 dan dapat digambarkan sebagai berikut 14 2
1
6
7
11
12
5
3 13
9 4
8
10
1 5
4
12
8
2
7 11
9 6
3
10
Gambar 22 Pelabelan super edge magic pada graf ๐ถ7 . Dari keempat ilustrasi dapat dilihat bahwa ๐ถ๐ dengan order ๐ genap yaitu ๐ถ4 dan ๐ถ6 merupakan graf edge magic, dan ๐ถ4 bukan graf super edge magic (bukti dapat dilihat dilampiran). Sedangkan ๐ถ๐ dengan order ๐ ganjil yaitu ๐ถ5 dan ๐ถ7 merupakan graf edge magic dan graf super edge magic. Pada teorema selanjutnya, yaitu Teorema 3.3, akan ditunjukkan bahwa graf wheel bukan graf super edge magic. Sebelum membuktikan Teorema 3.3 akan diperlihatkan contoh cara pelabelan edge magic pada suatu graf wheel. Misalkan diberikan graf wheel ber-order 5 dengan bentuk seperti pada Gambar 23. ๐5 :
Gambar 21 Pelabelan edge magic pada graf ๐ถ7 . Sedangkan untuk memperoleh pelabelan super edge magic maka graf ๐ถ7 dilabeli dengan ๐: ๐ ๐ถ7 โ {1, 2, 3, 4, 5, 6, 7} dan ๐: ๐ธ ๐ถ7 โ {8, 9, 10, 11, 12, 13, 14}. Misalkan simpul-simpul pada graf ๐ถ7 dipadankan dengan suatu nilai, yaitu ๐ ๐ =1 ๐ ๐ =3 ๐ ๐ =5 ๐ ๐ =7 ๐ ๐ =2 ๐ ๐ =4 ๐ ๐ =6 Karena graf ๐ถ7 dengan order 7 dan 7 merupakan bilangan ganjil maka berdasarkan Teorema 3.2 diperoleh graf ๐ถ7 super edge 5๐+3 magic maka berlaku ๐ = = 19 dan 2 diperoleh label sisi, sehingga ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 1 + 5 + 13 = 19 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 5 + 2 + 12 = 19 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 2 + 6 + 11 = 19 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 6 + 3 + 10 = 19 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 3 + 7 + 9 = 19 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 7 + 4 + 8 = 19 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 1 + 4 + 14 = 19 dan dapat digambarkan seperti pada Gambar 22.
14
13
v1
v4
v0
v2
v3
Gambar 23 Graf wheel ber-order 5. Untuk memperoleh pelabelan edge magic maka simpul dan sisi berlabel 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13. Misalkan simpulsimpul pada graf ๐5 dipadankan dengan suatu nilai, yaitu ๐ ๐ฃ0 = 7 ๐ ๐ฃ3 = 1 ๐ ๐ฃ1 = 4 ๐ ๐ฃ4 = 12 ๐ ๐ฃ2 = 11 Dipilih ๐ = 21, maka diperoleh label sisi, sehingga ๐ ๐ฃ1 + ๐ ๐ฃ2 + ๐ ๐ฃ1 ๐ฃ2 = 4 + 11 + 6 = 21 ๐ ๐ฃ2 + ๐ ๐ฃ3 + ๐ ๐ฃ2 ๐ฃ3 = 11 + 1 + 9 = 21 ๐ ๐ฃ3 + ๐ ๐ฃ4 + ๐ ๐ฃ3 ๐ฃ4 = 1 + 12 + 8 = 21
10
๐ ๐ฃ4 + ๐ ๐ฃ1 + ๐ ๐ฃ4 ๐ฃ1 = 12 + 4 + 5 = 21 ๐ ๐ฃ0 + ๐ ๐ฃ1 + ๐ ๐ฃ0 ๐ฃ1 = 7 + 4 + 10 = 21 ๐ ๐ฃ0 + ๐ ๐ฃ2 + ๐ ๐ฃ0 ๐ฃ2 = 7 + 11 + 3 = 21 ๐ ๐ฃ0 + ๐ ๐ฃ3 + ๐ ๐ฃ0 ๐ฃ3 = 7 + 1 + 13 = 21 ๐ ๐ฃ0 + ๐ ๐ฃ4 + ๐ ๐ฃ0 ๐ฃ4 = 7 + 12 + 2 = 21 dan dapat digambarkan seperti berikut 4 5
7
2
12 8
6
10
11
3 13
9
1
Gambar 24 Pelabelan edge magic pada graf ๐5 . Berikut diberikan beberapa contoh cara untuk memperoleh nilai ๐ . Untuk ๐6 seperti pada Gambar 26, karena ๐6 memiliki 10 sisi maka 10๐ = ๐ ๐ฃ1 + ๐ ๐ฃ2 + ๐(๐ฃ1 ๐ฃ2 ) +๐ ๐ฃ2 + ๐ ๐ฃ3 + ๐(๐ฃ2 ๐ฃ3 ) +๐ ๐ฃ3 + ๐ ๐ฃ4 + ๐(๐ฃ3 ๐ฃ4 ) +๐ ๐ฃ4 + ๐ ๐ฃ5 + ๐(๐ฃ4 ๐ฃ5 ) +๐ ๐ฃ5 + ๐ ๐ฃ1 + ๐(๐ฃ5 ๐ฃ1 ) +๐ ๐ฃ0 + ๐ ๐ฃ1 + ๐(๐ฃ0 ๐ฃ1 ) +๐ ๐ฃ0 + ๐ ๐ฃ2 + ๐(๐ฃ0 ๐ฃ2 ) +๐ ๐ฃ0 + ๐ ๐ฃ3 + ๐(๐ฃ0 ๐ฃ3 ) +๐ ๐ฃ0 + ๐ ๐ฃ4 + ๐(๐ฃ0 ๐ฃ4 ) +๐ ๐ฃ0 + ๐ ๐ฃ5 + ๐(๐ฃ0 ๐ฃ5 ) = ๐ ๐ฃ1 + ๐ ๐ฃ1 + ๐ ๐ฃ1 + ๐ ๐ฃ2 +๐ ๐ฃ2 + ๐ ๐ฃ2 + ๐ ๐ฃ3 + ๐ ๐ฃ3 +๐ ๐ฃ3 + ๐(๐ฃ4 ) + ๐(๐ฃ4 ) + ๐(๐ฃ4 ) +๐ ๐ฃ5 + ๐ ๐ฃ5 + ๐ ๐ฃ5 + ๐ ๐ฃ0 +๐ ๐ฃ0 + ๐ ๐ฃ0 + ๐ ๐ฃ0 + ๐ ๐ฃ0 +๐ ๐ฃ1 ๐ฃ2 + ๐ ๐ฃ2 ๐ฃ3 + ๐ ๐ฃ3 ๐ฃ4 +๐ ๐ฃ4 ๐ฃ5 + ๐ ๐ฃ5 ๐ฃ1 + ๐ ๐ฃ0 ๐ฃ1 +๐ ๐ฃ0 ๐ฃ2 + ๐ ๐ฃ0 ๐ฃ3 + ๐ ๐ฃ0 ๐ฃ4 +๐(๐ฃ0 ๐ฃ5 ) = 2๐ ๐ฃ1 + 2๐ ๐ฃ2 + 2๐ ๐ฃ3 + 2๐(๐ฃ4 ) +2๐ ๐ฃ5 + 4๐ ๐ฃ0 + ๐ ๐ฃ0 + ๐ ๐ฃ1 +๐ ๐ฃ2 + ๐ ๐ฃ3 + ๐(๐ฃ4 ) + ๐ ๐ฃ5 +๐ ๐ฃ1 ๐ฃ2 + ๐ ๐ฃ2 ๐ฃ3 + ๐ ๐ฃ3 ๐ฃ4 +๐ ๐ฃ4 ๐ฃ5 + ๐ ๐ฃ5 ๐ฃ1 + ๐ ๐ฃ0 ๐ฃ1 +๐ ๐ฃ0 ๐ฃ2 + ๐ ๐ฃ0 ๐ฃ3 + ๐ ๐ฃ0 ๐ฃ4 +๐(๐ฃ0 ๐ฃ5 ) 5
=2
16
๐ ๐ฃ๐ + 4๐(๐ฃ0 ) + ๐ =1
๐ ๐=1
Untuk ๐7 seperti pada Gambar 8, karena ๐7 memiliki 12 sisi maka 12๐ = ๐ ๐ฃ1 + ๐ ๐ฃ2 + ๐(๐ฃ1 ๐ฃ2 ) +๐ ๐ฃ2 + ๐ ๐ฃ3 + ๐(๐ฃ2 ๐ฃ3 ) +๐ ๐ฃ3 + ๐ ๐ฃ4 + ๐(๐ฃ3 ๐ฃ4 ) +๐ ๐ฃ4 + ๐ ๐ฃ5 + ๐(๐ฃ4 ๐ฃ5 ) +๐ ๐ฃ5 + ๐ ๐ฃ6 + ๐(๐ฃ5 ๐ฃ6 ) +๐ ๐ฃ6 + ๐ ๐ฃ1 + ๐(๐ฃ6 ๐ฃ1 ) +๐ ๐ฃ0 + ๐ ๐ฃ1 + ๐(๐ฃ0 ๐ฃ1 ) +๐ ๐ฃ0 + ๐ ๐ฃ2 + ๐(๐ฃ0 ๐ฃ2 ) +๐ ๐ฃ0 + ๐ ๐ฃ3 + ๐(๐ฃ0 ๐ฃ3 ) +๐ ๐ฃ0 + ๐ ๐ฃ4 + ๐(๐ฃ0 ๐ฃ4 ) +๐ ๐ฃ0 + ๐ ๐ฃ5 + ๐(๐ฃ0 ๐ฃ5 ) +๐ ๐ฃ0 + ๐ ๐ฃ6 + ๐(๐ฃ0 ๐ฃ6 ) = ๐ ๐ฃ1 + ๐ ๐ฃ1 + ๐ ๐ฃ1 + ๐ ๐ฃ2 +๐ ๐ฃ2 + ๐ ๐ฃ2 + ๐ ๐ฃ3 + ๐ ๐ฃ3 +๐ ๐ฃ3 + ๐(๐ฃ4 ) + ๐(๐ฃ4 ) + ๐(๐ฃ4 ) +๐ ๐ฃ5 + ๐ ๐ฃ5 + ๐ ๐ฃ5 + ๐ ๐ฃ6 +๐ ๐ฃ6 + ๐ ๐ฃ6 + ๐ ๐ฃ0 + ๐ ๐ฃ0 +๐ ๐ฃ0 + ๐ ๐ฃ0 + ๐ ๐ฃ0 + ๐ ๐ฃ0 +๐ ๐ฃ1 ๐ฃ2 + ๐ ๐ฃ2 ๐ฃ3 + ๐ ๐ฃ3 ๐ฃ4 +๐ ๐ฃ4 ๐ฃ5 + ๐ ๐ฃ5 ๐ฃ6 + ๐(๐ฃ6 ๐ฃ1 ) +๐ ๐ฃ0 ๐ฃ1 + ๐ ๐ฃ0 ๐ฃ2 + ๐ ๐ฃ0 ๐ฃ3 +๐ ๐ฃ0 ๐ฃ4 + ๐(๐ฃ0 ๐ฃ5 ) + ๐(๐ฃ0 ๐ฃ6 ) = 2๐ ๐ฃ1 + 2๐ ๐ฃ2 + 2๐ ๐ฃ3 + 2๐(๐ฃ4 ) +2๐ ๐ฃ5 + 2๐ ๐ฃ6 + 5๐ ๐ฃ0 + ๐ ๐ฃ0 +๐ ๐ฃ1 + ๐ ๐ฃ2 + ๐ ๐ฃ3 + ๐ ๐ฃ4 +๐ ๐ฃ5 + ๐ ๐ฃ6 + ๐ ๐ฃ1 ๐ฃ2 + ๐ ๐ฃ2 ๐ฃ3 +๐ ๐ฃ3 ๐ฃ4 + ๐ ๐ฃ4 ๐ฃ5 + ๐ ๐ฃ5 ๐ฃ6 +๐(๐ฃ6 ๐ฃ1 ) + ๐ ๐ฃ0 ๐ฃ1 + ๐ ๐ฃ0 ๐ฃ2 +๐ ๐ฃ0 ๐ฃ3 + ๐ ๐ฃ0 ๐ฃ4 + ๐(๐ฃ0 ๐ฃ5 ) +๐(๐ฃ0 ๐ฃ6 ) 6
19
=2
๐ ๐ฃ๐ + 5๐(๐ฃ0 ) + ๐ =1
๐ ๐=1
Dilihat dari beberapa contoh di atas maka bentuk umum untuk setiap graf ๐๐ adalah sebagai berikut 2(๐ โ 1)๐ = ๐ ๐ฃ1 + ๐ ๐ฃ2 + ๐ ๐ฃ1 ๐ฃ2 +๐ ๐ฃ2 + ๐ ๐ฃ3 + ๐(๐ฃ2 ๐ฃ3 ) โฎ +๐ ๐ฃ๐โ2 + ๐ ๐ฃ๐ โ1 + ๐ ๐ฃ๐ โ2 ๐ฃ๐ โ1 +๐ ๐ฃ๐โ1 + ๐ ๐ฃ1 + ๐ ๐ฃ๐โ1 ๐ฃ1 +๐ ๐ฃ0 + ๐ ๐ฃ1 + ๐ ๐ฃ0 ๐ฃ1 +๐ ๐ฃ0 + ๐ ๐ฃ2 + ๐ ๐ฃ0 ๐ฃ2 โฎ +๐ ๐ฃ0 + ๐ ๐ฃ๐ โ1 + ๐ ๐ฃ0 ๐ฃ๐โ1 2 ๐ โ 1 ๐ = 2๐ ๐ฃ1 + 2๐ ๐ฃ2 + โฏ +2๐ ๐ฃ๐โ1 + ๐ โ 2 ๐ ๐ฃ0 + ๐ ๐ฃ0 +๐ ๐ฃ1 + โฏ + ๐(๐ฃ๐ โ1 ) + ๐ ๐ฃ1 ๐ฃ2 +๐ ๐ฃ2 ๐ฃ3 + โฏ + ๐ ๐ฃ๐โ2 ๐ฃ๐โ1 +๐ ๐ฃ๐โ1 ๐ฃ1 + ๐ ๐ฃ0 ๐ฃ1 + ๐ ๐ฃ0 ๐ฃ2 + โฏ + ๐ ๐ฃ0 ๐ฃ๐ โ1 ๐โ1
2 ๐โ1 ๐ =2
3๐โ2
๐ ๐ฃ๐ + ๐ =1
+ ๐ โ 2 ๐(๐ฃ0 )
๐ ๐=1
(1)
11
Dari persamaan tersebut diperoleh
Cara tersebut akan digunakan untuk mempermudah pembuktian Teorema 3.3. Berikut akan dibuktikan Teorema 3.3.
3๐โ2
๐โ1
๐ = 2 ๐โ1 ๐ โ2 ๐=1
โ ๐ โ 2 ๐(๐ฃ0 ) Misalkan ๐ โก 0 mod 4 maka ๐ dapat ditulis ๐ = 4๐ dengan ๐ โ โค sehingga
Teorema 3.3 Graf wheel ๐๐ dengan order ๐ bukan graf super edge magic. Bahkan ๐๐ dengan ๐ โก 0 mod 4 bukan graf edge magic. (Enomoto et al. 1998)
๐โ1
2 ๐โ1 ๐ =2
3 4๐ โ2
3๐โ2
๐= ๐=1 3๐โ2
Akan dibuktikan: (i) Graf wheel ๐๐ dengan order ๐ bukan graf super edge magic. (ii) Graf wheel ๐๐ dengan ๐ โก 0 mod 4 bukan graf edge magic. Bukti : (i) Misalkan diberikan graf wheel ๐๐ dengan order ๐. Dengan Lema 3.1 akan dibuktikan ๐๐ bukan graf super edge magic. Bukti : Misalkan ๐๐ memiliki ๐ simpul dan ๐ sisi, maka ๐ ๐ ๐๐ โ {1, 2, โฆ , ๐} dan ๐ ๐ธ ๐๐ โ {๐ + 1, ๐ + 2, โฆ , ๐ + ๐}. Andaikan ๐๐ merupakan graf super edge magic. Berdasarkan Lema 3.1 diperoleh ๐ธ ๐๐ | โค 2 ๐ ๐๐ | โ 3 Sedangkan diketahui bahwa ๐ ๐๐ = ๐ dan ๐ธ ๐๐ = 2๐ โ 2, akibatnya |๐ธ ๐๐ | โค 2|๐ ๐๐ | โ 3 2๐ โ 2 โค 2๐ โ 3 โ2 โค โ3 terjadi kontradiksi. Akibatnya pengandaian salah, maka ๐๐ bukan graf super edge magic. (ii) Misalkan diberikan graf wheel ๐๐ dengan order ๐ dan ๐ โก 0 mod 4. Akan dibuktikan ๐๐ bukan graf edge magic. Bukti : Andaikan ๐๐ adalah graf edge magic artinya ada pelabelan edge magic ๐ dengan ๐ sebagai magic number, sehingga ๐ = ๐(๐ข) + ๐(๐ฃ) + ๐(๐ข๐ฃ). Misalkan ๐ ๐๐ = {๐ฃ0 , ๐ฃ1 , โฆ , ๐ฃ๐โ1 } dan ๐ธ ๐๐ = ๐ฃ๐ ๐ฃ๐+1 1 โค ๐ โค ๐ โ 2 โช ๐ฃ๐โ1 ๐ฃ1 โช {๐ฃ0 ๐ฃ๐ |1 โค ๐ โค ๐ โ 1} dengan deg ๐ฃ0 = ๐ โ 1. Karena untuk setiap ๐ข๐ฃ โ ๐ธ(๐๐ ) berlaku ๐ = ๐(๐ข) + ๐(๐ฃ) + ๐(๐ข๐ฃ) dan untuk setiap ๐๐ berlaku
๐ ๐ฃ๐ ๐ =1
๐ ๐=1 12๐โ2
๐ = ๐=1
๐ ๐=1
1 12๐ โ 2 (12๐ โ 1) 2 1 = 2 6๐ โ 1 12๐ โ 1 2 = 6๐ โ 1 (12๐ โ 1) = 72๐ 2 โ 18๐ + 1 = 2 36๐ 2 โ 9๐ + 1 = 2๐ก + 1 dengan ๐ก bilangan bulat. Jadi merupakan bilangan ganjil. Sedangkan =
3๐โ2 ๐=1 ๐
๐โ1
2 ๐โ1 ๐ โ2
๐ ๐ฃ๐ โ ๐ โ 2 ๐(๐ฃ0 ) ๐ =1
(2) Karena ๐ โก 0 mod 4, yang berarti ๐ = 4๐ untuk suatu bilangan bulat ๐, maka ๐ โ 2 ๐ ๐ฃ๐ = 4๐ โ 2 ๐(๐ฃ0 ) = 2 2๐ โ 1 ๐(๐ฃ0 ) merupakan bilangan genap. Akibatnya persamaan (2) merupakan bilangan genap, sehingga terjadi kontradiksi. Akibatnya pengandaian salah, maka ๐๐ bukan merupakan graf edge magic. โ
Berikut ini diberikan ilustrasi untuk lebih memahami Teorema 3.3. Ada beberapa ilustrasi yang akan diberikan. Pada dasarnya proses pelabelan edge magic pada graf wheel diperoleh dengan mencoba-coba semua kemungkinan label yang ada. ๐4 :
v1
3๐โ2
๐ ๐ฃ๐ + ๐ =1
+ ๐ โ 2 ๐(๐ฃ0 )
๐
v0
๐=1
v3
v2
Gambar 25 Graf wheel ber-order 4.
12
Ilustrasi pertama, misalkan diberikan graf wheel ber-order 4 dengan bentuk seperti pada Gambar 25. Misalkan simpul-simpul pada graf ๐4 dipadankan dengan suatu nilai, yaitu ๐ ๐ฃ0 = 5 ๐ ๐ฃ1 ๐ฃ2 = 10 ๐ ๐ฃ0 ๐ฃ1 = 8 ๐ ๐ฃ1 = 2 ๐ ๐ฃ2 ๐ฃ3 = 4 ๐ ๐ฃ0 ๐ฃ2 = 7 ๐ ๐ฃ2 = 3 ๐ ๐ฃ3 ๐ฃ1 = 6 ๐ ๐ฃ0 ๐ฃ3 = 9 ๐ ๐ฃ3 = 1 sehingga diperoleh ๐ ๐ฃ1 + ๐ ๐ฃ2 + ๐ ๐ฃ1 ๐ฃ2 = 2 + 3 + 10 = 15 ๐ ๐ฃ2 + ๐ ๐ฃ3 + ๐ ๐ฃ2 ๐ฃ3 = 3 + 1 + 4 = 8 ๐ ๐ฃ3 + ๐ ๐ฃ1 + ๐ ๐ฃ3 ๐ฃ1 = 1 + 5 + 6 = 12 ๐ ๐ฃ0 + ๐ ๐ฃ1 + ๐ ๐ฃ0 ๐ฃ1 = 5 + 2 + 8 = 15 ๐ ๐ฃ0 + ๐ ๐ฃ2 + ๐ ๐ฃ0 ๐ฃ2 = 5 + 3 + 7 = 15 ๐ ๐ฃ0 + ๐ ๐ฃ3 + ๐ ๐ฃ0 ๐ฃ3 = 5 + 1 + 9 = 15 Terdapat nilai ๐ yang berbeda, sehingga graf ๐4 bukan graf edge magic. Ilustrasi kedua, misalkan diberikan graf wheel ber-order 6 dengan bentuk seperti pada Gambar 26. ๐6 : v1
๐ ๐ฃ0 + ๐ ๐ฃ3 + ๐ ๐ฃ0 ๐ฃ3 = 7 + 11 + 3 = 21 ๐ ๐ฃ0 + ๐ ๐ฃ4 + ๐ ๐ฃ0 ๐ฃ4 = 7 + 4 + 10 = 21 ๐ ๐ฃ0 + ๐ ๐ฃ5 + ๐ ๐ฃ0 ๐ฃ5 = 7 + 1 + 13 = 21 dan dapat digambarkan sebagai berikut 5 15
9 13
1
10 4
2
12
7
16
14
3 6
8 11
Gambar 27 Pelabelan edge magic pada graf ๐6 . Ilustrasi ketiga, misalkan diberikan graf wheel ber-order 8 dengan bentuk seperti pada Gambar 28. ๐8 :
v1 v5
v2
v0
v7
v2 v0
v6 v4
v3
v3
Gambar 26 Graf wheel ber-order 6. Graf tersebut akan dilabeli sehingga memiliki graf edge magic. Simpul-simpul pada graf ๐6 dipadankan dengan suatu nilai, yaitu ๐ ๐ฃ0 = 7 ๐ ๐ฃ3 = 11 ๐ ๐ฃ1 = 5 ๐ ๐ฃ4 = 4 ๐ ๐ฃ2 = 2 ๐ ๐ฃ5 = 1 Dipilih ๐ = 21, maka diperoleh label sisi, sehingga ๐ ๐ฃ1 + ๐ ๐ฃ2 + ๐ ๐ฃ1 ๐ฃ2 = 5 + 2 + 14 = 21 ๐ ๐ฃ2 + ๐ ๐ฃ3 + ๐ ๐ฃ2 ๐ฃ3 = 2 + 11 + 8 = 21 ๐ ๐ฃ3 + ๐ ๐ฃ4 + ๐ ๐ฃ3 ๐ฃ4 = 11 + 4 + 6 = 21 ๐ ๐ฃ4 + ๐ ๐ฃ5 + ๐ ๐ฃ4 ๐ฃ5 = 4 + 1 + 16 = 21 ๐ ๐ฃ5 + ๐ ๐ฃ1 + ๐ ๐ฃ5 ๐ฃ1 = 1 + 5 + 15 = 21 ๐ ๐ฃ0 + ๐ ๐ฃ1 + ๐ ๐ฃ0 ๐ฃ1 = 7 + 5 + 9 = 21 ๐ ๐ฃ0 + ๐ ๐ฃ2 + ๐ ๐ฃ0 ๐ฃ2 = 7 + 2 + 12 = 21
v5
v4
Gambar 28 Graf wheel ber-order 8. Misalkan simpul-simpul pada graf ๐4 dipadankan dengan suatu nilai, yaitu ๐ ๐ฃ0 = 10 ๐ ๐ฃ1 ๐ฃ2 = 15 ๐ ๐ฃ0 ๐ฃ1 = 16 ๐ ๐ฃ1 = 2 ๐ ๐ฃ2 ๐ฃ3 = 8 ๐ ๐ฃ0 ๐ฃ2 = 7 ๐ ๐ฃ2 = 11 ๐ ๐ฃ3 ๐ฃ4 = 18 ๐ ๐ฃ0 ๐ฃ3 = 3 ๐ ๐ฃ3 = 9 ๐ ๐ฃ4 ๐ฃ5 = 19 ๐ ๐ฃ0 ๐ฃ4 = 14 ๐ ๐ฃ4 = 4 ๐ ๐ฃ5 ๐ฃ6 = 22 ๐ ๐ฃ0 ๐ฃ5 = 13 ๐ ๐ฃ5 = 5 ๐ ๐ฃ6 ๐ฃ7 = 21 ๐ ๐ฃ0 ๐ฃ6 = 17 ๐ ๐ฃ6 = 1 ๐ ๐ฃ7 ๐ฃ1 = 20 ๐ ๐ฃ0 ๐ฃ7 = 12 ๐ ๐ฃ7 = 6 sehingga diperoleh ๐ ๐ฃ1 + ๐ ๐ฃ2 + ๐ ๐ฃ1 ๐ฃ2 = 2 + 11 + 15 = 28 ๐ ๐ฃ2 + ๐ ๐ฃ3 + ๐ ๐ฃ2 ๐ฃ3 = 11 + 9 + 8 = 28 ๐ ๐ฃ3 + ๐ ๐ฃ4 + ๐ ๐ฃ3 ๐ฃ4 = 9 + 4 + 18 = 31 ๐ ๐ฃ4 + ๐ ๐ฃ5 + ๐ ๐ฃ4 ๐ฃ5 = 4 + 5 + 19 = 28 ๐ ๐ฃ5 + ๐ ๐ฃ6 + ๐ ๐ฃ5 ๐ฃ6 = 5 + 1 + 22 = 28
13
๐ ๐ฃ6 + ๐ ๐ฃ7 + ๐ ๐ฃ6 ๐ฃ7 = 1 + 6 + 21 = 28 ๐ ๐ฃ7 + ๐ ๐ฃ1 + ๐ ๐ฃ7 ๐ฃ1 = 6 + 2 + 20 = 28 ๐ ๐ฃ0 + ๐ ๐ฃ1 + ๐ ๐ฃ0 ๐ฃ1 = 10 + 2 + 16 = 28 ๐ ๐ฃ0 + ๐ ๐ฃ2 + ๐ ๐ฃ0 ๐ฃ2 = 10 + 11 + 7 = 28 ๐ ๐ฃ0 + ๐ ๐ฃ3 + ๐ ๐ฃ0 ๐ฃ3 = 10 + 9 + 3 = 22 ๐ ๐ฃ0 + ๐ ๐ฃ4 + ๐ ๐ฃ0 ๐ฃ4 = 10 + 4 + 14 = 28 ๐ ๐ฃ0 + ๐ ๐ฃ5 + ๐ ๐ฃ0 ๐ฃ5 = 10 + 5 + 13 = 28 ๐ ๐ฃ0 + ๐ ๐ฃ6 + ๐ ๐ฃ0 ๐ฃ6 = 10 + 1 + 17 = 28 ๐ ๐ฃ0 + ๐ ๐ฃ7 + ๐ ๐ฃ0 ๐ฃ7 = 10 + 6 + 12 = 28 Terdapat nilai ๐ yang berbeda, sehingga graf ๐8 bukan graf edge magic. Ilustrasi keempat, misalkan diberikan graf wheel ber-order 9 seperti pada Gambar 29. ๐9 : v1
v2
๐ ๐ฃ5 + ๐ ๐ฃ6 + ๐ ๐ฃ5 ๐ฃ6 = 1 + 22 + 16 = 39 ๐ ๐ฃ6 + ๐ ๐ฃ7 + ๐ ๐ฃ6 ๐ฃ7 = 22 + 2 + 15 = 39 ๐ ๐ฃ7 + ๐ ๐ฃ8 + ๐ ๐ฃ7 ๐ฃ8 = 2 + 23 + 14 = 39 ๐ ๐ฃ8 + ๐ ๐ฃ1 + ๐ ๐ฃ8 ๐ฃ1 = 23 + 7 + 9 = 39 ๐ ๐ฃ0 + ๐ ๐ฃ1 + ๐ ๐ฃ0 ๐ฃ1 = 13 + 7 + 19 = 39 ๐ ๐ฃ0 + ๐ ๐ฃ2 + ๐ ๐ฃ0 ๐ฃ2 = 13 + 20 + 6 = 39 ๐ ๐ฃ0 + ๐ ๐ฃ3 + ๐ ๐ฃ0 ๐ฃ3 = 13 + 8 + 18 = 39 ๐ ๐ฃ0 + ๐ ๐ฃ4 + ๐ ๐ฃ0 ๐ฃ4 = 13 + 21 + 5 = 39 ๐ ๐ฃ0 + ๐ ๐ฃ5 + ๐ ๐ฃ0 ๐ฃ5 = 13 + 1 + 25 = 39 ๐ ๐ฃ0 + ๐ ๐ฃ6 + ๐ ๐ฃ0 ๐ฃ6 = 13 + 22 + 4 = 39 ๐ ๐ฃ0 + ๐ ๐ฃ7 + ๐ ๐ฃ0 ๐ฃ7 = 13 + 2 + 24 = 39 ๐ ๐ฃ0 + ๐ ๐ฃ8 + ๐ ๐ฃ0 ๐ฃ8 = 13 + 23 + 3 = 39 dan dapat digambarkan sebagai berikut 7
20
12
9
v8
11
v3
6
19 23
v0
14
v7
10
5
v4
24 2
21
25
4 15
v6
8
18
13
3
19
v5 22
16
1
Gambar 29 Graf wheel ber-order 9. Graf tersebut akan dilabeli sehingga memiliki graf edge magic. Misalkan simpulsimpul pada graf ๐9 dipadankan dengan suatu nilai, yaitu ๐ ๐ฃ0 = 13 ๐ ๐ฃ5 = 1 ๐ ๐ฃ1 = 7 ๐ ๐ฃ6 = 22 ๐ ๐ฃ2 = 20 ๐ ๐ฃ7 = 2 ๐ ๐ฃ3 = 8 ๐ ๐ฃ8 = 23 ๐ ๐ฃ4 = 21 Dipilih ๐ = 39, maka diperoleh label sisi, sehingga ๐ ๐ฃ1 + ๐ ๐ฃ2 + ๐ ๐ฃ1 ๐ฃ2 = 7 + 20 + 12 = 39 ๐ ๐ฃ2 + ๐ ๐ฃ3 + ๐ ๐ฃ2 ๐ฃ3 = 20 + 8 + 11 = 39 ๐ ๐ฃ3 + ๐ ๐ฃ4 + ๐ ๐ฃ3 ๐ฃ4 = 8 + 21 + 10 = 39 ๐ ๐ฃ4 + ๐ ๐ฃ5 + ๐ ๐ฃ4 ๐ฃ5 = 21 + 1 + 19 = 39
Gambar 30 Pelabelan edge magic pada graf ๐9 . Ilustrasi kelima, misalkan diberikan graf wheel ber-order 11 dengan bentuk seperti pada Gambar 31. ๐11 : v1 v2
v10
v9
v3
v0
v8
v4
v7
v5 v6
Gambar 31 Graf wheel ber-order 11.
14
Graf tersebut akan dilabeli sehingga memiliki graf edge magic. Misalkan simpulsimpul pada graf ๐11 dipadankan dengan suatu nilai, yaitu ๐ ๐ฃ0 = 14 ๐ ๐ฃ6 = 4 ๐ ๐ฃ1 = 23 ๐ ๐ฃ7 = 22 ๐ ๐ฃ2 = 2 ๐ ๐ฃ8 = 5 ๐ ๐ฃ3 = 26 ๐ ๐ฃ9 = 25 ๐ ๐ฃ4 = 3 ๐ ๐ฃ10 = 8 ๐ ๐ฃ5 = 31 Dipilih ๐ = 46, maka diperoleh label sisi, sehingga ๐ ๐ฃ1 + ๐ ๐ฃ2 + ๐ ๐ฃ1 ๐ฃ2 = 23 + 2 + 21 = 46 ๐ ๐ฃ2 + ๐ ๐ฃ3 + ๐ ๐ฃ2 ๐ฃ3 = 2 + 26 + 18 = 46 ๐ ๐ฃ3 + ๐ ๐ฃ4 + ๐ ๐ฃ3 ๐ฃ4 = 26 + 3 + 17 = 46 ๐ ๐ฃ4 + ๐ ๐ฃ5 + ๐ ๐ฃ4 ๐ฃ5 = 3 + 31 + 12 = 46 ๐ ๐ฃ5 + ๐ ๐ฃ6 + ๐ ๐ฃ5 ๐ฃ6 = 31 + 4 + 11 = 46 ๐ ๐ฃ6 + ๐ ๐ฃ7 + ๐ ๐ฃ6 ๐ฃ7 = 4 + 22 + 20 = 46 ๐ ๐ฃ7 + ๐ ๐ฃ8 + ๐ ๐ฃ7 ๐ฃ8 = 22 + 5 + 19 = 46 ๐ ๐ฃ8 + ๐ ๐ฃ9 + ๐ ๐ฃ8 ๐ฃ9 = 5 + 25 + 16 = 46 ๐ ๐ฃ9 + ๐ ๐ฃ10 + ๐ ๐ฃ9 ๐ฃ10 = 25 + 8 + 13 = 46 ๐ ๐ฃ10 + ๐ ๐ฃ1 + ๐ ๐ฃ10 ๐ฃ1 = 8 + 23 + 15 = 46 ๐ ๐ฃ0 + ๐ ๐ฃ1 + ๐ ๐ฃ0 ๐ฃ1 = 14 + 23 + 9 = 46 ๐ ๐ฃ0 + ๐ ๐ฃ2 + ๐ ๐ฃ0 ๐ฃ2 = 14 + 2 + 30 = 46 ๐ ๐ฃ0 + ๐ ๐ฃ3 + ๐ ๐ฃ0 ๐ฃ3 = 14 + 26 + 6 = 46
๐ ๐ฃ0 + ๐ ๐ฃ4 + ๐ ๐ฃ0 ๐ฃ4 = 14 + 3 + 29 = 46 ๐ ๐ฃ0 + ๐ ๐ฃ5 + ๐ ๐ฃ0 ๐ฃ5 = 14 + 31 + 1 = 46 ๐ ๐ฃ0 + ๐ ๐ฃ6 + ๐ ๐ฃ0 ๐ฃ6 = 14 + 4 + 28 = 46 ๐ ๐ฃ0 + ๐ ๐ฃ7 + ๐ ๐ฃ0 ๐ฃ7 = 14 + 22 + 10 = 46 ๐ ๐ฃ0 + ๐ ๐ฃ8 + ๐ ๐ฃ0 ๐ฃ8 = 14 + 5 + 27 = 46 ๐ ๐ฃ0 + ๐ ๐ฃ9 + ๐ ๐ฃ0 ๐ฃ9 = 14 + 25 + 7 = 46 ๐ ๐ฃ0 + ๐ ๐ฃ10 + ๐ ๐ฃ0 ๐ฃ10 = 14 + 8 + 24 = 46 dan dapat digambarkan sebagai berikut 23 8
21
15
13
9
25 16
26
6
14
7
18
30
24
2
17
29 27
5
10
19 22
3
1 28
20
12 11
31
4
Gambar 32 Pelabelan edge magic pada graf ๐11 . Dari beberapa ilustrasi tersebut dapat dilihat bahwa ๐๐ dengan order ๐ dan ๐ โก 0 mod 4 yaitu ๐4 dan ๐8 bukan graf edge magic. Sedangkan ๐๐ dengan order ๐ dan ๐ โข 0 mod 4 yaitu ๐6 , ๐9 , dan ๐11 merupakan graf edge magic.
IV SIMPULAN DAN SARAN 4.1 Simpulan Dalam karya ilmiah ini telah dibuktikan bahwa graf cycle dan graf wheel memiliki pelabelan graf yang super edge magic. Selain itu ditunjukkan pula bahwa graf cycle ๐ถ๐ adalah graf super edge magic jika dan hanya jika ๐ bilangan ganjil. Graf ๐ถ๐ dengan order ๐ bilangan genap tidak dapat ditunjukkan mempunyai pelabelan super edge magic hanya dapat ditunjukkan pelabelan edge magic-nya. Dalam karya ilmiah ini juga ditunjukkan bahwa graf wheel ๐๐ dengan order ๐ bukan
graf super edge magic, bahkan ๐๐ dengan ๐ โก 0 mod 4 bukan graf edge magic. Graf wheel ๐๐ hanya memiliki pelabelan edge magic pada saat ๐ โข 0 mod 4, sedangkan graf ๐๐ dengan order ๐ dan ๐ โก 0 mod 4 bukan graf edge magic. Suatu graf ๐บ memiliki pelabelan super edge magic jika graf tersebut memiliki pelabelan edge magic. Tetapi tidak berlaku untuk sebaliknya, yaitu suatu graf ๐บ yang memiliki pelabelan edge magic belum tentu memiliki pelabelan super edge magic.
15
4.2 Saran Karya ilmiah ini membahas pelabelan super edge magic pada graf cycle dan graf wheel. Bagi yang berminat membuat karya ilmiah yang berhubungan dengan pelabelan
super edge magic dapat mencari pada graf selain dari graf cycle dan graf wheel, misalnya pada graf complete, graf complete bipartite, graf Petersen yang diperumum, atau pada graf yang lainnya.
DAFTAR PUSTAKA Chartrand G, Oellermann OR. 1993. Applied and Algorithmic Graph Theory. New York: McGraw-Hill. Enomoto H, Llado AS, Nakamigawa T, Ringel G. 1998. Super edge-magic graphs. SUT Journal of Mathematics 34: 105-109.
Foulds LR. 1992. Graph Theory Applications. New York: Springer-Verlag. Fukuchi Y. 2001. Edge-magic labelings of wheel graphs. Tokyo J. Math 24: 153167.
16
LAMPIRAN
17
Lampiran 1 bukti graf ๐ถ4 bukan graf super edge magic. Misalkan diberikan graf ๐ถ4 dengan banyaknya simpul 4 dan banyaknya sisi 4, dengan bentuk graf seperti pada Gambar 14. Untuk memperoleh pelabelan super edge magic maka simpul dan sisinya dilabeli dengan ๐: ๐ ๐ถ4 โ {1, 2, 3, 4} dan ๐: ๐ธ ๐ถ4 โ {5, 6, 7, 8}. Ada beberapa kemungkinan untuk melabeli graf ๐ถ4 , di antaranya: (i) Misalkan ๐ ๐ = 4 dan ๐ ๐ = 3, maka ๐ ๐๐ yang mungkin adalah ๐ ๐๐ = 8 dan ๐ = ๐ ๐ + ๐ ๐ + ๐(๐๐) = 4+3+8 = 15 Untuk ๐ ๐ = 2 dan ๐ ๐ = 1 tidak ada nilai yang mungkin, sehingga ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 15 3 + 2 + ๐(๐๐) = 15 ๐(๐๐) = 10 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 15 2 + 1 + ๐(๐๐) = 15 ๐(๐๐) = 12 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 15 4 + 1 + ๐(๐๐) = 15 ๐(๐๐) = 10 ๐(๐๐) = ๐(๐๐) = 10 dan ๐(๐๐) = 12 tidak mungkin karena ๐: ๐ ๐ถ4 โ {1, 2, 3, 4} dan ๐: ๐ธ ๐ถ4 โ {5, 6, 7, 8}, dan dapat digambarkan sebagai berikut 4 8 3
1
2
Gambar 33 Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 4, ๐ ๐ = 3, ๐(๐) = 2, ๐ ๐ = 1, dan ๐ ๐๐ = 8. Sedangkan untuk ๐ ๐ = 1 dan ๐ ๐ = 2 tidak ada nilai yang mungkin, sehingga ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 15 3 + 1 + ๐(๐๐) = 15 ๐(๐๐) = 11 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 15 1 + 2 + ๐(๐๐) = 15 ๐(๐๐) = 12 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 15 4 + 2 + ๐(๐๐) = 15 ๐(๐๐) = 9
๐(๐๐) = 11, ๐(๐๐) = 12, dan ๐(๐๐) = 9 tidak mungkin karena ๐: ๐ ๐ถ4 โ {1, 2, 3, 4} dan ๐: ๐ธ ๐ถ4 โ {5, 6, 7, 8}, dan dapat digambarkan sebagai berikut 4 8 3
2
1
Gambar 34 Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 4, ๐ ๐ = 3, ๐(๐) = 1, ๐ ๐ = 2, dan ๐ ๐๐ = 8. (ii) Misalkan ๐ ๐ = 4 dan ๐ ๐ = 3, maka ๐ ๐๐ yang mungkin adalah ๐ ๐๐ = 7 dan ๐ = ๐ ๐ + ๐ ๐ + ๐(๐๐) = 4+3+7 = 14 Untuk ๐ ๐ = 2 dan ๐ ๐ = 1 tidak ada nilai yang mungkin, sehingga ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 14 3 + 2 + ๐(๐๐) = 14 ๐(๐๐) = 9 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 14 2 + 1 + ๐(๐๐) = 14 ๐(๐๐) = 11 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 14 4 + 1 + ๐(๐๐) = 14 ๐(๐๐) = 9 ๐(๐๐) = ๐(๐๐) = 9 dan ๐(๐๐) = 11 tidak mungkin karena ๐: ๐ ๐ถ4 โ {1, 2, 3, 4} dan ๐: ๐ธ ๐ถ4 โ {5, 6, 7, 8}, dan dapat digambarkan sebagai berikut 4 7 3
1
2
Gambar 35 Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 4, ๐ ๐ = 3, ๐(๐) = 2, ๐ ๐ = 1, dan ๐ ๐๐ = 7.
18
Sedangkan untuk ๐ ๐ = 1 dan ๐ ๐ = 2 ada nilai yang mungkin, yaitu ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 14 4 + 2 + ๐(๐๐) = 14 ๐(๐๐) = 8 Ada dua kemungkinan untuk ๐(๐๐) yaitu 5 dan 6. Jika ๐(๐๐) = 5 maka ๐ = ๐ ๐ + ๐ ๐ + ๐(๐๐) = 3+1+5 =9 Jika ๐(๐๐) = 6 maka ๐ = ๐ ๐ + ๐ ๐ + ๐(๐๐) = 3+1+6 = 10 Karena untuk ๐ ๐๐ = 5 yaitu ๐ = 9 dan ๐ ๐๐ = 6 yaitu ๐ = 10, maka ๐ = 14 tidak dipenuhi. Dengan cara yang sama untuk ๐(๐๐) yaitu 5 dan 6 maka ๐ = 14 tidak dipenuhi. Dan dapat digambarkan sebagai berikut 4 8
7 3
2
1
Gambar 36 Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 4, ๐ ๐ = 3, ๐(๐) = 1, ๐ ๐ = 2, ๐ ๐๐ = 7, dan ๐ ๐๐ = 8. (iii) Misalkan ๐ ๐ = 4 dan ๐ ๐ = 3, maka ๐ ๐๐ yang mungkin adalah ๐ ๐๐ = 6 dan ๐ = ๐ ๐ + ๐ ๐ + ๐(๐๐) = 4+3+6 = 13 Untuk ๐ ๐ = 2 dan ๐ ๐ = 1 ada nilai yang mungkin, yaitu ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 13 4 + 1 + ๐(๐๐) = 13 ๐(๐๐) = 8 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 13 3 + 2 + ๐(๐๐) = 13 ๐(๐๐) = 8 Karena ada nilai yang sama yaitu ๐(๐๐) = ๐(๐๐) = 8 maka syarat pelabelan super edge magic tidak dipenuhi. Dan ada nilai yang tidak mungkin juga, yaitu ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 13 2 + 1 + ๐(๐๐) = 13 ๐(๐๐) = 10
Sehingga dapat digambarkan sebagai berikut 4 6 3
1
2
Gambar 37 Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 4, ๐ ๐ = 3, ๐(๐) = 2, ๐ ๐ = 1, dan ๐ ๐๐ = 6. Sedangkan untuk ๐ ๐ = 1 dan ๐ ๐ = 2 ada nilai yang mungkin, yaitu ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 13 4 + 2 + ๐(๐๐) = 13 ๐(๐๐) = 7 Ada dua kemungkinan untuk ๐(๐๐) yaitu 5 dan 8. Jika ๐(๐๐) = 5 maka ๐ = ๐ ๐ + ๐ ๐ + ๐(๐๐) = 3+1+5 =9 Jika ๐(๐๐) = 8 maka ๐ = ๐ ๐ + ๐ ๐ + ๐(๐๐) = 3+1+8 = 12 Karena untuk ๐ ๐๐ = 5 yaitu ๐ = 9 dan ๐ ๐๐ = 8 yaitu ๐ = 12, maka ๐ = 13 tidak dipenuhi. Dengan cara yang sama untuk ๐(๐๐) yaitu 5 dan 8 maka ๐ = 13 tidak dipenuhi. Dan dapat digambarkan sebagai berikut 4 7
6 3
2
1
Gambar 38 Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 4, ๐ ๐ = 3, ๐(๐) = 1, ๐ ๐ = 2, ๐ ๐๐ = 6, dan ๐ ๐๐ = 7. (iv) Misalkan ๐ ๐ = 4 dan ๐ ๐ = 3, maka ๐ ๐๐ yang mungkin adalah ๐ ๐๐ = 5 dan ๐ = ๐ ๐ + ๐ ๐ + ๐(๐๐) = 4+3+5 = 12
19
Untuk ๐ ๐ = 2 dan ๐ ๐ = 1 ada nilai yang mungkin, yaitu ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 12 4 + 1 + ๐(๐๐) = 12 ๐(๐๐) = 7 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 12 3 + 2 + ๐(๐๐) = 12 ๐(๐๐) = 7 Karena ada nilai yang sama yaitu ๐(๐๐) = ๐(๐๐) = 7 maka syarat pelabelan super edge magic tidak dipenuhi. Dan ada nilai yang tidak mungkin juga, yaitu ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 12 2 + 1 + ๐(๐๐) = 12 ๐(๐๐) = 9 Dan dapat digambarkan sebagai berikut 4 5 3
1
2
Gambar 39 Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 4, ๐ ๐ = 3, ๐(๐) = 2, ๐ ๐ = 1, dan ๐ ๐๐ = 5. Sedangkan untuk ๐ ๐ = 1 dan ๐ ๐ = 2 ada nilai yang mungkin, sehingga ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 12 3 + 1 + ๐(๐๐) = 12 ๐ ๐๐ = 8 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 12 4 + 2 + ๐(๐๐) = 12 ๐(๐๐) = 6 4 6
5 3
2 8 1
Gambar 40 Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 4, ๐ ๐ = 3, ๐(๐) = 1, ๐ ๐ = 2, ๐ ๐๐ = 5, ๐ ๐๐ = 8, dan ๐ ๐๐ = 6. Kemungkinan untuk sehingga
๐ ๐๐
yaitu 7,
๐ = ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 1+2+7 = 10 Karena untuk ๐ ๐๐ = 7 yaitu ๐ = 10 maka ๐ = 12 tidak dipenuhi. Dan dapat digambarkan seperti pada Gambar 40. (v) Misalkan ๐ ๐ = 1 dan ๐ ๐ = 2, maka ๐ ๐๐ yang mungkin adalah ๐ ๐๐ = 8 dan ๐ = ๐ ๐ + ๐ ๐ + ๐(๐๐) = 1+2+8 = 11 Untuk ๐ ๐ = 3 dan ๐ ๐ = 4 ada nilai yang mungkin, sehingga ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 11 2 + 3 + ๐(๐๐) = 11 ๐(๐๐) = 6 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 11 3 + 4 + ๐(๐๐) = 11 ๐(๐๐) = 4 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 11 1 + 4 + ๐(๐๐) = 11 ๐(๐๐) = 6 Karena ada nilai yang sama yaitu ๐(๐๐) = ๐(๐๐) = 6 dan ๐(๐๐) = ๐ ๐ = 4 maka syarat pelabelan super edge magic tidak dipenuhi. Dan dapat digambarkan sebagai berikut 1 8 2
4 6 3
Gambar 41 Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 1, ๐ ๐ = 2, ๐(๐) = 3, ๐ ๐ = 4, ๐ ๐๐ = 8, dan ๐ ๐๐ = 6. Sedangkan untuk ๐ ๐ = 4 dan ๐ ๐ = 3 ada nilai yang mungkin, sehingga ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 11 2 + 4 + ๐(๐๐) = 11 ๐ ๐๐ = 5 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 11 1 + 3 + ๐(๐๐) = 11 ๐(๐๐) = 7 Kemungkinan untuk ๐ ๐๐ yaitu 6, sehingga ๐ = ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 4+3+6 = 13
20
Karena untuk ๐ ๐๐ = 6 yaitu ๐ = 13 maka ๐ = 11 tidak dipenuhi. Dan dapat digambarkan sebagai berikut 1 7
8 2
3 5 4
Gambar 42 Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 1, ๐ ๐ = 2, ๐(๐) = 4, ๐ ๐ = 3, ๐ ๐๐ = 8, ๐ ๐๐ = 5, dan ๐ ๐๐ = 7. (vi) Misalkan ๐ ๐ = 2 dan ๐ ๐ = 3, maka ๐ ๐๐ yang mungkin adalah ๐ ๐๐ = 6 dan ๐ = ๐ ๐ + ๐ ๐ + ๐(๐๐) = 2+3+6 = 11 2
๐ ๐ + ๐ ๐ + ๐ ๐๐ = 11 2 + 1 + ๐(๐๐) = 11 ๐(๐๐) = 8 Karena ada nilai yang sama yaitu ๐(๐๐) = ๐(๐๐) = 6 dan ๐(๐๐) = ๐ ๐ = 4 maka syarat pelabelan super edge magic tidak dipenuhi. Dan dapat digambarkan seperti pada Gambar 43. Sedangkan untuk ๐ ๐ = 1 dan ๐ ๐ = 4 ada nilai yang mungkin, sehingga ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 11 3 + 1 + ๐(๐๐) = 11 ๐ ๐๐ = 7 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 11 2 + 4 + ๐(๐๐) = 11 ๐(๐๐) = 5 Kemungkinan untuk ๐ ๐๐ yaitu 8, sehingga ๐ = ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 1+4+8 = 13 Karena untuk ๐ ๐๐ = 8 yaitu ๐ = 13 maka ๐ = 11 tidak dipenuhi. Dan dapat digambarkan sebagai berikut 2
6
8
3
5
6 1 3
4 7
4
Gambar 43 Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 2, ๐ ๐ = 3, ๐(๐) = 4, ๐ ๐ = 1, ๐ ๐๐ = 6, dan ๐ ๐๐ = 8. Untuk ๐ ๐ = 4 dan ๐ ๐ = 1 ada nilai yang mungkin, sehingga ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 11 3 + 4 + ๐(๐๐) = 11 ๐(๐๐) = 4 ๐ ๐ + ๐ ๐ + ๐ ๐๐ = 11 4 + 1 + ๐(๐๐) = 11 ๐(๐๐) = 6
1
Gambar 44 Graf ๐ถ4 yang dilabeli dengan ๐ ๐ = 2, ๐ ๐ = 3, ๐(๐) = 1, ๐ ๐ = 4, ๐ ๐๐ = 8, ๐ ๐๐ = 7, dan ๐ ๐๐ = 5. Dilihat dari beberapa kemungkinan untuk melabeli graf ๐ถ4 tersebut maka graf ๐ถ4 bukan graf super edge magic.