PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI

PELABELAN TOTAL AJAIB TITIK PADA GRAF RODA

SKRIPSI

Diajukan Untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Pendidikan Program Studi Pendidikan Matematika

Oleh : Anastasia Meilina Kristinawati NIM : 101414024

PROGRAM STUDI PENDIDIKAN MATEMATIKA JURUSAN PENDIDIKAN MATEMATIKA DAN ILMU PENGETAHUAN ALAM FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS SANATA DHARMA YOGYAKARTA 2015

i


ii


iii


HALAMAN PERSEMBAHAN

Finish what you have started. Don’t quit though it hard, keep trying and believe in your self “you are an absolute gem”

Dengan penuh syukur karya ini kupersembahkan kepada : Tuhan Yesus, Bunda Maria, dan Santo Yusuf Bapak, Ibu, dan adik-adikku Para sahabat

iv


PERNYATAAN KEASLIAN KARYA

Saya menyatakan dengan sesungguhnya bahwa skripsi yang saya tulis ini tidak memuat karya atau bagian karya orang lain, kecuali yang telah disebutkan dalam kutipan dan daftar pustaka, sebagaimana layaknya karya ilmiah.

Yogyakarta, 27 Februari 2015 Penulis,

Anastasia Meilina Kristinawati

v


ABSTRAK Anastasia Meilina Kristinawati. 2015. Pelabelan Total Ajaib Titik pada Graf Roda. Skripsi. Program Studi Pendidikan Matematika, Fakultas Keguruan dan Ilmu Pendidikan, Universitas Sanata Dharma, Yogyakarta. Pelabelan Total Ajaib Titik atau Vertex Magic Total Labelings (VMTL) merupakan pemetaan bijektif 𝑓 dari 𝑉(𝐺) ∪ 𝐸(𝐺) ke bilangan bulat positif 1,2,3, … , 𝑣 + 𝑒 dengan 𝑣 = 𝑉(𝐺) dan 𝑒 = 𝐸(𝐺) sedemikian sehingga untuk setiap 𝑥 ∈ 𝑉(𝐺) berlaku 𝑓 𝑥 + 𝑓 𝑥𝑦 = 𝑘 untuk 𝑦 ∈ 𝑉(𝐺) yang berdekatan dengan 𝑥. Bilangan 𝑘 disebut konstanta ajaib. Graf roda 𝑊1,𝑛 merupakan graf yang dibangun dengan melakukan operasi join pada graf komplet 𝐾1 dengan graf sikel 𝐶𝑛 , dapat dinotasikan 𝑊1,𝑛 = 𝐾1 + 𝐶𝑛 . Pada skripsi ini, graf 𝑊1,𝑛 akan disebut 𝑊𝑛 . Tujuan penelitian ini adalah (1) mengetahui apakah graf roda memiliki Pelabelan Total Ajaib Titik, (2) mengetahui rentang nilai konstanta ajaib k, dan (3) mengetahui cara melabeli elemen graf roda 𝑊𝑛 . Batas nilai k ditentukan melalui perhitungan dasar dan perhitungan yang mempertimbangkan struktur graf roda, sehingga diperoleh batas nilai k, 13𝑛 2 +11𝑛+2 2 𝑛 +1

≤𝑘≤

17𝑛 2 +15𝑛+2 2 𝑛 +1

dan

𝑛+2 (𝑛 +1) 2

≤ 𝑘 ≤ 7𝑛 + 6. Setiap elemen pada

graf roda berpeluang dilabeli dengan bilangan bulat positif 1,2,3, … , 𝑣 + 𝑒 , sehingga ada banyak cara melabeli setiap elemen. Pelabelan merupakan suatu fungsi bijektif, sehingga setiap bilangan hanya dapat digunakan sekali. Pelabelan dilakukan secara iteratif dengan melabeli sebuah jari-jari (spoke), dua buah sisi pada sikel (rim), dan satu buah titik (vertex) secara berulang. Ada banyak cara melabeli elemen graf roda sehingga dibutuhkan suatu algoritma pelabelan untuk graf roda. Algoritma pelabelan disimulasikan melalui program. Graf roda dengan n besar ( n > 11 ) tidak dapat dilabeli. Pelabelan Total Titik Ajaib pada Graf roda ada jika 3 ≤ 𝑛 ≤ 11.

Kata kunci : pelabelan total ajaib titik, graf roda

vi


ABSTRACT Anastasia Meilina Kristinawati. 2015. Vertex-Magic Total Labelings of Wheel. Undergradute Thesis. Mathematics Education Study Program, Departement of Mathematics and Science, Faculty of Teacher Training and Education Science, Sanata Dharma University, Yogyakarta. Vertex-magic total labeling is a one-to-one function of f from 𝑉(𝐺) ∪ 𝐸(𝐺) onto the integer 1,2, … , 𝑒 + 𝑣 with 𝑣 = 𝑉 and 𝑒 = 𝐸 if there is contant k so that for every 𝑥 ∈ 𝑉(𝐺), 𝑓 𝑥 + 𝑓 𝑥𝑦 = 𝑘 where the sum is over all the vertices y adjecent to x. The integer k called magic constant. Wheel 𝑊1,𝑛 is the join of 𝐾1 with 𝐶𝑛 , that is 𝑊1,𝑛 = 𝐾1 + 𝐶𝑛 . In this study, the wheel 𝑊1,𝑛 is called 𝑊𝑛 . The purpose of this study were (1) to know whether the graph wheel has vertex-magic total labeling, (2) to know the interval magic constant k, and (3) to know how to label the elements of wheel 𝑊𝑛 . The feasiable range of k is determined by basic counting and computing which consider to the structure of wheel, in order to obtain the interval of k, 13𝑛 2 +11𝑛+2 2 𝑛 +1

≤𝑘≤

17𝑛 2 +15𝑛+2 2 𝑛 +1

and

𝑛+2 (𝑛 +1) 2

≤ 𝑘 ≤ 7𝑛 + 6. Each element of

wheel is labeled with positive integers 1,2,3, ..., 𝑣 + 𝑒, so there are many ways to label each element. Labeling is a one-to-one function, so that each label can only be used once. Labeling is started by attempting every possible label for spoke edge 𝑠1 , rim edge 𝑟1 and 𝑟𝑛 , also vertex 𝑣1 done iteratively. There are many ways to label the element of wheel therefore a labeling algorithm of wheel is needed. Labeling algorithm is simulated through the Matlab 7.1 program. The large wheels (n > 11) cannot be labeled. 𝑊𝑛 has a vertex-magic total labeling if and only if 3 ≤ 𝑛 ≤11. Keywords : vertex-magic total labeling, wheel

vii


LEMBAR PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS

Yang bertandatangan di bawah ini, saya mahasiswa Universitas Sanata Dharma : Nama

: Anastasia Meilina Kristinawati

No. Mahasiswa

: 101414024

Demi pengembangan ilmu pengetahuan, saya memberikan kepada Perpustakaan Universitas Sanata Dharma karya ilmiah saya yang berjudul : Pelabelan Total Ajaib Titik pada Graf Roda Dengan demikian saya memberikan kepada Perpustakaan Sanata Dharma hak untuk menyimpan, mengalihkan dalam bentuk media lain, mengelolanya dalam

bentuk

pangkalan

data,

mendistribusikan

secara

terbatas,

dan

mempublikasikannya di Internet atau media lain untuk kepentingan akademis tanpa perlu meminta ijin dari saya maupun memberikan royalti kepada saya selama tetap mencantumkan nama saya sebagai penulis. Demikian pernyataan ini yang saya buat dengan sebenarnya.

Dibuat di Yogyakarta Pada tanggal : 27 Februari 2015 Yang menyatakan,


viii


KATA PENGANTAR

Puji dan syukur kepada Tuhan Yang Maha Esa atas berkat dan rahmatNya, sehingga penulis dapat menyelesaikan skripsi dengan judul “Pelabelan Total Ajaib Titik pada Graf Roda.” Penyusunan skripsi ini dimaksudkan untuk memperoleh gelar Sarjana Pendidikan pada Program Studi Pendidikan Matematika, Fakultas Keguruan dan Ilmu Pendidikan, Universitas Sanata Dharma Yogyakarta. Selama penyusunan skripsi ini banyak kesulitan dan hambatan yang penulis alami. Namun, dengan bimbingan dari berbagai pihak semua hambatan dan kesulitan dapat teratasi. Untuk itu, pada kesempatan ini penulis ingin mengucapkan terima kasih kepada : 1. Bapak Rohandi, Ph. D selaku Dekan Fakultas Keguruan dan Ilmu Pendidikan Universitas Sanata Dharma Yogyakarta. 2. Bapak Dr. Marcellinus Andy Rudhito,S. Pd selaku Ketua Jurusan dan Ketua Program Studi

Pendidikan Matematika dan Ilmu Pengetahuan

Alam Universitas Sanata Dharma Yogyakarta. 3. Bapak D. Arif Budi Prasetyo,S.Si.,M.Si selaku Dosen Pembimbing Skripsi yang telah berkenan memberikan bimbingan, masukan, dan pengarahan dengan penuh kesabaran selama penyusunan skripsi ini. 4. Para dosen penguji yang telah berkenan memberikan saran dan kritik yang membangun pada penyusunan skripsi ini. 5. Segenap Dosen Prodi Pendidikan Matematika yang telah mendidik, membagi pengetahuan dan pengalaman yang bermanfaat bagi penulis. 6. Bapak Sugeng, Bu Tari, dan Mas Arif atas segala bantuan, keramahan, dan kerja sama selama penulis menempuh studi dan menyelesaikan penyususn skripsi ini. 7. Bapak Yohanes Sugeng, Ibu Theresia Sutimah, dan adik-adikku Catharina Aprillia Dwi Wijayanti, Cyrillus Tri Adhie Pamungkas atas kasih sayang, doa, perhatian, dan semangat yang diberikan. Semoga skripsi ini bisa menjadi hadiah kecil yang membanggakan. ix


8. Teman-teman Pendidikan Matematika 2010 atas semangat, keceriaan, dan kebersamaan selama menempuh kuliah. 9. Bapak Dedacus Teja Heri Sujana dan Ibu Rosalia Unung Redi Wuryanti atas semangat, bantuan, dan kebersamaan selama di Sayidan. 10. Seluruh staf perpustakaan Universitas Sanata Dharma di Paingan atas bantuan, kerja sama, dan keramahan yang telah diberikan. 11. Semua pihak yang tidak dapat disebutkan satu persatu telah memberikan bantuan dan dukungan hingga proses penyususan skripsi ini selesai. Akhirnya, penulis berharap semoga skripsi ini bermanfaat bagi pembaca.

Yogyakarta, 27 Februari 2015 Penulis


x


DAFTAR ISI

HALAMAN JUDUL................................................................................................ i HALAMAN PERSETUJUAN PEMBIMBING ..................................................... ii HALAMAN PENGESAHAN ................................................................................ iii HALAMAN MOTTO ............................................................................................ iv PERNYATAAN KEASLIAN KARYA ................................................................. v ABSTRAK ............................................................................................................. vi ABSTRACT ............................................................................................................ vii PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH ................. viii KATA PENGANTAR ........................................................................................... ix DAFTAR ISI .......................................................................................................... xi DAFTAR GAMBAR ........................................................................................... xiii DAFTAR TABEL ................................................................................................. xv DAFTAR LAMPIRAN ........................................................................................ xvi

BAB I PENDAHULUAN A. Latar Belakang ......................................................................................... 1 B. Batasan Masalah....................................................................................... 5 C. Rumusan Masalah .................................................................................... 5 D. Tujuan Penelitian ..................................................................................... 6 E. Manfaat Penelitian ................................................................................... 6 F. Metode Penelitian..................................................................................... 6 G. Sistematika Penulisan Skripsi .................................................................. 7

BAB II KAJIAN PUSTAKA A. Pengertian Graf ...................................... ................................................ .9 B. Jenis – jenis Graf................................ .................................................... 11 C. Isomorfik Graf.........................................................................................17 D. Pelabelan Graf................................... ......................................................19 E. Dualitas Graf............................................. ............................................. 23 xi


F. Kerangka Berpikir..................................... ............................................. 25

BAB III PELABELAN TOTAL AJAIB TITIK PADA GRAF RODA A. Perhitungan Dasar Pelabelan Total Ajaib Titik ..................................... 27 B. Interval Nilai Konstanta Ajaib Pelabelan Total Ajaib Titik................... 30 C. Pelabelan Graf Roda pada n Besar (n > 11) dan 3 ≤ 𝑛 ≤ 11 ................. 32 1. Pelabelan Graf Roda dengan n Besar (n > 11) .............................. 33 2. Pelabelan Graf Roda 𝑊𝑛 dengan 3 ≤ 𝑛 ≤ 11 ............................. 34

BAB IV ALGORITMA PELABELAN TOTAL AJAIB TITIK PADA GRAF RODA A. Proses Pelabelan Total Ajaib Titik pada Graf Roda ................................. 44 B. Diagram Alir Pelabelan Total Ajaib Titik pada Graf Roda ...................... 46 C. Deskripsi Algoritma Pelabelan Total Ajaib Titik pada Graf Roda ........... 54 D. Simulasi Pelabelan .................................................................................... 65

BAB V PENUTUP A. Kesimpulan ............................................................................................... 71 B. Saran .......................................................................................................... 71

DAFTAR PUSTAKA ........................................................................................... 73 LAMPIRAN .......................................................................................................... 74

xii


DAFTAR GAMBAR

Gambar 1.1

Jembatan Königsberg .................................................................... 1

Gambar 1.2

Graf representasi Jembatan Königsberg ........................................ 2

Gambar 1.3

Proses konversi citra sidik jari ke graf berbobot ........................... 3

Gambar 2.1

Tiga buah graf ............................................................................... 9

Gambar 2.2

Graf berbobot .............................................................................. 11

Gambar 2.3

Graf tak berhingga...................................................................... 12

Gambar 2.4

Graf tak berarah ........................................................................... 13

Gambar 2.5

Graf berarah................................................................................. 13

Gambar 2.6

Graf lengkap ................................................................................ 14

Gambar 2.7

Graf sikel ..................................................................................... 14

Gambar 2.8

Graf teratur .................................................................................. 15

Gambar 2.9

Graf roda ..................................................................................... 15

Gambar 2.10

Penamaan elemen graf roda ........................................................ 16

Gambar 2.11

Label elemen graf roda ................................................................ 16

Gambar 2.12

Graf isomorfik dan tidak isomorfik ............................................. 17

Gambar 2.13 Contoh pelabelan 𝑊4 dengan k = 26 .......................................... 18 Gambar 2.14 Pelabelan titik ............................................................................. 19 Gambar 2.15

Pelabelan sisi .............................................................................. 19

Gambar 2.16

Pelabelan total ............................................................................ 20

Gambar 2.17

Pelabelan total ajaib titik pada 𝑊4 .............................................. 21

Gambar 2.18 Pelabelan total ajaib sisi pada 𝑊6 ................................................ 22

xiii


Gambar 2.19 Dual pelabelan pada Graf 𝐾4 ........................................................ 24 Gambar 3.1

Pelabelan total ajaib titik pada 𝑊4 ............................................... 29

