pelabelan total ajaib sisi pada graf roda - core.ac.uk filepelabelan total ajaib sisi pada graf roda...

PELABELAN TOTAL AJAIB SISI PADA GRAF RODA

SKRIPSI

Diajukan untuk Memenuhi Salah Satu Syarat

Memperoleh Gelar Sarjana Pendidikan

Program Studi Pendidikan Matematika

Oleh:

Petrus Tri Hariyadi

NIM :121414080

PROGRAM STUDI PENDIDIKAN MATEMATIKA

JURUSAN PENDIDIKAN MATEMATIKA DAN ILMU PENGETAHUAN ALAM

FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN

UNIVERSITAS SANATA DHARMA

YOGYAKARTA

2017

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

i


SKRIPSI

Diajukan untuk Memenuhi Salah Satu Syarat

Memperoleh Gelar Sarjana Pendidikan

Program Studi Pendidikan Matematika

Oleh:

Petrus Tri Hariyadi

NIM : 121414080

PROGRAM STUDI PENDIDIKAN MATEMATIKA

JURUSAN PENDIDIKAN MATEMATIKA DAN ILMU PENGETAHUAN ALAM

FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN

UNIVERSITAS SANATA DHARMA

YOGYAKARTA

2017


ii

SKRIPSII


iii

SKRIPSI


iv

HALAMAN PERSEMBAHAN

Orang yang berhasil adalah orang bodoh yang tetap berjuang,dan orang

yang tidak menghasilkan apapun adalah

orang bijak yang berhenti berjuang

Celica, Rmkar


v

PERNYATAAN KEASLIAN KARYA

Saya menyatakan dengan sesungguhnya bahwa skripsi yang saya tulis ini

tidak memuat karya atau bagian dari karya orang lain, kecuali yang telah disebutkan

dalam kutipan dan daftar pustaka, sebagaimana layaknya karya ilmiah.

Yogyakarta, 24 Agustus 2017

Penulis

Petrus Tri Hariyadi


vi

LEMBAR PERNYATAAN PERSETUJUAN PUBLIKASI

KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS

Yang bertanda tangan di bawah ini, saya mahasiswa Universitas Sanata Dharma:

Nama : Petrus Tri Hariyadi

NIM : 12 1414 080

Demi pengembangan ilmu pengetahuan, saya memberikan kepada

Perpustakaan Universitas Sanata Dharma karya ilmiah saya yang berjudul:

Pelabelan Total Ajaib Sisi Pada Graf Roda

Dengan demikian saya memberikan kepada Universitas Sanata Dharma hak

untuk menyiapkan, mengalihkan dalam bentuk media lain, mengelola dalam bentuk

pangkalan data, mendistribusikan secara terbatas, dan mempublikasikan di internet

atau media lain untuk kepentingan akademis tanpa perlu meminta ijin dari saya

maupun member royalty kepada saya selama tetap mencantumkan nama saya

sebagai penulis.

Demikian pernyataan ini saya buat dengan sebenarnya

Dibuat di Yogyakarta

Pada Tanggal: 24 Agustus 2017

Yang menyatakan,

(Petrus Tri Hariyadi)


vii

ABSTRAK

Petrus Tri Hariyadi. 2017. Pelabelan Total Ajaib Sisi Pada Graf Roda. Skripsi.

Program Studi Pendidikan Matematika, Fakultas Keguruan dan Ilmu

Pendidikan, Universitas Sanata Dharma, Yogyakarta.

Pelabelan Total Ajaib Sisi atau Edge Magic Total Labelings (ETML)

merupakan pemetaan bijektif 𝜆 dari 𝑉(𝐺) ∪ 𝐸(𝐺) ke bilangan asli {1,2,3, … , 𝑣 +

𝑒} dengan 𝑣 = |V(G)| dan 𝑒 = |E(G)| sedemikian sehingga untuk setiap sisi

𝑣𝑖,𝑣𝑗 ∈ 𝐸(𝐺) berlaku, 𝜆(𝑣𝑖) + 𝜆(𝑣𝑖 , 𝑣𝑗) + 𝜆(𝑣𝑗) = 𝑘 untuk setiap konstanta ajaib

𝑘. Graf roda 𝑊1,𝑛 merupakan graf yang dibangun dengan operasi penggabungan

pada graf lengkap 𝐾1 dengan graf sikel 𝐶𝑛 , dinotasikan 𝑊1,𝑛 = 𝐾1 + 𝐶𝑛 . Pada

skripsi ini, graf roda 𝑊1,𝑛 akan disebut 𝑊𝑛 . Tujuan penelitian ini adalah (1)

mengetahui apakah pelabelan total ajaib sisi berlaku pada graf roda, (2) mengetahui

bagaimana rentang nilai konstanta ajaib 𝑘, dan (3) mengetahui cara memberikan

label sisi dan titik pada graf roda untuk nilai konstanta ajaib k.

Hasil penelitian ini adalah (1) pelabelan total ajaib sisi berlaku pada graf

roda 𝑊𝑛 jika (𝑛 ≢ 3(𝑚𝑜𝑑 4)) , (2) melalui perhitungan dasar dengan

mempertimbangkan struktur graf roda diperoleh rentang nilai kosntanta ajaib 𝑘

yaitu 11𝑛+17

4≤ 𝑘 ≤

25𝑛+7

4, dan (3) pelabelan dilakukan secara iteratif dengan

memberikan label titik tengah (𝑐) dan titik lainnya (𝑣) sehingga diperoleh label

untuk jari-jari (𝑒), dan pelabelan label sisi (𝑠). Ada banyak cara memberikan label

elemen pada graf roda sehingga dibutuhkan suatu algoritma untuk pelabelan pada

graf roda. Algoritma pelabelan disimulasikan melalui program MATLAB 7.1.

Kata kunci : pelabelan total ajaib sisi, graf roda


viii

ABSTRACT

Petrus Tri Hariyadi. 2017. Edge-Magic Total Labelings on Wheel.

Undergradute Thesis. Mathematics Education Study, Faculty of Teacher

Training and Education Science, Sanata Dharma University, Yogyakarta.

Edge-magic total labeling is one-to-one function of 𝜆 from 𝑉(𝐺) ∪ 𝐸(𝐺)

into the integer {1,2,3, … , 𝑣 + 𝑒} with 𝑣 = |V(G)| and 𝑒 = |E(G)| if there is so that

for every 𝑣𝑖,𝑣𝑗 ∈ 𝐸(𝐺), 𝜆(𝑣𝑖) + 𝜆(𝑣𝑖 , 𝑣𝑗) + 𝜆(𝑣𝑗) = 𝑘 for every magic constant 𝑘.

Wheel 𝑊1,𝑛 is the join of 𝐾1 with 𝐶𝑛 , that is 𝑊1,𝑛 = 𝐾1 + 𝐶𝑛 . In this thesis, the

wheel 𝑊1,𝑛 is called 𝑊𝑛. The purpose of this thesis were (1) to know whether the

graph wheel has edge-,magic total labeling, (2) to know to interval magic constant

𝑘, and (3) to know how to label the elements of wheel with magic constant 𝑘.

The product of the research are (1) graph wheel has edge-magic total

labeling if (𝑛 ≢ 3(𝑚𝑜𝑑 4)), (2) with basic counting of computing which consider

to the structure of wheel, The feasiable range of magic constant 𝑘 is 11𝑛+17

4≤ 𝑘 ≤

25𝑛+7

4, and (3) labeling is started by attempting possible label for central vertex (𝑐)

and another vertex (𝑣), spoke edge (𝑒) and rim edge (𝑠) 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.

Keywords : edge-magic total labeling, wheel


ix

KATA PENGANTAR

Puji dan syukur penulis panjatkan kepeda Tuhan Yang Maha Esa, karena

hanya dengan berkat dan karunia-Nya, serta campur tangan-Nya, penulis dapat

menyelesaikan skripsi yang berjudul “Pelabelan Total Ajaib Sisi pada Graf Roda”

dengan baik.

Pada kesempatan ini penulis juga mengucapkan rasa terima kasih

kepada:

1. Bapak Dominikus Arif Budi Prasetyo, S.Si., M.Si., selaku dosen

pembimbing yang sudah meluangkan waktu dan dengan sabar membimbing

penulis, sehingga skripsi ini dapat diselesaikan dengan baik.

2. Bapak Dr. Hongki Julie, M.Si. selaku Ketua Program Studi Pendidikan

Matematika dan Dosen Pembimbing Akademik.

3. Bapak Drs. Sugiarto Pudjohartono, M.T. selaku Dosen Pembimbing

Akademik dari tahun 2012-2017.

4. Segenap Dosen JPMIPA yang telah membantu dan memberikan setelah

penulis menempuh kuliah, sehingga akhirnya penulis dapat menyelesaikan

studi.

5. Segenap Staf Sekretariat JPMIPA yang telah membantu dalam hal

administrasi kampus selama penulis melakukan studi.

6. Keluarga yaitu Bapak Supardi, Ibu Maria, Mas Eko dan Desi yang selalu

memberikan dukungan serta doa kepada penulis sehingga skripsi ini dapat

diselesaikan.


https://www.usd.ac.id/profile_detail.php?id=00538

https://www.usd.ac.id/profile_detail.php?id=01147

x

7. Segenap keluarga, terutama Mbah Cipto, Le Tar, Le Topik, Le To, Mbah

Nem, Le Yatno dan Mas Heri yang selalu memberikan semangat, motivasi,

serta inspirasi kepad penulis sehingga penulis mampu menyelesaikan studi.

8. Nataya, Veronica dan Bella yang memberikan semangat dan dukungan yang

sangat berarti bagi penulis selama menjalani studi.

9. Remon, Bintang, Andi, Jepri, Setya, Ricat, David, Gesta dan Fauzi yang

memberikan dukungan kepada penulis selama studi.

10. Semua teman dari program studi Pendidikan Matematika angkatan 2012

yang memberikan dukungan kepada penulis selama studi.

11. Seluruh anggota dari Menwa Ignatian Universitas Sanata Dharma yang

selalu memberikan hal-hal baru kepada penulis.

12. Semua pihak yang tidak dapat disebutkan satu persatu yang telah membantu

sehingga penulis dapat menyelesaikan studi.

Akhirnya penulis berharap semoga skripsi ini dapat berguna bagi para

pembaca.

Penulis,

Petrus Tri Hariyadi


xi

DAFTAR ISI

HALAMAN JUDUL ............................................................................................... i

HALAMAN PERSETUJUAN PEMBIMBING ..................................................... ii

HALAMAN PENGESAHAN ............................................................................... iii

HALAMAN MOTTO ............................................................................................ iv

PERNYATAAN KEASLIAN KARYA ..................................................................v

LEMBAR PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH .. vi

ABSTRAK ............................................................................................................ vii

ABSTRACT ........................................................................................................... viii

KATA PENGANTAR ........................................................................................... ix

DAFTAR ISI .......................................................................................................... xi

DAFTAR GAMBAR ........................................................................................... xiii

DAFTAR NOTASI .............................................................................................. xvi

BAB I PENDAHULUAN

A. Latar Belakang ..................................................................................................... 1

B. Batasan Masalah .................................................................................................. 5

C. Rumusan Masalah ............................................................................................... 5

D. Tujuan Penelitian ................................................................................................ 5

E. Manfaat Penelitian .............................................................................................. 6

F. Metode Penelitian................................................................................................ 6

G. Sistematika Penulisan ......................................................................................... 7

BAB II KAJIAN PUSTAKA

A. Pengertian Graf .................................................................................................... 8

B. Jenis-jenis Graf .................................................................................................. 13

C. Pelabelan Graf ................................................................................................... 21

D. Dualitas Graf ...................................................................................................... 27


xii

BAB III PELABELAN TOTAL AJAIB SISI PADA GRAF RODA

A. Perhitungan Dasar Pelabelan Total Ajaib Sisi .............................................. 28

B. Perhitungan Dasar Pelabelan Total Ajaib Sisi Pada Graf Roda.................. 30

1. Batas Total Label Titik 𝑆𝑣 ...................................................................30

2. Batas Nilai Konstanta Ajaib k Untuk Setiap Graf Roda ......................31

3. Batas Nilai Titik Pusat c untuk Konstanta Ajaib k ..............................33

4. Pelabelan Titik dan Sisi Pada Graf Roda .............................................37

C. Pelabelan Total Ajaib Sisi Pada Graf Roda ................................................... 38

1. Pelabelan Total Ajaib Sisi Pada Graf Roda 𝑛 ≡ 0𝑚𝑜𝑑4 ....................39




BAB IV ALGORITMA PELABELAN TOTAL AJAIB SISI PADA GRAF RODA

A. Proses Pelabelan Total Ajaib Sisi Pada Graf Roda ...................................... 44

B. Diagram Alir Pelabelan Total Ajaib Sisi pada Graf Roda ........................... 46

1. Bagian Input (Menginput nilai 𝑛 dan 𝑘) ..............................................47

2. Bagian Pengolahan (Program perulangan) ..........................................48

3. Bagian Output (Mengeluarkan hasil) ...................................................52

C. Deskripsi Algoritma Pelabelan Total Ajaib Sisi pada Graf Roda .............. 52

1. Bagian Input (Menginput nilai 𝑛 dan 𝑘) ..............................................52

2. Bagian Pengolahan (Program perulangan) ..........................................53

3. Bagian Output (Mengeluarkan hasil) ...................................................58

D. Simulasi Pelabelan Total Ajaib Sisi pada Graf Roda ................................... 58

E. Kekurangan pelabelan dengan menggunakan software MATLAB 7.1 ....... 63

F. Contoh Pemanfaatan Pelabelan Total Ajaib Sisi pada Graf Roda .............. 64

BAB V PENUTUP

A. Kesimpulan ........................................................................................................ 69

B. Saran ................................................................................................................... 70

DAFTAR PUSTAKA ............................................................................................71

LAMPIRAN ...........................................................................................................72


xiii

DAFTAR GAMBAR

DAFTAR GAMBAR

Gambar 1.1 Diagram Alir Enkripsi dan Deskripsi ………………………... 2

Gambar 1.2 Proses Enkripsi dan Deskripsi sebuah pesan ………………… 2

Gambar 1.3 Pelabelan total ajaib sisi pada 𝑊6 dengan 𝑘 = 38 …………… 4

Gambar 2.1 Graf 𝐺1 dan 𝐺2………………………………………………… 8

Gambar 2.2 Bukan Graf …………………………………………………… 9

Gambar 2.3 Graf 𝐺3………………………………………………………... 9

Gambar 2.4 Graf 𝐺4………………………………………………………… 10

Gambar 2.5 Graf 𝐺5………………………………………………………... 11

Gambar 2.6 Graf Sederhana …..…………………………………………… 13

Gambar 2.7 Graf Tidak Sederhana

(a) graf ganda,

(b) graf semu ………………………………………………… 14

Gambar 2.8 Graf tidak berhingga ………………………………………… 15

Gambar 2.9 Graf tidak berarah …………………………………………… 16

Gambar 2.10 Graf berarah ………………………………………………….. 16

Gambar 2.11 Graf lengkap …………………………………………………. 17

Gambar 2.12 Graf sikel …………………………………………………….. 17

Gambar 2.13 Graf teratur …………………………………………………... 18

Gambar 2.14 Graf Lengkap 𝐾4 merupakan Graf Planar ……………………. 18

Gambar 2.15 Graf Lengkap 𝐾5 merupakan Graf Tidak Planar ……………... 19

Gambar 2.16 Operasi penggabungan graf ………………………………...... 20


xiv

Gambar 2.17 Graf roda …………………………………………………….. 20

Gambar 2.18 Penamaan elemen graf roda …………………………………. 21

Gambar 2.19 Label elemen graf roda ………………………………………. 22

Gambar 2.20 Pelabelan titik pada graf roda ………………………………... 22

Gambar 2.21 Pelabelan sisi pada graf roda ………………………………… 22

Gambar 2.22 Pelabelan total pada graf roda ……………………………….. 23

Gambar 2.23 Pelabelan total ajaib sisi pada graf roda 𝑊6 ………………… 25

Gambar 3.1 Pelabelan pada graf roda …………………………………….. 29

Gambar 3.2 Pelabelan pada graf roda …………………………………….. 34

Gambar 4.1 Diagram Alir Proses Pelabelan ………………………………. 46

Gambar 4.2 Diagram input nilai 𝑛 dan 𝑘 …………………………………. 47

Gambar 4.3 Diagram label 𝑐, 𝑣1 dan 𝑒1 …………………………………... 49

Gambar 4.4 Diagram label 𝑣, 𝑒 dan 𝑠1 sampai 𝑠𝑛−1 ……………………… 50

Gambar 4.5 Diagram label𝑠𝑛 …………………………………………….. 51