Gambar 3.2 Pelabelan pada 𝑊3 dengan k = 20 ................................................. 35 Gambar 3.3 Pelabelan pada 𝑊3 dengan k = 21 ................................................. 36 Gambar 3.4 Pelabelan pada 𝑊3 dengan k = 23 ................................................. 37 Gambar 3.5 Pelabelan pada 𝑊3 dengan k = 24 ................................................. 37 Gambar 3.6 Pelabelan pada 𝑊6 , 𝑊7 , dan 𝑊8 ................................................... 40 Gambar 4.1

Proses pelabelan pada graf roda 𝑊𝑛 ............................................ 46

Gambar 4.2 Diagram Alir Proses Pelabelan ..................................................... 47 Gambar 4.3 Diagram Alir Sub-Program Batas Nilai k ..................................... 50 Gambar 4.4 Diagram Alir Sub-Program label_awal ........................................ 51 Gambar 4.5 Diagram Alir Sub-Program label_tengah .................................... 53 Gambar 4.6 Diagram Alir Sub-Program label_akhir....................................... 54 Gambar 4.7 (a)Tampilan awal pada command window ................................... 65 Gambar 4.7 (b)Tampilan input n pada command window ............................... 66 Gambar 4.7 (c)Tampilan akhir pada command window .................................. 66 Gambar 4.8 Berkas keluaran fungsi label_awal pada command window ......... 67 Gambar 4.9 Ilustrasi berkas keluaran fungsi label_awal .................................. 67 Gambar 4.10 Berkas keluaran fungsi label_tengah pada command window .... 68 Gambar 4.11 Ilustrasi berkas keluaran fungsi label_tengah ............................. 68 Gambar 4.12 Berkas keluaran fungsi label_awal pada command window ....... 69 Gambar 4.13 Ilustrasi berkas keluaran pelabelan n = 3 dengan k = 21 .......... 69

xiv


DAFTAR TABEL

Tabel 3.1

Kemungkinan Nilai Konstanta Ajaib k ........................................... 31

Tabel 3.2

Banyaknya Pelabelan pada 𝑊3 ....................................................... 38

Tabel 4.1

Variabel yang digunakan dalam pelabelan ..................................... 44

xv


DAFTAR LAMPIRAN

Lampiran 1 : Berkas Keluaran Program label ...................................................... 74 Lampiran 2 : Listing Program label ...................................................................... 75 Lampiran 3 : Listing Program label_awal ............................................................ 76 Lampiran 4 : Listing Program label_tengah ........................................................ 77 Lampiran 5 : Listing Program label_akhir .......................................................... 77

xvi


BAB I PENDAHULUAN

A. Latar Belakang Ada berbagai permasalahan dalam kehidupan sehari – hari yang dapat dimodelkan dalam diagram titik dan garis. Titik

memperagakan

objek

permasalahan dan garis memperagakan hubungan antar objek. Pemodelan semacam ini secara khusus dipelajari dalam metematika pada pokok bahasan graf. Teori graf muncul pertama kali pada tahun 1736 ketika seorang matematikawan Swiss bernama Leonhard Euler mencoba mencari solusi dari teka-teki Jembatan Königsberg. Ada tujuh jembatan yang dibangun di atas Kota Königsberg. Ketujuh jembatan tersebut dibangun di antara aliran Sungai Pregel, sehingga kota tersebut terbagi menjadi empat bagian seperti tampak pada gambar berikut (Munir, 2001).

Gambar 1.1 Jembatan Königsberg

1

PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI 2

Teka-teki jembatan Königsberg merupakan suatu pertanyaan yaitu apakah mungkin berjalan melewati ketujuh jembatan tepat satu kali dan kembali ke tempat semula. Pertanyaan ini menarik perhatian Euler yang kemudian mempresentasikan masalah tersebut dalam suatu diagram. Diagram tersebut terdiri dari empat simpul dan tujuh garis. Simpul A, B, C, dan D yang mempresentasikan keempat wilayah yang dilalui aliran Sungai Pregel, sedangkan tujuh buah garis yang mempresentasikan jembatan yang dibangun di atasnya. Diagram tersebut terlihat seperti gambar berikut

Gambar 1.2 Graf representasi Jembatan Königsberg

Menurut Euler, orang dapat melewati ketujuh jembatan itu tepat satu kali dan kembali ke tempat asal keberangkatan jika setiap titik berderajat genap. Derajat suatu titik menyatakan

banyaknya garis yang bersisian dengan titik

tersebut. Pada gambar 2.1, titik C bersisian dengan sisi AC, BC, dan CD maka titik C berderajat 3. Titik B dan D berderajat tiga, sedangkan titik A berderajat lima. Karena A, B, C, dan D berderajat ganjil maka orang tidak dapat melewati ketujuh jembatan tepat satu kali dan kembali ke tempat asal keberangkatan.


Representasi semacam ini dirasakan manfaatnya pada berbagai bidang antara lain dalam perancangan jalur transportasi, optimasi jaringan komunikasi, pembuatan jadwal kuliah, model ikatan kimia, perancangan alur pengunjung pameran, perancangan jaringan elektrik, dll. Pada beberapa kasus, solusi dari permasalahan-permasalahan tersebut adalah dengan melakukan pelabelan pada sisi atau titiknya, sehingga dapat ditentukan bobot elemen yang dievaluasi. Pelabelan graf merupakan kajian dalam teori graf yang berkembang dan banyak diteliti. Kajian ini pertama kali diperkenalkan oleh Sedláček pada tahun 1963. Kemudian dikembangkan Steward pada tahun 1966 dan pada tahun 1970, Kotzig dan Rosa membahasnya dengan istilah valuation (Wallis, 2001). Pelabelan graf juga mempunyai aplikasi yang cukup luas dalam berbagai bidang seperti x-ray, crystallography, teori koding, kriptografi, radar astronomi, desain sirkuit, dan desain jaringan komunikasi. Sebagai contoh sistem biometrik dengan sidik jari. Citra digital sidik jari dikonversi menjadi graf berbobot. Bobot setiap titik dikonversi menjadi kumpulan bit dan dapat digunakan sebagai alat autentifikasi (Fathoni,2011).

Gambar 1.3 Proses konversi citra sidik jari ke graf berbobot


Pelabelan graf merupakan pemetaan bijektif yang memetakan setiap elemen graf ke bilangan bulat positif. Beberapa jenis pelabelan menurut himpunan asalnya, yaitu pelabelan titik (vertex labelings), pelabelan sisi (edge labelings), dan pelabelan total (total labelings). Pelabelan titik merupakan pelabelan dengan himpunan asal berupa titik, pelabelan sisi adalah pelabelan dengan himpunan asal berupa sisi, sedangkan pelabelan total adalah pelabelan yang himpunan asalnya adalah titik dan sisi. Bila pelabelan yang dilakukan memenuhi nilai tertentu, maka pelabelan graf dibedakan menjadi dua yakni pelabelan ajaib (magic labelings) dan pelabelan tak–ajaib (antimagic labelings). Pada pelabelan ajaib, bobot elemen graf yang dievaluasi memenuhi suatu nilai tertentu. Nilai ini selalu tetap untuk semua elemen yang dievaluasi dan disebut konstanta ajaib. Sedangkan pada pelabelan tak-ajaib, bobot elemen graf yang dievaluasi membentuk barisan aritmetika. Pada penelitian ini akan digunakan pelabelan total ajaib titik (vertex-magic total labelings). Pelabelan total ajaib titik merupakan pemetaan bijektif yang memetakan himpunan titik dan sisi ke himpunan bilangan bulat positif 1,2,3, … , 𝑣 + 𝑒 dimana 𝑣 dan 𝑒 secara berturut-turut menyatakan banyaknya titik dan sisi, sedemikian hingga jumlahan dari label titik dan sisi-sisi yang bersisian sama / konstan (Wallis, 2001). Pelabelan total ajaib titik dikembangkan pada berbagai kelas graf, seperti graf sikel, graf lengkap, graf roda, dll. Sejauh ini MacDougall, dkk (2002) menunjukkan bahwa pelabelan total ajaib titik pada graf roda ada jika 3 ≤ 𝑛 ≤ 11. Joseph A. Gallian (2014) menyatakan pelabelan total ajaib titik pada graf roda ada jika 𝑛 ≤ 11. Namun, hasil yang ditunjukkan belum mencakup


semua pelabelan yang (mungkin) ada. Setiap sisi dan titik pada graf roda dapat dilabeli dengan label yang hadir, sehingga ada banyak cara melabelinya. Perkembangan bidang komputasi dimanfaatkan untuk membantu menemukan pelabelan yang (mungkin) ada. Pada tahun 2008, Andrew Baker dan Joe Sawada membangun algoritma pelabelan total ajaib titik diperumum untuk graf sikel dan roda. Algoritma tersebut diwujudkan dalam suatu program dengan keluaran berupa hasil pelabelan yang tidak isomorfik. Karena alasan tersebut, penulis tertarik untuk mengkaji tentang pelabelan total ajaib titik pada graf roda. Kajian tersebut meliputi pelabelan total ajaib titik pada graf roda, interval nilai konstanta ajaib, dan cara melabeli sisi dan titik graf roda. Proses pelabelan dilakukan dengan membangun algoritma pelabelan dan mengaplikasikannya pada salah satu perangkat lunak.

B. Batasan Masalah Pada skripsi ini akan dibahas graf roda dan pelabelan total ajaib titiknya pada konstanta ajaib tertentu. Algoritma pelabelan disimulasikan dengan program MATLAB 7.1 pada konstanta ajaib k yang mungkin.

C. Rumusan Masalah Berdasarkan latar belakang dan batasan masalah di atas, rumusan masalah yang akan dibahas dalam tugas akhir ini adalah 1. Apakah pelabelan total ajaib titik berlaku pada graf roda?


2. Bagaimana rentang nilai konstanta ajaib yang terbentuk dalam pelabelan total ajaib titik pada graf roda? 3. Bagaimana cara melabeli sisi dan titik pada graf roda untuk nilai konstanta ajaib k?

D. Tujuan Penelitian 1. Mengetahui apakah pelabelan total ajaib titik berlaku pada graf roda 2. Mengetahui bagaimana rentang nilai konstanta ajaib yang terbentuk dalam pelabelan total ajaib titik pada graf roda 3. Mengetahui cara melabeli sisi dan titik pada graf roda untuk nilai konstanta ajaib k

E. Manfaat Penelitian Manfaat penelitian ini adalah 1. Menambah wawasan mengenai pelabelan total ajaib titik pada graf roda dan rentang nilai k yang terbentuk 2. Dapat melabeli sisi dan titik pada graf roda dengan menentukan nilai konstanta ajaibnya

F. Metode Penelitian Penelitian dalam tugas akhir ini adalah penelitian pustaka (literature research) yang mengacu pada buku Magic Graph oleh W. D. Walis (2001), jurnal Magic Labelings on Cycle and Wheels oleh Andrew Baker dan Joe Sawada


(2008), dan A Dynamic Survey of Graph Labeling oleh Joseph A. Gallian (2014). Penelitian ini menggunakan pendekatan kualitatif, sehingga pola pembahasan dimulai dari hal-hal khusus (induktif) menuju pada suatu generalisasi yang bersifat umum (deduktif). Secara garis besar langkah-langkah penelitian ini sebagai berikut : 1. Mengumpulkan literatur yang berhubungan dengan topik 2. Mempelajari topik 3. Menganalisa sifat-sifat pelabelan total ajaib titik 4. Membangun graf roda 5. Menentukan apakah pelabelan total ajaib titik berlaku pada graf roda, dan menentukan rentang nilai konstanta ajaibnya 6. Menentukan cara melabeli sisi dan titik pada graf roda untuk nilai konstanta tertentu

G. Sistematika Penulisan Sistematika penulisan tugas akhir ini dibagi menjadi empat bagian, yaitu Bab I : Pendahuluan Pada bab ini dijelaskan tentang latar belakang, rumusan masalah, pembatasan masalah, tujuan penelitian, manfaat penelitian, metode penelitan, dan sistematika penulisan.


Bab II : Kajian Pustaka Pada bab ini dijelaskan mengenai teori graf dasar, jenis-jenis graf, pelabelan graf, dan kerangka berpikir. Bab III : Pelabelan Total Ajaib Titik pada Graf Roda Pada bab ini dianalisis mengenai perhitungan dasar untuk menentukan batasan nilai konstanta ajaib, rentang nilai konstanta ajaib berdasarkan struktur graf roda, dan pelabelan graf roda untuk 3 ≤ 𝑛 ≤ 11 Bab IV : Algoritma Pelabelan Total Ajaib Titik pada Graf Roda Algoritma pelabelan total ajaib titik pada graf roda dan simulasinya Bab V : Penutup Pada bab ini dijelaskan kesimpulan dari pembahasan yang telah diuraikan pada bab sebelumnya serta saran-saran yang berkaitan dengan pembahasan tersebut.


BAB II KAJIAN PUSTAKA

A. Pengertian Graf Suatu graf 𝐺 didefinisikan sebagai pasangan himpunan 𝑉, 𝐸 yang terdiri dari himpunan berhingga dan tak kosong dari simpul-simpul / titik-titik (vertices) dan himpunan sisi (edges) yang menghubungkan sepasang simpul. Titik pada graf dinomori dengan huruf, angka, atau gabungan keduanya, contoh v, w,... atau 1, 2, 3,... atau 𝑣1 , 𝑣2 , ….. Sementara sisi yang menghubungkan titik u dan v dinyatakan dengan pasangan (u,v) atau dengan lambang 𝑒1 , 𝑒2 , …. Dengan demikian, jika e adalah sisi yang menghubungkan titik u dan v maka e dapat ditulis sebagai e = (u,v) (Munir, 2001).

𝑣1 𝑒1 𝑣2

𝑣4

(c) 𝐺1

𝑒3

𝑒4

𝑣2 𝑒5

𝑣3

𝑣1

𝑣1

𝑒2

𝑒1 𝑣4

𝑒6 𝑒7

𝑒3

𝑒4

𝑣2 𝑒5

𝑒2

𝑣4

𝑒6 𝑒7

𝑣3

𝑣3

(b) 𝐺2

(a) 𝐺3

Gambar 2.1 Tiga buah graf (a)graf sederhana, (b)graf ganda, (c)graf semu

9

𝑒8


Berikut ini beberapa istilah yang berkaitan dengan graf (Munir, 2001) : 1. Ketetanggan (Adjacent) Titik u bertetangga dengan titik v jika keduanya terhubung langsung, sehingga e = (u,v). Contoh : Pada 𝐺1 , titik 𝑣1 bertetangga dengan titik 𝑣2 dan 𝑣4 , tapi tidak bertetangga dengan 𝑣3 . 2. Bersisian (Incident) Pada sembarang sisi e = (u,v) dikatakan e bersisian dengan titik u dan e bersisian dengan titik v. Jika e = (u,u) maka e adalah gelang / kalang (looping) Contoh : Pada 𝐺2 , 𝑒1 bersisian dengan titik 𝑣1 dan 𝑣2 , tapi tidak bersisian dengan 𝑣4 . Pada 𝐺3 terdapat gelang 𝑒8 . 3. Derajat (Degree) Derajat titik v atau d(v) adalah banyak sisi yang bersisian dengan titik v. Jika d(𝑣𝑖 ) = 0 maka 𝑣𝑖 disebut titik terisolasi (isolated vertex). d(𝑣𝑖 ) = 1, maka 𝑣𝑖 disebut antingan (pendant vertex). Pada sembarang gelang e = (u,u), d(u) = 2. Contoh : Pada 𝐺3 , 𝑣1 bersisian dengan sisi 𝑒1 , 𝑒3 , dan 𝑒4 sehingga 𝑑 𝑣1 = 3 𝑣2 bersisian dengan sisi 𝑒1 , 𝑒2 , dan 𝑒5 sehingga 𝑑 𝑣2 = 3

Jika


𝑣3 bersisian dengan sisi 𝑒5 , 𝑒6 , dan 𝑒7 sehingga 𝑑 𝑣3 = 3 𝑣4 bersisian dengan sisi 𝑒2 , 𝑒3 , 𝑒4 , 𝑒6 , 𝑒7 , dan gelang 𝑒8 , maka 𝑑 𝑣4 = 7. 4. Graf Berbobot (Weighted Graph) Graf berbobot adalah graf yang elemennya diberikan label. Bobot pada setiap sisi dapat merepresentasikan jarak antara dua kota, waktu tempuh dua kota, dll. Contoh : a 12

10 8

e

b 11

15

9

d

c 14

Gambar 2.2 Graf berbobot

B. Jenis – jenis Graf Berdasarkan cara pengelompokkannya, graf dapat dibedakan dalam beberapa jenis, antara lain : 1. Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf dikelompokkan menjadi dua jenis (Munir, 2001) : a. Graf sederhana (simple graph) Graf sederhana adalah graf yang tidak mengandung gelang maupun sisi ganda. 𝐺1 pada gambar 2.1 (a) merupakan contoh dari graf sederhana.


b. Graf tak sederhana (unsimple graph) Graf tak sederhana adalah graf yang mengandung gelang atau sisi ganda. Graf tak sederhana dibedakan menjadi dua macam, yakni 1.) Graf ganda (multigraph) adalah graf yang mengandung sisi ganda. Graf 𝐺2 pada gambar 2.1(b) adalah contoh graf ganda 2.) Graf semu adalah (pseudograph) graf yang mengandung sisi ganda dan gelang. Graf 𝐺3 pada gambar 2.1(c) merupakan contoh graf semu. 2. Banyaknya titik atau sisi pada graf disebut kardinalitas graf dan dinyatakan dengan 𝑣 = 𝑉 dan 𝑒 = 𝐸 . Berdasarkan banyak titik pada suatu graf, maka graf dapat dikelompokkan menjadi dua macam, yakni : a. Graf berhingga (limited graph) Graf berhingga adalah graf yang banyaknya titik dan sisi n berhingga. Graf pada gambar 2.1 merupakan contoh graf berhingga. b. Graf tak berhingga Graf tak berhingga adalah graf yang banyak titik dan sisinya tidak terbatas.Contoh :

Gambar 2.3 Graf tak berhingga


3. Berdasarkan orientasi arah pada sisi, maka secara umum graf dikelompokkan menjadi dua jenis, yakni : a. Graf tak berarah (Undirect Graph) Graf tidak berarah adalah graf yang sisinya tidak mempunyai orientasi arah sehingga urutan pasangan titik yang dihubungkan tidak diperhatikan.

𝑣1 𝑒1

𝑒3

𝑒4

𝑣2 𝑒5

𝑣4

𝑒6

𝑒2

𝑒7 𝑣3

Gambar 2.4 Graf tak berarah

b. Graf berarah (Direct Graph) Graf berarah adalah graf yang setiap sisinya diberi orientasi arah, sehingga urutan pasangan titik diperhatikan. Pada graf berarah (𝑣𝑖 , 𝑣𝑗 ) berbeda dengan (𝑣𝑗 , 𝑣𝑖 ), sebab pada (𝑣𝑖 , 𝑣𝑗 ), 𝑣𝑖 adalah titik awal (initial vertex) dan 𝑣𝑗 merupakan titik terminal (terminal vertex). Sementara pada (𝑣𝑗 , 𝑣𝑖 ) berlaku sebaliknya. Sisi berarah pada graf berarah disebut busur (arc). 𝑣1

𝑣2

𝑣4

𝑣3

Gambar 2.5 Graf berarah


Selain pengelompokkan di atas, terdapat beberapa jenis graf sederhana khusus, antara lain : 1. Graf lengkap (Complete Graph) Graf lengkap adalah graf sederhana yang setiap titiknya mempunyai sisi ke semua titik yang lain. Graf lengkap dengan n buah simpul dilambangkan dengan 𝐾𝑛 . Graf lengkap 𝐾𝑛 mempunyai sisi sebanyak

𝐾1

𝑛(𝑛−1) 2

𝐾2

. Berikut contoh graf lengkap:

𝐾4

𝐾3

𝐾5

Gambar 2.6 Graf lengkap 2. Graf Sikel Graf sikel 𝐶𝑛 merupakan graf sederhana yang setiap titiknya berderajat dua. Graf sikel dengan n buah simpul dilambangkan dengan 𝐶𝑛 . Gambar berikut memperagakan graf sikel

𝐶4

𝐶3

𝐶5

Gambar 2.7 Graf sikel 3. Graf teratur (Regular Graph) Graf teratur adalah graf yang setiap titiknya memiliki derajat yang sama. Graf lengkap 𝐾𝑛 adalah graf teratur berderajat (n– 1). Graf


sikel 𝐶𝑛 adalah graf teratur berderajat 2. Berikut contoh graf teratur berderajat 3.

Gambar 2.8 Graf teratur Penelitian dan pengembangan pokok bahasan graf, memunculkan beberapa jenis graf baru. Graf tersebut diperoleh dengan melakukan operasi union, join, penghapusan sisi atau titik (edge or vertex deleting) pada suatu graf. Graf roda 𝑊1,𝑛 merupakan graf yang dibangun dengan melakukan operasi join pada graf lengkap 𝐾1 dengan graf sikel

𝐶𝑛 , dapat dinotasikan

𝑊1,𝑛 = 𝐾1 + 𝐶𝑛 (Buckley & Lewinter, 2002). Selanjutnya pada skripsi ini, graf 𝑊1,𝑛 akan disebut 𝑊𝑛 dengan n mengacu pada banyak titik pada graf sikel. Berikut beberapa contoh graf roda 𝑊𝑛 :

𝑾𝟑

𝑾𝟒

𝑾𝟓

Gambar 2.9 Graf roda Dengan memperhatikan cara terbentuknya, graf roda 𝑊𝑛 memiliki titik sebanyak (𝑛 + 1) dan sisi sebanyak 2𝑛. Titik 𝑣1 sampai 𝑣𝑛 merujuk titik pada sikel. Sisi pada sikel disebut rim dan mendapatkan label 𝑟1 sampai 𝑟𝑛 .


Setiap label rim berkorespondensi dengan label sisi 𝑒1 sampai 𝑒𝑛 . Sisi yang menghubungkan titik pusat dengan titik pada sikel disebut spoke. Label spoke dapat dinyatakan pula dengan 𝑠𝑖 = ℎ𝑢𝑏, 𝑣𝑖

untuk 1 ≤ 𝑖 ≤ 𝑛. Pola

penamaan secara grafis pada graf roda diperagakan pada gambar berikut (Baker dan Sawada, 2008):

Simpul (vertex)

Sisi (rim)

Jari-jari (spoke)

Titik tengah (hub)

Gambar 2.10 Penamaan elemen graf roda

𝒗𝟏 𝒓𝟏

𝒓𝒏

𝒗𝟐

𝒗𝒏 𝒔𝒏

𝒔𝟏

𝒓𝟐 𝒔𝟐

𝒓𝒏−𝟏 𝒗𝒏−𝟏 𝒓𝒏−𝟐

𝒔𝒏−𝟏 𝒔𝒏−𝟐

𝒔𝟑 𝒉

𝒗𝟑

𝒓𝟑 𝒗𝟒

𝒔𝟒

𝒗𝒏−𝟐

Gambar 2.11 Label elemen graf roda


C. Isomorfik Graf Dua buah graf yang sama namun secara geometri tampak berbeda disebut isomorfik. 3

d

c

v

w

a

b

x

y

4

1

2

(b)𝐺2

(a)𝐺1

(c)𝐺3

Gambar 2.12 Graf isomorfik dan tidak isomorfik

Graf 𝐺1 isomorfik dengan 𝐺2 . Titik 1, 2, 3, dan 4 pada 𝐺1 berkorespondensi dengan titik a, b, c, dan d pada 𝐺2 . Sisi (1,2), (2,3), (3,1), (3,4), dan (2,4) pada 𝐺1 berkorespondensi dengan (a,b), (b,c),(c,d),(a,d),(a,c), dan (b,d) pada 𝐺2 . Graf 𝐺1 dan 𝐺2 tidak isomorfik dengan 𝐺3 . (Munir, 2001).

Graf G dan graf H dikatakan isomorfik, dinotasikan 𝐺 ≅ 𝐻, jika mereka dapat dilabeli sedemikian sehingga u dan v bertetangga pada graf G, jika dan hanya jika titik yang berkorespondensi juga bertetangga pada graf H. Bila pernyataan tersebut dinyatakan dengan konsep fungsi maka menjadi graf G dan graf H dikatakan isomorfik jika terdapat fungsi bijektif 𝑓: 𝑉(𝐺) → 𝑉(𝐻) sedemikian sehingga setiap pasangan titik u dan v yang bertetangga dalam G jika dan hanya jika f(u) dan f(v) juga bertetangga dalam H (Buckley &


Lewinter, 2002). Dengan kata lain, bila dua graf dikatakan isomorfik, maka setiap titiknya memiliki derajat yang sama. Pada pelabelan, graf G dan graf H disebut isomorfik jika terdapat fungsi bijektif f dari V(G) ke V(H) dimana a dan b adalah titik yang bertetangga pada G, jika dan hanya jika f(a) dan f(b) adalah titik bertetangga pada H. 𝟖

𝟏𝟎

𝟏𝟏

𝟓

𝟒

𝟐

𝟕

𝟏𝟐

𝟏𝟎 𝟏𝟑

𝟕 𝟒

𝟏𝟏 𝟏

𝟏

𝟖

𝟗

𝟑

𝟏𝟑

𝟔

𝟗

(a)

𝟑 𝟔

𝟐 𝟓

𝟏𝟐

(b)

Gambar 2.13 Contoh pelabelan 𝑊4 dengan k = 26 Graf A dan B pada gambar 2.12 merupakan contoh dua buah graf yang isomorfik. Pada graf A dan B, Titik dengan label 13 bertetangga dengan titik berlabel 1, 2, 3, dan 7 Titik dengan label 10 bertetangga dengan titik berlabel 11, 1, dan 4 Titik dengan label 8 bertetangga dengan titik berlabel 11, 2, dan 5 Titik dengan label 12 bertetangga dengan titik berlabel 5, 3, dan 6 Titik dengan label 9 bertetangga dengan titik berlabel 6, 7, dan 4. Graf A dan B merupakan graf yang sama baik secara geometri maupun pelabelan.


D. Pelabelan Graf Pelabelan graf merupakan fungsi bijektif yang memetakan setiap elemen graf ke bilangan bulat positif. Menurut himpunan asalnya, terdapat tiga jenis pelabelan yaitu (Wallis, 2001): 1. Pelabelan titik (vertex labelings) Pelabelan titik adalah pelabelan yang himpunan asalnya titik. Berikut contoh pelabelan titik. 2

3

5 1

4

Gambar 2.14 Pelabelan titik

2. Pelabelan sisi (edge labelings) Pelabelan sisi adalah yang himpunan asalnya sisi.

4

1 8

5

7

6

2

3

4

Gambar 2.15 Pelabelan sisi


3. Pelabelan total (total labelings) Pelabelan total adalah pelabelan yang domainnya titik dan sisi 10 7

8

4

2

12

3

11 5

6 9

13

1

Gambar 2.15 Pelabelan total

Bobot elemen graf adalah hasil penjumlahan label yang dievaluasi dengan label elemen yang bersisian. Berikut ini contoh bobot titik x pada pelabelan f 𝑤𝑡 𝑥 = 𝑓 𝑥 +

𝑓 𝑥𝑦

Sementara, bobot sisi xy dinyatakan 𝑤𝑡 𝑥𝑦 = 𝑓 𝑥 + 𝑓 𝑦 + 𝑓(𝑥𝑦) Menurut bobot elemen graf yang dievaluasi, terdapat dua jenis pelabelan yaitu 1. Pelabelan ajaib (magic labelings) Pelabelan ajaib adalah suatu pelabelan dimana bobot setiap elemen yang dievaluasi sama / konstan. 2. Pelabelan tak-ajaib (antimagic labelings). Pelabelan tak-ajaib adalah suatu pelabelan bobot elemen yang dievaluasi membentuk suatu barisan bilangan aritmetika.


Berdasarkan himpunan asal, bobot, dan elemen graf yang dievalusi terdapat jenis pelabelan berikut : 1. Pelabelan total ajaib titik atau vertex-magic total labelings (VMTL) Pelabelan total ajaib titik merupakan pemetaan bijektif 𝑓 dari 𝑉(𝐺) ∪ 𝐸(𝐺) ke bilangan bulat positif

1,2,3, … , 𝑣 + 𝑒

dengan

𝑣 = 𝑉(𝐺) dan 𝑒 = 𝐸(𝐺) sedemikian sehingga untuk setiap 𝑥 ∈ 𝑉(𝐺) berlaku 𝑓 𝑥 +

𝑓 𝑥𝑦 = 𝑘 untuk 𝑦 ∈ 𝑉(𝐺) yang berdekatan dengan

𝑥. Bilangan 𝑘 disebut konstanta ajaib (Wallis, 2001). Pada pelabelan total ajaib titik, setiap elemen (sisi dan titik) dilabeli dengan bilangan bulat 1,2,3, … sampai sejumlah titik dan sisi dari graf yang bersangkutan. Label-label ditempatkan sedemikian sehingga setiap titik pada graf tersebut memiliki bobot yang sama. Bobot titik diperoleh dengan menambahkan label titik yang ditunjuk dengan semua label sisi yang bersisian.

𝟏𝟑

𝟑

𝟖 𝟐 𝟏𝟎 𝟏𝟐

𝟕 𝟗 𝟒 𝟔

𝟏 𝟓

𝟏𝟏

Gambar 2.16 Pelabelan total ajaib titik pada 𝑊4

Graf roda 𝑊4 pada gambar 2.16 memiliki konstanta ajaib 26. Titik dengan label 13 bersisian dengan sisi-sisi yang memiliki label 3, 2, dan 8, sehingga bobot titiknya adalah 13 + 8 + 2 + 3 = 26.