Gambar 4.6 Diagram output label 𝑐, 𝑣, 𝑒 dan 𝑠 …………………………… 52

Gambar 4.7 Tampilan awal pada 𝑐𝑜𝑚𝑚𝑎𝑛𝑑 𝑤𝑖𝑛𝑑𝑜𝑤 …………………… 58

Gambar 4.8 Tampilan input 𝑛 = 5 pada 𝑐𝑜𝑚𝑚𝑎𝑛𝑑 𝑤𝑖𝑛𝑑𝑜𝑤 …………… 59

Gambar 4.9 Tampilan hasil pelabelan dengan 𝑛 = 5 dan 𝑘 = 25 pada

𝑐𝑜𝑚𝑚𝑎𝑛𝑑 𝑤𝑖𝑛𝑑𝑜𝑤 …………………………………………. 59

Gambar 4.10 Tahap pertama ilustrasi hasil pelabelan ………………….…… 60

Gambar 4.11 Tahap kedua ilustrasi hasil pelabelan ………………………… 60

Gambar 4.12 Tahap ketiga ilustrasi hasil pelabelan ………………………… 61

Gambar 4.13 Tahap keempat ilustrasi hasil pelabelan ……………………… 62


xv

Gambar 4.14 Tahap kelima ilustrasi hasil pelabelan ……………………….. 62

Gambar 4.15 Pelabelan total ajaib sisi pada 𝑊6 …………..………………… 64


xvi

DAFTAR NOTASI

V(G) Himpunan titik di G

E(G) Himpunan sisi di G

𝑣𝑖 Titik ke-i

𝑣𝑖 , 𝑣𝑗 Sisi yang menghubungkan titik 𝑣𝑖 dengan 𝑣𝑗

𝑒𝑖 Sisi ke-i

Dalam graf roda berupa sisi pada jari-jari di mana 𝑒𝑖 bersisian dengan

𝑐 dan 𝑣𝑖

|𝑉(𝐺)| Order (banyaknya titik) pada G

|𝐸(𝐺)| Ukuran (banyaknya sisi) pada G

𝑑(𝑣𝑖) Degree (banyaknya sisi yang bersisian) pada titik 𝑣𝑖

𝐺 + 𝐻 Operasi penggabungan (Join) graf G dengan graf H

c Dalam graf roda berupa titik pusat

𝑠𝑖 Dalam graf roda berupa sisi pada sikel di mana 𝑠𝑖 bersisian dengan 𝑣𝑖

dan 𝑣𝑖+1

𝜆(𝑣𝑖) Label pada titik 𝑣𝑖

𝜆(𝑣𝑖 , 𝑣𝑗) Label pada sisi yang menghubungkan titik 𝑣𝑖 dengan 𝑣𝑗

𝑤𝑡(𝑣𝑖) Bobot pada titik 𝑣𝑖

𝑤𝑡(𝑣𝑖, 𝑣𝑗) Bobot pada sisi yang menghubungkan titik 𝑣𝑖 dengan 𝑣𝑗

𝑆𝑣 Jumlah semua label titik

𝑆𝑒 Jumlah semua label sisi

𝑆𝑤 Jumlah semua bobot sisi


1

BAB I

PENDAHULUAN

A. Latar Belakang

Ada berbagai permasalahan dalam kehidupan sehari-hari yang dapat

dimodelkan dalam diagram titik dan garis. Titik merepresentasikan objek

permasalahan dan garis merepresentasikan hubungan antara objek. Permodelan

semacam ini secara khusus dipelajari dalam matematika pada pokok bahasan

graf.

Representasi semacam ini dirasakan manfaatnya pada berbagai bidang

antara lain dalam perencanaan jalur transportasi, optimasi jaringan komunikasi,

model ikatan kimia, perencanaan alur pengunjung pameran, perancanaan

jaringan elekrik, dll.

Pelabelan graf merupakan kajian yang terdapat dalam teori graf yang

berkembang dan banyak diteliti. Kajian ini pertama kali diperkenalkan oleh

Sadlacek pada tahun 1963. Kemudian dikembangkan Steward pada tahun 1966

dan pada tahun 1970, Kotzig dan Rosa membahasnya dengan istilah valuation

dalam Wallis (2001). Pelabelan graf juga memiliki aplikasi yang cukup luas

dalam berbagai bidang seperti x-ray, kriptografi, sistem biometrik, radar

astronomi, desain sirkuit dan desain jaringan komunikasi.


2

Sebagai contoh dalam kriptografi penggunaan Mesin Enigma untuk

merubah sebuah pesan menjadi sebuah pesan acak (Enkripsi) dan merubah

pesan acak tersebut menjadi pesan yang sesungguhnya (Deskripsi) melalui

algoritma tertentu.

Gambar 1.1 Diagram Alir Enkripsi dan Deskripsi

Gambar 1.2 Proses Enkripsi dan Deskripsi sebuah pesan

Pada beberapa kasus, solusi dari permasalahan-permasalahan tersebut dapat

ditemukan dengan melakukan pelabelan pada sisi atau titiknya.

Pelabelan graf merupakan pelabelan yang memetakan setiap elemen graf ke

bilangan asli, beberapa jenis pelabelan menurut himpunan asalnya, yaitu

pelabelan titik (vertex labelings), pelabelan sisi (edge labeling) dan pelabelan

total (total labeling). Pelabelan titik merupakan pelabelan dengan himpunan


3

asal berupa titik, pelabelan sisi merupakan pelabelan dengan himpunan asal

berupa sisi, sedangkan pelabelan total adalah pelabelan yang himpunan asalnya

adalah titik dan sisi.

Bila pelabelan yang dilakukan memenuhi suatu nilai tertentu, maka

pelabelan graf dibedakan menjadi dua yakni pelabelan ajaib (magic labeling)

dan pelabelan tidak-ajaib (antimagic labeling). Pada pelabelan ajaib, bobot

elemen graf yang dievaluasai memenuhi suatu nilai tertentu, nilai ini selalu tetap

untuk semua elemen yang dievaluasi dan disebut konstanta ajaib. Sedangkan

pada pelabelan tidak-ajaib, nilai bobot elemen graf yang dievaluasi berbeda satu

dengan yang lainnya.

Pada penerapan pelabelan, bobot elemen yang dievaluasi dapat berupa titik

maupun sisi, sehingga terdapat banyak penerapan yang dapat digunakan.

Pelabelan total ajaib sisi merupakan pelabelan yang memetakan setiap

himpunan sisi dan titik ke himpunan bilangan asli {1,2,3,…, e + v} di mana e

dan v secara beruntun menyatakan banyaknya sisi dan titik, sedemikian hingga

jumlahan dari label sisi dan titik yang bersisian sama/konstan. Wallis (2001).

Pelabelan graf tersebut dapat diterapkan untuk memecahkan suatu

permasalahan dengan menggunakan model tertentu, sehingga label pada setiap

elemen yang dievaluasi dapat terhubung. Pada penerapannya, pelabelan total

ajaib sisi pada graf roda dapat digunakan sebagai kode yang diterapkan pada

suatu kartu, dimana kartu tersebut dapat digunakan untuk menggunakan dua

buah akses antara lain berdasarkan label yang terdapat pada kartu sebagai akses

untuk membuka suatu ruangan dan berdasarkan nilai konstanta ajaib yang di


4

terapkan pada kartu tersebut sebagai akses untuk menggunakan lift pada suatu

bangunan bertingkat.

Gambar 1.3 Pelabelan total ajaib sisi pada 𝑊6 dengan 𝑘 = 38

Sebagai contoh pada lantai 6 sebuah bangunan, terdapat 12 ruangan berbeda

di mana setiap ruangan memiliki kodenya masing-masing. Ruangan tersebut

hanya dapat dibuka dengan menggunakan kartu yang memiliki kode yang sama.

Misalkan kode pada ruangan 601 adalah 160319 sedangkan pada ruangan 602

adalah 160517. Pada saat menggunakan lift dari kedua kartu tersebut langsung

terintegrasi dengan lantai 6 karena nilai konstanta ajaib yang diterapkan pada

kedua kartu tersebut adalah 38.

Dalam penelitiannya, Kristinawati (2015) telah membuktikan bahwa

pelabelan total ajaib dengan model roda dengan bobot elemen yang dievaluasi

adalah titik dapat diberikan label dengan batasan banyaknya titik pada sikel

terletak pada (3 ≤ 𝑛 ≤ 11).

Berdasarkan penelitaian yang telah dilakukan oleh Kristinawati, peneliti

tertarik untuk meneliti pelabelan total ajaib dengan roda sebagai modelnya.

Pada penelitian ini, bobot elemen yang akan dievaluasi adalah sisi.

8

12 18

3

17

15 9

13

11

6

2

16

1

7

5

19

4 10

14


5

B. Batasan Masalah

Pada skripsi ini akan dibahas graf roda 𝑊𝑛 dan pelabelan total ajaib sisi pada

suatu nilai konstanta ajaib k tertentu. Algoritma pelabelan disimulasikan

menggunakan program MATLAB 7.1 untuk suatu nilai konstanta ajaib k

tertentu.

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 sisi berlaku pada graf roda?

2. Bagaimana rentang nilai konstanta ajaib yang terbentuk dalam pelabelan

total ajaib sisi pada graf roda?

3. Bagaimana cara memberikan label sisi dan titik pada graf roda untuk nilai

konstanta ajaib k?

D. Tujuan Penelitian

1. Mengetahui apakah pelabelan total ajaib sisi berlaku pada graf roda.

2. Mengetahui bagaimana rentang nilai konstanta ajaib yang terbentuk dalam

pelabelan total ajaib sisi pada graf roda.

3. Mengetahui cara memberikan label sisi dan titik pada graf roda untuk nilai

konstanta ajaib k.


6

E. Manfaat Penelitian

Manfaat penelitian ini adalah

1. Menambah wawasan mengenai pelabelan total ajaib sisi pada graf roda dan

rentang nilai konstanta ajaib k yang terbentuk.

2. Dapat memberikan label sisi dan titik pada graf roda dengan menetukan

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).

Penelitian ini menggunakan pendekatan kualitatif, sehingga pola pembahasan

dimulai dari hal-hal khusus (induktif) menuju pada sebuah generalisasi yang

bersifat umum (deduktif).

Secara garis besar langkah-langkah penelitian ini sebagai berikut:

1. Mengumpulkan literatur yang berhubungan dengan graf roda 𝑊𝑛.

2. Mempelajari graf roda 𝑊𝑛.

3. Menganalisa sifat-sifat pelabelan total ajaib sisi.

4. Menentukan apakah pelabelan total ajaib sisi berlaku pada roda 𝑊𝑛, dan

menentukan rentang nilai konstanta ajaibnya.

5. Menentukan cara memberikan label sisi dan titik pada graf roda untuk nilai

konstanta ajaib tertentu.


7

G. Sistematika Penulisan

Sistematika penulisan tugas akhir ini dibagi menjadi lima bagian, yakni

Bab I : Pendahuluan

Pada bab ini dijelaskan tentang latar belakang, rumusan masalah, pembatasan

masalah, tujuan penelitian, manfaat penelitian, metode penelitian dan

sistematika penulisan.

Bab II : Kajian Pustaka

Pada bab ini dijelaskan tentang teori graf dasar, jenis-jenis graf, pelabelan graf

dan kerangka berpikir.

Bab III : Pelabelan Total Ajaib Sisi pada Graf Roda

Pada bab ini dianalisis menganai perhitungan dasar untuk menentukan nilai

konstanta ajaib, dan rentang konstanta ajaib berdasarkan struktur graf roda.

Bab IV : Algoritma Pelabelan Total Ajaib Sisi pada Graf Roda

Algoritma pelabelan total ajaib sisi 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.


8

BAB II

KAJIAN PUSTAKA

A. Pengertian Graf

Dalam mempelajari graf, terdapat beberapa teori dasar untuk mendukung

pembuktian dan mempermudah pemahaman. Googaire dan Parmenter (1998)

mendefinisikan graf sebagai:

Definisi 2.1 Graf (Googaire dan Parmenter, 1998)

Graf adalah himpunan pasangan G = (V,E) di mana V(G) adalah himpunan

tak kosong dan himpunan pasangan elemen yang berbeda pada E(G).

Elemen V(G) disebut titik (vertex) dan elemen E(G) disebut sisi (edge). Jika

e ∈ E(G) maka e merupakan himpunan pasangan e = (𝑣𝑖, 𝑣𝑗 ) di mana

𝑣𝑖 , 𝑣𝑗 ∈ V(G) di mana 𝑣𝑖 dan 𝑣𝑗 disebut titik ujung dari e atau dengan kata

lain e =(𝑣𝑖, 𝑣𝑗) yang menghubungkan titik 𝑣𝑖 dan 𝑣𝑗 .

Chartrand dan Oellermann (1993) mengemukakan bahwa secara geografis

graf dapat digambarkan dengan sekumpulan titik pada bidang dimensi dua yang

dihubungkan dengan sekumpulan sisi.

(a) Graf 𝐺1 (b) Graf 𝐺2

Gambar 2.1 Graf

𝑣1

𝑣2

𝑣3

𝑣4 𝑣2 𝑣5

𝑒1 𝑣1

𝑒3

𝑒4 𝑒6

𝑒2

𝑣3 𝑣4 𝑒5

𝑣6


9

Gambar 2.2 Bukan Graf

Pada Gambar 2.2 bukan merupakan suatu graf karena tidak memenuhi

Definisi 2.1 yaitu V(G) himpunan kosong.

Dengan mendalami pengertian pada Definisi 2.1, himpunan di V(G) pada

sebuah graf bukanlah himpunan kosong sehingga dapat dipastikan terdapat

minimal sebuah unsur di V(G) pada sebuah graf. Banyaknya unsur yang

terdapat pada V(G) menentukan order dari graf tersebut.

Definisi 2.2 Order (Googaire dan Parmenter, 1998)

Banyaknya unsur di V(G) pada graf tersebut disebut order dari G

dilambangkan dengan |V(G)|.

Pada Gambar 2.1 (a), banyaknya unsur V(G) pada graf 𝐺1 adalah 4 sehingga

order dari graf 𝐺1 atau |V(G)| = 4

Berdasarkan Definisi 2.1 diketahui bahwa V(G) bukanlah himpunan kosong

sehingga |V(G)| lebih besar sama dengan satu. Antara satu unsur V(G) dengan

yang lainnya dimungkinkan adanya unsur E(G) yang menghubungkan dua buah

unsur V(G) seperti gambar dibawah ini.

Gambar 2.3 Graf 𝐺3

𝑣1

𝑣2

𝑣3

𝑣4

𝑣5

𝑒5

𝑒1

𝑒2 𝑒3

𝑒4


10

Dengan memperhatikan Gambar 2.3 graf 𝐺3, antara satu unsur V(G) dengan

yang lainnya ada yang dihubungkan melalui E(G) dan ada yang tidak. Titik 𝑣1

bertetangga dengan titik 𝑣2 dan 𝑣4 karena adanya unsur E(G) yaitu e yang

menghubungkan dua buah titik tersebut, tetapi titik 𝑣1 tidak bertetangga dengan

𝑣3 dan 𝑣5.

Definisi 2.3 Ketetanggaan (Munir, 2001)

Dua titik 𝑣𝑖 dan 𝑣𝑗 pada graf G dikatakan bertetangga bila terdapat sisi yang

menghubungkan kedua titik tersebut. e = (𝑣𝑖, 𝑣𝑗) ∈ E(G) di mana 𝑣𝑖 ≠ 𝑣𝑗 .


Dengan adanya Definisi 2.3, diantara dua titik yang bertetangga pasti

terdapat sisi e yang menghubungkan kedua titik tersebut, tetapi tidak terdapat

batasan berapa banyaknya sisi yang menghubungkan kedua titik yang

bertetangga tersebut. Pada Gambar 2.4 graf 𝐺4 memiliki lebih dari satu sisi yang

menghubungkan kedua titik 𝑣1 dan 𝑣2 yaitu 𝑒4 dan 𝑒7.

Definisi 2.4 Sisi ganda (Munir, 2001)

Graf G dikatakan memiliki sisi ganda jika pada graf G tersebut terdapat titik

𝑣𝑖 dan 𝑣𝑗 yang dihubungkan oleh lebih dari satu sisi.

𝑣1

𝑣2

𝑣3

𝑣4

𝑒1

𝑒2 𝑒3

𝑒4 𝑒5

𝑒6

𝑒7


11

Dengan adanya Definisi 2.3, diantara dua titik yang bertetangga pasti

terdapat sisi e yang menghubungkan kedua titik tersebut, oleh sebab itu sisi e

akan bersisian dengan kedua titik tersebut. Sebagai contoh pada Gambar 2.4 sisi

𝑒1 bersisian dengan titik 𝑣1 dan 𝑣2, tetapi tidak bersisian dengan 𝑣4.

Definisi 2.5 Bersisian (Munir, 2001)

Untuk sembarang sisi 𝑒 = (𝑢, 𝑣) dikatakan 𝑒 bersisisan dengan titik 𝑢 dan

𝑒 bersisian dengan titik 𝑣.


Dengan mendalami Definisi 2.5, di mana sebuah sisi dikatakan bersisian

dengan dua buah titik yang dihubungkan oleh sisi tersebut, tetapi tidak terdapat

batasan apakah kedua titik yang dihubungkan oleh sisi tersebut merupakan titik

yang berbeda. Seperti pada Gambar 2.5 graf 𝐺5 terdapat sebuah sisi 𝑒8 yang

menghubungkan sebuah dua buah titik yang sama yaitu 𝑣4 . Sisi yang

menghubungkan dua buah titik yang sama disebut gelang.

Definisi 2.6 Gelang (Munir, 2001)

Gelang (loop) merupakan sisi yang bersisian dengan dua buah titik yang

sama. Jika 𝑒 = (𝑢, 𝑢) maka 𝑒 adalah gelang.

𝑣1

𝑣2

𝑣3

𝑣4

𝑒1

𝑒2 𝑒3

𝑒4 𝑒5

𝑒6

𝑒7 𝑒8


12

Berdasarkan Definisi 2.5 sebuah titik bersisian dengan sebuah sisi jika sisi

tersebut menghubungkan dua buah titik namun tidak terdapat batasan mengenai

banyaknya sisi yang bersisian dengan titik tersebut, sehingga banyaknya sisi

yang bersisian dengan sebuah titik dapat dinyatakan derajat dari titik tersebut.

Definisi 2.7 Derajat (Munir, 2001)

Derajat (degree) titik v atau d(v) adalah banyaknya sisi yang bersisian dengan

titik v.

Jika 𝑑(𝑣𝑖) = 0 maka 𝑣𝑖 disebut titik terisolasi (isolated vertex).

Jika 𝑑(𝑣𝑖) = 1, maka 𝑣𝑖 disebut antingan (pendant vertex).

Pada sembarang gelang 𝑒 = (𝑣𝑖, 𝑣𝑖), 𝑑(𝑣𝑖) = 2.

Berdasarkan Gambar 2.5 diketahui bahwa:

𝑣1 bersisian dengan 𝑒1, 𝑒4 dan 𝑒7 sehingga 𝑑(𝑣1) = 3

𝑣2 bersisian dengan 𝑒1, 𝑒2 dan 𝑒5 sehingga 𝑑(𝑣2) = 3

𝑣4 bersisian dengan 𝑒3, 𝑒4, 𝑒5𝑒6, 𝑒7 dan gelang 𝑒8 sehingga 𝑑(𝑣3) = 7

Berdasarkan Definisi 2.3 di mana dua titik dikatakan bertetangga jika

terdapat sisi yang menghubungan kedua titik tersebut. Banyaknya sisi pada

sebuah graf menyatakan ukuran (size) dari graf tersebut.

Definisi 2.8 Ukuran (Googaire dan Parmenter, 1998)

Banyaknya unsur pada E(G) disebut ukuran (size) dari G dilambangkan

dengan |E(G)|.

Pada Gambar 2.1 (b), banyaknya unsur E(G) pada graf 𝐺2 adalah 6 sehingga

order dari graf 𝐺2 atau |E(G)| = 6


13

B. Jenis-jenis Graf

Dengan banyaknya kemungkinan bentuk graf, graf dapat dibagi menjadi

beberapa jenis. Berikut ini pembagian jenis graf menurut sifat-sifat yang

terdapat pada graf:

1. Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf

Dengan banyaknya bentuk-bentuk graf, mungkin saja terdapat sisi

ganda pada graf tersebut sehingga graf dikelompokan menjadi dua yakni:

Definisi 2.9 Graf sederhana (Munir, 2001)

Graf sederhana merupakan graf yang tidak mengandung gelang maupun

sisi ganda. Berikut ini pada Gambar 2.6 merupakan contoh dari graf

sederhana.

Gambar 2.6 Graf sederhana

Definisi 2.10 Graf tidak sederhana (Munir, 2001)

Graf tidak sederhana merupakan graf yang mengandung gelang atau sisi

ganda.

𝑣1

𝑣2

𝑣3

𝑣4

𝑒1

𝑒2 𝑒3

𝑒4

𝑒5


14

Graf tidak sederhana dibedakan menjadi dua macam, yakni:

Gambar 2.7 Graf tidak sederhana

a. Graf ganda (𝑚𝑢𝑙𝑡𝑖𝑔𝑟𝑎𝑝ℎ) adalah graf yang mengandung sisi

ganda. Graf pada Gambar 2.7 (a) adalah contoh graf ganda.

b. Graf semu (𝑝𝑠𝑒𝑢𝑑𝑜𝑔𝑟𝑎𝑝ℎ) graf yang mengandung sisi ganda dan

gelang. Graf pada Gambar 2.7 (b) merupakan contoh graf semu.

Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf,

peneliti akan meneliti mengenai graf sederhana.

2. Berdasarkan banyaknya titik pada suatu graf

Berdasarkan Definisi 2.1 di mana graf dikatakan benar sebuah graf jika

V(G) adalah himpunan tak kosong, tetapi tidak terdapat batasan banyaknya

himpunan yang terdapat V(G) berhingga ataupun tidak, sehingga

dimungkinkan graf dikelompokan menjadi dua macam, yakni:

Definisi 2.11 Graf berhingga (Munir, 2001)

Graf berhingga merupakan graf yang banyaknya titik berhingga.

Graf pada Gambar 2.7 merupakan contoh graf berhingga.

𝑣1

𝑣2

𝑣3

𝑣4

𝑒1

𝑒2 𝑒3

𝑒4 𝑒5

𝑒6

𝑒7 𝑣1

𝑣2

𝑣3

𝑣4

𝑒1

𝑒2 𝑒3

𝑒4 𝑒5

𝑒6

𝑒7 𝑒8

(a) Graf ganda (b) Graf semu


15

Definisi 2.12 Graf tidak berhingga (Munir, 2001)

Graf tidak berhingga adalah graf yang banyak titik tidak berhingga.

Berikut ini pada Gambar 2.8 merupakan contoh dari graf tidak

berhingga.

Gambar 2.8 Graf tidak berhingga

Graf pada Gambar 2.8 merupakan contoh graf tidak berhingga karena

banyaknya titik pada Gambar 2.8 tidak berhingga.

Berdasarkan banyaknya titik pada suatu graf, peneliti akan meneliti

mengenai graf berhingga.

3. Berdasarkan arah pada sisi

Berdasarkan Definisi 2.3 di mana dua titik dikatakan bertetangga jika

terdapat sebuah sisi yang menghubungkan kedua titik tersebut, namun tidak

terdapat batasan mengenai arah pada sisi tersebut sehingga secara umum

graf dikelompokan menjadi dua jenis, yakni:

Definisi 2.13 Graf tidak berarah (Munir, 2001)

Graf tidak berarah adalah graf yang sisinya tidak memiliki arah sehingga

urutan pasangan titik yang dihubungkan tidak diperhatikan.


16

Gambar 2.9 Graf tidak berarah

Definisi 2.14 Graf berarah (Munir, 2001)

Graf berarah adalah graf yang setiap sisinya diberi arah, sehingga urutan

pasangan titik diperhatikan. Pada graf berarah (𝑣𝑖, 𝑣𝑗) berbeda dengan

(𝑣𝑗 , 𝑣𝑖) , sebab (𝑣𝑖 , 𝑣𝑗) 𝑣𝑖 adalah titik awal (𝑖𝑛𝑖𝑡𝑖𝑎𝑙 𝑣𝑒𝑟𝑡𝑒𝑥) dan 𝑣𝑗

merupakan titik terminal (𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙 𝑣𝑒𝑟𝑡𝑒𝑥). Sementara pada (𝑣𝑗 , 𝑣𝑖)

berlaku sebaliknya. Sisi berarah pada graf berarah disebut busur (𝑎𝑟𝑐).

Berikut ini pada Gambar 2.10 merupakan contoh dari graf berarah.

Gambar 2.10 Graf berarah

Berdasarkan arah pada sisi, peneliti akan meneliti mengenai graf tidak

berarah.

Berdasarkan tiga jenis pengelompokan di atas, peneliti akan mengenai

tentang graf sederhana yang berhingga dan tidak tidak berarah.

𝑣1

𝑣2

𝑣3

𝑣4

𝑒1

𝑒2 𝑒3

𝑒4

𝑒5

𝑣1

𝑣2

𝑣3

𝑣4

𝑒1

𝑒2 𝑒3

𝑒4

𝑒5


17

Selain pengelompokan berdasarkan sifat-sifat di atas, terdapat beberapa

jenis graf sederhana khusus, antara lain:

1. Graf lengkap (𝐶𝑜𝑚𝑝𝑙𝑒𝑡𝑒 𝐺𝑟𝑎𝑝ℎ)

Graf lengkap adalah graf sederhana yang di mana setiap titiknya saling

bertetangga. Graf lengkap dengan 𝑛 buah simpul dilambangkan dengan 𝐾𝑛.

Gambar berikut ini merupakan contoh dari graf lengkap:

Gambar 2.11 Graf lengkap

2. Graf Sikel

Graf sikel 𝐶𝑛 merupakan graf sederhana yang setiap titiknya berderajat dua.

Graf sikel dengan 𝑛 buah simpul dilambangkan dengan 𝐶𝑛. Gambar berikut

ini merupakan contoh dari graf sikel:

Gambar 2.12 Graf sikel

𝐾1 𝐾2 𝐾3 𝐾4 𝐾5

𝐶3 𝐶4 𝐶5


18

3. Graf teratur (𝑅𝑒𝑔𝑢𝑙𝑎𝑟 𝐺𝑟𝑎𝑝ℎ)

Graf teratur adalah graf yang setiap titiknya memiliki derajat yang sama.

Graf lengkap 𝐾𝑛 adalah graf teratur berderajat (𝑛 − 1) . Graf sikel 𝐶𝑛

adalah graf teratur berderajat dua. Gambar berikut ini merupakan contoh

dari graf teratur:

Gambar 2.13 Graf teratur

4. Graf Planar (Planar Graph) dan Graf Bidang (Plane Graph)

Suatu graf disebut graf planar jika graf tersebut dapat digambarkan pada

bidang datar sedemikian sehingga tidak ada sisi yang berpotongan kecuali

di titik di mana keduanya bersisian. Graf planar yang digambarkan dengan

sisi-sisi yang tidak saling berpotongan dinamakan graf bidang. Suatu graf

mungkin saja planar meskipun biasanya digambarkan saling berpotongan,

karena graf tersebut dapat digambarkan dengan cara yang berbeda. Gambar

berikut ini akan memperjelas mengenai graf planar:

Gambar 2.14 Graf Lengkap 𝐾4 merupakan Graf Planar


19

Gambar 2.15 Graf Lengkap 𝐾5 merupakan Graf Tidak Planar

Penelitian dan perkembangan pokok bahasan graf, memunculkan beberapa

jenis graf baru. Graf tersebut diperoleh dengan melakukan operasi

penggabungan, penghapusan sisi atau titik (𝑒𝑑𝑔𝑒 𝑜𝑟 𝑣𝑒𝑟𝑡𝑒𝑥 𝑑𝑒𝑙𝑒𝑡𝑖𝑛𝑔) pada

suatu graf.

Dua buah graf yang saling tidak terhubung dapat dibuat sebuah graf baru

dengan cara melakukan operasi penggabungan (Join).

Definisi 2.15 Penggabungan graf (Join) (Buckley & Lewinter, 2002)

Dua buah graf yang saling tidak terhubung (graf G dan graf H) dapat dibuat

sebuah graf baru dengan cara melakukan operasi penggabungan (Join).

Operasi penggabungan pada graf dapat dilakukan dengan cara menjadikan

setiap titik yang terdapat pada graf G bertetangga dengan setiap titik yang

terdapat pada graf H, dilambangkan dengan G + H.


20

Berikut ini contoh operasi penggabungan pada graf:

Gambar 2.16 Operasi penggabungan graf

Graf roda 𝑊1,𝑛 merupakan graf yang dibangun dengan melakukan operasi

penggabungan pada graf lengkap 𝐾1 dengan graf sikel 𝐶𝑛 , dapat dinotasikan

𝑊1,𝑛 = 𝐾1 + 𝐶𝑛 . Selanjutnya pada skripsi ini, graf 𝑊1,𝑛 akan disebut 𝑊𝑛

dengan 𝑛 mengacu pada banyaknya titik padak graf sikel. Berikut ini beberapa

contoh graf roda 𝑊𝑛:

Gambar 2.17 Graf roda

Dengan memperhatikan cara terbentuknya, graf roda 𝑊𝑛 memiliki titik

(order) sebanyak (𝑛 + 1) dengan banyaknya sisi (size) yaitu 2𝑛 . Titik 𝑣1

sampai 𝑣𝑛 merujuk titik pada sikel. Sisi pada sikel mendapatkan label 𝑠1 sampai

𝑠𝑛. Sisi yang menghubungkan titik pusat dengan titik pada sikel disebut jari-

jari. Label jari-jari dapat dinyatakan pula dengan 𝑒𝑖 = {𝑐, 𝑣𝑖} untuk 1 ≤ 𝑖 ≤ 𝑛.

Pola penamaan secara grafis pada graf roda diperagakan pada gambar berikut.

𝑊3 𝑊4 𝑊5

(a) Graf 𝑃3 (b) Graf 𝑃5 (c) Graf (𝑃3

+ 𝑃5)


21

Gambar 2.18 Penamaan elemen graf roda

Gambar 2.19 Label elemen graf roda

C. Pelabelan Graf

Dengan memperhatikan struktur yang terdapat pada suatu graf, graf tersebut

memiliki titik (order) sebanyak 𝑣 = |𝑉(𝐺)| dengan banyaknya sisi (size) yaitu

𝑒 = |𝐸(𝐺)|. Jika setiap elemen yang terdapat pada graf tersebut diberikan label,

maka banyaknya label yang akan diberikan pada graf tersebut sebanyak 𝑣 + 𝑒.

Pelabelan pada graf merupakan pelabelan yang memetakan setiap elemen pada

graf tersebut ke bilangan asli 1,2,3, … sebanyak elemen yang akan berikan label

pada graf tersebut.

Titik (𝑣)

Sisi (𝑠)

Jari-jari

(𝑒)

Titik tengah

(𝑐)

𝑣2

𝑣1

𝑣3

𝑣4

𝑣5 𝑣𝑛

𝑣𝑛−1

𝑣𝑛−2

𝑒1 𝑒2 𝑒3

𝑒4

𝑒5 𝑒𝑛

𝑒𝑛−1 𝑒𝑛−2

𝑠1 𝑠2

𝑠3

𝑠4 𝑠𝑛

𝑠𝑛−1

𝑠𝑛−2

𝑐


22

Berdasarkan Definisi 2.1 graf adalah himpunan pasangan G = (V,E) di mana

V(G) adalah himpunan tak kosong dan himpunan pasangan elemen yang

berbeda pada E(G), maka pelabelan graf merupakan pelabelan yang memetakan

setiap elemen pada graf ke bilangan asli. Pelabelan pada graf dibagi antara lain:

1. Pelabelan titik (𝑣𝑒𝑟𝑡𝑒𝑥 𝑙𝑎𝑏𝑒𝑙𝑖𝑛𝑔𝑠)

Pelabelan titik merupakan pelabelan yang himpunan asalnya titik.

Gambar 2.20 Pelabelan titik pada graf roda

2. Pelebelan sisi (𝑒𝑑𝑔𝑒 𝑙𝑎𝑏𝑒𝑙𝑖𝑛𝑔𝑠)

Pelabelan sisi merupakan pelabelan yang himpunan asalnya sisi.

Gambar 2.21 Pelabelan sisi pada graf roda

3. Pelabelan total (𝑡𝑜𝑡𝑎𝑙 𝑙𝑎𝑏𝑒𝑙𝑖𝑛𝑔𝑠)

Pelabelan total merupakan pelabelan yang domainnya titik dan sisi.

Pada pelabelan total, banyaknya elemen titik yang akan diberikan label

sebanyak v dan benyaknya elemen sisi yang akan diberikan label sebanyak

e, sehingga banyaknya elemen yang akan diberikan label pada pelabelan

3

5

7

1

4

6

2

3

5

7 1

4

6

2

8

9

10

11

12


23

total sebanyak 𝑣 + 𝑒. Oleh sebab itu pemetaan total yang terdapat pada