Titik dengan label 12 memiliki bobot 12 + 8 + 1 + 5 = 26. Titik dengan label 11 memiliki bobot 11 + 5 + 4 + 6 = 26. Titik dengan label 7 memiliki bobot 7 + 6 + 10 + 3 = 26 Titik dengan label 9 memiliki bobot 9 + 2 + 1 + 4 + 10 = 26. 2. Pelabelan total ajaib sisi atau edge-magic total labelings (EMTL) Pelabelan total ajaib sisi merupakan pemetaan bijektif 𝑓 dari 𝑉(𝐺) ∪ 𝐸(𝐺) ke bilangan bulat positif

1,2,3, … , 𝑣 + 𝑒

𝑣 = 𝑉(𝐺) dan 𝑒 = 𝐸(𝐺) sedemikian sehingga 𝑥𝑦 ∈ 𝑉(𝐺) berlaku

dengan

untuk setiap sisi

𝑓 𝑥 + 𝑓 𝑥𝑦 + 𝑓 𝑦 = ℎ untuk setiap konstanta

ajaib ℎ (Wallis, 2001). Pada pelabelan total ajaib sisi, setiap elemen (sisi dan titik) dilabeli dengan bilangan bulat 1,2,3, … sampai sejumlah titik dan sisi dari graf. Label-label ditempatkan sedemikian sehingga setiap sisi pada graf tersebut memiliki bobot yang sama. Bobot sisi diperoleh dengan menjumlahkan label sisi yang dievaluasi dengan semua label titik yang bertetangga dengan sisi tersebut. 19

7

6

1

10

8 14

17

18

3 12

2

4 13

9 15

16

11

5

Gambar 2.16 Pelabelan total ajaib sisi pada 𝑊6


Graf roda 𝑊6 pada gambar 2.16 memiliki konstanta ajaib 32. Setiap

sisi pada 𝑊6 memiliki bobot yang sama. Sisi dengan label 1

bertetangga dengan titik berlabel 12 dan 19, sehingga bobot sisinya adalah 1 + 12 + 19 = 32. Sisi berlabel 14 memiliki bobot 14 + 12 + 6 = 32 Sisi berlabel 2 memiliki bobot 2 + 12 + 18 = 32 Sisi berlabel 15 memiliki bobot 15 + 12 + 5 = 32 Sisi berlabel 4 memiliki bobot 4 + 12 + 16 = 32 Sisi berlabel 17 memiliki bobot 17 + 12 + 3 = 32 Sisi berlabel 7 memiliki bobot 7 + 19 + 6 = 32 Sisi berlabel 8 memiliki bobot 8 + 6 + 18 = 32 Sisi berlabel 9 memiliki bobot 9 + 18 + 5 = 32 Sisi berlabel 11 memiliki bobot 11 + 5 + 16 = 32 Sisi berlabel 13 memiliki bobot 13 + 16 + 3 = 32 Sisi berlabel 10 memiliki bobot 10 + 3 + 19 = 32

E. Dualitas Graf Pada suatu pelabelan graf teratur dapat dibentuk pelabelan baru dari pelabelan yang ada. Suatu pelabelan f dual dengan pelabelan f’ didefiniskan sebagai 𝑓 ′ 𝑥𝑖 = 𝑣 + 𝑒 + 1 − 𝑓 𝑥𝑖

untuk sembarang titik 𝑥𝑖

𝑓 ′ 𝑥𝑦 = 𝑣 + 𝑒 + 1 − 𝑓 𝑥𝑦 untuk sembarang sisi 𝑥𝑦


Dengan demikian pelabelan f’ merupakan pelabelan bijektif dari 𝑉 ∪ 𝐸 ke bilangan positif 1,2,3, … , 𝑣 + 𝑒 dan pelabelan f’ disebut dual dari pelabelan f. Pada pelabelan f, bobot elemen yang dievalusi dinyatakan sebagai konstanta ajaib k. Pada pelabelan f’ , bobot elemen tang dievalusi diperoleh dengan 𝑤𝑡 ′ 𝑥 = 𝑓 ′ 𝑥 + =

𝑓′(𝑥𝑦)

𝑣+𝑒+1 −𝑓 𝑥

+

𝑣 + 𝑒 + 1 − 𝑓(𝑥𝑦)

= 𝑟+1 𝑣+𝑒+1 −𝑘 dengan r adalah derajat titik x. Graf lengkap 𝐾𝑛 merupakan graf teratur dengan berderajat (n – 1). Berikut contoh pelabelan pada 𝐾4 dan dual pelabelannya. 𝟗

𝟓

𝟐

𝟒

𝟐 𝟏𝟎

𝟏

𝟕

𝟗

𝟔

𝟏

𝟏𝟎

𝟒

𝟕 𝟑

𝟖

𝟖

𝟑

𝟔

𝟓

(a)

(b)

Gambar 2.17 Dual pelabelan pada 𝐾4

Graf pada gambar 2.17 (a) dual dengan graf pada gambar 2.17 (b). Graf lengkap 𝐾4 memiliki 𝑣 = 4 dan 𝑒 = 6, sehingga 𝑣 + 𝑒 = 10. Label–label titik graf pada gambar 2.17 (b) diperoleh dari : 2 = 10 + 1 − 9


8 = 10 + 1 − 3 3 = 10 + 1 − 8 1 = 10 + 1 − 10 Label–label sisi graf pada gambar 2.17 (b) diperoleh dari : 7 = 10 + 1 − 4 5 = 10 + 1 − 6 6 = 10 + 1 − 5 9 = 10 + 1 − 2 4 = 10 + 1 − 7 10 = 10 + 1 − 1 Graf pada gambar 2.17 (a) memiliki konstanta ajaib 20, konstanta ajaib untuk graf pada gambar 2.17(b) adalah 𝑘 ′ = 3 + 1 10 + 1 − 20 𝑘 ′ = 24

F. Kerangka Berpikir Graf roda merupakan graf sederhana yang dibangun dengan menambahkan satu titik di bagian tengah sikel dan menghubungkan titik tersebut dengan semua titik pada sikel. Graf roda memiliki n + 1 titik dan 2n sisi. Pelabelan merupakan fungsi bijektif yang memasangkan setiap elemen graf dengan bilangan bulat positif. Bila graf roda dikenakan pelabelan maka banyaknya label atau bilangan bulat positif yang hadir sebanyak 3n + 1. Pada pelabelan total ajaib titik, setiap label diletakkan sedemikian hingga bobot setiap titik


pada graf roda tersebut sama. Ada banyak variasi atau cara meletakkan label agar memperoleh bobot titik yang diingikan. Namun, pelabelan yang dilakukan pada graf roda tidak boleh menghasilkan graf roda yang isomorfik baik yang diakibatkan rotasi maupun refleksi. Sebab, pelabelan yang bersifat isomorfik hanya menunjuk satu cara pelabelan meskipun letak label nampak berbeda.


BAB III PELABELAN TOTAL AJAIB TITIK PADA GRAF RODA

A. Perhitungan Dasar Pelabelan Total Ajaib Titik Suatu

pemetaan

bijektif

𝑉∪𝐸

dari

ke

bilangan

bulat

positif

1,2,3, … , 𝑣 + 𝑒 disebut pelabelan total ajaib titik jika ada konstata k sehingga untuk setiap titik berlaku 𝑓 𝑥 +

𝑓 𝑥𝑦 = 𝑘

(1)

dimana jumlahan label tersebut merupakan hasil penjumlahan label titik dengan semua label sisi dimana y bertetangga dengan x. Selanjutnya jumlahan label pada titik x merupakan bobot titik, sehingga dapat ditulis wt(x) = k untuk semua x. Selanjutnya, kata pelabelan pada skripsi ini merujuk pada pelabelan total ajaib titik. Tidak semua graf memiliki pelabelan, contohnya graf 𝐾2 dengan yang hanya memiliki satu sisi xy, jika 𝑓(𝑥) ≠ 𝑓(𝑦), maka 𝑓 𝑥 + 𝑓 𝑥𝑦 ≠ 𝑓 𝑦 + 𝑓(𝑥𝑦), sehingga tidak ada pelabelan yang mungkin (MacDougall, dkk, 2001). MacDougall, dkk (2001) meneliti bahwa graf roda memiliki pelabelan. Selanjutnya akan dijelaskan pelabelan yang ada pada graf roda. Pada pelabelan ajaib, nilai konstanta ajaib k akan ditentukan terlebih dahulu. Melalui perhitungan dasar akan diperoleh batas nilai k, sehingga nilai k untuk pelabelan tertentu dapat ditentukan. Andaikan M = v + e dan 𝑆𝑣 adalah jumlah semua label titik serta 𝑆𝑒 adalah jumlah semua label sisi. Label adalah bilangan bulat 1,2,3, … , 𝑀, sehingga jumlah semua label adalah

27


𝑀

𝑆𝑣 + 𝑆𝑒 =

𝑖= 1

Untuk setiap titik 𝑥𝑖 berlaku 𝑓 𝑥𝑖 +

28

𝑀+1 𝑀 2

𝑓 𝑥𝑖 𝑦 = 𝑘. Dengan menjumlahkan

label titik 𝑥𝑖 sebanyak 𝑣 dan ditambah dua kali jumlah semua label sisi, maka diperoleh 𝑆𝑣 + 2𝑆𝑒 = 𝑣𝑘

(2)

Dengan mengombinasikan (1) dan (2) maka diperoleh

(𝑆𝑣 + 𝑆𝑒 ) + 𝑆𝑒 = 𝑣𝑘 1 + 2 + ⋯ + 𝑀 + 𝑆𝑒 = 𝑣𝑘 𝑀 𝑀+1 2

+ 𝑆𝑒 = 𝑣𝑘

(3)

Berdasarkan persamaan (2), label sisi memberi sumbangan dua kali pada total konstanta ajaib, maka label sisi perlu diketahui lebih dahulu. Sementara label titik dapat ditentukan kemudian dengan mengurangi konstanta ajaib dengan label sisi yang hadir. Namun, hal ini tidak berlaku sebaliknya. Selanjutnya, untuk kepentingan pelabelan, batas 𝑆𝑒 perlu ditentukan. Batas bawah diperoleh dengan memberikan label terkecil sebanyak e sisi. Sementara itu batas atas nilai 𝑆𝑒 diperoleh dengan melabeli e sisi dengan label terbesar.

𝑒 𝑖=1 𝑖

≤ 𝑆𝑒 ≤

1 + 2 + ⋯ + 𝑒 ≤ 𝑆𝑒 ≤ 𝑒 𝑒+1 2

≤ 𝑆𝑒 ≤

𝑒+𝑣 𝑖=𝑣+1 𝑖

𝑣 +1 + 𝑣 +2 +⋯+ 𝑣 +𝑒 𝑣+𝑒 𝑣+𝑒+1 2

−

𝑣 𝑣+1 2

(4)


29

Batas nilai 𝑆𝑒 yang diperoleh dapat dimanfaatkan untuk memperoleh batas nilai konstanta ajaib. Dengan menggabungkan pertidaksamaan (3) dan (4) diperoleh

𝑒 𝑒+1 2

𝑒 𝑒+1 2

+

𝑣+𝑒 𝑣+𝑒+1

+

≤ 𝑣𝑘 ≤

2



≤ 𝑣𝑘 ≤ 2

2

2

−

𝑣 𝑣+1


−

2


+

2

2

𝑣 𝑣+1

(5)

2

Pertidaksamaan (5) menyatakan interval nilai k yang memenuhi suatu pelabelan total ajaib titik pada suatu graf. Secara keseluruhan, persamaan (1) menyatakan ketika nilai k diberikan dan label sisi telah diketahui, maka label titik dapat ditentukan. Jadi, pelabelan secara lengkap digambarkan oleh label sisi. Akibatnya, untuk konstanta ajaib yang sudah tertentu, sisi suatu graf dapat dilabeli dengan cara yang berbeda, meskipun label titiknya tidak diganti.

𝟏𝟏

𝟏𝟏

𝟏𝟎

𝟕

𝟖

𝟕 𝟒

𝟔 𝟗

𝟏𝟐 𝟑

𝟐 𝟏 𝟖

𝟏

𝟔 𝟏𝟑

𝟓

𝟑

𝟐

𝟗 𝟏𝟑

𝟒

𝟏𝟐 𝟏𝟎

𝟓

Gambar 3.1 Pelabelan total ajaib titik pada 𝑊4


30

Pelabelan total ajaib titik pada 𝑊4 yang terdapat pada gambar 3.2 merupakan contoh pelabelan total ajaib titik dengan nilai konstanta ajaib yang sama yakni 32 dan label titik yang sama, namun label sisinya berbeda. Hal ini menunjukkan bahwa label sisi memiliki peran penting dalam penggambaran suatu pelabelan, sehingga dalam suatu pelabelan total ajaib titik, label sisi perlu ditentukan terlebih dahulu.

B. Interval Nilai Konstanta Ajaib Pelabelan Total Ajaib Titik pada Graf Roda Graf roda 𝑊𝑛 merupakan graf sederhana yang diperoleh dengan cara menghubungkan semua titik pada graf sikel 𝐶𝑛 ke titik baru yang disebut titik pusat (hub). Nilai n menyatakan banyaknya titik pada graf sikel𝐶𝑛 . Graf roda 𝑊𝑛 memiliki 𝑛 + 1 titik dan 2𝑛 sisi. Titik 𝑣𝑖 sampai 𝑣𝑛 terletak pada sikel, sisi 𝑟𝑖 samapi 𝑟𝑛 berkorespondensi dengan sisi 𝑒𝑖 sampai 𝑒𝑛 . Jari – jari (spoke) menghubungkan titik pusat (hub) dengan setiap titik pada sikel dan terhitung sebagai sisi. Berdasarkan pertidaksamaan (5) diperoleh interval nilai konstanta k untuk graf roda sebagai berikut :

2𝑛 2𝑛+1 2

+

3𝑛 +1 3𝑛 +2 2 13𝑛 2 +11𝑛+2 2

≤ (𝑛 + 1)𝑘 ≤ 2 ≤ 𝑛+1 𝑘 ≤

13𝑛 2 +11𝑛+2 2 𝑛+1

≤𝑘≤

3𝑛 +1 3𝑛+2 2

−

(𝑛+1) 𝑛 +2 2

17𝑛 2 +15𝑛+2

17𝑛 2 +15𝑛+2 2 𝑛+1

2

(6)


31

Dengan menyubstitusikan nilai n pada pertidaksamaan (6) maka diperoleh kemungkinan nilai k sebagai berikut :

Tabel 3.1 Kemungkinan Nilai Konstanta Ajaib k n ganjil

Batas nilai k

Kemungkinan nilai k

3

19 ≤ 𝑘 ≤ 25

5

31,83 ≤ 𝑘 ≤ 41,83

7

9

44,75 ≤ 𝑘 ≤ 58,75 57,7 ≤ 𝑘 ≤ 75,7

11

70,67 ≤ 𝑘 ≤ 92,67

...

...

n genap

Batas nilai k

19,20,21,22,23, 24,25

4

25,4 ≤ 𝑘 ≤ 33,4

32,33,34,35,36, 37,38,39,40,41

6

38,28 ≤ 𝑘 ≤ 50.28

45,46,47,48,49, 50,51,52,53,54, 55,56,57,58

8