suatu graf merupakan pemetaan 𝑉(𝐺) ∪ 𝐸(𝐺) ke bilangan asli 1,2, … , 𝑣 +

𝑒.

Pelabelan total pada graf merupakan pemetaan yang memetakan setiap

elemen yang terdapat pada graf tersebut ke ke bilangan asli 1,2,3, … , 𝑣 + 𝑒.

Pelabelan yang diberikan untuk setiap elemen pada graf berbeda satu

dengan yang lainnya dan setiap bilangan asli 1,2,3, … , 𝑣 + 𝑒 memiliki

prapeta pada 𝑉(𝐺) ∪ 𝐸(𝐺). Oleh sebab itu pelabelan pada graf merupakan

pemetaan yang bijektif.

Definisi 2.16 Pelabelan total pada graf (Wallis, 2001)

Pelabelan total pada suatu graf G adalah pemetaan bijektif 𝜆 dari

𝑉(𝐺) ∪ 𝐸(𝐺) ke bilangan asli 1,2, … , 𝑣 + 𝑒 , di mana 𝑣 = 𝑉(𝐺) dan

𝑒 = 𝐸(𝐺).

Gambar 2.22 Pelabelan total pada graf roda

Dengan adanya pelabelan total, di mana domainnya adalah titik dan sisi

maka dapat diperoleh bobot elemen di mana bobot elemen adalah hasil

penjumlahan label yang dievaluasi dengan label elemen yang bersisisan.

1

2 3

4

5

6 7

8

9

10

11

12

13

14

15

16

17 18

19


24

Definisi 2.17 Bobot titik (Stewart, 1966)

Bobot titik merupakan bobot yang diperoleh dari titik yang dievaluasi dan

semua sisi yang bersisian dengan titik tersebut.

Bobot titik x pada pelabelan 𝜆 dinyatakan sebagai berikut:

𝑤𝑡(𝑣𝑖) = 𝜆(𝑣𝑖) + ∑ 𝜆(𝑣𝑖, 𝑣𝑗)

∑ 𝜆(𝑣𝑖, 𝑣𝑗) adalah semua sisi yang bersisian dengan dengan titik 𝑣𝑖

Berdasarkan Gambar 2.22 bobot titik pada titik (16) adalah

𝑤𝑡(16) = 16 + 13 + 4 + 11

= 44

Definisi 2.18 Bobot sisi (Stewart, 1966)

Bobot sisi merupakan bobot yang diperoleh dari sisi dan dua buah titik

bertetangga di mana kedua titik tersebut dihubungkan oleh sisi tersebut.

Bobot sisi 𝑥𝑦 pada pelabelan 𝜆 dinyatakan sebagai berikut

𝑤𝑡(𝑣𝑖 , 𝑣𝑗) = 𝜆(𝑣𝑖,) + (𝑣𝑖 , 𝑣𝑗) + 𝜆(𝑣𝑗)

Berdasarkan Gambar 2.22 bobot titik pada sisi (4) adalah

𝑤𝑡(4) = 4 + 16 + 12

= 32

Berdasarkan hasil bobot elemen graf yang dievaluasi, bobot elemen

memiliki hasil yang beragam, tetapi berdasarkan hasil tersebut pelabelan graf

dapat dibagi menjadi dua jenis yaitu sama dan tidak sama.

Definisi 2.19 Pelabelan ajaib (Wallis, 2001)

Pelabelan ajaib (magic labelings) adalah suatu pelabelan di mana bobot

setiap elemen yang dievaluasi sama.


25

Definisi 2.20 Pelabelan tak-ajaib (Wallis, 2001)

Pelabelan tak-ajaib ( antimagic labelings) adalah suatu pelabelan bobot

elemen yang dievaluasi tidak sama.

Berdasarkan jenis pelabelan graf dan bobot elemen graf yang dievaluiasi,

peneliti akan meneliti mengenai pelabelan ajaib dengan bobot elemen yang

dievaluasi adalah sisi.

Berdasarkan himpunan asal, bobot dan elemen graf yang dievaluasi terdapat

pelabelan total ajaib sisi (𝑒𝑑𝑔𝑒 − 𝑚𝑎𝑔𝑖𝑐 𝑡𝑜𝑡𝑎𝑙 𝑙𝑎𝑏𝑒𝑙𝑖𝑛𝑔𝑠) (𝐸𝑀𝑇𝐿)

Pelabelan total ajaib sisi merupakan pemetaan bijektif 𝜆 dari 𝑉(𝐺) ∪

𝐸(𝐺) ke bilangan asli {1,2,3, … , 𝑣 + 𝑒} dengan 𝑣 = |𝑉(𝐺)| dan 𝑒 =

|𝐸(𝐺)| sedemikian sehingga untuk setiap sisi 𝑥𝑦 ∈ 𝐸(𝐺) berlaku 𝜆(𝑥) +

𝜆(𝑥𝑦) + 𝜆(𝑦) = 𝑘 untuk setiap konstanta ajaib 𝑘 (Wallis, 2001).

Pelabelan total ajaib sisi, adalah pemetaan di mana setiap elemen (sisi

dan titik) diberikan label bilangan asli 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 dan dievaluasi dengan dua buah label titik yang

bersisian dengan sisi tersebut.

Gambar 2.23 Pelabelan total ajaib sisi pada graf roda 𝑊6

1

2 3

4

5

6 7

8

9

10

11

12

13

14

15

16

17 18

19


26

Pada Gambar 2.23 graf roda 𝑊6 memiliki konstanta ajaib 32. Setiap sisi

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

bertetangga dengan titik berlabel 12 dan 19, sehingga bobot sisinya adalah:

Sisi berlabel 1 memiliki bobot 𝑤𝑡(1) = 1 + 12 + 19 = 32












Berdasarkan penelitiannya, Wallis menyatakan sebuah graf G di mana

banyaknya sisi pada graf G genap, 𝑣 + 𝑒 ≡ 2(𝑚𝑜𝑑 4) dan untuk setiap titik

pada graf G berderajat ganjil maka graf G tersebut tidak memiliki pelabelan

total ajaib sisi.


27

D. Dualitas Graf

Googaire dan Parmenter (1998) menyatakan sebuah graf tertentu dapat

dibentuk pelabelan baru dari pelabelan yang ada.

Suatu pelabelan 𝜆 dual dengan pelabelan 𝜆′ didefiniskan sebagai

𝜆′(𝑥𝑖) = (𝑣 + 𝑒 + 1) − 𝜆(𝑥) untuk sembarang titik 𝑥𝑖

𝜆′(𝑥𝑦) = (𝑣 + 𝑒 + 1) − 𝜆(𝑥𝑦) untuk sembarang sisi 𝑥𝑦

Dengan demikian pelabelan 𝜆′ merupakan pelabelan dari 𝑉(𝐺) ∪ 𝐸(𝐺) ke

bilangan positif {1,2,3, … , 𝑣 + 𝑒} dan pelabelan 𝜆′ disebut dual dari pelabelan

𝜆 . Pada pelabelan 𝜆 , bobot elemen yang dievaluasi dinyatakan sebagai

konstanta ajaib 𝑘.

Pada pelabelan 𝜆′, bobot elemen dievaluasi diperoleh dengan

𝑘′ = 𝜆′(𝑥) + 𝜆′(𝑥𝑦) + 𝜆′(𝑦)

= ((𝑣 + 𝑒 + 1) − 𝜆(𝑥)) + ((𝑣 + 𝑒 + 1) − 𝜆(𝑥𝑦)) + ((𝑣 + 𝑒 + 1) − 𝜆(𝑦))

= 3(𝑣 + 𝑒 + 1) − (𝜆(𝑥) + 𝜆(𝑥𝑦) + 𝜆(𝑦))

= 3(𝑣 + 𝑒 + 1) − 𝑘


28

BAB III


A. Perhitungan Dasar Pelabelan Total Ajaib Sisi

Berdasarkan Definisi 2.16, Definisi 2.18 dan Definisi 2.19, pelabelan total

ajaib sisi pada graf merupakan pemetaan bijektif 𝜆 dari 𝑉(𝐺) ∪ 𝐸(𝐺) ke

bilangan asli 1,2, … , 𝑣 + 𝑒, di mana 𝑣 = 𝑉(𝐺) dan 𝑒 = 𝐸(𝐺), di mana untuk

setiap sisi (𝑣𝑖, 𝑣𝑗) berlaku

𝜆(𝑣𝑖) + 𝜆(𝑣𝑖, 𝑣𝑗) + 𝜆(𝑣𝑗) = 𝑘

(3.1)

untuk setiap nilai konstanta k. Dengan kata lain, 𝑤𝑡(𝑣𝑖, 𝑣𝑗) = 𝑘 untuk setiap

sisi yang terdapat pada graf tersebut. Selanjutnya 𝑘 disebut dengan nilai

konstanta ajaib dari graf 𝐺. Wallis (2001).

Pada pelabelan ajaib, nilai konstanta ajaib 𝑘 akan ditentukan lebih dahulu.

Melalui perhitungan dasar akan diperoleh batas nilai kostanta ajaib 𝑘, sehingga

dapat ditentukan suatu pelabelan untuk nilai konstanta ajaib 𝑘. Misalkan 𝑀 =

𝑣 + 𝑒, 𝑆𝑒 adalah jumlah seluruh label sisi dan 𝑆𝑣 adalah jumlah seluruh label

titik dengan setiap label adalah bilangan bulat 1,2,3, … , 𝑀 sehingga jumlah

semua label adalah

𝑆𝑒 + 𝑆𝑣 = ∑ 𝑖

𝑀

𝑖=1

=𝑀(𝑀 + 1)

2

(3.2)


29

Gambar 3.1 Pelabelan pada graf roda

Pada pelabelan total ajaib sisi khususnya pada roda, label sisi dihitung

sebanyak satu kali dan label titik dihitung sebanyak tiga kali kecuali untuk label

titik pusat (c) dihitung sebanyak 𝑛-kali. Berdasarkan persamaan (3.1) sehingga

diperoleh

𝑆𝑤 = 𝑒1 + 𝑒2 + ⋯ + 𝑒𝑛 + 𝑠1 + 𝑠2 + ⋯ + 𝑠𝑛 + 3𝑣1 + 3𝑣2 + ⋯ + 3𝑣𝑛 + 𝑛𝑐

= (𝑒1 + 𝑒2 + ⋯ + 𝑒𝑛 + 𝑠1 + 𝑠2 + ⋯ + 𝑠𝑛) +

3𝑣1 + 3𝑣2 + ⋯ + 3𝑣𝑛 + 3𝑐 + (𝑛 − 3)𝑐

= 𝑆𝑒 + 3(𝑣1 + 𝑣2 + ⋯ + 𝑣𝑛 + 𝑐) + (𝑛 − 3)𝑐

= 𝑆𝑒 + 3Sv + (n − 3)c

2𝑛𝑘 = (𝑆𝑒 + 𝑆𝑣) + 2𝑆𝑣 + (n − 3)c

=𝑀(𝑀 + 1)

2+ 2𝑠𝑣 + (n − 3)c

𝑘 =

𝑀(𝑀+1)

2+ 2𝑠𝑣 + (n − 3)c

2n

(3.3)

Berdasarkan persamaan tersebut maka label titik perlu diketahui lebih

dahulu sementara label sisi dapat ditentukan dengan mengurangkan nilai

konstanta ajaib dengan label titik yang bersisian dengan sisi tersebut.

𝑣2

𝑣1

𝑣3

𝑣4

𝑣5

𝑣𝑛

𝑣𝑛−1

𝑣𝑛−2

𝑒1 𝑒2 𝑒3

𝑒4

𝑒5 𝑒𝑛

𝑒𝑛−1 𝑒𝑛−2

𝑠1 𝑠2

𝑠3

𝑠4 𝑠𝑛

𝑠𝑛−1

𝑠𝑛−2

𝑐


30

Untuk kepentingan pelabelan, batas 𝑆𝑣 perlu ditentukan. Batas bawah

diperoleh dengan memberikan label terkecil sebanyak 𝑣 titik dan batas atas

diperoleh dengan memberikan label terbesar, sehingga

∑ 𝑖

𝑣

𝑖=1

≤ 𝑆𝑣 ≤ ∑ 𝑖

𝑣+𝑒

𝑖=𝑒+1

∑ 𝑖

𝑣

𝑖=1

≤ 𝑆𝑣 ≤ (𝑒 + 1) + (𝑒 + 2) + ⋯ + (𝑣 + 𝑒)

∑ 𝑖

𝑣

𝑖=1

≤ 𝑆𝑣 ≤ (1 + 2 + ⋯ + (𝑣 + 𝑒)) − (1 + 2 + ⋯ + 𝑒)

∑ 𝑖

𝑣

𝑖=1

≤ 𝑆𝑣 ≤ ∑ 𝑖

𝑣+𝑒

𝑖=1

− ∑ 𝑖

𝑒

𝑖=1

(3.4)

B. Perhitungan Dasar Pelabelan Total Ajaib Sisi Pada Graf Roda

1. Batas Total Label Titik 𝑆𝑣

Berdasarkan persamaan (3.3) untuk kepentingan pencarian nilai konstanta

ajaib 𝑘, batas total label 𝑆𝑣 perlu ditentukan terlebih dahulu. Berdasarkan

persamaan (3.4) diperoleh

∑ 𝑖

𝑣

𝑖=1

≤ 𝑆𝑣 ≤ ∑ 𝑖

𝑣+𝑒

𝑖=1

− ∑ 𝑖

𝑒

𝑖=1

𝑣(𝑣 + 1)

2≤ 𝑆𝑣 ≤

(𝑣 + 𝑒)(𝑣 + 𝑒 + 1)

2−

𝑒(𝑒 + 1)

2

(𝑛 + 1)(𝑛 + 2)

2≤ 𝑆𝑣 ≤

(3𝑛 + 1)(3𝑛 + 2)

2−

2𝑛(2𝑛 + 1)

2

(𝑛 + 1)(𝑛 + 2)

2≤ 𝑆𝑣 ≤

9𝑛2 + 9𝑛 + 2

2−

4𝑛2 + 2𝑛

2


31

(𝑛 + 1)(𝑛 + 2)

2≤ 𝑆𝑣 ≤

5𝑛2 + 7𝑛 + 2

2

(𝑛 + 1)(𝑛 + 2)

2≤ 𝑆𝑣 ≤

(𝑛 + 1)(5𝑛 + 2)

2

𝑆𝑣 =(𝑛+1)(𝑛+2)

2+ 𝑎, di mana 𝑎 adalah

0 ≤ 𝑎 ≤(𝑛 + 1)(5𝑛 + 2)

2−

(𝑛 + 1)(𝑛 + 2)

2

0 ≤ 𝑎 ≤(𝑛 + 1)((5𝑛 + 2) − (𝑛 + 2))

2

0 ≤ 𝑎 ≤(𝑛 + 1)4𝑛

2

0 ≤ 𝑎 ≤ 2𝑛(𝑛 + 1)

0 ≤ 𝑎 ≤ 2𝑛2 + 2𝑛

𝑆𝑣 =(𝑛 + 1)(𝑛 + 2)

2+ 𝑎, 0 ≤ 𝑎 ≤ 2𝑛2 + 2𝑛, 𝑎 ∈ ℤ

(3.5)

2. Batas Nilai Konstanta Ajaib k Untuk Setiap Graf Roda

Batas nilai konstanta ajaib 𝑘 yang diperoleh dari perhitungan dasar

menunjukan adanya pelabelan pada graf roda. Perhitungan dasar

memberikan batas nilai kosntanta ajaib 𝑘 yang memungkinkan pada suatu

graf secara umum. Sementara, setiap graf memiliki struktur yang berbeda-

beda, sehingga memungkinkannya ditemui beberapa permasalahan untuk

graf roda 𝑊𝑛 sehingga untuk nilai 𝑛 tertentu tidak dapat diberikan label,

atau adanya suatu nilai kosntanta ajaib 𝑘 yang tidak memiliki pelabelan, dll.

Dengan demikian perlu adanya perhitungan khusus untuk menentukan batas

nilai kosntanta ajaib.


32

Berdasarkan persamaan (3.3) dan (3.5) diperoleh

𝑘 =

𝑀(𝑀+1)

2+ 2𝑆𝑣 + (𝑛 − 3)𝑐

2𝑛

=

(3𝑛+1)(3𝑛+2)

2+ 2 (

(𝑛+1)(𝑛+2)

2+ 𝑎) + (𝑛 − 3)𝑐

2𝑛

=

9𝑛2+9𝑛+2

2+ 2 (

𝑛2+3𝑛+2

2+ 𝑎) + (𝑛 − 3)𝑐

2𝑛

=

9𝑛2+9𝑛+2

2+

2𝑛2+6𝑛+4

2+ 2𝑎 + (𝑛 − 3)𝑐

2𝑛

=

11𝑛2+15𝑛+6

2+ 2𝑎 + (𝑛 − 3)𝑐

2𝑛, 0 ≤ 𝑎 ≤ 2𝑛2 + 2𝑛, 𝑎 ∈ ℤ

(3.6)

Berdasarkan persamaan (3.6) diperoleh batas nilai kosntanta ajaib 𝑘 terkecil

dapat diperoleh jika𝑎 = 0 dan 𝑐 = 1 sehingga

𝑘𝑡𝑒𝑟𝑘𝑒𝑐𝑖𝑙 =

11𝑛2+15𝑛+6

2+ 2𝑎 + (𝑛 − 3)𝑐

2𝑛

=

11𝑛2+15𝑛+6

2+ 2 ∙ 0 + (𝑛 − 3)1

2𝑛

=

11𝑛2+15𝑛+6

2+ (𝑛 − 3)

2𝑛

=

11𝑛2+15𝑛+6

2+

2𝑛−6

2

2𝑛

=11𝑛2 + 17𝑛

4𝑛

=11𝑛 + 17

4

(3.7)


33

Berdasarkan persamaan (3.6) diperoleh batas nilai kosntanta ajaib 𝑘

terbesar dapat diperoleh jika 𝑎 = 2n2 + 2n dan 𝑐 = 3𝑛 + 1 sehingga

𝑘𝑡𝑒𝑟𝑏𝑒𝑠𝑎𝑟 =

11𝑛2+15𝑛+6

2+ 2𝑎 + (𝑛 − 3)𝑐

2𝑛

=

11𝑛2+15𝑛+6

2+ 2(2n2 + 2n) + (𝑛 − 3)(3𝑛 + 1)

2𝑛

=

11𝑛2+15𝑛+6

2+

8n2+8n

2+ 3𝑛2 − 8𝑛 − 3

2𝑛

=

19𝑛2+23𝑛+6

2+

6𝑛2−16𝑛−6

2

2𝑛

=25𝑛2 + 7𝑛

4𝑛

=25𝑛 + 7

4

(3.8)

Sehingga untuk setiap graf roda 𝑊𝑛, konstanta ajaib 𝑘 yang memenuhi

adalah

11𝑛 + 17

4≤ 𝑘 ≤

25𝑛 + 7

4

(3.9)

3. Batas Nilai Titik Pusat c untuk Konstanta Ajaib k

Pada graf roda terdapat titik sebanyak 𝑛 + 1 dan sisi sebanyak 2𝑛

sehingga banyaknya pelabelan yang akan terjadi pada graf roda sebanyak

3𝑛 + 1. Pada skripsi ini pelabelan pada graf roda mengacu pada titik pusat


34

sebagai pusat, sisi yang bersisian dengan pusat sebagai jari-jari, dan titik

lainnya yang bertetangga dengan titik pusat.

Gambar 3.2 Pelabelan pada graf roda

Berdasarkan gambar di atas, untuk semua 𝑖, total label 𝑒𝑖 + 𝑣𝑖 dalam

pelabelan total ajaib sisi pada graf roda adalah sama yaitu 𝑘 − 𝑐 di mana 𝑘

merupakan nilai konstanta ajaib dan 𝑐 merupakan label untuk titik pusat.

Karena untuk semua 𝑖 total label 𝑒𝑖 + 𝑣𝑖 sama maka pasangan label

𝑒𝑖 + 𝑣𝑖 terkecil dapat diperoleh dari label bilangan asli mulai dari 1 sampai

2𝑛 yang saling berpasangan yaitu {𝑖, 2𝑛 + 1 − 𝑖}. Dengan cara yang sama,

pasangan label 𝑒𝑖 + 𝑣𝑖 terbesar diperoleh dari label bilangan asli mulai dari

𝑛 + 2 sampai 3𝑛 + 1 yang saling pasangan yaitu {𝑛 + 1 + 𝑖, 3𝑛 + 2 − 𝑖},

Untuk setiap nilai konstanta ajaib 𝑘 terdapat batasan untuk label titik

pusat c pada graf roda. Label titik pusat c terkecil diperoleh dengan

mengurangi nilai konstanta ajaib 𝑘 dengan jumlahan dari pasangan label

𝑒𝑖 + 𝑣𝑖 terbesar, sehingga label titik pusat 𝑐 terkecil adalah

𝑐𝑡𝑒𝑟𝑘𝑒𝑐𝑖𝑙 = 𝑘 − ((𝑛 + 1 + 𝑖) + (3𝑛 + 2 − 𝑖))

= 𝑘 − (4𝑛 + 3)

Misalkan nilai kosntanta ajaib 𝑘 yang digunakan merupakan nilai

konstanta ajaib terkecil, sehingga

𝑣𝑛

𝑣1 𝑣2

𝑣3 𝑐

𝑠1

𝑠2 𝑠𝑛

𝑒𝑛

𝑒1 𝑒2

𝑒3


35

𝑐𝑡𝑒𝑟𝑘𝑒𝑐𝑖𝑙 = 𝑘 − (4𝑛 + 3)

=11𝑛 + 17

4− (4𝑛 + 3)

=11𝑛 + 17

4−

4

4(4𝑛 + 3)

=11𝑛 + 17

4−

16𝑛 + 12

4

=−5𝑛 + 5

4

= 1,25 − 1,25𝑛

Untuk 𝑛 = 4 sehingga label 𝑐𝑡𝑒𝑟𝑘𝑒𝑐𝑖𝑙

𝑐𝑡𝑒𝑟𝑘𝑒𝑐𝑖𝑙 = 1,25 − 1,25𝑛

= 1,25 − 1,25 ∙ 4

= 1,25 − 5

= −3,75

Berdasarkan persamaan di atas, koefisien dari 𝑛 bernilai negatif

sehingga semakin besar nilai 𝑛 maka semakin besar pula label negatif untuk

label 𝑐𝑡𝑒𝑟𝑘𝑒𝑐𝑖𝑙. Label yang terdapat pada pelabelan total ajaib adalah label

dengan bilangan asli sehingga diperlukan batasan bahwa untuk setiap label

merupakan bilangan asli (𝑐 ≥ 1) sehingga

𝑐𝑡𝑒𝑟𝑘𝑒𝑐𝑖𝑙 = 𝑘 − (4𝑛 + 3), 𝑐 ≥ 1

(3.10)

Dengan cara yang sama, label titik pusat 𝑐 terbesar dapat diperoleh

dengan mengurangi nilai konstanta ajaib 𝑘 dengan jumlahan dari pasangan

label 𝑒𝑖 + 𝑣𝑖 terkecil, sehingga label titik pusat 𝑐 terbesar adalah

𝑐𝑡𝑒𝑟𝑏𝑒𝑠𝑎𝑟 = 𝑘 − ((𝑖) + (2𝑛 + 1 − 𝑖))

= 𝑘 − (2𝑛 + 1)


36

Misalkan nilai kosntanta ajaib 𝑘 yang digunakan merupakan nilai

konstanta ajaib terbesar, sehingga

𝑐𝑡𝑒𝑟𝑏𝑒𝑠𝑎𝑟 = 𝑘 − (2𝑛 + 1)

=25𝑛 + 7

4− (2𝑛 + 1)

=25𝑛 + 7

4−

4

4(2𝑛 + 1)

=25𝑛 + 7

4−

8𝑛 + 4

4

=17𝑛 + 3

4

= 4,25𝑛 + 0,75

= (3𝑛 + 1) + (1,25𝑛 − 0,25)

Untuk 𝑛 = 4 sehingga label 𝑐𝑡𝑒𝑟𝑏𝑒𝑠𝑎𝑟

𝑐𝑡𝑒𝑟𝑏𝑒𝑠𝑎𝑟 = (3𝑛 + 1) + (1,25𝑛 − 0,25)

= (3𝑛 + 1) + (1,25 ∙ 4 − 0,25)

= (3𝑛 + 1) + (5 − 0,25)

= (3𝑛 + 1) + 4,75

Berdasarkan persamaan di atas, semakin besar nilai 𝑛 maka semakin

besar pula label untuk label 𝑐𝑡𝑒𝑟𝑏𝑒𝑠𝑎𝑟 , tetapi label untuk label 𝑐𝑡𝑒𝑟𝑏𝑒𝑠𝑎𝑟

sudah melebihi batas pelabelan yang ada pada graf roda 𝑊𝑛 yaitu (3𝑛 + 1),

sehingga diperlukan batasan bahwa label maksimum untuk setiap label di

mana label 𝑐 juga termasuk yaitu (3𝑛 + 1) sehingga batas untuk label 𝑐

adalah (𝑐 ≤ 3𝑛 + 1) sehingga

𝑐𝑡𝑒𝑟𝑏𝑒𝑠𝑎𝑟 = 𝑘 − (2𝑛 + 1), 𝑐 ≤ 3𝑛 + 1

(3.11)


37

Sehingga untuk setiap nilai konstanta ajaib 𝑘, label titik pusat 𝑐 yang

memenuhi adalah

𝑘 − (4𝑛 + 3) ≤ 𝑐 ≤ 𝑘 − (2𝑛 + 1), 𝑐 ≥ 1, 𝑐 ≤ 3𝑛 + 1 (3.12)

4. Pelabelan Titik dan Sisi Pada Graf Roda

Pelabelan titik dan sisi dalam pelabelan ajaib sisi pada graf roda dibagi

menjadi dua, yaitu

a. Pelabelan untuk pasangan label titik (𝑣) dan sisi pada jari-jari (𝑒) yang

terdapat pada graf roda

Pelabelan untuk pasangan label titik dan sisi adalah himpunan bilangan

pasangan berurut yang memungkinkan di mana (𝑣, 𝑒) = {𝑖, 𝑘 − 𝑐 − 𝑖}

b. Pelabelan untuk sisi 𝑠𝑖𝑘𝑒𝑙 (𝑠) pada graf roda

Pelabelan untuk sisi (𝑠) himpunan bilangan yang memungkinkan di

mana bukan titik pusat (𝑠) = {1 ≤ 𝑖 ≤ 3𝑛 + 1, 𝑖 ≠ 𝑐}


38

C. Pelabelan Total Ajaib Sisi Pada Graf Roda

Pada pelabelan total ajaib sisi untuk graf roda ditemukan banyak cara

memperoleh nilai konstanta ajaib 𝑘, tetapi setiap graf memiliki struktur yang

berbeda-beda, sehingga memungkinkannya ditemui beberapa permasalahan

untuk nilai 𝑛 tertentu sehingga graf roda tidak dapat diberikan label, atau

adanya suatu nilai kosntanta ajaib 𝑘 yang tidak memiliki pelabelan, dll.

Berdasarkan persamaan (3.6) nilai konstanta ajaib pada pelabelan total ajaib

sisi dapat diperoleh yaitu:

𝑘 =

11𝑛2+15𝑛+6

2+ 2𝑎 + (𝑛 − 3)𝑐

2𝑛, 0 ≤ 𝑎 ≤ 2𝑛2 + 2𝑛

=11𝑛2 + 15𝑛 + 6

4𝑛+

2𝑎 + (𝑛 − 3)𝑐

2𝑛

=8𝑛2 + 12𝑛 + 3𝑛2 + 3𝑛 + 6

4𝑛+

2𝑎 + (𝑛 − 3)𝑐

2𝑛

= (2𝑛 + 3) +3𝑛2 + 3𝑛 + 6

4𝑛+

2𝑎 + (𝑛 − 3)𝑐

2𝑛

= (2𝑛 + 3) +3

4

𝑛2 + 𝑛 + 2

𝑛+

2𝑎 + (𝑛 − 3)𝑐

2𝑛

(3.13)


39

1. Pelabelan Total Ajaib Sisi Pada Graf Roda (𝑛 ≡ 0(𝑚𝑜𝑑4))

𝑛 ≡ 0(𝑚𝑜𝑑4)𝑛 = 4ℎ, ℎ ∈ ℕ

Berdasarkan persamaan (3.13) sehingga

𝑘 = (2𝑛 + 3) +3

4

𝑛2 + 𝑛 + 2

𝑛+

2𝑎 + (𝑛 − 3)𝑐

2𝑛

= (2(4ℎ) + 3) +3

4

(4ℎ)2 + (4ℎ) + 2

4ℎ+

2𝑎 + ((4ℎ) − 3)𝑐

2(4ℎ)

= (8ℎ + 3) +3

4

16ℎ2 + 4ℎ + 2

4ℎ+

2𝑎 + (4ℎ − 3)𝑐

8ℎ

= (8ℎ + 3) +48ℎ2 + 12ℎ + 6

16ℎ+

2𝑎 + (4ℎ − 3)𝑐

8ℎ

= (8ℎ + 3) + 3ℎ +12ℎ + 6

16ℎ+

2𝑎 + (4ℎ − 3)𝑐

8ℎ

= (11ℎ + 3) +6ℎ + 3

8ℎ+

2𝑎 + (4ℎ − 3)𝑐

8ℎ

= (11ℎ + 3) +6ℎ + 2𝑎 + 3 + (4ℎ − 3)𝑐

8ℎ

∀ 𝑎, 𝑐, ℎ di mana

0 ≤ 𝑎 ≤ 2𝑛2 + 2𝑛, 𝑎 ∈ ℤ, 1 ≤ 𝑐 ≤ 3𝑛 + 1, 𝑐 ∈ ℕ dan ∀ℎ ∈ ℕ

8ℎ menghasilkan suatu bilangan asli genap,

6ℎ + 2𝑎 + 3 + (4ℎ − 3)𝑐 menghasilkan suatu bilangan asli genap jika 𝑐

merupakan label dengan bilangan asli ganjil

Oleh sebab itu ∃𝑎, 𝑐, ℎ sehingga dapat ditemukan sebuah nilai konstanta

ajaib 𝑘 jika label 𝑐 merupakan label dengan bilangan asli ganjil.


40


𝑛 ≡ 1(𝑚𝑜𝑑4)𝑛 = 4ℎ + 1, ℎ ∈ ℕ


𝑘 = (2𝑛 + 3) +3

4

𝑛2 + 𝑛 + 2

𝑛+

2𝑎 + (𝑛 − 3)𝑐

2𝑛

= (2(4ℎ + 1) + 3) +3

4

(4ℎ + 1)2 + (4ℎ + 1) + 2

4ℎ + 1+

2𝑎 + ((4ℎ + 1) − 3)𝑐

2(4ℎ + 1)

= (8ℎ + 2 + 3) +3

4

(16ℎ2 + 8ℎ + 1) + 4ℎ + 3

4ℎ + 1+

2𝑎 + (4ℎ − 2)𝑐

8ℎ + 2

= (8ℎ + 5) +3

4

16ℎ2 + 12ℎ + 4

4ℎ + 1+

𝑎 + (2ℎ − 1)𝑐

4ℎ + 1

= (8ℎ + 5) +3(4ℎ2 + 3ℎ + 1)

4ℎ + 1+

𝑎 + (2ℎ − 1)𝑐

4ℎ + 1

= (8ℎ + 5) +12ℎ2 + 9ℎ + 3

4ℎ + 1+

𝑎 + (2ℎ − 1)𝑐

4ℎ + 1

= (8ℎ + 5) +(12ℎ2 + 7ℎ + 1) + 2ℎ + 2

4ℎ + 1+

𝑎 + (2ℎ − 1)𝑐

4ℎ + 1

= (8ℎ + 5) + (3ℎ + 1) +2ℎ + 2

4ℎ + 1+

𝑎 + (2ℎ − 1)𝑐

4ℎ + 1

= (11ℎ + 6) +2ℎ + 𝑎 + 2 + (2ℎ − 1)𝑐

4ℎ + 1


0 ≤ 𝑎 ≤ 2𝑛2 + 2𝑛, 𝑎 ∈ ℤ, 1 ≤ 𝑐 ≤ 3𝑛 + 1, 𝑐 ∈ ℕ dan ∀ℎ ∈ ℕ

4ℎ + 1 menghasilkan suatu bilangan asli ganjil


ajaib 𝑘.


41


𝑛 ≡ 2(𝑚𝑜𝑑4)𝑛 = 4ℎ + 2, ℎ ∈ ℕ


𝑘 = (2𝑛 + 3) +3

4

𝑛2 + 𝑛 + 2

𝑛+

2𝑎 + (𝑛 − 3)𝑐

2𝑛

= (2(4ℎ + 2) + 3) +3

4

(4ℎ + 2)2 + (4ℎ + 2) + 2

4ℎ + 2+

2𝑎 + ((4ℎ + 2) − 3)𝑐

2(4ℎ + 2)

= (8ℎ + 4 + 3) +3

4

(16ℎ2 + 16ℎ + 4) + 4ℎ + 4