58,59,60,61,62, 63,64,65,66,67, 68,69,70,71,72, 73,74,75 71,72,73,74,75, 76,77,78,79,80, 81,82,83,84,85, 86,87,89,90,91, 92 ...

10

12

...

51,22 ≤ 𝑘 ≤ 67,22

64,18 ≤ 𝑘 ≤ 84,18

77,15 ≤ 𝑘 ≤ 101,53

...

Kemungkinan nilai k 26,27,28,29,30, 31,32,33 39,40,41,42,43, 44,45,46,47,48, 49,50 52,53,54,55,56, 57,58,59,60,61, 62,63,64,65,66, 67 65,66,67,68,69, 70,71,72,73,74, 75,76,77,78,79, 80,81,82,83,84 78,79,80,81,82, 83,84,85,86,87, 88,89,90,91,92, 93,94,95,96,97, 98,99,100 ...

Perhitungan dasar memberikan batas nilai k secara umum untuk semua jenis graf. Batas nilai konstanta k untuk graf roda dinyatakan oleh pertidaksamaan (6). Sementara kemungkinan nilai konstanta ajaib k pada setiap nilai n untuk graf roda dinyatakan pada tabel 3.1. Dalam prakteknya, tidak semua graf roda dapat dilabeli. Ada beberapa graf roda dengan n tertentu atau nilai k tertentu tidak memiliki pelabelan. MacDougall (2002) menyatakan interval dari nilai konstanta k yang ditunjukkan pertidaksamaan (6) diperoleh dan belum mempertimbangkan stuktur khusus pada graf yang bersangkutan. Dengan


32

demikian, perlu ada batasan nilai k yang telah disesuaikan dengan struktur graf yang bersangkutan, yakni struktur graf roda.

C. Pelabelan Graf Roda pada 𝒏 𝐁𝐞𝐬𝐚𝐫 ( 𝒏 > 11 ) dan 𝟑 ≤ 𝒏 ≤ 𝟏𝟏 Interval nilai kontanta ajaib k yang diperoleh dari perhitungan dasar menunjukkan ada pelabelan pada graf roda. Perhitungan dasar memberikan batas nilai konstanta k yang mungkin pada suatu graf secara umum. Sementara, setiap kelas graf memiliki struktur yang berbeda-beda, sehingga kadang ditemui beberapa permasalahan seperti pada nilai n tertentu, graf roda tidak dapat dilabeli, ada nilai konstanta ajaib k yang tidak memiliki pelabelan, dll. Dengan demikian, perlu ada perhitungan khusus untuk menentukan batas nilai

konstanta ajaib yang memepertimbangkan struktur

graf yang

bersangkutan. Graf roda memiliki struktur yang berbeda dengan kelas graf yang lain. Berdasarkan cara terbentuknya, setiap titik pada sikelnya berderajat tiga dan titik pusat berderajat n, menyesuaikan banyaknya nilai n. Setiap titik pada bagian sikel bersisian dengan tiga sisi yakni dua sisi di samping kanan dan kirinya serta satu jari-jari. Titik pusat graf roda memilki derajat n, sesuai dengan banyaknya titik pada sikel yang terhubung dengannya. Dengan kata lain, titik pusat memiliki derajat yang paling tinggi atau sama dengan titik pada sikel saat n = 3. Derajat titik pusat menentukan suatu graf roda dapat dilabeli atau tidak. Semakin besar derajatnya, makin besar juga nilai konstanta ajaibnya.


33

Sementara, label yang tersedia terbatas sehingga dimungkinkan pelabelan untuk n besar terbatas atau tidak ada pelabelan (MacDougal, 2002). 1. Pelabelan Graf roda dengan n besar (n > 11) Graf roda 𝑊𝑛 memiliki titik sebanyak (n + 1) dan sisi sebanyak 2n, sehingga M = v + e = 3n + 1. Misal c adalah titik pusat dan 𝑥1 , 𝑥2 , … , 𝑥𝑛 adalah titik pada sikel, sehingga 𝑘 ≥ 𝑤𝑡 ℎ = 1 + 2 + ⋯+ 𝑛 + 1 =

𝑛 +2 (𝑛+1)

(7)

2

Pertidaksamaan (7) menyatakan batas bawah untuk bobot titik pusat dengan asumsi titik pusat memiliki derajat yang besar. Selanjutnya akan dihitung jumlah bobot titik pada sikel. Batas atas untuk jumlah bobot ini diperoleh dengan melabeli n sisi pada sikel dengan label besar. Label ini dihitung dua kali. Selanjutnya 2n label besar digunakan melabeli titik dan jari-jari, sehingga diperoleh 3𝑛+1

𝑤𝑡 𝑥1 + 𝑤𝑡 𝑥2 + ⋯ + 𝑤𝑡 𝑥𝑛 ≤

3𝑛+1

𝑖+ 2

=2

𝑖 2𝑛+2

3𝑛 +1 (3𝑛+2) 2

−

2𝑛 +1 (2𝑛+2) 2

−1

= 𝑛(7𝑛 + 6) Dengan n titik pada sikel , maka diperoleh 𝑘 ≤ 7𝑛 + 6 Nilai batas bawah lebih kecil dari batas atas, sehingga dapat ditulis

(8)


𝑛 +2 𝑛 +1 2

< 7𝑛 + 6

34

(9)

Dengan menyederhanakan pertidaksamaan (9) diperoleh 𝑛− Saat nilai n > 11

10 𝑛

< 11

(10)

pertidaksamaan (10) menjadi tidak benar. Dengan

demikian, untuk n > 11 tidak ada pelabelan yang mungkin pada graf roda.

2. Pelabelan Graf roda 𝑊𝑛 dengan 3 ≤ 𝑛 ≤ 11 Graf roda 𝑊𝑛 merupakan hasil operasi join antara graf lengkap 𝐾1 dan graf sikel 𝐶𝑛 . Nilai n terkecil untuk graf sikel adalah 3 sehingga nilai n terkecil untuk 𝑊𝑛 adalah 3. Pada pembahasan sebelumnya dinyatakan bahwa graf roda tidak dapat dilabeli bila 𝑛 > 11. Jadi, graf roda dapat dilabeli jika 3 ≤ 𝑛 ≤ 11 (Gallian, 2014). Proses pelabelan yang dilakukan menemukan bahwa 𝑊3 , 𝑊4 , dan 𝑊5 dapat dilabeli dengan beberapa cara. a. Pelabelan pada 𝑊3 Graf roda 𝑊3 isomorfik dengan graf lengkap 𝐾4 dan graf lengkap 𝐾4 merupakan graf teratur, maka 𝑊3 merupakan graf teratur. Dualitas pada graf teratur berlaku pada 𝑊3 . Graf roda 𝑊3 isomorfik dengan graf lengkap 𝐾4 . Graf lengkap 𝐾4 merupakan graf teratur, maka graf roda 𝑊3 merupakan graf teratur. sehingga dualitas juga berlaku pada 𝑊3 .


35

Berdasarkan pertidaksamaan (7), (8), dan (9) diperoleh nilai konstanta k untuk 𝑊3 adalah 19 ≤ 𝑘 ≤ 25. Dual nilai k pada 𝑊3 yakni 20 dual 24 dan 21 dual 23. 𝑊3 tidak ada pelabelan untuk nilai k = 19, 22, 25. Berikut ini contoh pelabelan dengan nilai konstanta 1) k = 20 𝟗

𝟒

𝟓

𝟒

𝟐

𝟖

𝟏𝟎

𝟏

𝟏𝟎

𝟏

𝟔

𝟕 𝟑

𝟖

𝟓

𝟑

𝟕

𝟗

𝟔

𝟐

Gambar 3.2 Pelabelan pada 𝑊3 dengan k =20

2) k = 21

𝟕

𝟗

𝟏

𝟑

𝟖

𝟑

𝟗

𝟐 𝟓

𝟔 𝟏𝟎

𝟏𝟎 𝟒

𝟒 𝟓

𝟐 𝟕

𝟏

𝟖 𝟔


𝟓

𝟗

𝟐

𝟕

36

𝟔

𝟑

𝟗

𝟏 𝟖

𝟓

𝟐

𝟒 𝟏𝟎

𝟏𝟎 𝟔

𝟏

𝟕

𝟒

𝟖

𝟑

𝟕

𝟑

𝟏𝟎

𝟏 𝟔

𝟓 𝟗 𝟐

𝟖

𝟒

Gambar 3.3 Pelabelan pada 𝑊3 dengan k = 21

3) k = 23 𝟗

𝟖

𝟒

𝟏𝟎

𝟑

𝟐

𝟏

𝟓

𝟏

𝟔

𝟕

𝟕 𝟔

𝟗 𝟒

𝟖

𝟗

𝟏𝟎

𝟑 𝟓


37

𝟓

𝟐

𝟗

𝟒

𝟓

𝟖

𝟐

𝟏𝟎 𝟑

𝟔

𝟗

𝟕 𝟏

𝟏 𝟓

𝟏𝟎

𝟒

𝟕

𝟑

𝟖

𝟒

𝟖

𝟏

𝟏𝟎 𝟓

𝟔 𝟐 𝟗

𝟑

𝟒

Gambar 3.4 Pelabelan pada 𝑊3 dengan k = 23 4) k = 24

𝟕

𝟐

𝟗

𝟔

𝟕

𝟖 𝟏𝟎

𝟏𝟎 𝟏

𝟏

𝟒 𝟑

𝟔

𝟑

𝟓 𝟖

𝟓

𝟐

𝟒 𝟗

Gambar 3.5 Pelabelan pada 𝑊3 dengan k = 24


38

Banyaknya pelabelan untuk nilai konstanta k pada 𝑊3 (𝑁3 (𝑘)) ditunjukkan oleh tabel berikut ini

Tabel 3.2 Banyaknya pelabelan pada 𝑊3 K

19

20

21

22

23

24

25

𝑁3 (𝑘)

-

2

5

-

5

2

-

Graf roda 𝑊3 tidak ada pelabelan untuk nilai k = 19, 22, dan 25. Banyaknya pelabelan pada k = 20 sama dengan banyaknya pelabelan pada k = 24. Demikian juga pada k = 21 dengan k = 23. Dualitas pada 𝑊3 Nilai konstanta yang baru 𝑘 ′ = 𝑟 + 1 𝑣 + 𝑒 + 1 − 𝑘, dengan r menyatakan derajat titik pada graf. Label-label sisi dan titik diperoleh dengan 𝑓 ′ 𝑥𝑖 = 𝑣 + 𝑒 + 1 − 𝑓 𝑥𝑖

untuk sembarang titik 𝑥𝑖

𝑓 ′ 𝑥𝑦 = 𝑣 + 𝑒 + 1 − 𝑓 𝑥𝑦 untuk sembarang sisi 𝑥𝑦 maka Untuk k = 20 diperoleh 𝑘 ′ = 3 + 1 4 + 6 + 1 − 20 = 24, dengan label-label jari-jari sebagai berikut 𝑓′ 2 = 4 + 6 + 1 − 2 = 9 𝑓′ 7 = 4 + 6 + 1 − 7 = 4 𝑓 ′ 1 = 4 + 6 + 1 − 1 = 10


39

Label – label sisi pada sikel : 𝑓′ 4 = 4 + 6 + 1 − 4 = 7 𝑓′ 6 = 4 + 6 + 1 − 6 = 5 𝑓′ 5 = 4 + 6 + 1 − 5 = 6

Label –label titik : 𝑓′ 9 = 4 + 6 + 1 − 9 = 2 𝑓′ 4 = 4 + 6 + 1 − 4 = 8 𝑓′ 8 = 4 + 6 + 1 − 8 = 3 𝑓 ′ 10 = 4 + 6 + 1 − 10 = 1

Pada 𝑊3 , k = 19 berkorespondensi dengan k = 25, k = 22 berkorespondensi dengan k = 26, namun k = 26 tidak terdapat dalam rentang nilai k pada 𝑊3 .

b. Pelabelan pada graf roda 𝑊𝑛 dengan 4 ≤ 𝑛 ≤ 11 Berbeda dengan 𝑊3 , graf roda 𝑊𝑛 dengan 4 ≤ 𝑛 ≤ 11 bukan graf teratur, sehingga dualitas tidak berlaku. Pelabelan graf roda dapat dilakukan dengan meletakkan label sedemikian sehingga setiap titik memiliki bobot yang sama. Jari-jari pada graf roda 𝑊𝑛 dilabeli dengan label yang tersedia. Label yang sudah digunakan tidak dapat digunakan lagi, sebab pelabelan merupakan fungsi bijektif. Selanjutnya, sisi dan titik pada sikel dilabeli dengan label yang tersisa.


40

Setiap elemen graf roda dapat dilabeli dengan label yang hadir, sehingga ada banyak cara melabeli elemen graf roda. Pelabelan pada graf roda 𝑊𝑛 untuk 4 ≤ 𝑛 ≤ 11 dilakukan dengan membangun suatu algoritma pelabelan. Algoritma yang dibangun akan disumulasikan dalam suatu program pada Matlab. Berikut ini contoh pelabelan graf roda pada k tertentu.

𝟏𝟗

𝟏𝟖

𝟔

𝟏𝟑

𝟏𝟏

𝟏𝟕 𝟗

𝟐

𝟕 𝟏

𝟏𝟖 𝟐𝟐

𝟏𝟓

𝟕

𝟒

𝟔 𝟏𝟒

𝟏𝟓

𝟏𝟔

𝟒

𝟏𝟕

𝟏𝟎

𝟏𝟗

𝟏𝟔

𝟐𝟏

𝟓

𝟑

𝟏𝟎

𝟐

𝟏

𝟖

𝟖

𝟓

𝟗

𝟏𝟏

𝟏𝟒

𝟏𝟐

𝟑

𝟏𝟐 𝟐𝟎 𝟏𝟑

𝟏𝟑

(a)

(b) 𝟏𝟐

𝟐𝟐

𝟐𝟒

𝟗 𝟏𝟗

𝟏𝟕

𝟏𝟏

𝟖

𝟓 𝟏𝟒

𝟒

𝟔

𝟐

𝟐𝟏

𝟐𝟓

𝟏 𝟐𝟑

𝟑 𝟕

𝟏𝟎 𝟐𝟎

𝟏𝟖 𝟏𝟔

(c)

𝟏𝟓

Gambar 3.6 Pelabelan pada 𝑊6 , 𝑊7 , dan 𝑊8


41

Gambar 3.6 menunjukkan contoh pelabelan pada 𝑊6 , 𝑊7 , dan 𝑊8 dengan konstanta ajaib secara berturut – turut 39, 48, dan 58. (a) Pelabelan pada 𝑊6 dengan k = 39 𝑤𝑡 17 = 1 + 7 + 14 + 17 = 39 𝑤𝑡 19 = 2 + 11 + 7 + 19 = 39 𝑤𝑡 13 = 3 + 12 + 11 + 13 = 39 𝑤𝑡 15 = 4 + 8 + 12 + 15 = 39 𝑤𝑡 16 = 5 + 10 + 8 + 16 = 39 𝑤𝑡 9 = 6 + 14 + 10 + 9 = 39 𝑤𝑡 18 = 1 + 2 + 3 + 4 + 5 + 6 + 18 = 39