4ℎ + 2+

2𝑎 + (4ℎ − 1)𝑐

8ℎ + 4

= (8ℎ + 7) +3

4

16ℎ2 + 20ℎ + 8

4ℎ + 2+

2𝑎 + (4ℎ − 1)𝑐

8ℎ + 4

= (8ℎ + 7) +3(4ℎ2 + 5ℎ + 2)

4ℎ + 2+

2𝑎 + (4ℎ − 1)𝑐

8ℎ + 4

= (8ℎ + 7) +12ℎ2 + 15ℎ + 6

4ℎ + 2+

2𝑎 + (4ℎ − 1)𝑐

8ℎ + 4

= (8ℎ + 7) +(12ℎ2 + 14ℎ + 4)(ℎ + 2)

4ℎ + 2+

2𝑎 + (4ℎ − 1)𝑐

8ℎ + 4

= (8ℎ + 7) + (3ℎ + 2) +ℎ + 2

4ℎ + 2+

2𝑎 + (4ℎ − 1)𝑐

8ℎ + 4

= (11ℎ + 9) +2ℎ + 2𝑎 + 4 + (4ℎ − 1)𝑐

8ℎ + 4


0 ≤ 𝑎 ≤ 2𝑛2 + 2𝑛, 𝑎 ∈ ℤ, 1 ≤ 𝑐 ≤ 3𝑛 + 1, 𝑐 ∈ ℕ dan ∀ℎ ∈ ℕ

8ℎ + 4 menghasilkan suatu bilangan asli genap

2ℎ + 2𝑎 + 4 + (4ℎ − 1)𝑐 menghasilkan suatu bilangan asli genap jika 𝑐

merupakan label dengan bilangan asli genap


42


ajaib 𝑘 jika label 𝑐 merupakan label dengan bilangan asli genap.


Enomoto, dkk (1998) meneliti bahwa pada graf roda sampai 𝑛 = 29

menemukan suatu pelabelan untuk graf jika 𝑛 ≢ 3(𝑚𝑜𝑑4) , hal ini

diperkuat oleh Fukuchi (2001) yang membuktikan dugaan tersebut.

Pembuktian untuk membuktikan bahwa tidak terdapat pelabelan untuk

𝑛 ≡ 3(𝑚𝑜𝑑4) antara lain:

𝑛 ≡ 3(𝑚𝑜𝑑4)𝑛 = 4ℎ + 3, ℎ ∈ ℕ


𝑘 = (2𝑛 + 3) +3

4

𝑛2 + 𝑛 + 2

𝑛+

2𝑎 + (𝑛 − 3)𝑐

2𝑛

= (2(4ℎ + 3) + 3) +3

4

(4ℎ + 3)2 + (4ℎ + 3) + 2

4ℎ + 3+

2𝑎 + ((4ℎ + 3) − 3)𝑐

2(4ℎ + 3)

= (8ℎ + 6 + 3) +3

4

(16ℎ2 + 24ℎ + 9) + 4ℎ + 5

4ℎ + 3+

2𝑎 + 4ℎ𝑐

8ℎ + 6

= (8ℎ + 9) +3

4

16ℎ2 + 28ℎ + 14

4ℎ + 3+

2𝑎 + 4ℎ𝑐

8ℎ + 6

= (8ℎ + 9) +3

2

8ℎ2 + 14ℎ + 7

4ℎ + 3+

2𝑎 + 4ℎ𝑐

8ℎ + 6

= (8ℎ + 9) +24ℎ2 + 42ℎ + 21

8ℎ + 6+

2𝑎 + 4ℎ𝑐

8ℎ + 6

= (8ℎ + 9) +24ℎ2 + 42ℎ + 18 + 3

8ℎ + 6+

2𝑎 + 4ℎ𝑐

8ℎ + 6

= (8ℎ + 9) + (3ℎ + 3) +3

8ℎ + 6+

2𝑎 + 4ℎ𝑐

8ℎ + 6


43

= (11ℎ + 12) +3 + 2𝑎 + 4ℎ𝑐

8ℎ + 6


0 ≤ 𝑎 ≤ 2𝑛2 + 2𝑛, 𝑎 ∈ ℤ, 1 ≤ 𝑐 ≤ 3𝑛 + 1, 𝑐 ∈ ℕ dan ∀ℎ ∈ ℕ

3 + 2𝑎 + 4ℎ𝑐 menghasilkan suatu bilangan asli ganjil, dan

8ℎ + 6 menghasilkan suatu bilangan asli genap

Oleh sebab itu untuk ∀𝑎, 𝑐, ℎ tidak dapat ditemukan sebuah bilangan

bulat untuk

3 + 2𝑎 + 4ℎ𝑐

8ℎ + 6

Oleh sebab itu untuk setiap 𝑛 tidak ada pelabelan total ajaib sisi pada

graf roda jika 𝑛 ≡ 3(𝑚𝑜𝑑4).


44

BAB IV

ALGORITMA PELABELAN TOTAL AJAIB SISI PADA GRAF RODA

Pelabelan total ajaib sisi pada graf roda memperhatikan urutan label yang

digunakan, sehingga munculnya banyak cara memberikan label. Bila satu label

elemen diganti, maka label elemen yang lain akan berubah. Dengan pelabelan yang

dapat berubah-ubah diperlukan 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.

Secara umum, ide pelabelan total ajaib sisi adalah dengan memberikan label

titik dan sisi secara berulang sampai semua sisi memiliki bobot yang sama. Label

titik (𝑣) ditentukan secara acak dan berbeda sedangkan untuk pelabelan sisi jari-jari

( 𝑒 ) mengikuti urutan pasangan label (𝑣, 𝑒 ) sedangkan label sisi pada 𝑠𝑖𝑘𝑒𝑙

diperoleh dengan mengurangkan nilai konstanta ajaib 𝑘 dengan total label titik

yang bersisian dengan sisi pada 𝑠𝑖𝑘𝑒𝑙 tersebut. Perulangan ini dilakukan sampai

semua sisi memiliki bobot yang sama.

A. Proses Pelabelan Total Ajaib Sisi Pada Graf Roda

Pada proses pelabelan, label titik, sisi jari-jari, sisipada 𝑠𝑖𝑘𝑒𝑙 secara

berturut-turut dinotasikan 𝑣, 𝑒, 𝑠 dengan indeks 1,2,3, … , 𝑛 . Berikut ini

variabel-variabel yang digunakan dalam proses pelabelan


45

Tabel 4.1 Variabel yang Digunakan dalam Pelabelan

Variabel Keterangan

𝑛 Indeks pada graf roda 𝑊𝑛, menyatakan banyaknya titik pada 𝑠𝑖𝑘𝑒𝑙, nilai

diinputkan oleh pengguna

𝑘 Konstanta ajaib dalam pelabalen, nilai diinputkan oleh pengguna

𝑐 Titik pusat, variabel yang memuat titik pusat

𝑣 Titik pada 𝑠𝑖𝑘𝑒𝑙, variabel yang memuat label-label titik, dalam proses

pelabelan memiliki keluaran dalam bentuk matriks 𝑣 = [𝑣1, 𝑣2, … , 𝑣𝑛]

𝑒 Sisi jari-jari, variabel yang memuat label-label sisi, dalam proses

pelabelan memiliki keluaran dalam bentuk matriks 𝑒 = [𝑒1, 𝑒2, … , 𝑒𝑛]

𝑠 Sisi pada 𝑠𝑖𝑘𝑒𝑙, variabel yang memuat label-label sisi, dalam proses

pelabelan memiliki keluaran dalam bentuk matriks 𝑠 = [𝑠1, 𝑠2, … , 𝑠𝑛]

𝑀 Matriks 𝑀 , variabel yang memuat label-label yang terdapat dalam

pelabelan 𝑀 = [1,2,3, … ,3𝑛 + 1]

𝑘𝑐 Matriks kc, variabel yang memuat label-label yang memungkinkan

sebagai titik pusat

𝐴 Matriks 𝐴, variabel yang memuat label-label yang terdapat pada matriks

𝑀 kecuali variabel titik pusat 𝑐

𝐵 Matriks B, variabel yang memuat pasangan yang memenuhi persyaratan

sebagai variabel untuk 𝑣 dan 𝑒

𝐶 Matriks 𝐶 , variabel yang memuat label-label yang belum digunakan

dalam pelabelan, anggota matriks 𝐶 selalu diperbaharui

𝐷 Matriks 𝐷 , variabel yang memuat label-label pasangan yang belum

digunakan dalam pelabelan, anggota matriks 𝐷 selalu diperbaharui

𝑎, 𝑏, 𝑑, 𝑝𝑠

Variabel sementara pada perulangan, 𝑎 untuk label titik, 𝑏 untuk label

sisi pada jari-jari, 𝑑 untuk label sisi pada 𝑠𝑖𝑘𝑒𝑙 , 𝑝𝑠 untuk pasangan

dengan 𝑑


46

B. Diagram Alir Pelabelan Total Ajaib Sisi 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 𝑓𝑙𝑜𝑤𝑐ℎ𝑎𝑟𝑡 , membangun algoritma

proses pelabelan, dan membahas algoritma pelabelan ke bahasa pemprograman

MATLAB 7.1.

Dalam pemprograman ini dibagi menjadi beberapa bagian yang membahas

alir pelabelan pada graf roda. Rancangan proses pelabelan graf roda tampak

pada gambar. Pada diagram alir tersebut terdapat beberapa bagian pelabelan.

Gambar 4.1 Diagram Alir Proses Pelabelan

Mulai

Selesai

Masukan :

nilai n

Masukan

nilai k

𝑛 ≢ 3(𝑚𝑜𝑑 4)

𝑘𝑚𝑖𝑛 ≤ 𝑘 ≤ 𝑘𝑚𝑎𝑥

Pelabelan Pertama

Pelabelan Kedua - n

Pelabelan Terakhir

Keluaran :

Label

𝑐, 𝑣, 𝑒, 𝑠

A

Benar

Benar

Benar

Benar

Salah

Salah

Salah

Salah

A


47

Dalam proses pelabelan pada graf roda dibagi menjadi tiga bagian utama

yaitu :

1. Bagian Input (Menginput nilai 𝑛 dan 𝑘)

Proses pelabelan diawali dengan menginput nilai 𝑛. Berdasarkan nilai 𝑛

diperoleh batas nilai kostanta ajaib 𝑘, yang kemudian batas nilai ajaib 𝑘

tersebut ditampilkan, sehingga pengguna dapat menginput nilai kostanta

ajaib 𝑘 yang diinginkan. Pada bagian ini diperoleh nilai 𝑛 dan nilai 𝑘 serta

matriks M yang memuat label yang akan digunakan pada pelabelan total

ajaib sisi pada graf roda yaitu 𝑀 = [1 2 3 … 3𝑛 + 1]yang akan digunakan

untuk mencari label-label lain pada pelabelan total ajaib sisi pada graf roda.

Gambar 4.2 Diagram input nilai 𝑛 dan 𝑘

Mulai

Masukan :

nilai n

Masukan

nilai k

𝑛 ≢ 3(𝑚𝑜𝑑 4)

𝑘𝑚𝑖𝑛 ≤ 𝑘 ≤ 𝑘𝑚𝑎𝑥

A

Benar

Benar

Salah

Salah

𝑀 = [1 2 … 3𝑛 + 1]


48

2. Bagian Pengolahan (Program perulangan sampai seluruh label diberikan

label)

Berdasarkan nilai konstanta ajaib 𝑘 diperoleh batas untuk label titik

pusat 𝑐. Untuk setiap label titik pusat 𝑐 dapat dibuat sebuah matriks 𝐴 di

mana label yang terdapat pada merupakan label pada matriks 𝑀 kecuali

untuk label titik pusat 𝑐 tidak terdapat pada matriks 𝐴. Selain Matriks 𝐴,

Diperlukan sebuah matriks lain yaitu matriks 𝐵 di mana label pada matriks

𝐵 terdiri dari label yang hanya memenuhi syarat untuk menjadi pasangan

label (𝑣, 𝑒).

Setelah diperoleh matriks 𝐴 dan matriks 𝐵, diperlukan matris lain yang

akan digunakan dalam proses pembuktian yaitu matris 𝐶 yang merupakan

salinan dari matriks 𝐴 dan matriks 𝐷 yang merupakan salinan dari matriks

𝐵.

a. Pada pelabelan pertama, label 𝑎 diperoleh secara acak dari label yang

terdapat pada matriks 𝐷. Berdasarkan label 𝑎 dapat ditemukan label 𝑏

di mana label 𝑏 merupakan pasangan label 𝑎 yang juga terdapat pada

matriks 𝐷. Label 𝑎 akan diinput kedalam label 𝑣 sebagai 𝑣1 dan label 𝑏

akan diinput kedalam label 𝑒 sebagai 𝑒1. Setelah dilakukan input label

𝑎 dan 𝑏 kedalam 𝑣 dan 𝑒 , matriks 𝐶 dan matriks 𝐷 diperbaharui

dengan menghilangkan elemen yang telah dipergunakan pada proses

pelabelan pertama.


49

Gambar 4.3 Diagram label 𝑐, 𝑣1 dan 𝑒1

b. Pada pelabelan kedua sampai dengan ke-𝑛 dapat digunakan cara yang

sama dengan tambahan pelabelan 𝑑 di mana label 𝑑 diperoleh dari hasil

pengurangan nilai konstanta ajaib 𝑘 dengan jumlah label titik yang

bersisian dengan sisi pada 𝑠𝑖𝑘𝑒𝑙 tersebut. Setelah diperoleh label 𝑑

diperlukan label lain yaitu label 𝑝𝑠 di mana label 𝑝𝑠 merupakan label

yang memastikan apakah label d merupakan salah satu label yang

terdapat pada matriks 𝐷. Label d akan diinput sebagai label 𝑠 sebagai

𝑠𝑖−1. Jika label 𝑑 bukan salah satu dari label yang terdapat pada matriks

𝐶, maka pelabelan akan kembali diulangi dari proses pelabelan yang

bagian pertama. Setelah label 𝑎, 𝑏 dan 𝑑 diinput dalam 𝑣, 𝑒 dan 𝑠 ,

A

𝑘 − (4𝑛 + 3) ≤ 𝑐 ≤ 𝑘 − (2𝑛 + 1)

𝐴 = 𝑀 di mana tidak ada label 𝑐

𝐵 = Matriks di mana memuat pasangan (𝑣, 𝑒)

𝐶 = 𝐴

𝐷 = 𝐵

𝑎 = 𝐷 (𝑟𝑎𝑛𝑑𝑝𝑒𝑟𝑚(𝑛𝑢𝑚𝑒𝑙(𝐷)))

𝑏 = 𝑘 − 𝑐 − 𝑎

𝑣𝑖 = 𝑎

𝑒𝑖 = 𝑏

𝐶 = 𝑠𝑒𝑡𝑑𝑖𝑓𝑓(𝐶, [𝑎 𝑏])

𝐷 = 𝑠𝑒𝑡𝑑𝑖𝑓𝑓(𝐷, [𝑎 𝑏])

B


50

matriks C diperbaharui dengan menghilangkan elemen 𝑎, 𝑏 dan 𝑑 yang

telah dipergunakan, serta matriks 𝐷 diperbaharui dengan

menghilangkan 𝑎, 𝑏 dan 𝑑 serta 𝑝𝑠 di mana 𝑎, 𝑏 dan 𝑑 merupakan label

yang telah dipergunakan dan 𝑝𝑠 merupakan pasangan dari label 𝑑.

Gambar 4.4 Diagram label 𝑣, 𝑒 dan 𝑠1 sampai 𝑠𝑛−1

c. Pada pelabelan terakhir yaitu pelabelan ke-(𝑛 + 1) adalah pelabelan

yang memastikan 𝑑 di mana label 𝑑 diperoleh dari hasil pengurangan

nilai konstanta ajaib 𝑘 dengan jumlah label titik yang bersisian dengan

sisi pada 𝑠𝑖𝑘𝑒𝑙 tersebut yaitu 𝑑 = 𝑘 − (𝑣𝑛 + 𝑣1) sama dengan label

𝑛𝑢𝑚𝑒𝑙(𝐶) ≠ 𝑛𝑢𝑚𝑒𝑙(𝑠𝑒𝑡𝑑𝑖𝑓𝑓(𝐶, 𝑑))

B

Benar

Salah

A


𝑏 = 𝑘 − 𝑐 − 𝑎

𝑣𝑖 = 𝑎

𝑒𝑖 = 𝑏

𝑑 = 𝑘 − (𝑣𝑖 + 𝑣𝑖−1)

𝑝𝑠 = 𝑘 − 𝑐 − 𝑑