(b) Pelabelan pada 𝑊7 dengan k = 48 𝑤𝑡 22 = 4 + 14 + 8 + 22 = 48 𝑤𝑡 17 = 11 + 6 + 14 + 17 = 48 𝑤𝑡 18 = 15 + 9 + 6 + 18 = 48 𝑤𝑡 16 = 2 + 21 + 9 + 16 = 48 𝑤𝑡 10 = 5 + 12 + 21 + 12 = 48 𝑤𝑡 13 = 3 + 20 + 12 + 13 = 48 𝑤𝑡 19 = 1 + 8 + 20 + 19 = 48 𝑤𝑡 7 = 4 + 11 + 15 + 2 + 5 + 3 + 1 = 48

(c) Pelabelan pada 𝑊8 dengan k = 58 𝑤𝑡 9 = 19 + 22 + 8 + 9 = 58


42

𝑤𝑡 13 = 11 + 12 + 22 + 13 = 58 𝑤𝑡 24 = 5 + 17 + 12 + 24 = 58 𝑤𝑡 14 = 2 + 25 + 17 + 14 = 58 𝑤𝑡 10 = 3 + 20 + 25 + 10 = 58 𝑤𝑡 15 = 7 + 16 + 20 + 15 = 58 𝑤𝑡 18 = 1 + 23 + 16 + 918 = 58 𝑤𝑡 21 = 6 + 8 + 23 + 21 = 58 𝑤𝑡 4 = 19 + 11 + 5 + 2 + 3 + 7 + 1 + 6 = 58

Contoh pelabelan yang ditunjukkan gambar 3.6 merupakan sebagian dari pelabelan yang mungkin untuk nilai n dan k tertentu. Selanjutnya algoritma dan simulasi pelabelan total ajaib titik pada graf roda akan dibahas pada bab berikutnya.


BAB IV ALGORITMA PELABELAN TOTAL AJAIB TITIK PADA GRAF RODA

Andrew Baker dan Joe Sawada (2008) membangun algoritma pelabelan total ajaib titik pada graf sikel dan roda. Melalui algoritma tersebut, semua pelabelan yang (mungkin) ada dapat diketahui dengan menentukan konstanta ajaib. Hasil pelabelan merupakan semua pelabelan total ajaib titik yang (mungkin) ada dan tidak isomorfik. Pelabelan total ajaib titik pada graf roda memperhatikan urutan label yang digunakan, sehingga muncul banyak cara melabeli. Bila satu label elemen diganti, maka label elemen yang lain dapat berubah. Dalam hal ini kemampuan fisik manusia memiliki keterbatasan, sehingga diperlukan suatu perangkat yang dapat membantu proses pelabelan tersebut. Perangkat tersebut dapat dirancang dengan memanfaatkan aplikasi yang berkembang di bidang komputasi. Rancangan perangkat dinyatakan dalam suatu algoritma pelabelan. Selanjutnya, algoritma tersebut disimulasikan dalam suatu program. Graf roda dapat dilabeli jika dan hanya jika 𝑛 ≤ 11 (Gallian, 2014). Nilai konstanta ajaib k berada pada rentang 𝑛 +2 (𝑛+1) 2

13𝑛 2 +11𝑛+2 2 𝑛 +1

≤𝑘≤

17𝑛 2 +15𝑛+2 2 𝑛 +1

dan

≤ 𝑘 ≤ 7𝑛 + 6.

Secara umum, ide pelabelan total ajaib titik graf roda adalah melabeli sisi dan titik secara berulang sampai semua titik memiliki bobot yang sama. Label sisi

43


44

dan titik ditentukan secara acak dan berbeda. Perulangan ini dilakukan sampai semua titik memiliki bobot yang sama. Graf roda merupakan graf sederhana yang dibangun dengan melakukan operasi join graf lengkap 𝐾1 dengan graf sikel 𝐶𝑛 , sehingga graf roda memiliki 2𝑛 sisi dan 𝑛 + 1 titik. Label yang hadir adalah 1,2,3, … ,3𝑛 + 1. Contoh : Jika 𝑛 = 4, dari pertidaksamaan (6) diperoleh 25,4 ≤ 𝑘 ≤ 33,4 dan dari pertidaksamaan (7) dan (8) diperoleh 15 ≤ 𝑘 ≤ 34, maka batas nilai k untuk pada 𝑊4 adalah 26 ≤ 𝑘 ≤ 33. Label yang hadir untuk n = 4 adalah 1,2,3, … ,13.

A. Proses Pelabelan Total Ajaib Titik pada Graf Roda Pada proses pelabelan, label sisi (spoke), sisi pada sikel (rim), titik (vertex) secara berturut-turut dinotasikan s, r, v dengan indeks 1,2,3, … , 𝑛. Proses pelabelan pada graf roda ditunjukkan gambar 4.1. Berikut ini variabel-variabel yang digunakan dalam proses pelabelan :

Tabel 4.1 Variabel yang digunakan dalam pelabelan

Variabel n

k

s

Keterangan Indeks pada graf roda 𝑊𝑛 , menyatakan banyaknya titik pada sikel, variabel global yang dibaca oleh semua perintah, nilai diinputkan oleh pengguna Konstanta ajaib dalam pelabelan, variabel global yang dibaca oleh semua perintah, nilai diinputkan oleh pengguna Sisi jari-jari (spoke), variabel yang memuat label-label sisi (spoke), dalam proses pelabelan memiliki keluaran dalam bentuk matriks 𝑠 = 𝑠1 𝑠2 … 𝑠𝑛 .


Variabel

dalam pelabelan memiliki keluaran dalam bentuk matriks 𝑟 = 𝑟1 𝑟2 … 𝑟𝑛 Titik (vertex), variabel yang memuat label-label titik, dalam proses pelabelan

v

memiliki keluaran dalam bentuk matriks 𝑣 = 𝑣1 𝑣2 … 𝑣𝑛 Titik pusat (hub), variabel yang memuat label titik pusat, dalam pelabelan

h

memiliki keluaran berupa matriks ℎ = [ℎ1 ]

a ,b, c, d

B

D

Keterangan Sisi pada sikel (rim), variabel yang memuat label-label sisi pada sikel (rim),

r

M

45

Variabel sementara pada perulangan, a untuk label spoke, b dan c untuk label rim, d untuk label titik Matriks M, variabel yang memuat label-label yang hadir dalam pelabelan 𝑀 = 1 2 … 3𝑛 + 1 Matriks B, variabel yang memuat label-label yang belum digunakan dalam pelabelan, anggota matriks B selalu diperbaharui Matriks D, variabel yang memuat label-label yang belum digunakan dalam perulangan, anggota matriks D selalu diperbaharui

Proses pelabelan terbagi menjadi tiga sub-program, yakni 1. Label_awal Pelabelan pada graf roda dimulai dengan melabeli sebuah sisi (spoke), dua buah sisi pada sikel (rim), dan satu buah titik (vertex). Setiap elemen tersebut diberi label secara acak dan berbeda. Keluaran label_awal adalah label-label 𝑠1 , 𝑟1 , 𝑟𝑛 , dan 𝑣1 . 2. Label_tengah Proses pelabelan berikutnya menentukan satu label sisi (spoke), satu label sisi pada sikel (rim), dan satu label titik (vertex). Proses ini diulang (n-2) kali. Keluaran label_tengah adalah label 𝑠𝑖 , 𝑟𝑖 , dan 𝑣𝑖 dengan 2 ≤ 𝑖 ≤ 𝑛 − 1.


46

3. Label_akhir Proses pelabelan diselesaikan dengan melabeli satu sisi (spoke), satu titik (vertex), dan titik pusat (hub). Keluaran label_akhir adalah 𝑠𝑛 , 𝑣𝑛 , dan h. 𝒇(𝒗𝟏 )

𝒗𝟏

𝒗𝟐

𝒓𝟏

𝒇(𝒓𝟏 )

𝒓𝒏

𝒓𝟐

𝒗𝒏

𝒔𝟏

𝒓𝒏−𝟏 𝒗𝒏−𝟏 𝒓𝒏−𝟐

𝒉

𝒗𝟒

𝒗𝒏−𝟐

𝒉

𝒔𝒏−𝟐

𝒓𝒏−𝟐 𝒗𝒏−𝟐

(b)

𝒇(𝒗𝟏 )

𝒇(𝒗𝟏 ) 𝒇(𝒓𝟏 )

𝒇(𝒓𝟏 )

𝒇(𝒗𝟐 )

𝒇(𝒓𝒏 ) 𝒇(𝒔𝟏 )

𝒇(𝒔𝒏 ) 𝒇(𝒓𝒏−𝟏 )

𝒓𝒏−𝟏

𝒓𝟑 𝒔𝟑

𝒔𝒏−𝟏 𝒔𝒏−𝟐

𝒉

𝒔𝟒

𝒇(𝒓𝟐 )

𝒇(𝒗𝒏 ) 𝒗𝟑

𝒇(𝒔)𝟐

𝒔𝒏

𝒇(𝒗𝟐 )

𝒇(𝒓𝒏 )

𝒇(𝒓𝟐 )

𝒗𝒏

𝒓𝒏−𝟐

𝒗𝟒

𝒔𝟒

(a)

𝒗𝒏−𝟏

𝒓𝟑

𝒔𝟑

𝒔𝒏−𝟏

𝒗𝒏−𝟏

𝒔𝟒

𝒗𝟑

𝒔𝟐

𝒓𝒏−𝟏

𝒓𝟑

𝒔𝒏−𝟐

𝒇(𝒔𝟏 ) 𝒔𝒏

𝒔𝟑

𝒔𝒏−𝟏

𝒓𝟐

𝒗𝒏

𝒗𝟑

𝒔𝟐

𝒔𝒏

𝒗𝟐

𝒇(𝒓𝒏 )

𝒇(𝒔𝟏 ) 𝒇(𝒔𝟐 )

𝒇(𝒓𝟑 )

𝒇(𝒔𝒏−𝟏 )

f(𝐬𝟑 )

𝒇(𝒗𝒏−𝟏 ) 𝒗𝟒

𝒇(𝒓𝒏−𝟐 )

𝒇(𝒗𝟑 )

𝒇(𝒔𝒏−𝟐 )

𝒉

𝒇(𝒔𝟒 )

f(𝒗𝒏−𝟐)

𝒗𝒏−𝟐

(c)

(d)

Gambar 4.1 Proses pelabelan pada graf roda 𝑊𝑛

B. Diagram Alir Pelabelan Total Ajaib Titik pada Graf Roda Gagasan proses pelabelan pada graf roda perlu dikembangkan sehingga diperoleh program yang sesuai. Gagasan tersebut dibangun secara bertahap, meliputi membangun diagram alir atau flowchart, membangun algoritma

𝒇(𝒗𝟒 )


47

proses pelabelan, dan membahasakan algoritma pelabelan ke bahasa pemrograman Matlab 7.1. Sub-bab ini membahas diagram alir pelabelan pada graf roda. Rancangan proses pelabelan graf roda tampak pada Gambar 4.2. Pada diagram alir tersebut terdapat beberapa sub-program pelabelan. Perancangan sub-program dimaksudkan untuk memudahkan pengorganisasian perintah. Dalam proses pelabelan pada graf roda terdapat tiga sub-program utama yakni label_awal, label_tengah, dan label_akhir. Sub-program interval menampilkan batas bawah dan batas atas nilai k. mulai

Nilai n

interval Masukan : nilai k

label_awal

Sub 1

label_tengah

Sub 2

minbobot>k

Sub 3

label_akhir

Keluaran : Hasil pelabelan

selesai

Gambar 4.2 Diagram alir proses pelabelan


48

Proses pelabelan diawali dengan menginputkan nilai n untuk menentukan rentang nilai konstanta k. Berdasarkan rentang nilai k yang ditampilkan, pengguna memilih nilai konstanta k yang dikehendaki dan menginputkan nilai tersebut untuk sub-program label_awal. Label-label yang diperoleh pada proses label awal disimpan dalam variabel s, r, dan v. Keluaran label_awal adalah label-label 𝑠1 , 𝑟1 , 𝑟𝑛 , dan 𝑣1 . Satu label sisi (𝑟1 ) yang diperoleh pada sub-program

label_awal dibaca untuk menentukan label-label berikutnya.

Perulangan sub-program label_tengah dilakukan sampai (n – 2) kali. Setiap label yang sudah disimpan akan dikurangkan dari daftar label yang hadir, sehingga label-label tersebut hanya dapat digunakan sekali. Sub-program label_akhir memastikan bahwa label yang tersisa merupakan label yang sesuai untuk nilai konstanta k. Keluaran dari proses pelabelan berupa matriks s, r, v, dan h dari proses pelabelan. Bila label yang tersisa tidak sesuai untuk nilai konstanta k, maka proses diulang dari label_tengah. Diagram alir berikut ini menggambarkan sub-program dari program pelabelan pada graf roda 𝑊𝑛 , meliputi interval, label_awal, label_tengah, dan label_akhir. 1. Diagram alir interval Diagram alir ini menyatakan proses menentukan batas nilai konstanta k, yakni batas bawah dan batas atas. Pertidaksamaan

(6) , (7), dan (8)

menyatakan rentang nilai konstanta ajaib k. Berdasarkan gambar diagram alir 4.3, diketahui bahwa tidak ada pelabelan pada n < 3 dan n > 11. Bila 𝑛 ≥ 3 dan kurang dari 12 akan diuji dengan menyubstitusikan nilai n ke


pertidaksamaan

13𝑛 2 +11𝑛+2 2 𝑛+1

<𝑘≤

𝑛+2 (𝑛+1) 2

49

. Bila bernilai salah, maka

batas atas dan batas bawahnya diperoleh dengan mensubstitusikan nilai n ke

𝑛+2 (𝑛+1) 2

dan 7𝑛 + 6 secara berturut – turut. Sementara bila bernilai

benar, maka batas bawah diperoleh dengan mensubstitusikan nilai n ke 13𝑛 2 +11𝑛+2 2 𝑛+1

. Batas atas ditentukan dari hasil kondisi

17𝑛 2 +15𝑛 +2 2 𝑛 +1

< 7𝑛 + 6.

Bila

hasilnya salah, maka batas atasnya diperoleh dari hasil substitusi nilai n ke 7𝑛 + 6.

Jika hasilnya benar maka batas atasnya merupakan hasil substitusi

nilai n ke

17𝑛 2 +15𝑛+2 . 2 𝑛+1

Keluaran proses ini adalah batas nilai konstanta k.

2. Diagram alir sub-program label_awal Ada 4 variabel keluaran sub-program label_awal yakni 𝑠1 , 𝑟1 , 𝑟𝑛 , dan 𝑣1 . Sebagai variabel sementara terdapat variabel a, b, c, dan d yang digunakan dalam proses perulangan. Keempat variabel ini diberi nilai nol sebagai nilai awal. Perintah berikutnya adalah mengacak label sejumlah (3n+1) untuk setiap variabel. Bila masing-masing label sudah dipastikan tidak sama, barulah keempat label dijumlahkan. Perintah mengacak label akan dilakukan berulang-ulang sampai hasil penjumlahan nilai keempat variabel sama dengan nilai k yang dipilih. Label-label yang memenuhi disimpan pada variabel s, r, dan v sebagai array, tepatnya disimpan pada variabel 𝑠1 , 𝑟1 , 𝑟𝑛 , dan 𝑣1 .


50

mulai

Masukan nilai n

𝑛≥3 Keluaran : tidak ada pelabelan

𝑛 < 12

Keluaran : tidak ada pelabelan

13𝑛 2 + 11𝑛 + 2 < 2 𝑛+1

𝑛 + 2 (𝑛 + 1) 2

13𝑛2 + 11𝑛 + 2 2 𝑛+1

𝑛 + 2 (𝑛 + 1) 2

7𝑛 + 6

17𝑛2 + 15𝑛 + 2 < 7𝑛 + 6 2 𝑛+1

17𝑛2 + 15𝑛 + 2 2 𝑛+1

7𝑛 + 6

Keluaran : batas nilai k

selesai

Gambar 4.3 Diagram alir sub-program batas nilai k


51

a=0 b=0 c=0 d=0 temp=a+b+c+d

a=random(3n+1) b=random(3n+1) c=random(3n+1) d=random(3n+1)

label_awal

a<>b<>c<>d

temp=a+b+c+d

s(1)=a r(2)=b r(n)=c v(1)=d

Gambar 4.4 Diagram alir sub-program label_awal

3. Diagram alir sub-program label_tengah Ide sub-program label_tengah hampir sama dengan sub-program label_awal. Sub-program akan melakukan perulangan sampai hasil penjumlahan keempat variabelnya sama dengan nilai k yang dipilih. Pada sub-program ini, nilai 𝑟𝑡−1 selalu diperbaharui untuk perhitungan berikutnya. Sub-program label_tengah diulang sampai (n – 2) kali. Demikian juga dengan keluaran sub-program ini, label-label diperoleh


52

pada setiap perulangan yang disimpan pada variabel s(i), r(i), r(i-1), dan v(i) dengan 2 ≤ 𝑖 ≤ 𝑛 − 1. Pada akhir proses label_tengah, semua label sisi (spoke) dijumlahkan. Hasilnya ditambah dengan label terkecil yang belum digunakan dan disimpan pada variabel minbobot. Label yang belum digunakan sebanyak (n-i) dijumlahkan, hasilnya ditambahkan pada variabel minbobot. Bila nilai minbobot kurang dari k maka proses dilanjutkan ke sub-program label_akhir. Namun, bila sebaliknya proses label_tengah harus diulang.

4. Diagram alir sub-program label_akhir Setelah perulangan yang dilakukan pada sub–program label_tengah, tersisa tiga elemen yang belum dilabeli yakni 𝑠𝑛 , 𝑣𝑛 , dan h. Elemen 𝑠𝑛 dan 𝑣𝑛 dilabeli dengan label yang tersisa. Label titik pusat ditentukan dengan mengurangkan nilai k dengan hasil penjumlahan semua label jarijari.


53

a=0 b=0 c=r d=0 temp=a+b+c+d

a=random(numel(B)) b=random(numel(B)) d=random(numel(B))

label_tengah a<>b<>c<>d

temp=a+b+c+d

minbobot
label_akhir

s(i)=a r(i)=b r(i-1)=c v(i)=d

i< (n-1)

Gambar 4.5 Diagram alir sub-program label_tengah


54

a=0 p=0 x=a+p+sum(s)

a=random(3n+1) d=random(3n+1)

label_akhir

a<>d

x=a+p+sum(s)

s(n)=a h=p v(n)=D(1)

Gambar 4.6 Diagram alir sub-program label_akhir

C. Deskripsi Algoritma Pelabelan Total Ajaib Titik pada Graf Roda Pada sub-bab ini akan dibahas algoritma pelabelan pada graf roda. Diagram alir yang telah dibuat, selanjutnya dikembangkan dalam algoritma pelabelan. Seperti diagram alirnya, algoritma pelabelan dibangun secara global dengan nama label. Sub-program dari label adalah label_awal, label_tengah, dan label_akhir. Sub-program interval menampilkan batas nilai konstanta k.


55

Masukan program pelabelan adalah nilai n yang menyatakan banyaknya titik pada sikel. Keluaran proses ini adalah label-label untuk

semua sisi

(spokes), sisi pada sikel (rims), dan titik (vertices). Nilai n merupakan masukan untuk menentukan rentang nilai konstanta ajaib k. Batas bawah dan batas atas ditentukan berdasarkan perhitungan dasar dan perhitungan yang memperhatikan struktur graf roda. Keluarannya berupa batas nilai konstanta k. Proses selanjutnya, nilai konstanta ajaib k dipilih dan diinputkan untuk proses pelabelan. Nilai n dan k merupakan variabel global yang akan dibaca oleh semua perintah dalam pelabelan. Sub-program label_awal dipanggil untuk memperoleh label-label awal untuk elemen 𝑠1 , 𝑟1 , 𝑟𝑛 , dan 𝑣1 . Proses pelabelan

dilanjutkan

dengan

memanggil

sub-program

label_tengah.

Keluaran sub-program ini berupa label-label 𝑠𝑖 , 𝑟𝑖 , 𝑟𝑖−1 , dan 𝑣𝑖 dengan 2 ≤ 𝑖 ≤ 𝑛 − 1. Sub-program label_akhir dipanggil untuk memperoleh label 𝑠𝑛 dan 𝑣𝑛 . Berikut ini algoritma pelabelan pada graf roda : Langkah 1

: baca nilai n

Langkah 2

: memanggil fungsi interval. Menampilkan batas nilai k

Langkah 3

: input nilai k yang dipilih

Langkah 4

: memanggil fungsi label_awal. Menyimpan label 𝑠1 , 𝑟1 , 𝑟𝑛 , dan 𝑣1 . Mengurangkan label yang sudah dipakai dari label

yang tersedia. Langkah 5

: memanggil fungsi label_tengah. Menyimpan label 𝑠𝑖 , 𝑟𝑖 , 𝑟𝑖−1 , 𝑣𝑖 . Mengurangkan label yang sudah dipakai dari label yang tersedia.


Langkah 6

56

: menjumlah semua label 𝑠𝑖 dengan 1 ≤ 𝑖 ≤ 𝑛 − 1 pada variabel bobot. Menentukan label terkecil, disimpan pada variabel kecil. Menentukan (n-i) label terkecil, menjumlahkannya, dan disimpan pada variabel jarijari. bobot+kecil+jarijari= minbobot. Bila nilai minbobot lebih besar dari nilai k maka langkah 5 diulang. Bila sebaliknya, lanjut ke langkah 7

Langkah 7

: memanggil fungsi label_akhir. Menyimpan label 𝑠𝑛 , 𝑣𝑛 .

Langkah 8

: menentukan label titik pusat melalui pusat = k – bobot

Langkah 9

: menampilkan label pusat, label 𝑠𝑖 , 𝑟𝑖 , 𝑣𝑖 dengan 1 ≤ 𝑖 ≤ 𝑛 − 1

Dalam algoritma pelabelan terdapat beberapa sub-program. Selanjutnya, subprogram ini akan disebut fungsi. Berikut ini algoritma dari setiap fungsi yang terdapat pada algoritma pelabelan graf roda. 1.

Algoritma fungsi interval Fungsi interval dipanggil setelah nilai n diinputkan. Keluaran fungsi interval adalah batas bawah dan batas atas nilai k. Berikut ini algoritma fungsi interval : Langkah 1

: baca nilai n, Jika 𝑛 < 3, tampilkan „tidak ada pelabelan‟ Jika 𝑛 > 12, tampilkan „tidak ada pelabelan‟ Jika 3 ≤ 𝑛 ≤ 11, lanjut langkah 2

Langkah 2

2

: nilai n disubstitusikan ke 13𝑛2 +11𝑛+2 < 𝑛+1

𝑛+2 (𝑛+1) . 2


Jika salah : batas bawah =

𝑛+2 (𝑛+1) 2

Jika benar : batas bawah =

57

, batas atas = 7𝑛 + 6.

13𝑛 2 +11𝑛+2 2 𝑛+1

, batas atas lanjut

langkah 3 Langkah 3

17𝑛 2 +15𝑛 +2

: nilai n disubstitusikan ke

2 𝑛 +1

< 7𝑛 + 6,

Jika salah : batas atas = 7𝑛 + 6 2

+2 Jika benar : batas atas = 17𝑛2 +15𝑛 𝑛 +1

Langkah 4

: tampilkan batas bawah dan batas atas untuk nilai n yang diinputkan

2. Algoritma fungsi label_awal Fungsi label_awal mencari empat buah label secara acak untuk 𝑠1 , 𝑟1 , 𝑟𝑛 , dan 𝑣1 . Variabel sementara yang digunakan untuk memperoleh label awal adalah a,b,c,dan d. Label – label yang diperoleh disimpan pada 𝑠1 , 𝑟1 , 𝑟𝑛 , dan 𝑣1 sebagai array. Semua label yang telah digunakan pada proses label awal akan dikurangkan dari himpunan label – label yang tersedia. Cara ini digunakan untuk menghindari label yang sama digunakan lebih dari satu kali. Langkah-langkah dalam fungsi label_awal sebagai berikut : Langkah 1

: inisialisasi a, b, c, dan d

Langkah 2

: temp  a + b + c + d

Langkah 3

: ulang hingga syarat temp ~= k terpenuhi

Langkah 4

: a  random(3n+1) b  random(3n+1) c  random(3n+1)


58

d  random(3n+1) Langkah 5

: jika a < > b < > c < > d, temp  a + b + c + d

Langkah 6

: akhiri perulangan

Langkah 7

: s(1) a r(1) b r(n) c v(1) d

Langkah 8

: setdiff(M,[a b c d])

Label yang tersedia untuk pelabelan adalah

1,2,3, . . ,3𝑛 + 1

dinyatakan pada matriks M. Pelabelan total ajaib titik pada graf roda melibatkan empat elemen yakni 𝑠𝑖 , 𝑟𝑖 , 𝑟𝑖−1 , dan 𝑣𝑖 dengan 1 ≤ 𝑖 ≤ 𝑛, sehingga dibutuhkan variabel sementara selama proses perulangan. Keempat variabel tersebut adalah a, b, c, dan d. Langkah pertama pada algoritma label_awal adalah tahap inisialisasi a, b, c, dan d. Pada tahap ini semua variabel sementara diberi nilai nol sebagai nilai awal. Program pelabelan mengenali variabel a, b, c, dan d dengan nilai nol. Langkah kedua, menyediakan variabel temp untuk menampung hasil penjumlahan nilai variabel a, b, c, dan d. Karena nilai awal variabel a, b, c, dan d adalah nol, maka variabel temp memiliki nilai awal nol. Langkah ketiga, perintah-perintah yang dinyatakan setelah langkah ketiga akan diulang sampai syarat temp = k terpenuhi. Perulangan dilakukan sampai jumlah keempat variabel yang ditampung pada variabel


59

temp sama dengan nilai konstanta k yang diinputkan. Bila syarat temp = k belum terpenuhi, perulangan dilakukan mulai dari langkah pertama. Langkah keempat, memberi nilai variabel a, b, c, dan d dengan label yang tersedia secara acak. Perintah random(3n+1) adalah perintah untuk mengacak bilangan dari 1 sampai (3n+1). Langkah kelima, jika keempat variabel memiliki nilai yang berbeda, maka temp menyimpan hasil penjumlahan keempat bilangan tersebut. Bila ada bilangan yang sama maka proses diulangi dari langkah pertama. Langkah keenam, bila syarat temp = k sudah terpenuhi maka perulangan akan diakhiri. Langkah ketujuh, label-label yang diperoleh dari perulangan disimpan pada variabel s, r, dan v sebagai array, khususnya dalam bentuk matriks. Variabel s kolom 1 atau 𝑠1 diberi nilai oleh label a. Variabel 𝑟1 diberi nilai oleh label b. Nilai label c disimpan pada variabel r kolom ke n atau 𝑟𝑛 . Nilai variabel d disimpan pada variabel 𝑣1 . Langkah kedelapan, label-label yang sudah disimpan, dikurangkan dari matriks M dengan perintah setdiff(M,[a b c d]).

3. Algoritma fungsi label_tengah Bilangan-bilangan yang diperoleh pada fungsi label_awal dapat disebut sebagai label inisial. Label inisial diasumsikan memiliki susunan benar, sehingga

label

berikutnya

dapat

ditentukan.

Label-label

untuk


60

sub– program label_tengah dipilih dari sisa label yang tersedia. Perulangan pada proses label_tengah dilakukan untuk memperoleh label sisi (spoke), satu sisi pada sikel (rim), dan label titik (vertex) secara acak. Setiap label yang telah digunakan tidak dapat digunakan lagi. Langkah-langkah fungsi label_tengah : Langkah 1

: baca variabel a, b, c, dan d. a0 b0 c  r(i-1) d0

Langkah 2

: temp  a + b + c + d

Langkah 3

: ulang hingga syarat temp ~= k terpenuhi

Langkah 4

: a  random(numel(B)) b  random(numel(B)) d  random(numel(B))

Langkah 5

: jika a < > b < > c < > d, temp  a + b + c + d

Langkah 6

: akhiri perulangan

Langkah 7

: s(i) a r(i) b r(i-1) c v(i) d

Langkah 8

: setdiff(D,[a b c d]) jarijari = jumlah (n – i ) label terkecil


61

bobot = jumlah label s(i) kecil = label terkecil minbobot = jarijari + bobot + kecil Langkah 9

: jika minbobot>k, ulangi dari langkah 1

Langkah 10

: s(i) a r(i) b v(i) d

Label-label yang belum digunakan disimpan pada matriks dengan nama berbeda untuk menghindari salah baca. Langkah pertama, inisialisasi variabel sementara. Variabel a, b, dan d diberi nilai nol, sedangkan c membaca nilai label 𝑟𝑖−1 yang diperoleh dari label_awal. Langkah kedua, hasil penjumlahan label a, b, c, dan d disimpan pada variabel temp. Langkah ketiga, perintah-perintah yang dinyatakan setelah langkah ketiga akan diulang sampai syarat temp = k terpenuhi. Perulangan dilakukan sampai jumlah keempat variabel yang ditampung pada variabel temp sama dengan nilai konstanta k yang diinputkan. Bila syarat temp = k belum terpenuhi, perulangan dilakukan mulai dari langkah pertama. Langkah keempat, memberi nilai variabel a, b, dan d dengan label yang belum digunakan secara acak. Perintah random(numel(B)) adalah perintah untuk mengacak bilangan dari 1 sebanyak elemen matriks B.


62