Dari 2 ≤ 𝑖 ≤ 𝑛 𝑣𝑖 = 𝑎

𝑒𝑖 = 𝑏

𝑠𝑖−1 = 𝑑 𝐶 = 𝑠𝑒𝑡𝑑𝑖𝑓𝑓(𝐶, [𝑎 𝑏 𝑑])

𝐷 = 𝑠𝑒𝑡𝑑𝑖𝑓𝑓(𝐷, [𝑎 𝑏 𝑑 𝑝𝑠])

C

Diulangi Dari 2 ≤ 𝑖 ≤ 𝑛

𝑖 = 𝑛 + 1


51

yang tersisa pada matriks 𝐶. Jika label 𝑑 sama dengan label yang tersisa

pada matriks 𝐶 maka label 𝑑 diinput kedalam 𝑠 sebagai 𝑠𝑛 dan jika

label 𝑑 tidak sama dengan label yang tersisa pada matriks 𝐶 , maka

pelabelan akan diulangi dari proses pelabelan bagian pertama.

Gambar 4.5 Diagram label.𝑠𝑛

Berdasarkan tiga bagian dalam proses pelabelan, diketahui bahwa

pelabelan tersebut tidak akan pernah berhenti sebelum pelabelan tersebut

menemukan pelabelan yang benar, baik pelabelan tersebut benar-benar ada

maupun tidak, sehingga diperlukan batasan perulangan yang mencakup

ketiga bagian pelabelan tersebut sehingga proses pelabelan tidak dilakukan

secara terus menerus.

𝑑 = 𝐶

C

Benar

Salah

A

𝑑 = 𝑘 − (𝑣𝑛 + 𝑣1)

𝑠𝑛 = 𝑑

D


52

3. Bagian Output (Mengeluarkan hasil)

Dari proses yang dilakukan pada bagian kedua, jika proses yang

dilakukan menghasilkan pelabelan yang benar maka hasil label 𝑐, 𝑣, 𝑒 dan 𝑠

akan ditampilkan, tetapi jika proses yang dilakukan tidak menemukan suatu

pelabelan yang benar sampai dengan batas tertentu, maka akan ditampilkan

pemberitahuan bahwa proses yang telah dilakukan tidak mendapatkan label

yang sesuai dengan nilai konstanta akaib 𝑘

Gambar 4.6 Diagram output label 𝑐, 𝑣, 𝑒 dan 𝑠

C. Deskripsi Algoritma Pelabelan Total Ajaib Sisi pada Graf Roda

Pada sub-bab ini akan dibahas algoritma pelabelan pada pelabelan total

ajaib sisi pada graf roda. Diagram alir yang telah dibuat, selanjutnya

dikembangkan dalam algoritma pelabelan.

1. Bagian Input (Menginput nilai 𝑛 dan 𝑘)

Langkah 1 : Input nilai 𝑛

Langkah 2 : Membaca nilai.

Selesai

Keluaran :

Label

𝑐, 𝑣, 𝑒, 𝑠

D


53

Jika 𝑛 ≡ 3(𝑚𝑜𝑑 4) kembali ke langkah 1

Langkah 3 : Mencari batas nilai konstanta ajaib yang memungkinkan, di

mana batas nilai 𝑘 adalah 𝑘𝑚𝑖𝑛 ≤ 𝑘 ≤ 𝑘𝑚𝑎𝑥.

𝑘𝑚𝑖𝑛 = 𝑐𝑒𝑖𝑙 (11𝑛+17

4) dan 𝑘𝑚𝑎𝑥 = 𝑓𝑙𝑜𝑜𝑟 (

25𝑛+7

4).

Langkah 4 : Menampilkan batas nilai kostanta ajaib 𝑘

Langkah 5 : Input nilai kostanta ajaib 𝑘

Langkah 6 : Membaca nilai kostanta ajaib 𝑘

Jika tidak dalam batas kembali ke langkah 5

Langkah 7 : Membuat matriks 𝑀 di mana variabel yang memuat label-

label yang terdapat dalam pelabelan 𝑀 = [1 2 3 … 3𝑛 + 1]

2. Bagian Pengolahan (Program perulangan sampai seluruh label diberikan

label)

a. Pada pelabelan pertama

Langkah 1 : Mencari batas label titik pusat 𝑐 yang memungkinkan di

mana label 𝑐 yang memungkinkan adalah 𝑘 − (4𝑛 +

3) ≤ 𝑐 ≤ 𝑘 − (2𝑛 + 1)

Langkah 2 : Menampilkan 𝑘𝑐 di mana 𝑘𝑐 matriks yang berisi label

yang memungkinkan sebagai label titik 𝑐

Langkah 3 : Memilih salah satu label dari matriks 𝑘𝑐 yang akan

dipergunakan sebagai nilai pusat 𝑐


54

Langkah 4 : Membuat matriks 𝐴 di mana variable yang memuat

label-label yang memuat label pada matriks 𝑀 kecuali

label yang dipergunakan sebagai label titik pusat 𝑐

𝐴 = 𝑠𝑒𝑡𝑑𝑖𝑓𝑓(𝑀, 𝑐)

Langkah 5 : Membuat matriks B di mana variable yang memuat

label-label yang memungkinkan sebagai pasangan (𝑣, 𝑒)

𝑓𝑜𝑟 𝑖 = 1:1

2(𝑘 − 𝑐 − 1)

𝐵 = [𝐵; 𝑖; 𝑘 − 𝑐 − 𝑖]

𝑒𝑛𝑑

𝑡𝑒𝑚𝑝 = [𝑠𝑒𝑡𝑑𝑖𝑓𝑓(𝐴, 𝐵), 𝑐]

𝑡𝑒𝑚𝑝 = [𝑡𝑒𝑚𝑝; (3𝑛 + 2) − 𝑡𝑒𝑚𝑝]

𝐵 = 𝑠𝑒𝑡𝑑𝑖𝑓𝑓(𝐵, 𝑡𝑒𝑚𝑝)

Langkah 6 : Membuat matriks 𝐶 di mana matriks 𝐶 merupakan

duplikat dari matriks 𝐴

Langkah 7 : Membuat matriks 𝐷 di mana matriks 𝐷 merupakan

duplikat dari matriks 𝐵

Langkah 8 : Membuat label 𝑧 di mana label 𝑧 merupakan banyaknya

perulangan yang akan terjadi.

𝑧 = 0

Langkah 9 : Membuat perulangan dari 𝑖 = 1 sampai 𝑛 + 1

Langkah 10 : Memperbaharui label 𝑧 sebanyak perulangan yang terjadi

𝑧 = 𝑧 + 1


55

Langkah 11 : Memilih salah satu label dari matriks 𝐷 yang akan

dipergunakan sebagai label 𝑎


𝑎 = 𝑎(1)

Langkah 12 : Membuat label 𝑏 di mana label 𝑏 adalah pasangan label

𝑎

𝑏 = 𝑘 − 𝑐 − 𝑎

Langkah 13 : Menginput label 𝑎 dan 𝑏 ke dalam label 𝑣 dan 𝑒 ke 𝑖

𝑣(𝑖) = 𝑎

𝑒(𝑖) = 𝑏

Langkah 14 : Memperbaharui matriks 𝐶 dan 𝐷 karena berdapat label

yang telah dipergunakan

𝐶 = 𝑠𝑒𝑡𝑑𝑖𝑓𝑓(𝐶, [𝑎 𝑏])


b. Pada pelabelan kedua

Langkah 1 : Memilih salah satu label dari matriks 𝐷 yang akan

dipergunakan sebagai label 𝑎


𝑎 = 𝑎(1)

Langkah 2 : Membuat label 𝑏 di mana label 𝑏 adalah pasangan label

𝑎

𝑏 = 𝑘 − 𝑐 − 𝑎


56

Langkah 3 : Menginput label 𝑎 dan 𝑏 ke dalam label 𝑣 dan 𝑒 ke 𝑖

𝑣(𝑖) = 𝑎

𝑒(𝑖) = 𝑏

Langkah 4 : Membuat label 𝑑 di mana 𝑑 merupakan hasil

pengurangan nilai konstanta 𝑘 dengan jumlah label titik

yang bersisian dengan sisi pada 𝑠𝑖𝑘𝑒𝑙

𝑑 = 𝑘 − (𝑣𝑖 + 𝑣𝑖−1)

Langkah 5 : Mengecek apakah label d merupakan salah satu label

yang terdapat pada matriks 𝐶

𝑛𝑢𝑚𝑒𝑙(𝐶) = 𝑛𝑢𝑚𝑒𝑙(𝑠𝑒𝑡𝑑𝑖𝑓𝑓(𝐶, 𝑑))

Jika maka pelabelan kembali pada bagian pengolahan

pelabelan pertama langkah 9

Langkah 6 : Membuat label 𝑝𝑠 di mana label 𝑝𝑠 merupakan pasangan

label 𝑑

𝑝𝑠 = 𝑘 − 𝑐 − 𝑑

Langkah 7 : Menginput label 𝑎, 𝑏 dan 𝑑 ke dalam label 𝑣, 𝑒 ke 𝑖 dan

𝑠 ke 𝑖 − 1

𝑣(𝑖) = 𝑎

𝑒(𝑖) = 𝑏

𝑠(𝑖 − 1) = 𝑑

Langkah 8 : Memperbaharui matriks 𝐶 dan 𝐷 karena berdapat label

yang telah dipergunakan

𝐶 = 𝑠𝑒𝑡𝑑𝑖𝑓𝑓(𝐶, [𝑎 𝑏 𝑑])


57

𝐷 = 𝑠𝑒𝑡𝑑𝑖𝑓𝑓(𝐷, [𝑎 𝑏 𝑑 𝑝𝑠])

Langkah 1 − 8 diulangi sampai nilai 𝑖 = 𝑛

c. Pada pelabelan terakhir

Langkah 1 : Membuat label 𝑑 di mana 𝑑 merupakan hasil

pengurangan nilai konstanta 𝑘 dengan jumlah label titik

yang bersisian dengan sisi pada 𝑠𝑖𝑘𝑒𝑙

𝑑 = 𝑘 − (𝑣𝑛 + 𝑣1)

Langkah 2 : Mengecek apakah label d sama dengan matriks 𝐶

𝑡𝑓 = 𝑑 == 𝐶

Jika 𝑡𝑓 = 0 maka pelabelan kembali pada bagian

pengolahan pelabelan pertama langkah 9

Jika 𝑡𝑓 = 1 maka diperoleh pelabelan total ajaib sisi

untuk graf roda-𝑛 dengan konstanta 𝑘

Langkah 3 : Jika nilai z melebihi batasan yang telah ditentukan maka

𝑡𝑓 = 2 untuk melanjutkan pencarian dengan label titik

pusat yang lain

Pelabelan kembali pada bagian pengolahan pelabelan

pertama langkah 3

Langkah 4 : Menginput label 𝑑 ke dalam label 𝑠 ke 𝑛

𝑠(𝑛) = 𝑑


58

3. Bagian Output (Mengeluarkan hasil)

Langkah 1 : Jika 𝑡𝑓 = 1 maka menampilkan hasil pelabelan total ajaib

sisi yang diperoleh

Jika 𝑡𝑓 = 0 maka akan ditampilkan untuk pelabelan total

ajaib sisi pada graf roda 𝑊𝑛 dengan konstanta ajaib 𝑘 belum

ditemukan

D. Simulasi Pelabelan Total Ajaib Sisi pada Graf Roda

Algoritma yang dibuat dapat dibahasakan dengan bahasa pemprograman.

Salah satu software yang dapat digunakan adalah MATLAB 7.1. Proses

pelabelan total ajaib sisi pada graf roda menggunakan nilai 𝑛 dan 𝑘 sebagai

𝑖𝑛𝑝𝑢𝑡 dan 𝑜𝑢𝑡𝑝𝑢𝑡 dari program ini beruapa matriks 𝑐, 𝑣, 𝑒 dan 𝑠 dengan

elemen berupa label.

Algoritma pelabelan yang disusun diterjemahkan menggunakan software

MATLAB 7.1. Program pelabelan tital ajaib sisi pada graf roda ketika

dipergunakan maka pada 𝑐𝑜𝑚𝑚𝑎𝑛𝑑 𝑤𝑖𝑛𝑑𝑜𝑤 akan muncul tampilan berikut.

Gambar 4.7 Tampilan awal pada 𝑐𝑜𝑚𝑚𝑎𝑛𝑑 𝑤𝑖𝑛𝑑𝑜𝑤


59

Selanjutnya, diinputkan nilai 𝑛 . Misal nilai 𝑛 yang diinputkan adalah 5,

maka pada 𝑐𝑜𝑚𝑚𝑎𝑛𝑑 𝑤𝑖𝑛𝑑𝑜𝑤 akan muncul tampilan berikut.

Gambar 4.8 Tampilan input 𝑛 = 5 pada 𝑐𝑜𝑚𝑚𝑎𝑛𝑑 𝑤𝑖𝑛𝑑𝑜𝑤

Selanjutnya, diinputkan niilai kosntanta ajaib 𝑘 yang sesuai dengan batas

yang diberikan. Misal nilai kostanta ajaib 𝑘 yang diinputkan adalah 25, maka

pada 𝑐𝑜𝑚𝑚𝑎𝑛𝑑 𝑤𝑖𝑛𝑑𝑜𝑤 akan muncul tampilan berikut.

Gambar 4.9 Tampilan hasil pelabelan dengan 𝑛 = 5 dan 𝑘 = 25 pada

𝑐𝑜𝑚𝑚𝑎𝑛𝑑 𝑤𝑖𝑛𝑑𝑜𝑤

Berdasarkan hasil pelabelan yang diperoleh dari 𝑐𝑜𝑚𝑚𝑎𝑛𝑑 𝑤𝑖𝑛𝑑𝑜𝑤, dapat

dibuat sebuah graf yang mengilustrasikan hasil pelabelan tersebut. Adapun


60

tahapan untuk memberikan label berdasarkan hasil pelabelan yang diperoleh

dari 𝑐𝑜𝑚𝑚𝑎𝑛𝑑 𝑤𝑖𝑛𝑑𝑜𝑤 antara lain:

1. Buatlah graf roda 𝑊𝑛

Gambar 4.10 Tahap pertama ilustrasi hasil pelabelan

2. Berikan label untuk titik pusat berdasarkan hasil yang diperoleh pada


Berdasarkan hasil pada 𝑐𝑜𝑚𝑚𝑎𝑛𝑑 𝑤𝑖𝑛𝑑𝑜𝑤 pada Gambar 4.9, label

untuk titik pusat c adalah 2 sehingga

Gambar 4.11 Tahap kedua ilustrasi hasil pelabelan

2


61

3. Berikan label untuk titik (v) pada sikel berdasarkan hasil yang diperoleh

pada 𝑐𝑜𝑚𝑚𝑎𝑛𝑑 𝑤𝑖𝑛𝑑𝑜𝑤

Berdasarkan hasil pada 𝑐𝑜𝑚𝑚𝑎𝑛𝑑 𝑤𝑖𝑛𝑑𝑜𝑤 yang terdapat pada

Gambar 4.9, label untuk titik pada 𝑠𝑖𝑘𝑒𝑙 terletak pada kolom pertama yaitu

8, 11, 13, 7 dan 14.

Cara memberikan label untuk titik (𝑣𝑖) pada sikel adalah dengan

memberikan label secara berurutan sehingga untuk ∀𝑖, 1 ≤ 𝑖 ≤ 𝑛 ,

𝑣𝑖 bertetangga dengan 𝑣1−1 dan 𝑣𝑖+1.

Gambar 4.12 Tahap ketiga ilustrasi hasil pelabelan

4. Berikan label untuk jari-jari (e) berdasarkan hasil yang diperoleh pada



Gambar 4.9, label untuk jari-jari (𝑒𝑖) terletak pada kolom kedua yaitu 15,

12, 10, 16 dan 9.

Cara memberikan label untuk jari-jari adalah dengan memberikan label

secara berurutan sehingga untuk ∀𝑖, 1 ≤ 𝑖 ≤ 𝑛, 𝑒𝑖 bersisian dengan 𝑣𝑖 dan

𝑐.

8

11

13 7

14 2


62

Gambar 4.13 Tahap keempat ilustrasi hasil pelabelan

5. Berikan label untuk sisi (s) pada sikel berdasarkan hasil yang diperoleh pada



Gambar 4.9, label untuk sisi (𝑠𝑖) pada 𝑠𝑖𝑘𝑒𝑙 terletak pada kolom ketiga

yaitu 6, 1, 5, 4 dan 3.

Cara memberikan label untuk sisi pada sikel adalah dengan memberikan

label secara berurutan sehingga untuk ∀𝑖, 1 ≤ 𝑖 ≤ 𝑛, 𝑠𝑖 bersisian dengan