Langkah kelima, jika keempat variabel memiliki nilai yang berbeda, maka hasil penjumlahan keempat bilangan tersebut disimpan pada variabel temp. Bila ada bilangan yang sama maka proses diulangi dari langkah pertama. Langkah keenam, perulangan diakhiri bila syarat temp = k sudah terpenuhi. Langkah ketujuh, label-label yang diperoleh dari perulangan disimpan. Label s(i) diisi label a, label r(i) diisi label b, dan label v(i) diisi label d. Langkah kedelapan, label-label yang diperoleh pada langkah 7 dikurangkan dari label yang tersedia. Label yang tersisa perlu dipastikan dapat digunakan sebagai label. Variabel minbobot menyatakan hasil penjumlahan dari variabel jarijari, bobot, dan kecil. Variabel jarijari menyatakan hasil penjumlahan (n – i ) label terkecil dari label yang belum digunakan. Variabel bobot menyatakan hasil penjumlahan semua label sisi (spoke). Variabel kecil menyatakan label terkecil dari label yang belum digunakan. Langkah kesembilan, jika nilai minbobot lebih besar dari nilai konstanta k, maka proses pelabelan diulangi dari langkah pertama. Namun, jika nilai minbobot lebih kecil atau sama dengan nilai k maka proses dilanjutkan langkah kesepuluh.


63

Langkah kesepuluh, label-label yang diperoleh disimpan pada variabel 𝑠𝑖 , 𝑟𝑖 , dan 𝑣𝑖 dengan 2 ≤ 𝑖 ≤ 𝑛 . Proses label_tengah diulang sebanyak (n – 1) kali.

4. Algoritma fungsi label_akhir Pada akhir proses pelabelan label_tengah, terdapat tiga elemen yang belum dilabeli. Elemen tersebut adalah 𝑠𝑛 , 𝑣𝑛 dan h. Label untuk ketiga elemen graf roda tersebut ditentukan pada fungsi label_akhir. Langkah 1

: baca variabel a dan p. a0 p0

Langkah 2

: x  a + p + jumlah label s

Langkah 3

: ulang hingga syarat x ~= k terpenuhi

Langkah 4

: a  random(numel(D)) p  random(numel(D))

Langkah 5

: jika a < > p, x  a + p + jumlah label s

Langkah 6

: akhiri perulangan

Langkah 7

: s(n) a h p

Langkah 8

: v(n) label yang tersisa

Label yang tersisa diacak untuk melabeli 𝑠𝑛 , 𝑣𝑛 , dan h. Langkah pertama, membaca variabel a dan p. Variabel a dan p diberi nilai nol.


64

Keluaran fungsi label_akhir adalah label s dan v dengan indeks n serta label titik tengah (h). Langkah pertama, inisialisasi variabel sementara. Variabel a dan p diberi nilai nol, variabel p akan menyatakan label titik tengah. Langkah kedua, hasil penjumlahan label sisi jari-jari (s), a, dan p disimpan pada variabel x. Langkah ketiga, perintah-perintah yang dinyatakan setelah langkah ketiga akan diulang sampai syarat x = k terpenuhi. Bila syarat x = k belum terpenuhi, perulangan dilakukan mulai dari langkah pertama. Langkah keempat, memberi nilai variabel a dan p dengan label yang belum digunakan secara acak. Perintah random(numel(D)) adalah perintah untuk mengacak bilangan sebanyak elemen matriks D. Langkah kelima, jika kedua variabel memiliki nilai yang berbeda, maka hasil penjumlahannya disimpan pada variabel x. Bila ada bilangan yang sama maka proses diulangi dari langkah pertama. Langkah keenam, perulangan diakhiri bila syarat x = k sudah terpenuhi. Langkah ketujuh, variabel s(n) diisi oleh nilai label a dan variabel h diisi oleh nilai label p. Langkah kedelapan, memberi label v (n) dengan sisa label pada matriks D. Semua label yang telah disimpan pada variabel s, r, v, dan h ditampilkan pada akhir fungsi.


65

D. Simulasi Pelabelan Total Ajaib Titik pada Graf Roda Algoritma yang dibuat dapat dibahasakan dengan bahasa pemrograman. Salah satu software yang dapat digunakan adalah Matlab 7.1. Program pelabelan total ajaib pada graf roda menggunakan nilai n dan k sebagai masukan. Keluaran dari program ini berupa matriks s, r, v, dan h dengan elemen berupa label-label. Program pelabelan pada graf roda terdiri dari satu program utama yaitu label yang menjalankan tiga sub-program yakni fungsi label_awal, fungsi label_tengah, dan fungsi label_akhir. Variabel n dan k merupakan variabel global yang dapat dibaca semua perintah. Algoritma pelabelan yang disusun diterjemahkan menggunakan sofware Matlab 7.1 (terlampir). Program pelabelan total ajaib titik pada graf roda dipanggil dengan mengetik “label” pada command window, maka akan muncul tampilan berikut.

Gambar 4.7 (a) Tampilan awal pada command window


66

Selanjutnya, nilai n diinputkan. Misal nilai n yang diinputkan adalah 3, maka pada command window akan muncul tampilan berikut.

Gambar 4.7 (b) Tampilan input n pada command window

Tahap berikutnya, nilai konstanta k diinputkan berada pada rentang nilai yang ditampilkan pada command window.

Sebagai contoh, nilai k yang

diinputkan adalah 21. Berikut tampilan pada command window.

Gambar 4.7 (c) Tampilan akhir pada command window


67

Setelah nilai k diinputkan, fungsi label_awal dipanggil untuk melabeli 𝑠1 , 𝑟1 , 𝑟𝑛 , dan 𝑣1 . Berkas keluaran fungsi label_awal dapat ditampilkan seperti gambar 4.8. Label sisi 𝑠1 adalah 1, label sisi 𝑟1 adalah 9, label sisi 𝑟3 adalah 6, dan label 𝑣1

adalah 5 sehingga bobot 𝑣1

adalah

1 + 9 + 6 + 5 = 21. Label yang belum digunakan ditampilkan sebagai matriks B.

Gambar 4.8 Berkas keluaran fungsi label_awal pada command window

Berkas keluaran fungsi label_awal pada gambar 4.8 dapat diilustrasikan sebagai berikut.

𝟗 𝟏

𝟓

𝟔

Gambar 4.9 Ilustrasi Berkas keluaran fungsi label_awal


68

Fungsi label_tengah dipanggil untuk melabeli 𝑠𝑖 , 𝑟𝑖 , dan 𝑣𝑖 untuk 2 ≤ 𝑖 ≤ 𝑛 − 1.

Berkas keluaran fungsi label_tengah ditampilkan pada gambar 4.10.

Label 𝑠2 adalah 2, label 𝑟2 adalah 3, dan label 𝑣2 adalah 7, sehingga bobot 𝑣2 adalah 2 + 3 + 9 + 7 = 21. Label yang belum digunakan ditampilkan pada matriks B.

Gambar 4.10 Berkas keluaran fungsi label_tengah pada command window

Berkas keluaran fungsi label_tengah pada gambar 4.10 dapat diilustrasikan sebagai berikut : 𝟕

𝟗

𝟐

𝟑

𝟏

𝟓

𝟔

Gambar 4.11 Ilustrasi berkas keluaran fungsi label_tengah


69

Fungsi label_akhir dipanggil untuk melabeli 𝑠𝑛 , 𝑣𝑛 , dan h. Label 𝑠3 adalah 8, label 𝑣3 adalah 4, sehingga bobot 𝑣3 adalah 8 + 3 + 6 + 4 = 21. Variabel h menyatakan label titik pusat yakni 10, sehingga bobot h adalah 1+2+8+10 = 21.

Gambar 4.12 Berkas keluaran fungsi label_akhir pada command window

Berkas keluaran fungsi label_akhir pada gambar 4.12 dapat dilustrasikan sebagai berikut : 𝟕

𝟗

𝟑

𝟐 𝟏𝟎

𝟏

𝟖 𝟓

𝟒 𝟔

Gambar 4.13 Ilustrasi berkas keluaran pelabelan n = 3 dengan k = 21


70

Berdasarkan ilustrasi pada gambar 4.13, bobot setiap titik sebagai berikut 𝑤𝑡 5 = 1 + 9 + 6 + 5 = 21 𝑤𝑡 7 = 2 + 3 + 9 + 7 = 21 𝑤𝑡 4 = 8 + 6 + 3 + 4 = 21 𝑤𝑡 10 = 1 + 2 + 8 + 10 = 21

Simulasi pelabelan yang dilakukan program pelabelan dengan software Matlab 7.1 memiliki beberapa kelemahan, antara lain 

Banyaknya kemungkinan cara melabeli tiap elemen dapat mengakibatkan waktu yang dibutuhkan untuk mengeksekusi perintah menjadi cukup lama



Algoritma yang dibuat dapat diterjemahkan dalam beberapa bahasa pemrograman, sehingga waktu yang dibutuhkan untuk melakukan pelabelan pun beragram



Semakin tinggi nilai n atau semakin besar nilai k yang diinputkan mengakibatkan waktu mengeksekusi perintah menjadi lebih lama


BAB V PENUTUP

A. Kesimpulan Dari permasalahan yang dibahas pada skripsi ini, dapat diambil beberapa kesimpulan sebagai berikut : 1. Pelabelan total ajaib titik berlaku pada graf roda 2. Nilai konstanta ajaib k untuk pelabelan total ajaib titik graf roda 𝑊𝑛 berada pada rentang 𝑛 +2 (𝑛+1) 2

13𝑛 2 +11𝑛+2 2 𝑛 +1

≤𝑘≤

17𝑛 2 +15𝑛+2 2 𝑛 +1

dan

≤ 𝑘 ≤ 7𝑛 + 6

3. Pelabelan total ajaib titik pada graf roda dapat dilakukan secara iteratif yakni dengan memberi label pada jari-jari, sisi pada sikel, dan titiknya dengan label yang tersedia. Algoritma pelabelan dibangun dan disimulasikan dengan Matlab 7.1. Graf roda dengan n besar ( n > 11 ) tidak dapat dilabeli . Pelabelan total titik ajaib pada graf roda 𝑊𝑛 ada bila 3 ≤ 𝑛 ≤ 11.

B. Saran Penelitian selanjutnya dapat membahas graf roda dengan 1. Jenis pelabelan yang lain, seperti Pelabelan Total Ajaib Sisi, Pelabelan Total Tak – Ajaib Titik, atau Pelabelan Total Tak – Ajaib Sisi.

71


72

2. Pelabelan Total Ajaib Titik disimulasikan dengan bahasa pemrograman yang lain, seperti Pascal, Visual Basic, atau lainnya


DAFTAR PUSTAKA

Baker, A. & J. Sawada. (2008). Magic Labelings on Cycles and Wheels. COCOA LNCS, 361 – 373.

Buckley, Fred & Marty Lewinter . (2002). A Friendly Introduction to Graph Theory. New York : Pearson Education inc.

Fathoni, Zain. (2011). Penggunaan Autentifikasi Sidik Jari untuk Pengamanan Transaksi ATM. Bandung, 053.

Gallian, J. A. (2014). A Dynamic Survey of Graph Labelings. The Electronic Journal of Combinatorics, # DS6. MacDougall, J.A., M. Miller, W.D. Wallis. (2002). Vertex – Magic Total Labelings of Wheels and Related Graphs. Utilitas Math.

Munir, Rinaldi. (2003). Matematika Diskrit. Bandung :Informatika Bandung.

Wallis, W.D. (2001). Magic Graph. New York : Birkhäuser.

73


LAMPIRAN

1. Berkas Keluaran Program label

74


2. Listing Program label function[]=label(n,k) %LABEL : Pelabelan Total Ajaib Titik pada Graf Roda %Function LABEL melabeli setiap elemen pada graf roda %label pada s(i),r(i),r(i-1),dan v(i)dijumlahkan %nilai konstanta k menyatakan hasil jumlahannya clear all; disp(' Program Pelabelan Total Ajaib-Titik'); disp('=======================================================); disp(' '); disp('Program ini untuk menentukan Pelabelan Total Ajaib Titik'); disp('pada graf roda Wn'); disp(' '); global n k n=input('masukkan nilai n= '); disp(' ') %menampilkan rentang nilai k if n<3 fprintf('tidak ada pelabelan'); return; elseif n>11 fprintf('tidak ada pelabelan'); return; elseif n>2 interval(n,k) end disp(' ') k=input('masukkan nilai k yg dipilih : '); %memanggil fungsi label_awal label_awal(n,k) s; r; v; B=setdiff(M,[s r v]); %memanggil fungsi label_tengah label_tengah(n,k) s; r; v; D=setdiff(B,[s r v]); %memanggil fungsi roda_akhir label_akhir(n,k) %mencetak label s r v h function interval(n,k) m=3*n+1; if n>=10

75


((13*(n^2))+(11*n)+2)/(2*(n+1))< (((n+1)*(n+2))/2); %berlaku untuk n = 10 s.d 11 batas_bawah=(((n+1)*(n+2))/2); batas_atas=(7*n+6); elseif ((17*(n^2))+(15*n)+2)/(2*(n+1))>(7*n+6) %berlaku untuk n = 5 s.d 9 batas_bawah=((13*(n^2))+(11*n)+2)/(2*(n+1)); batas_atas=(7*n+6); else batas_bawah=((13*(n^2))+(11*n)+2)/(2*(n+1)); %berlaku untuk n = 3 s.d 4 batas_atas=((17*(n^2))+(15*n)+2)/(2*(n+1)); end fprintf('rentang k : %.f\t',batas_bawah) fprintf('sampai %.f\t',batas_atas) disp(' '); end end

3. Listing Program label_awal function label_awal(n,k) m=3*n+1; M=[1:m]; a=0; b=0; c=0; d=0; temp=a+b+c+d; while temp~=k a=M(randperm(m)); b=M(randperm(m)); c=M(randperm(m)); d=M(randperm(m)); A=[a;b;c;d]; for i=1:m tf=(length(unique(A(:,i)))==(prod(numel(A(:,i))))); if tf==1 temp=a(:,i)+b(:,i)+c(:,i)+d(:,i); break end end end s(1)=a(:,i); r(1)=b(:,i); r(n)=c(:,i); v(1)=d(:,i); end

76


4. Listing Program label_tengah function label_tengah(n,k) jarijari=0; kecil=0; bobot=sum(s); minbobot=jarijari+kecil+bobot; if minbobot>k label_tengah(n,k) else for j=2:n-1 a=0; b=0; c=r(j-1); d=0; temp=a+b+c+d; while temp~=k a=B(randperm(numel(B))); b=B(randperm(numel(B))); c=r(j-1)*ones(1,numel(B)); d=B(randperm(numel(B))); C=[a;b;c;d]; for i=1:numel(B) tf=(length(unique(B(:,i)))==prod(numel(B(:,i)))); if tf==1 temp=a(:,i)+b(:,i)+c(:,i)+d(:,i); break end end end s(j)=a(:,i); r(j)=b(:,i); v(j)=d(:,i); D=setdiff(B,[s r v]); B=D; jarijari=sum(B(1:n-i)); bobot=sum(s); kecil=min(B); minbobot=jarijari+bobot+kecil; end end end

5. Listing Program label_akhir function label_akhir(n,k) a=0; p=0; x=a+p+sum(s); while x~=k a=D(randperm(numel(D))); p=D(randperm(numel(D))); C=[a;p];

77


for j=1:(numel(D)) tf=(length(unique(C(:,j)))==(prod(numel(C(:,j))))); if tf==1 x=a(:,j)+p(:,j)+sum(s); break end s(n)=a(:,j); h=p(:,j); end D=setdiff(D,C(:,j)); end v(n)=D(1) end

78

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Recommend Documents