𝑣𝑖 dan 𝑣𝑖+1.

Gambar 4.14 Tahap kelima ilustrasi hasil pelabelan

Berdasarkan ilustrasi pada Gambar 4.10, bobot setiap sisi sebagai berikut

𝑤𝑡(15) = 8 + 15 + 2 = 25

𝑤𝑡(12) = 11 + 12 + 2 = 25

𝑤𝑡(10) = 13 + 10 + 2 = 25

𝑤𝑡(16) = 7 + 16 + 2 = 25

8

11

13 7

14 9

15

12

10 16

2

8

11

13 7

14 9

15

12

10 16

2

3 6

5

4 1


63

𝑤𝑡(9) = 14 + 9 + 2 = 25

𝑤𝑡(6) = 8 + 6 + 11 = 25

𝑤𝑡(1) = 11 + 1 + 13 = 25

𝑤𝑡(5) = 13 + 5 + 7 = 25

𝑤𝑡(4) = 7 + 4 + 14 = 25

𝑤𝑡(3) = 14 + 3 + 8 = 25

E. Kekurangan pelabelan dengan menggunakan software MATLAB 7.1

Simulasi pelabelan yang dilakukan program pelabelan dengan 𝑠𝑜𝑓𝑡𝑤𝑎𝑟𝑒

MATLAB 7.1 memiliki beberapa kelemahan, antara lain

1. Tidak adanya kepastian apakah untuk graf roda 𝑊𝑛 dengan nilai kosntanta

ajaib 𝑘 memiliki sebuah pelabelan total ajaib sisi.

2. Dalam menjalankan perintah perulangan dibutuhkan sebuah batasan, agar

perulangan tersebut tidak terus berulang, hal tersebut mengakibatkan ada

kemungkinan suatu pelabelan total ajaib sisi pada graf roda 𝑊𝑛 untuk nilai

konstanta ajaib 𝑘 yang sebenarnya ada namun karena pembatasan

perulangan sehingga mengakibatkan hasil tersebut tidak muncul.

3. Banyaknya kemungkinan cara memberikan label tiap elemen sehingga

membuhtuhkan waktu yang cukup lama untuk menjalankan perintah.

4. Semakin tinggi nilai 𝑛 yang diinputkan maka semakin lama pula waktu

yang diperlukan untuk menjalankan perintah.


64

F. Contoh Pemanfaatan Pelabelan Total Ajaib Sisi pada Graf Roda

1. Penerapan kartu sebagai kode akses pembuka ruangan dan lift

Pada sebuah banguan bertingkat (contoh: hotel), bangunan tersebut pasti

memiliki banyak ruangan, baik yang terdapat pada lantai dasar sampai

dengan lantai yang tertinggi. Setiap ruangan diperlukan sebuah kunci, baik

kunci yang seperti biasa maupun kunci yang berupa sebuah kartu. Pelabelan

total ajaib sisi pada graf roda dapat diterapkan dalam penerapan label

sebagai kode akses dari ruangan-ruangan yang ada di hotel tersebut.

Gambar 4.15 Pelabelan total ajaib sisi pada 𝑊6 dengan 𝑘 = 38

Pada lantai 6 pada sebuah bangunan hotel memiliki 12 ruangan berbeda

di mana setiap ruangan memiliki kodenya masing-masing. Ruangan

tersebut hanya dapat dibuka dengan menggunakan kartu yang memiliki

kode yang sama.

Misalkan kode pada ruangan 601 adalah 160319 sedangkan pada

ruangan 602 adalah 160517. Pada saat menggunakan lift dari kedua kartu

tersebut hanya memiliki akses untuk lantai 6 karena nilai konstanta ajaib

yang diterapkan pada kedua kartu tersebut adalah 38 yang diintegrasikan

8

12 18

3

17

15 9

13

11

6

2

16

1

7

5

19

4 10

14


65

untuk akses untuk lantai 6 dan pada lantai 6 hanya memiliki akses untuk

ruangannya masing-masing.

2. Penerapan password untuk masuk pada sistem internet

Pada jaman modern, kebutuhan untuk terhubung dengan dunia luar

bukan lagi termasuk kebutuhan sekunder, tetapi sudah menjadi kebutuhan

primer. Oleh sebab itu, para penyedia jasa yang saling berlomba-lomba

untuk menawarkan berbagai promo berdasarkan kebutuhan pelanggan.

Penyedia jasa tersebut akan membagi kebutuhan pelanggan tersebut dalam

beberapa tingkatan, baik untuk kelas bawah, kelas menengah maupun kelas

atas, sehingga terdapat banyak pilihan yang dapat ditawarkan kepada

pelanggan. Pelabalan total ajaib sisi dapat diterapkan sebagai kode akses

masuk (password) untuk membedakan setiap tingkatan pelayanan ketika

hendak menggunakan layanan dari penyedia jasa tersebut.

Setiap password merepresentasikan pelabelan dan nilai konstanta ajaib

k merepresentasikan tingkatan pelayanan. Hal ini dapat diterapkan untuk

mengefisienkan sistem pemberian kode. Antara satu buah password dengan

yang lainnya berbeda tetapi memiliki pengelompokan yang sama untuk

tingkat pelayanan jika nilai konstanta ajaib k-nya sama.

Sebagai contoh pada pelabelan total ajaib sisi pada graf roda 𝑊102 di

mana nilai konstanta ajaib yang 512.


66

Graf roda 𝑊102 dengan nilai kostanta ajaib 𝑘 = 512 diperoleh ketika

nilai pusat c adalah 204 dan label-label lainnya seperti yang terdapat pada

tabel berikut ini:

Tabel 4.2 Label 𝑣𝑖 , 𝑒𝑖 dan 𝑠𝑖 pada 𝑊102 dengan 𝑘 = 512 dan 𝑐 = 204

i Titik

(𝑣𝑖)

Jari-

Jari

(𝑒𝑖)

Sisi

(𝑠𝑖)

i Titik

(𝑣𝑖)

Jari-

Jari

(𝑒𝑖)

Sisi

(𝑠𝑖)

1 307 001 103 27 294 014 129

2 102 206 104 28 089 219 130

3 306 002 105 29 293 015 131

4 101 207 106 30 088 220 132

5 305 003 107 31 292 016 133

6 100 208 108 32 087 221 134

7 304 004 109 33 291 017 135

8 099 209 110 34 086 222 136

9 303 005 111 35 290 018 137

10 098 210 112 36 085 223 138

11 302 006 113 37 289 019 139

12 097 211 114 38 084 224 140

13 301 007 115 39 288 020 141

14 096 212 116 40 083 225 142

15 300 008 117 41 287 021 143

16 095 213 118 42 082 226 144

17 299 009 119 43 286 022 145

18 094 214 120 44 081 227 146

19 298 010 121 45 285 023 147

20 093 215 122 46 080 228 148

21 297 011 123 47 284 024 149

22 092 216 124 48 079 229 150

23 296 012 125 49 283 025 151

24 091 217 126 50 078 230 152

25 295 013 127 51 282 026 153

26 090 218 128 52 077 231 155


67

i Titik

(𝑣𝑖)

Jari-

Jari

(𝑒𝑖)

Sisi

(𝑠𝑖)

i Titik

(𝑣𝑖)

Jari-

Jari

(𝑒𝑖)

Sisi

(𝑠𝑖)

53 280 028 156 78 063 245 181

54 076 232 157 79 268 040 182

55 279 029 158 80 062 246 183

56 075 233 159 81 267 041 184

57 278 030 160 82 061 247 185

58 074 234 161 83 266 042 186

59 277 031 162 84 060 248 187

60 073 235 163 85 265 043 188

61 276 032 164 86 059 249 189

62 072 236 165 87 264 044 190

63 275 033 166 88 058 250 191

64 071 237 167 89 263 045 192

65 274 034 168 90 057 251 193

66 070 238 169 91 262 046 194

67 273 035 170 92 056 252 195

68 069 239 171 93 261 047 196

69 272 036 172 94 055 253 197

70 068 240 173 95 260 048 198

71 271 037 174 96 054 254 199

72 067 241 175 97 259 049 200

73 270 038 176 98 053 255 201

74 066 242 177 99 258 050 202

75 269 039 178 100 052 256 179

76 065 243 203 101 281 027 180

77 244 064 205 102 051 257 154

Antara satu pelanggan dengan yang lain akan medapatkan password yg

berbeda, sebagai contoh password untuk Pelanggan A adalah 204307001,

sedangkan password untuk Pelanggan B adalah 204102206. Kedua pelanggan

tersebut mendapatkan tingkat pelayanan yang sama dikarenakan faktor dari

nilai konstanta ajaib k yang ditetapkan pada password tersebut sama yaitu 512


68

Pelabelan total ajaib sisi dengan penerapan penggunaan password tidak

terbatas pada pelayanan internet, tetapi dapat diterapkan untuk hal lainnya,

seperti token pada pulsa seluler, token pulsa listrik, dll.


69

BAB V

PENUTUP

A. Kesimpulan

Dari pembahasan yang terdapat pada skripsi ini, dapat diambil beberapa

kesimpulan antara lain sebagai berikut:

1. Pelabelan total ajaib sisi berlaku pada graf roda 𝑊𝑛.

2. Nilai kosntanta ajaib 𝑘 pada pelabelan total ajaib sisi pada graf roda 𝑊𝑛

berada pada

11𝑛 + 17

4≤ 𝑘 ≤

25𝑛 + 7

4

3. Pelabelan total ajaib sisi graf roda 𝑊𝑛 dapat ditemukan pelabelannya jika

𝑛 ≢ 3(𝑚𝑜𝑑4).

4. Pelabelan total ajaib sisi pada graf roda 𝑊𝑛 di mana 𝑛 ≡ 0(𝑚𝑜𝑑 4) dapat

ditemukan pelabelannya jika label 𝑐 merupakan label dengan bilangan asli

ganjil.

5. Pelabelan total ajaib sisi pada graf roda 𝑊𝑛 di mana 𝑛 ≡ 2(𝑚𝑜𝑑 4) dapat

ditemukan pelabelannya jika label 𝑐 merupakan label dengan bilangan asli

genap.

6. Pelabelan total ajaib sisi pada graf roda 𝑊𝑛 dapat dilakukan secara iteratif

yakni dengan memberi label pada titik tengah, titik pada sikel, jari-jari dan

sisi pada sikel dengan label yang tersedia. Algoritma pelabelan dibangun

dan disimulasikan dengan menggunakan MATLAB 7.1.


70

B. Saran

1. Penelitian selanjutnya dapat membahas Pelabelan Total Tidak – Ajaib Sisi

atau Pelabelan Total Tidak – Ajaib Titik.

2. Penggunaan bahasa pemprograman yang lain yang dapat meningkatkan

kecepatan dalan proses pencarian label.


71

DAFTAR PUSTAKA

Buckley, Fred & Marty Lewinter. (2002). A Friendly Introduction to Graph Theory.

New York : Pearson Education, Inc.

Chartrand, Gari & Ortrud R. Oellermann. (1993). Applied and Algorithmic Graph

Theory. New York : McGraw-Hill, Inc.

Fathoni, Zain. (2011). Penggunaan Audentifikasi Sidik Jari untuk Pengaman

Transaksi ATM. Bandung, 053.

Fukuchi, Y. (2001). Edge Magic Labelings of Wheel Graphs. Tokyo J.Math.

Gallian, J.A. (2016). A Dynamic Survey of Graph Labelings. The Electronic Journal

of Combinatorics, #DS6.

Goodaire, Edgar G. & Michael M. Parmenter. (1998). Discrete Mathematicswith

Graph Theory. New York : Inc.

Kristinawati, A.M. (2015), “Pelabelan Total Ajaib Titik Pada Graf Roda”, Skripsi

Matematika. Yogyakarta : Universitas Sanata Dharma.

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

Stewart, B.M. (1966). Magic Graphs. Canad J.Math.

Wallis, W.D. (2001). Magic Graph. New York : Birkhauser.

Yuliyanto, B.D. (2012), “Pelabelan Total Ajaib Sisi Kuat Pada Graf Sikel Dengan

Tambahan Dua Anting”,Skripsi Matematika. Yogyakarta : Universitas

Sanata Dharma.


72

LAMPIRAN

1. Listing Program

clear all clc disp('========================================================='); disp('========== Programan Pelabelan Total Ajaib Sisi ========='); disp('========================================================='); disp(' Program ini untuk menentukan Pelabelan Total Ajaib Sisi '); disp('========== pada graf roda Wn di mana n~=3(mod 4) ========'); disp('========================================================='); disp(' ');

%Bagian Input

%Input nilai n n=input('Masukan nilai n = '); while mod(n,4)==3 disp('Nilai n yang anda masukan merupakan 3(mod)4'); disp('Silakan diulangi');disp(' '); n=input('Masukan Nilai n = '); end M=1:3*n+1;

%Batas nilai ajaib k kmin=ceil((11*n+17)/4); kmax=floor((25*n+7)/4);

%Input nilai ajaib k fprintf('Batas konstanta magic k pada n = %d',n);disp(' '); fprintf('Nilai k terkecil adalah %d',kmin); fprintf(' dan Nilai k terbesar adalah %d',kmax);disp(' '); tf=0; while tf==0 k=input('Masukan nilai konstanta ajaib k = '); if k<kmin disp('Nilai yang anda masukan kurang dari batas k, silakan

diulangi');disp(' '); elseif k>kmax disp('Nilai yang anda masukan melebihi dari batas k,

silakan diulangi');disp (' '); else tf=1; end end


73

%Bagian Proses

tic; %Batas nilai pusat cmin=k-(4*n+3); cmax=k-(2*n+1); if cmin<1 cmin=1; end

if cmax>3*n+1 cmax=3*n+1; end

kc=cmin:cmax;

if mod(n,4)==0 for i=1:length(kc) if mod(kc(i),2)==0 kc(i)=0; end end kc=unique(kc); kc=setdiff(kc,0); elseif mod(n,4)==2 for i=1:length(kc) if mod(kc(i),2)==1 kc(i)=0; end end kc=unique(kc); kc=setdiff(kc,0); end disp('nilai c yang memenuhi'); disp(kc); fprintf('Pencarian magic graf dengan n = %d',n); fprintf(' dengan nilai k = %d',k);disp(' ');

%Proses perulangan untuk menentukan nilai variabel pada graf roda for j=1:length(kc) %Data awal c=kc(j); fprintf('Proses untuk nilai c = %d',c);disp(' '); A=setdiff(M,c); B=1; for i=1:(1/2)*(k-c-1) B=[B;i;k-c-i]; end y=setdiff(B,A); B=setdiff(B,[y k-c-y]); B=unique(B); B=setdiff(B,[c k-2*c]); tf=0; z=0;


74

while tf==0 C=A; D=B; i=0; z=z+1; if length(D)<2*n break else i=1; end while i<=n+1 if i==1 a=D(randperm(numel(D))); v(i)=a(1); e(i)=k-c-v(i); D=setdiff(D,[v(i) e(i)]); C=setdiff(C,[v(i) e(i)]); elseif i<n+1 a=D(randperm(numel(D))); a=a(1); b=k-c-a; v(i)=a; e(i)=b; d=k-v(i)-v(i-1);s(i-1)=d; if numel(C)==numel(setdiff(C,d)) break end ps=k-c-d; D=setdiff(D,[a b d ps]); C=setdiff(C,[a b d]); f=length(D); if f<2*(n-i) break end elseif i==n+1 s(n)=k-v(1)-v(n); if s(n)==C tf=1; end end i=i+1; end if z==(factorial(n-1))*2^(n); tf=2; end end if tf==1 break else tf=0; end end


75

%Bagian Output %Menampilkan output berhasil atau tidaknya if tf==0 fprintf('Setelah proses perulangan sebanyak %d',z);disp(' kali

untuk setiap nilai c yang memungkinkan'); fprintf('Tidak ditemukan magic grap pada n = %d',n);disp(' '); fprintf('Dengan nilai magic k = %d',k);disp(' '); elseif tf==1 clc H=[v;e;s];H=H'; disp('=======Programan Pelabelan Total Ajaib Sisi ======'); disp('=================================================='); disp(' Program ini untuk menentukan Pelabelan Total Ajaib Sisi

'); disp(' '); fprintf('Dengan n = %d',n); fprintf(' dan konstanta ajaib = %d',k);disp(' ');

fprintf('Diperoleh label titik tengah c = %d',c);fprintf('

dengan');disp(' '); disp('label titik, jari-jari, sisi adalah');disp(H); fprintf('Hasil diperoleh setelah proses perulangan sebanyak

%d',z);disp(' kali'); end


pelabelan total ajaib sisi pada graf roda - core.ac.uk filepelabelan total ajaib sisi pada graf roda...

Documents