pelabelan total ajaib sisi kuat pada graf … · pelabelan total ajaib sisi kuat pada graf sikel...

PELABELAN TOTAL AJAIB SISI KUAT

PADA GRAF SIKEL DENGAN TAMBAHAN 𝒏 ANTING

UNTUK 𝒏 ≥ 𝟑 DAN 𝒏 GANJIL

Skripsi

Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana

Program Studi Pendidikan Matematika

Oleh:

Ayu Kristianna

091414050

PROGRAM STUDI PENDIDIKAN MATEMATIKA

JURUSAN PENDIDIKAN MATEMATIKA DAN ILMU PENGETAHUAN ALAM

FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN

UNIVERSITAS SANATA DHARMA

YOGYAKARTA

2013

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJIPLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

i

PELABELAN TOTAL AJAIB SISI KUAT

PADA GRAF SIKEL DENGAN TAMBAHAN 𝒏 ANTING

UNTUK 𝒏 ≥ 𝟑 DAN 𝒏 GANJIL

Skripsi

Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana

Program Studi Pendidikan Matematika

Oleh:

Ayu Kristianna

091414050

PROGRAM STUDI PENDIDIKAN MATEMATIKA

JURUSAN PENDIDIKAN MATEMATIKA DAN ILMU PENGETAHUAN ALAM

FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN

UNIVERSITAS SANATA DHARMA

YOGYAKARTA

2013


ii


iii


iv

”Ia membuat segala sesuatu indah pada waktunya, bahkan Ia memberikan

kekekalan dalam hati mereka.” (Kolose 3:23)

Kupersembahkan karya ini untuk:

Tuhan Yesus Kristus, Sahabat dan Juru Selamat

yang selalu menyertai setiap langkahku

Orang tuaku terkasih, Bapak Yohanes Sumiran dan

Ibu Anastasia Sri Murwani atas segala kasih, doa,

dukungan, serta pengorbanan selama hidupku

Adik-adikku, Lukas Kris Pradikta dan

Ester Rina Apriliyani yang menjadi pemacu semangatku

Fr. Adrianus Wisnu W., OCSO, Ibu Inge Umboh, serta

seluruh keluarga besar yang telah mendukungku

Almamaterku “SMA Sedes Sapientiae Bedono” dan

“Universitas Sanata Dharma Yogyakarta”


v

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, 20 Agustus 2013

Penulis,

Ayu Kristianna


vi

LEMBAR PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH

UNTUK KEPENTINGAN AKADEMIS

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

Nama : Ayu Kristianna

NIM : 091414050

Demi pengembangan ilmu pengetahuan, saya memberikan kepada

Perpustakaan Universitas Sanata Dharma karya ilmiah saya yang berjudul:

Pelabelan Total Ajaib Sisi Kuat

Pada Graf Sikel dengan Tambahan 𝒏 Anting untuk 𝒏 ≥ 𝟑 dan 𝒏 Ganjil

Dengan demikian saya memberikan kepada Perpustakaan Universitas

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 saya buat dengan sebenarnya.

Dibuat di Yogyakarta

Pada Tanggal : 20 Agustus 2013

Yang menyatakan,

(Ayu Kristianna)


vii

ABSTRAK

Ayu Kristianna, 2013. Pelabelan Total Ajaib Sisi Kuat pada Graf Sikel dengan

Tambahan 𝒏 Anting untuk 𝒏 ≥ 𝟑 dan 𝒏 Ganjil. Program Studi Pendidikan

Matematika, Jurusan Pendidikan Matematika dan Ilmu Pengetahuan Alam,

Fakultas Keguruan dan Ilmu Pendidikan, Universitas Sanata Dharma,

Yogyakarta.

Penelitian ini menyelidiki pelabelan total ajaib sisi kuat pada graf sikel

dengan tambahan 𝑛 anting untuk 𝑛 ≥ 3 dan 𝑛 ganjil. Tujuan dari penelitian ini

adalah meninjau apakah graf sikel dengan tambahan 𝑛 anting untuk 𝑛 ≥ 3 dan 𝑛

ganjil memenuhi pelabelan total ajaib sisi kuat, menentukan nilai konstanta ajaib

yang terbentuk, serta menentukan nilai label untuk masing-masing titik dan sisi.

Penelitian ini mengkaji beberapa buku, jurnal, dan hasil penelitian sebelumnya

untuk mendapatkan teori-teori yang mendukung.

Hasil penelitian ini menunjukkan bahwa pelabelan total ajaib sisi kuat

berlaku pada graf sikel dengan tambahan 𝑛 anting untuk 𝑛 ≥ 3 dan 𝑛 ganjil

dengan nilai konstanta ajaib 𝑐 terletak pada interval 9𝑛+3

2≤ 𝑐 ≤

11𝑛+3

2. Nilai label

titik dan sisi untuk pelabelan total ajaib sisi kuat pada graf sikel dengan tambahan

𝑛 anting, 𝑛 ≥ 3 dan 𝑛 ganjil untuk 𝑐 =9𝑛+3

2 dan 𝑐 =

11𝑛+3

2 adalah sebagai

berikut:

a. Untuk 𝑐 =9𝑛+3

2

1) 𝑛 = 2𝑘 + 1, 𝑘 = 1, 3, 5, …,

𝑤 𝑣𝑖 =

𝑖 + 1

2 𝑖 = 1, 3, 5, … , 𝑛

𝑛 + 𝑖 + 1

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

𝑤 𝑣𝑛+𝑖 =

3𝑛 + 𝑖 + 2

2 𝑖 = 1, 3, 5, … , 𝑛 − 2

2 𝑛 + 1 + 𝑖

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

𝑛 + 1 𝑖 = 𝑛


viii

𝑤 𝑒𝑖 ,𝑖+1 = 4𝑛 − 𝑖 𝑖 = 1, 2, 3, … , 𝑛 − 1

𝑤 𝑒1,𝑖 = 4𝑛 𝑖 = 𝑛

𝑤 𝑒𝑖 ,𝑛+𝑖 = 3𝑛 − 𝑖 𝑖 = 1, 2, 3, … , 𝑛 − 13𝑛 𝑖 = 𝑛

2) 𝑛 = 2𝑘 + 1, 𝑘 = 2, 4, 6, …,

𝑤 𝑣𝑖 =

𝑖 + 1

2 𝑖 = 1, 3, 5, … , 𝑛

𝑛 + 1 + 𝑖

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

𝑤 𝑣𝑛+𝑖 = 2𝑛 − 𝑖 + 1 𝑖 = 1, 2, 3, … , 𝑛

𝑤 𝑒𝑖 ,𝑖+1 = 4𝑛 − 𝑖 𝑖 = 1, 2, 3, … , 𝑛 − 1

𝑤 𝑒1,𝑖 = 4𝑛 𝑖 = 𝑛

𝑤 𝑒𝑖 ,𝑛+𝑖 =

5𝑛 + 𝑖

2 𝑖 = 1, 3, 5, … , 𝑛

4𝑛 + 𝑖

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

b. Untuk 𝑐 =11𝑛+3

2

𝑤 𝑣𝑖 =

2𝑛 + 𝑖 + 1

2 𝑖 = 1, 3, 5, … , 𝑛

3𝑛 + 𝑖 + 1

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

𝑤 𝑣𝑛+𝑖 = 𝑛 − 𝑖 𝑖 = 1, 2, 3, … , 𝑛 − 1𝑛 𝑖 = 𝑛

𝑤 𝑒𝑖 ,𝑖+1 = 3𝑛 − 𝑖 𝑖 = 1, 2, 3, … , 𝑛 − 1

𝑤 𝑒1,𝑖 = 3𝑛 𝑖 = 𝑛


7𝑛 + 𝑖 + 2

2 𝑖 = 1, 3, 5, … , 𝑛 − 2

6𝑛 + 𝑖 + 2

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

3𝑛 + 1 𝑖 = 𝑛

Kata Kunci : graf, pelabelan graf, graf sikel dengan tambahan 𝑛 anting, pelabelan

total ajaib sisi kuat


ix

ABSTRACT

Ayu Kristianna, 2013. Strong Edge Magic Total Labeling on The Cycle Graph

with 𝒏 Extra Arms for 𝒏 ≥ 𝟑 and 𝒏 is Odd. Mathematics Education Study

Program. Mathematics and Science Education Department, Faculty of

Teachers Training and Education, Sanata Dharma University, Yogyakarta.

This research observed the strong edge magic total labeling on the cycle

graph with 𝑛 extra arms for 𝑛 ≥ 3 and 𝑛 is odd. The purpose of this research is to

observe whether the cycle graph with 𝑛 extra arms for 𝑛 ≥ 3 and 𝑛 is odd satisfy

the strong edge magic total labeling, to observe the value of magic constant, and

to find the labeling values for each vertex and edge. This research examined

several books, journals, and the result of previous researches to obtain the

supporting theories.

The result of this research show that the cycle graph with 𝑛 extra arms for

𝑛 ≥ 3 and 𝑛 is odd satisfy the strong edge magic total labeling with the value of

magic constant 9𝑛+3

2≤ 𝑐 ≤

11𝑛+3

2. The labeling values for each vertex and edge on

the strong edge magic total labeling on the cycle graph with 𝑛 extra arms, 𝑛 ≥ 3

and 𝑛 is odd for 𝑐 =9𝑛+3

2 and 𝑐 =

11𝑛+3

2 are shown as below:

a. For 𝑐 =9𝑛+3

2

1) 𝑛 = 2𝑘 + 1, 𝑘 = 1, 3, 5, …,

𝑤 𝑣𝑖 =

𝑖 + 1

2 𝑖 = 1, 3, 5, … , 𝑛

𝑛 + 𝑖 + 1

2 𝑖 = 2, 4, 6, … , 𝑛 − 1


3𝑛 + 𝑖 + 2

2 𝑖 = 1, 3, 5, … , 𝑛 − 2

2 𝑛 + 1 + 𝑖

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

𝑛 + 1 𝑖 = 𝑛

𝑤 𝑒𝑖 ,𝑖+1 = 4𝑛 − 𝑖 𝑖 = 1, 2, 3, … , 𝑛 − 1


x

𝑤 𝑒1,𝑖 = 4𝑛 𝑖 = 𝑛

𝑤 𝑒𝑖 ,𝑛+𝑖 = 3𝑛 − 𝑖 𝑖 = 1, 2, 3, … , 𝑛 − 13𝑛 𝑖 = 𝑛

2) 𝑛 = 2𝑘 + 1, 𝑘 = 2, 4, 6, …,

𝑤 𝑣𝑖 =

𝑖 + 1

2 𝑖 = 1, 3, 5, … , 𝑛

𝑛 + 1 + 𝑖

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

𝑤 𝑣𝑛+𝑖 = 2𝑛 − 𝑖 + 1 𝑖 = 1, 2, 3, … , 𝑛

𝑤 𝑒𝑖 ,𝑖+1 = 4𝑛 − 𝑖 𝑖 = 1, 2, 3, … , 𝑛 − 1

𝑤 𝑒1,𝑖 = 4𝑛 𝑖 = 𝑛


5𝑛 + 𝑖

2 𝑖 = 1, 3, 5, … , 𝑛

4𝑛 + 𝑖

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

b. For 𝑐 =11𝑛+3

2

𝑤 𝑣𝑖 =

2𝑛 + 𝑖 + 1

2 𝑖 = 1, 3, 5, … , 𝑛

3𝑛 + 𝑖 + 1

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

𝑤 𝑣𝑛+𝑖 = 𝑛 − 𝑖 𝑖 = 1, 2, 3, … , 𝑛 − 1𝑛 𝑖 = 𝑛

𝑤 𝑒𝑖 ,𝑖+1 = 3𝑛 − 𝑖 𝑖 = 1, 2, 3, … , 𝑛 − 1

𝑤 𝑒1,𝑖 = 3𝑛 𝑖 = 𝑛


7𝑛 + 𝑖 + 2

2 𝑖 = 1, 3, 5, … , 𝑛 − 2

6𝑛 + 𝑖 + 2

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

3𝑛 + 1 𝑖 = 𝑛

Key words : graph, graph labeling, cycle graph with 𝑛 extra arms, strong edge

magic total labeling


xi

KATA PENGANTAR

Puji dan syukur kehadirat Tuhan Yang Maha Kuasa atas segala kasih, rahmat

dan berkat-Nya sehingga penulis dapat menyelesaikan skripsi dengan judul

”Pelabelan Total Ajaib Sisi Kuat pada Graf Sikel dengan Tambahan 𝑛 Anting

untuk 𝑛 ≥ 3 dan 𝑛 Ganjil” ini . Skripsi ini diajukan untuk memenuhi salah satu

syarat memperoleh gelar sarjana pendidikan pada Program Studi Pendidikan

Matematika, Jurusan Pendidikan Matematika dan Ilmu Pengetahuan Alam, Fakultas

Keguruan dan Ilmu Pendidikan, Universitas Sanata Dharma, Yogyakarta.

Skripsi ini dapat tersusun berkat bimbingan dan bantuan dari berbagai pihak.

Oleh karena itu, pada kesempatan kali ini penulis menyampaikan terima kasih

kepada:

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

Akademik sekaligus dosen pembimbing skripsi atas dukungan dan bimbingan

selama studi terlebih selama proses penyusunan skripsi ini

2. Bapak Rohandi, Ph.D selaku Dekan Fakultas Keguruan dan Ilmu Pendidikan

Universitas Sanata Dharma

3. Bapak Drs. A. Atmadi, M.Si. selaku Ketua Jurusan Pendidikan dan Ilmu

Pengetahuan Alam, FKIP, Universitas Sanata Dharma

4. Bapak Dr. M. Andy Rudhito, S.Pd. selaku Kaprodi Pendidikan Matematika

5. Bapak Drs. Thomas Sugiarto, M.T. dan Bapak Sutrisno, M.Sc. selaku dosen

penguji skripsi


xii

6. Seluruh Dosen Program Studi Pendidikan Matematika yang telah banyak

memberikan ilmu pengetahuan dan bekal keterampilan sehingga penulis dapat

menyelesaikan studi dengan baik

7. Kedua orang tua penulis, Bapak Yohanes Sumiran dan Ibu Anastasia Sri

Murwani, Adik Lukas Kris Pradikta dan Ester Rina Apriliyani, Eyang Maria

Suyatmi, fr. Adrianus Wisnu W. OCSO, Ibu Inge Umboh, serta Dominico S.

Saputra yang telah memberikan dukungan dan doa

8. Teman-teman Program Studi Pendidikan Matematika Angkatan 2009, khususnya

Yasintha Rizky, Chintya Rudiyanto, Ryan Sanjaya, Endar Retnowati, Cicilia

Viranti, serta Th. Ridarta Intan P. yang telah berbagi hari-hari menyenangkan

serta semangat dan dukungan untuk terus maju

9. Semua pihak yang tidak dapat disebutkan satu persatu, atas bantuan dan saran

yang berguna selama penulisan skripsi ini

Penulis mengharapkan kritik dan saran guna kemajuan penelitian, khususnya

dalam bidang matematika. Akhir kata, penulis berharap kiranya skripsi ini dapat

bermanfaat bagi para pembaca.

Yogyakarta, 20 Agustus 2013

Penulis


xiii

DAFTAR ISI

Halaman

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

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

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

HALAMAN PERSEMBAHAN ..................................................................... iv

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

PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH............. vi

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

ABSTRACT ................................................................................................... ix

KATA PENGANTAR .................................................................................... xi

DAFTAR ISI ................................................................................................... xiii

DAFTAR GAMBAR ...................................................................................... xv

DAFTAR TABEL ........................................................................................... xvii

DAFTAR NOTASI ......................................................................................... xviii

BAB I PENDAHULUAN ............................................................................... 1

1.1. Latar Belakang ................................................................................. 1

1.2. Batasan Masalah ............................................................................... 5

1.3. Rumusan Masalah ............................................................................ 5

1.4. Tujuan ............................................................................................... 5

1.5. Manfaat Penelitian ............................................................................ 6

1.6. Metode Penelitian ............................................................................. 6

1.7. Sitematika Penulisan ........................................................................ 7


xiv

BAB II KAJIAN PUSTAKA DAN LANDASAN TEORI ............................ 9

2.1. Teori Graf ......................................................................................... 9

2.2. Pelabelan Graf .................................................................................. 22

2.3. Graf Sikel dengan Tambahan Satu Anting ...................................... 24

2.4. Graf Sikel dengan Tambahan Dua Anting ....................................... 25

2.5. Kerangka Berpikir ............................................................................ 27

BAB III HASIL PENELITIAN DAN PEMBAHASAN ................................ 28

3.1. Pelabelan Total Ajaib Sisi Kuat pada Graf Sikel dengan

Tambahan n Anting .......................................................................... 28

3.2. Pelabelan Total Ajaib Sisi Kuat pada 𝐶𝑛 + 𝑛𝐴1 untuk 𝑛 ≥ 3 dan

𝑛 Ganjil dengan 𝑐 =9𝑛+3

2 .......................................................... 34

3.3. Pelabelan Total Ajaib Sisi Kuat pada 𝐶𝑛 + 𝑛𝐴1 untuk 𝑛 ≥ 3 dan

𝑛 Ganjil dengan 𝑐 =11𝑛+3

2 ......................................................... 47

BAB IV PENUTUP ........................................................................................ 55

4.1. Kesimpulan ...................................................................................... 55

4.2. Saran ................................................................................................. 57

DAFTAR PUSTAKA ..................................................................................... 58


xv

DAFTAR GAMBAR

Halaman

Gambar 1.1 Model Jembatan Königsberg................................................... 1

Gambar 1.2 Graf Model Jembatan Königsberg .......................................... 2

Gambar 1.3 Ilustrasi Kondisi Jalan Raya menggunakan Graf .................... 3

Gambar 2.1 Graf ......................................................................................... 10

Gambar 2.2 Bukan Graf .............................................................................. 10

Gambar 2.3 Graf 𝐺1 .................................................................................... 12

Gambar 2.4 Graf Sederhana ........................................................................ 14

Gambar 2.5 Graf Tak Sederhana................................................................. 15

Gambar 2.6 Graf Berhingga ........................................................................ 15

Gambar 2.7 Graf Tak Berhingga................................................................. 16

Gambar 2.8 Graf Tak Berarah..................................................................... 17

Gambar 2.9 Graf Berarah ............................................................................ 17

Gambar 2.10 Graf Lengkap .......................................................................... 18

Gambar 2.11 Graf Sikel ................................................................................ 19

Gambar 2.12 Graf Roda ................................................................................ 19

Gambar 2.13 Graf Teratur ............................................................................. 20

Gambar 2.14 Graf Planar .............................................................................. 20

Gambar 2.15 Graf Tak Planar ....................................................................... 21

Gambar 2.16 Graf Bidang ............................................................................. 21

Gambar 2.17 Graf Bipartit ............................................................................ 22

Gambar 2.18 Pelabelan Total Ajaib Sisi pada Graf 𝐶4 dengan 𝑐 = 12 ........ 23


xvi

Gambar 2.19 Pelabelan Total Ajaib Sisi Kuat pada Graf 𝐶3 dengan 𝑐 = 9 . 24

Gambar 2.20 Graf Sikel dengan Tambahan Satu Anting ............................. 25

Gambar 2.21 Graf Sikel dengan Tambahan Dua Anting .............................. 26

Gambar 3.1 Graf Sikel dengan Tambahan 𝑛 Anting .................................. 28

Gambar 3.2 Ilustrasi Pelabelan Total Ajaib Sisi Kuat pada 𝐶𝑛 + 𝑛𝐴1, 𝑛 ≥ 3,

𝑛 = 2𝑘 + 1, 𝑘 = 1, 3, 5,… , 𝑐 =9𝑛+3

2 .................................... 42

Gambar 3.3 Ilustrasi Pelabelan Total Ajaib Sisi Kuat pada 𝐶𝑛 + 𝑛𝐴1, 𝑛 ≥ 3

𝑛 = 2𝑘 + 1, 𝑘 = 2, 4, 6,… , 𝑐 =9𝑛+3

2 ..................................... 43

Gambar 3.4 Pelabelan Total Ajaib Sisi Kuat pada 𝐶7 + 7𝐴1, 𝑐 = 33 ....... 45


Gambar 3.6 Ilustrasi Pelabelan Total Ajaib Sisi Kuat pada 𝐶𝑛 + 𝑛𝐴1, 𝑛 ≥ 3,

𝑛 Ganjil, 𝑐 =11𝑛+3

2 ................................................................. 52



xvii

DAFTAR TABEL

Halaman

Tabel 3.1 Interval Nilai c pada Pelabelan Total Ajaib Sisi Kuat pada

𝐶𝑛 + 𝑛𝐴1 ...................................................................................... 32

Tabel 3.2 Nilai Label Titik dan Sisi pada Pelabelan Total Ajaib Sisi Kuat pada

𝐶𝑛 + 𝑛𝐴1 untuk 𝑛 ≥ 3 dan 𝑛 Ganjil dengan 𝑐 =9𝑛+3

2 ............... 34

Tabel 3.3 Nilai Label Titik dan Sisi pada Pelabelan Total Ajaib Sisi Kuat pada

𝐶𝑛 + 𝑛𝐴1 untuk 𝑛 ≥ 3 dan 𝑛 Ganjil dengan 𝑐 =11𝑛+3

2 ............ 47


xviii

DAFTAR NOTASI

𝑉(𝐺) himpunan titik di 𝐺

𝐸(𝐺) himpunan sisi di 𝐺

𝑉(𝐺) order (banyak titik) dari 𝐺

𝐸(𝐺) size (banyak sisi) dari 𝐺

𝑣𝑖 titik ke-𝑖

𝑒𝑖 ,𝑗 sisi yang menghubungkan titki ke-𝑖 dan titik ke-𝑗

𝑆𝑣 jumlah semua label titik

𝑆𝑒 jumlah semua label sisi

𝑆𝑤 jumlah semua bobot sisi

𝑤(𝑣𝑖) label titik 𝑣𝑖

𝑤 𝑒𝑖 ,𝑗 label sisi 𝑒𝑖 ,𝑗

𝑤𝑡 𝑒𝑖 ,𝑗 bobot masing-masing sisi 𝑒𝑖 ,𝑗

𝐶𝑛 graf sikel berorder 𝑛

𝐴1 anting pada graf

∅ himpunan kosong

∪ gabungan himpunan

□ akhir pembuktian


1

BAB I

PENDAHULUAN

1.1 Latar Belakang

Teori graf merupakan salah satu pokok bahasan yang memiliki banyak

terapan praktis hingga saat ini. Graf digunakan untuk merepresentasikan

objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi

visual dari graf adalah dengan menyatakan objek sebagai noktah, bulatan,

atau titik (vertex), sedangkan hubungan antara objek dinyatakan dengan garis

atau sisi (edge).

Teori graf muncul pertama kali pada tahun 1736 ketika Leonhard Euler,

seorang matematikawan dari Swiss, mencoba mencari solusi dari

permasalahan Jembatan Königsberg. Sungai Pregel yang melalui kota

Königsberg membagi wilayah daratan pada kota tersebut menjadi empat

bagian dengan tujuh buah jembatan dibangun di atasnya seperti gambar

berikut.

Gambar 1.1 Model Jembatan Königsberg

Teka-teki Jembatan Königsberg mulai muncul pada abad XVII ketika

warga Königsberg memikirkan apakah mungkin untuk berjalan di seluruh


2

wilayah Königsberg dengan melalui setiap jembatan hanya sekali. Teka-teki

tersebut menarik perhatian Euler yang kemudian merepresentasikan masalah

tersebut dalam sebuah diagram. Diagram tersebut terdiri dari empat titik A,

B, C, dan D yang merepresentasikan keempat wilayah daratan, serta tujuh

buah garis yang merepresentasikan jembatan, seperti terlihat pada gambar

berikut (Suryadi, 1996:3).

Gambar 1.2 Graf Model Jembatan Königsberg

Salah satu kajian yang banyak diteliti dan dikembangkan dalam teori graf

adalah pelabelan graf yang pertama kali diperkenalkan oleh Sedláček (1963),

kemudian Stewart (1966), serta Kotzig dan Rosa (1970). Hingga saat ini

pemanfaatan teori pelabelan graf sangat dirasakan peranannya, misalnya pada

sektor sistem komunikasi, transportasi, navigasi geografis, radar,

penyimpanan data komputer, dan pemancar frekuensi radio.

Pada sektor transportasi misalnya, pelabelan graf digunakan untuk

memantau arus dan kepadatan kendaraan di jalan. Graf yang digunakan

adalah graf berarah yang menunjukkan arah arus kendaraan yang telah diberi

label berupa lambang bilangan pada masing-masing titik dan sisinya. Label

pada titik menunjukkan banyak kendaraan yang melewati titik tersebut setiap


3

satuan waktu. Sementara itu, label pada sisi menunjukkan kapasitas efektif

jalan untuk dilalui sejumlah kendaraan setiap satuan waktu beserta presentase

dari kondisi arus sebenarnya dibandingkan kapasitas efektif jalan. Bila arus

kendaraan telah melebihi kapasitas efektif jalan, maka presentasenya akan

bernilai lebih dari 100%. Bila terjadi kepadatan di suatu titik, polisi dapat

berkoordinasi untuk mengalihkan sebagian kendaraan ke jalur yang belum

padat. Sistem ini diterapkan terutama pada kondisi tertentu seperti mudik

tahunan.

Gambar 1.3 Ilustrasi Kondisi Jalan Raya menggunakan Graf

Pelabelan pada suatu graf adalah suatu pemetaan bijektif yang

memetakan unsur-unsur graf (titik dan/atau sisi) dengan bilangan bulat

positif. Jika domain dari pelabelan adalah titik (vertex), maka pelabelan

tersebut dinamakan pelabelan titik (vertex labelling), jika domainnya adalah

sisi (edge), maka pelabelannya disebut pelabelan sisi (edge labelling),

sedangkan jika domainnya adalah titik dan sisi, maka pelabelannya disebut

pelabelan total (total labelling) (Wallis, 2001:11).

150

100

120

200

60

100

125

25

75/75%

160/125%

125/100%

75/100%

50/50%

120/50%

160/75%


4

Salah satu jenis pelabelan yang dikenal hingga saat ini adalah pelabelan

ajaib (magic labeling), yang dibagi menjadi dua yaitu pelabelan ajaib sisi

(edge magic labeling) dan pelabelan ajaib titik (vertex magic labeling). Pada

penelitian ini akan digunakan pelabelan ajaib sisi yaitu pemetaan bijektif

yang memetakan himpunan titik dan sisi pada himpunan bilangan bulat

{1, 2, 3, … , 𝑒 + 𝑣} dengan 𝑒 menyatakan banyak titik dan 𝑣 menyatakan

banyak sisi, sedemikian hingga bobot masing-masing sisinya sama/konstan.

Bobot sisi adalah jumlah dari label sisi dan label titik-titik yang bersisian

dengan sisi tersebut.

Penelitian mengenai pelabelan ajaib terus berkembang hingga kemudian

Wallis (2001:17) memperkenalkan istilah pelabelan total ajaib sisi kuat

(strong edge magic total labeling). Pelabelan ajaib sisi dikatakan kuat jika

himpunan titik-titiknya 𝑣1 , 𝑣2, 𝑣3, … , 𝑣𝑛 dipetakan satu-satu dengan

himpunan bilangan bulat positif {1, 2, 3, … , 𝑣} dengan 𝑣 menyatakan banyak

titik pada graf tersebut. Graf yang memenuhi pelabelan total ajaib sisi kuat

dinamakan graf total ajaib sisi kuat.

Berdasarkan hasil penelitian sebelumnya, penulis mengembangkan hasil

penelitian yang berkaitan dengan graf total ajaib sisi kuat dengan menentukan

interval serta pola konstanta ajaib yang terbentuk pada graf sikel 𝐶𝑛 dengan

tambahan 𝑛 anting, serta rumus pelabelan total ajaib sisi kuat pada graf sikel

𝐶𝑛 dengan tambahan 𝑛 anting untuk nilai konstanta ajaib dengan pola

tertentu.


5

1.2 Batasan Masalah

Pada tugas akhir ini, graf yang digunakan adalah graf yang berhingga,

sederhana, dan tak berarah, yaitu graf sikel 𝐶𝑛 dengan tambahan 𝑛 anting

untuk 𝑛 ≥ 3 dan 𝑛 ganjil. Anting pada graf sikel 𝐶𝑛 dibentuk dari 𝑛 buah

titik yang masing-masing dihubungkan dengan tepat satu titik pada graf sikel

𝐶𝑛 oleh sebuah sisi. Titik-titik di luar graf sikel 𝐶𝑛 berturut-turut dinamakan

𝑣𝑛+1 , 𝑣𝑛+2 , 𝑣𝑛+3 , … , 𝑣2𝑛 . Sedangkan pelabelan yang digunakan adalah

pelabelan total ajaib sisi kuat (strong edge magic total labeling).

1.3 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 kuat berlaku pada graf sikel 𝐶𝑛 dengan

tambahan 𝑛 anting untuk 𝑛 ≥ 3 dan 𝑛 ganjil? Bagaimana interval

konstanta ajaib yang terbentuk?

2. Bagaimana rumus untuk menentukan nilai label titik dan sisi pada

pelabelan total ajaib sisi kuat pada graf sikel 𝐶𝑛 dengan tambahan 𝑛

anting untuk 𝑛 ≥ 3 dan ganjil dengan nilai konstanta ajaib berpola

tertentu?


6

1.4 Tujuan Penelitian

1. Mengetahui apakah pelabelan total ajaib sisi kuat berlaku pada graf sikel

𝐶𝑛 dengan tambahan 𝑛 anting untuk 𝑛 ≥ 3 dan 𝑛 ganjil, serta mengetahui

bagaimana interval dari konstanta ajaib yang terbentuk.

2. Mengetahui rumus untuk menentukan nilai label titik dan sisi pada

pelabelan total ajaib sisi kuat pada graf sikel 𝐶𝑛 dengan tambahan 𝑛

anting untuk 𝑛 ≥ 3 dan 𝑛 ganjil untuk nilai konstanta ajaib dengan pola

tertentu.

1.5 Manfaat Penelitian

Manfaat dari penelitian ini adalah:

1. Menambah jenis graf baru yang memenuhi pelabelan total ajaib sisi kuat

2. Menambah wawasan mengenai pelabelan total ajaib sisi kuat

3. Dapat memberi label pada graf sikel dengan tambahan 𝑛 anting dengan

menentukan nilai konstanta ajaibnya

1.6 Metode Penelitian

Penelitian yang digunakan 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 suatu


7

generalisasi yang bersifat umum (deduktif). Secara garis besar langkah

penelitian ini sebagai berikut.

1. Mengumpulkan berbagai literatur yang berhubungan dengan topik

2. Mempelajari topik

3. Menganalisa sifat-sifat pelabelan total ajaib sisi kuat (strong edge magic

total labeling)

4. Membangun graf sikel dengan tambahan 𝑛 anting dan menganalisa sifat

graf tersebut

5. Menentukan apakah pelabelan total ajaib sisi kuat berlaku pada graf sikel

dengan tambahan 𝑛 anting untuk 𝑛 ≥ 3 dan 𝑛 ganjil, sekaligus

menentukan pola konstanta ajaib yang terbentuk

6. Menentukan rumus nilai label titik dan sisi pada graf sikel dengan

tambahan 𝑛 anting, 𝑛 ≥ 3 dan 𝑛 ganjil untuk nilai konstanta ajaib dengan

pola tertentu

1.7 Sistematika Penulisan

Sistematika penulisan tugas akhir ini dibagi menjadi empat bagian:

BAB I : PENDAHULUAN

Pada bab ini dijelaskan mengenai latar belakang, rumusan masalah,

pembatasan masalah, tujuan penelitian, manfaat penelitian, metode

penelitian, dan sistematika penulisan.


8

BAB II : KAJIAN PUSTAKA DAN LANDASAN TEORI

Pada bab ini dijelaskan mengenai teori graf dasar seperti definisi graf,

beberapa istilah dalam teori graf, jenis-jenis graf, pelabelan graf, graf sikel

dengan tambahan satu anting (𝐶𝑛 + 𝐴1), serta graf sikel dengan tambahan

dua anting (𝐶𝑛 + 2𝐴1).

BAB III : HASIL PENELITIAN DAN PEMBAHASAN

Pada bab ini dianalisis mengenai sifat graf sikel dengan tambahan 𝑛

anting, pelabelan total ajaib sisi kuat pada graf tersebut, serta rumus nilai

label masing-masing titik dan sisi pada graf tersebut, khususnya untuk 𝑛 ≥ 3

dan 𝑛 ganjil untuk nilai konstanta ajaib dengan pola tertentu.

BAB IV : PENUTUP

Pada bab ini dijelaskan kesimpulan dari pembahasan yang telah diuraikan

pada bab sebelumnya serta saran-saran yang berkaitan dengan pembahasan

tersebut.


9

BAB II

KAJIAN PUSTAKA DAN LANDASAN TEORI

2.1. Teori Graf

1. Pengertian Graf

Definisi 2.1.1 (Goodaire dan Parmenter, 1998:329)

Graf adalah himpunan pasangan terurut 𝐺 = (𝑉, 𝐸) di mana 𝑉(𝐺)

himpunan tak kosong dan 𝐸(𝐺) adalah himpunan pasangan elemen yang

berbeda di 𝑉(𝐺). Elemen 𝑉(𝐺) disebut titik (vertex) dan elemen 𝐸(𝐺)

disebut sisi (edge). Jadi, jika 𝑒 ∈ 𝐸(𝐺), maka e merupakan himpunan

pasangan 𝑒 = (𝑣𝑖 , 𝑣𝑗 ), di mana 𝑣𝑖 ≠ 𝑣𝑗 , 𝑣𝑖 , 𝑣𝑗 ∈ 𝑉(𝐺). Selanjutnya, 𝑣𝑖

dan 𝑣𝑗 disebut titik ujung dari e, atau dengan kata lain 𝑒 = (𝑣𝑖 , 𝑣𝑗 )

menghubungkan titik 𝑣𝑖 dan 𝑣𝑗 . Selanjutnya sisi 𝑒 = (𝑣𝑖 , 𝑣𝑗 ) dinotasikan

dengan 𝑒𝑖 ,𝑗 di mana sisi tersebut merupakan sisi yang sama dengan sisi

𝑒 = (𝑣𝑗 , 𝑣𝑖) yang dinotasikan dengan 𝑒𝑗 ,𝑖 .

Banyaknya unsur di 𝑉(𝐺) disebut order dari G dilambangkan

dengan 𝑉(𝐺) dan banyaknya unsur di 𝐸(𝐺) disebut ukuran (size) dari

𝐺 dilambangkan dengan 𝐸(𝐺) . Secara geometris graf dapat

digambarkan sebagai sekumpulan titik pada bidang dimensi dua yang

dihubungkan dengan sekumpulan sisi (Chartrand dan Oellermann,

1993:3).


10

Contoh:

Gambar 2.1 Graf

Pada Gambar 2.1 gambar (a) merupakan graf dengan 𝑉(𝐺) = 7 dan

𝐸(𝐺) = 8, sedangkan gambar (b) merupakan graf dengan 𝑉(𝐺) = 6

dan 𝐸(𝐺) = 0.

Gambar 2.2 Bukan Graf

Gambar 2.2 bukan merupakan graf karena tidak memenuhi definisi 2.1.1

yaitu 𝑉 𝐺 = ∅.

2. Beberapa Istilah dalam Graf

Berikut diberikan definisi berdekatan (adjacent) yang digunakan

untuk menjelaskan jenis-jenis graf khususnya graf lengkap (complete

graph).

(a) (b)


11

Definisi 2.1.2 (Munir, 2001:191)

Misal terdapat dua titik 𝑣𝑖 dan 𝑣𝑗 pada graf G, dua titik tersebut

dikatakan berdekatan (adjacent) bila terdapat sebuah sisi yang

menghubungkan kedua titik tersebut. Dapat ditulis dengan notasi

𝑒 = (𝑣𝑖 , 𝑣𝑗 ) ∈ 𝐸(𝐺) di mana 𝑣𝑖 ≠ 𝑣𝑗 .

Berikut diberikan definisi bersisian (incident) yang digunakan untuk

menjelaskan derajat sebuah titik, graf sikel dan graf planar, pelabelan

total ajaib sisi, serta sifat pada graf sikel dengan tambahan 𝑛 anting.


Diberikan graf G dan 𝑣𝑖 , 𝑣𝑗 ∈ 𝑉 𝐺 , jika terdapat sebuah sisi yang

menghubungkan 𝑣𝑖 dengan 𝑣𝑗 , dinotasikan 𝑒 = (𝑣𝑖 , 𝑣𝑗 ) ∈ 𝐸(𝐺) maka

dikatakan bahwa e bersisian (incident) dengan titik 𝑣𝑖 dan 𝑣𝑗 .

Berikut diberikan definisi derajat (degree) sebuah titik yang

digunakan untuk menjelaskan jenis-jenis graf khususnya graf teratur.

Definisi 2.1.4 (Chartrand dan Oellermann, 1993:6)

Derajat (degree) sebuah titik 𝑣𝑖 pada graf G yang dituliskan dengan

deg(𝑣𝑖) menyatakan banyak sisi yang bersisian dengan 𝑣𝑖 , dengan kata

lain banyak sisi yang memuat 𝑣𝑖 sebagai titik ujung. Titik dengan derajat

nol disebut titik terisolasi (isolated vertex).


12

Berikut diberikan definisi sisi ganda (multiple edge) yang digunakan

untuk menjelaskan jenis-jenis graf khususnya graf sederhana dan graf

tak sederhana.


Jika terdapat beberapa sisi berbeda pada graf yang menghubungkan

pasangan titik yang sama maka graf tersebut dikatakan mempunyai sisi

ganda (multiple edge).

Berikut diberikan definisi sisi ganda (multiple edge) yang digunakan

untuk menjelaskan jenis-jenis graf khususnya graf sederhana dan graf

tak sederhana.


Jika terdapat sebuah sisi pada graf yang berawal dan berakhir pada satu

titik maka graf tersebut dikatakan memiliki gelang (loop).

Berikut diberikan contoh untuk memperjelas Definisi 2.1.2, 2.1.3,

2.1.4, 2.1.5, dan 2.1.6.

Contoh :

Gambar 2.3 Graf 𝐺1

𝑣1

𝑣2 𝑣3

𝑣4 𝑣7

𝑣5 𝑣6

𝑒1

𝑒9

𝑒3

𝑒5

𝑒2

𝑒6

𝑒8

𝑒4

𝑒7


13

Graf 𝐺1 memuat himpunan titik 𝑉 𝐺1 = {𝑣1 , 𝑣2, 𝑣3, 𝑣4, 𝑣5,𝑣6, 𝑣7} dan

himpunan sisi 𝐸 𝐺1 = 𝑒1 , 𝑒2, 𝑒3, 𝑒4, 𝑒5,𝑒6 , 𝑒7 , 𝑒8 , 𝑒9 .

(i) Pada graf 𝐺1, pasangan titik 𝑣2 dan 𝑣3 serta titik 𝑣2 dan 𝑣5

merupakan titik-titik yang adjacent karena terhubung langsung oleh

sebuah sisi yaitu sisi 𝑒2 dan sisi 𝑒8, sedangkan titik 𝑣2 dan 𝑣4

bukan merupakan titik-titik yang adjacent karena tidak terdapat sisi

yang menghubungkan 𝑣2 dan 𝑣4.

(ii) Pada graf 𝐺1, sisi 𝑒1 incident dengan titik 𝑣1 dan 𝑣2 karena 𝑒1

menghubungkan 𝑣1 dan 𝑣2, tetapi tidak terdapat sisi yang incident

dengan titik 𝑣1dan 𝑣3 karena tidak ada sisi yang menghubungkan

kedua titik tersebut.

(iii) Pada graf 𝐺1, deg(𝑣3) = 4, deg(𝑣5) = 4, deg(𝑣1) = 2, 𝑣7 disebut

isolated vertex karena deg(𝑣7) = 0.

(iv) Graf 𝐺1 memuat multiple edge yaitu sisi 𝑒6 dan 𝑒7 karena dua sisi

tersebut menghubungkan pasangan titik yang sama yaitu 𝑣5 dan 𝑣6,

serta memuat loop yaitu 𝑣3, 𝑒3, 𝑣3 dimana sisi 𝑒3 berawal dan

berakhir di satu titik yaitu titik 𝑣3.

3. Jenis-jenis Graf

Graf dikelompokkan berdasarkan sifat-sifatnya, antara lain

berdasarkan ada tidaknya gelang atau sisi ganda, berdasarkan banyaknya

titik, serta berdasarkan orientasi arah pada sisinya.


14

Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf,

graf dikelompokkan menjadi dua jenis (Munir, 2001:182), yaitu:

a. Graf Sederhana (Simple Graph)

Graf sederhana adalah graf yang tidak mengandung gelang maupun

sisi-ganda.

Contoh:

Gambar 2.4 Graf Sederhana

b. Graf Tak Sederhana (Unsimple Graph)

Graf tak sederhana adalah graf yang mengandung sisi ganda atau

gelang atau keduanya. Graf tak sederhana dibagi menjadi dua

macam, yaitu graf ganda (multigraph) dan graf semu (pseudograph).

Graf ganda adalah graf yang mengandung sisi ganda. Graf semu

adalah graf yang mengandung sisi ganda dan gelang.


15

Contoh :

Gambar 2.5 Graf Tak Sederhana

Pada Gambar 2.5, (a) merupakan graf ganda karena memiliki sisi

ganda, sedangkan (b) merupakan graf semu karena selain memiliki

sisi ganda juga memiliki gelang.

Berdasarkan banyak titik pada suatu graf, maka secara umum graf

dapat dikelompokkan menjadi dua jenis (Munir, 2001:183), yaitu :

a. Graf Berhingga (Finite Graph)

Graf berhingga adalah graf yang banyak titiknya berhingga.

Contoh:

Gambar 2.6 Graf Berhingga

b. Graf Tak Berhingga (Infinite Graph)

Graf tak berhingga adalah graf yang banyak titiknya tidak berhingga.

(a) (b)


16

Contoh :

Gambar 2.7 Graf Tak Berhingga

Berdasarkan orientasi arah pada sisi, maka secara umum graf

dikelompokkan menjadi dua jenis (Munir, 2001:183), yaitu :

a. Graf Tak Berarah (Undirected Graph)

Graf tak berarah adalah graf yang sisinya tidak mempunyai orientasi

arah. Pada graf tak berarah, urutan pasangan titik yang dihubungkan

oleh sisi tidak diperhatikan. Jadi (𝑣𝑖 , 𝑣𝑗 ) dan (𝑣𝑗 , 𝑣𝑖) adalah sisi yang

sama.


17

Contoh:

Gambar 2.8 Graf Tak Berarah

b. Graf Berarah (Directed Graph/Diagraph)

Graf berarah adalah graf yang setiap sisinya diberikan orientasi arah.

Pada graf berarah (𝑣𝑖 , 𝑣𝑗 ) dan (𝑣𝑗 , 𝑣𝑖) menyatakan dua sisi yang

berbeda ((𝑣𝑖 , 𝑣𝑗 ) ≠ (𝑣𝑗 , 𝑣𝑖)). Pada sisi (𝑣𝑖 , 𝑣𝑗 ) titik 𝑣𝑖 dinamakan

titik asal (initial vertex) dan titik 𝑣𝑗 dinamakan titik terminal

(terminal vertex), sedangkan pada sisi (𝑣𝑗 , 𝑣𝑖) titik 𝑣𝑗 dinamakan

titik asal (initial vertex) dan titik 𝑣𝑖 dinamakan titik terminal

(terminal vertex).

Contoh :

Gambar 2.9 Graf Berarah

𝒗𝟐

𝒗𝟏

𝒗𝟒

𝒗𝟑

𝒗𝟐

𝒗𝟏

𝒗𝟑

𝒗𝟓

𝒗𝟒

𝒗𝟔

𝒗𝟐

𝒗𝟏

𝒗𝟒

𝒗𝟑

𝒗𝟐

𝒗𝟏

𝒗𝟑

𝒗𝟓

𝒗𝟒

𝒗𝟔


18

Terdapat beberapa jenis graf sederhana khusus (Munir, 2001:205) antara

lain:

a. Graf Lengkap (Complete Graph)

Graf lengkap adalah graf sederhana yang setiap titiknya berdekatan

atau terhubung langsung oleh satu sisi. Graf lengkap dengan n buah

titik dilambangkan dengan Kn. Banyak sisi pada sebuah graf lengkap

yang terdiri dari n buah titik adalah 𝑛(𝑛 − 1)/2.

Contoh :

Gambar 2.10 Graf Lengkap

Gambar 2.12 menunjukkan graf lengkap 𝐾1, 𝐾2, 𝐾3, 𝐾4 dan 𝐾5

dengan banyak titik masing-masing 1, 2, 3, 4, dan 5.

b. Graf Sikel (Cycle Graph)

Graf sikel merupakan graf sederhana yang setiap titiknya

mempunyai dua sisi yang bersisian. Graf sikel dengan n titik

dilambangkan dengan 𝐶𝑛 .


19

Contoh:

Gambar 2.11 Graf Sikel

Gambar 2.11 menunjukkan graf sikel 𝐶3, 𝐶4 , 𝐶5 dan 𝐶6 dengan

banyak titik masing-masing 3, 4, 5, dan 6.

c. Graf Roda (Wheels Graph)

Graf roda merupakan graf yang diperoleh dengan cara

menambahkan satu titik pada graf sikel 𝐶𝑛 , dan menghubungkan titik

baru tersebut dengan semua titik pada graf sikel tersebut.

Contoh:

Gambar 2.12 Graf Roda

d. Graf Teratur (Regular Graph)

Graf teratur merupakan graf yang setiap titiknya mempunyai derajat

yang sama. Apabila derajat setiap titik pada graf teratur adalah r,

maka graf tersebut dinamakan graf teratur berderajat r. Banyak sisi

pada graf teratur dengan n titik adalah 1

2𝑛𝑟 sisi.


20

Contoh :

Gambar 2.13 Graf Teratur

Gambar 2.13 menunjukkan graf teratur dengan 𝑟 = 2 dan 𝑟 = 3.

e. 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-sisinya yang

berpotongan kecuali di titik di mana keduanya bersisian. Namun,

suatu graf mungkin saja planar meskipun biasanya digambarkan

dengan sisi yang saling berpotongan, karena graf tersebut dapat

digambarkan dengan cara berbeda di mana sisi-sisinya tidak saling

berpotongan. Graf planar yang digambarkan dengan sisi-sisi yang

tidak saling berpotongan disebut graf bidang.

Contoh:

Gambar 2.14 Graf Lengkap 𝐾4 merupakan Graf Planar


21

Gambar 2.15 Graf Lengkap 𝐾5 merupakan Graf Tak Planar

Gambar 2.16 Semua Graf Sikel dan Graf Lengkap 𝐾1, 𝐾2, 𝐾3

merupakan Graf Bidang

f. Graf Bipartit (Bipartite Graph)

Suatu graf sederhana G disebut bipartit jika mempunyai himpunan

titik V yang dapat dipartisi menjadi dua himpunan tak kosong yang

tak beririsan 𝑉1 dan 𝑉2 sedemikian hingga setiap sisi hubung dalam

graf menghubungkan suatu titik di 𝑉1 dengan titik di 𝑉2, atau tak ada

sisi hubung di dalam G yang menghubungkan dua titik di 𝑉1 maupun

di 𝑉2.


22

Contoh:

Gambar 2.17 Graf Bipartit

Dari Gambar 2.17 kedua graf adalah graf bipartit karena setiap sisinya

menghubungkan dua titik dari himpunan yang berbeda.

2.2. Pelabelan Graf (Graf Labeling)

Pelabelan graf adalah pemetaan bijektif yang memetakan elemen dari

graf tersebut (titik dan/atau sisi) dengan bilangan bulat positif. Terdapat

beberapa macam pelabelan graf berdasarkan domainnya, yaitu pelabelan

titik (vertex labeling) yang domainnya himpunan titik, pelabelan sisi (edge

labeling) yang domainnya himpunan sisi, serta pelabelan total (total

labeling) yang domainnya titik dan sisi.

Bobot adalah jumlahan dari label-label pada setiap elemen graf. Pada

pelabelan graf terdapat dua jenis pelabelan menurut jumlah dari setiap

bobotnya yaitu pelabelan ajaib (magic labeling) dan pelabelan tak ajaib

(antimagic labeling). Pelabelan ajaib adalah suatu pelabelan yang bobot

masing-masing titik atau sisinya sama/konstan, sedangkan pelabelan tak

ajaib adalah suatu pelabelan yang bobot masing-masing titik atau sisinya

berbeda.


23

Pada penelitian ini akan digunakan pelabelan total ajaib sisi kuat (strong

edge magic total labeling).

Definisi 2.2.1 (Wallis, 2001:17)

Pelabelan total ajaib sisi adalah pemetaan bijektif 𝑤 dari 𝐸(𝐺) ∪ 𝑉(𝐺) ke

bilangan bulat positif 1, 2, 3, … , 𝑒 + 𝑣, dengan 𝑒 = 𝐸(𝐺) dan 𝑣 = 𝑉(𝐺) ,

jika terdapat konstanta c sedemikian sehingga untuk setiap sisi 𝑒𝑖 ,𝑗 dan

semua titik 𝑣𝑖 dan 𝑣𝑗 yang bersisian dengan sisi 𝑒𝑖 ,𝑗 berlaku:

𝑤(𝑣𝑖) + 𝑤 𝑒𝑖 ,𝑗 + 𝑤(𝑣𝑗 ) = 𝑐

dengan 𝑤(𝑒𝑖 ,𝑗 ) adalah label sisi 𝑒𝑖 ,𝑗 , 𝑤(𝑣𝑖) dan 𝑤(𝑣𝑗 ) adalah label titik yang

bersisian dengan sisi 𝑒𝑖 ,𝑗 . Dengan kata lain 𝑤𝑡(𝑒𝑖 ,𝑗 ) = 𝑐 untuk setiap sisi sisi

𝑒𝑖 ,𝑗 , dengan 𝑤𝑡(𝑒𝑖 ,𝑗 ) adalah bobot masing-masing sisi 𝑒𝑖 ,𝑗 . Bilangan c

disebut konstanta ajaib (magic constant) dari 𝐺.

Contoh:

Gambar 2.18 Pelabelan Total Ajaib Sisi pada Graf 𝐶4 dengan 𝑐 = 12

Pada Gambar 2.18 bobot setiap sisi konstan, yaitu 12. Bobot 𝑒1,2 adalah

1 + 5 + 6 = 12, bobot 𝑒2,3 adalah 6 + 4 + 2 = 12, bobot 𝑒3,4 adalah

2 + 7 + 3 = 12, dan bobot 𝑒1,4 adalah 1 + 8 + 3 = 12. Jadi contoh

5

8

2

6

3

1

4

7

𝑣2

𝑣4 𝑣1

𝑣3


24

pelabelan pada Gambar 2.20 disebut pelabelan total ajaib sisi pada 𝐶4

dengan 𝑐 = 12.

Definisi 2.2.2 (Wallis, 2001:17)

Pelabelan total ajaib sisi dikatakan kuat (strong) jika label-label titiknya

merupakan bilangan bulat positif 1, 2, 3, … , 𝑣, 𝑣 = 𝑉(𝐺) .

Contoh:

Gambar 2.19 Pelabelan Total Ajaib Sisi Kuat pada Graf 𝐶3 dengan 𝑐 = 9

Pada Gambar 2.19 𝑉(𝐺) = 3 dan bobot setiap sisi konstan yaitu 9.

Bobot 𝑒1,2 adalah 1 + 6 + 2 = 9, bobot 𝑒2,3 adalah 2 + 4 + 3 = 9, dan

bobot 𝑒1,3 adalah 3 + 5 + 1 = 9. Karena bobot setiap sisi konstan dan label-

label titiknya adalah 1, 2, 3 maka contoh pelabelan pada Gambar 2.21

disebut pelabelan total ajaib sisi kuat pada 𝐶3 dengan 𝑐 = 9.

2.3. Graf Sikel (Cycle Graph) dengan Tambahan Satu Anting

Graf sikel merupakan graf sederhana yang setiap titiknya berderajat dua,

atau graf dengan lintasan tertutup. Graf sikel dengan n titik dilambangkan

dengan 𝐶𝑛 .

Graf sikel dengan tambahan satu anting merupakan pengembangan

bentuk dari graf sikel 𝐶𝑛 dengan menambahkan satu titik diluar 𝐶𝑛 dan

5

6

4

3

1 2 𝑣1 𝑣2

𝑣3


25

sebuah sisi yang menghubungkan titik tersebut dengan 𝐶𝑛 . Graf sikel

dengan tambahan satu anting dilambangkan dengan 𝐶𝑛 + 𝐴1 (Septian,

2011:27).

Contoh:

Gambar 2.20 Graf Sikel dengan Tambahan Satu Anting

Setiap graf sikel dengan tambahan satu anting (𝐶𝑛 + 𝐴1) mempunyai

𝑎, 𝑑 𝑉𝐴𝑇𝐿 (vertex antimagic total labeling) dengan 𝑎 ≥ 3 dan 𝑑 ≤ 8

untuk semua 𝑛 ≥ 3. Jika label sisi adalah himpunan bilangan bulat positif

{1, 2, 3, … , 𝑛 + 1} dan label titik adalah himpunan bilangan bulat positif

{𝑛 + 2, 𝑛 + 3, … , 2𝑛 + 2} maka nilai 𝑎 adalah 𝑛(5−𝑑)

2+ 4. Untuk 𝑛 ≥ 3 dan

𝑛 ganjil, 𝑑 = 1, 3, 5; untuk 𝑛 ≥ 3 dan 𝑛 genap, 𝑑 = 2, 4; sedangkan

𝑑 = 6, 7, 8 tidak memenuhi untuk semua 𝑛 ≥ 3. Pada graf sikel dengan

tambahan satu anting (𝐶𝑛 + 𝐴1) terdapat 2𝑛 + 4, 1 𝑉𝐴𝑇𝐿 dan 𝑛 +

4, 3 𝑉𝐴𝑇𝐿 untuk 𝑛 ≥ 3 dan 𝑛 ganjil (Septian, 2011:56).

2.4. Graf Sikel (Cycle Graph) dengan Tambahan Dua Anting

Graf sikel dengan tambahan dua anting merupakan pengembangan dari

graf sikel 𝐶𝑛 dengan menambahkan dua titik diluar 𝐶𝑛 dan dua sisi yang

(a) 𝐶4 + 𝐴1 (b) 𝐶5 + 𝐴1 (c) 𝐶6 + 𝐴1


26

menghubungkan masing-masing titik tersebut dengan 𝐶𝑛 . Graf sikel dengan

tambahan satu anting dilambangkan dengan 𝐶𝑛 + 2𝐴1 (Yuliyanto, 2012:26).

Contoh:

Gambar 2.21 Graf Sikel dengan Tambahan Satu Anting

Graf sikel dengan tambahan dua anting (𝐶𝑛 + 2𝐴1) memenuhi pelabelan

total ajaib sisi kuat dengan nilai konstanta ajaib 𝑐 terletak pada interval

5𝑛+9

2< 𝑐 <

5𝑛+17

2. Untuk nilai konstanta ajaib 𝑐 =

5𝑛+13

2, nilai label untuk

masing-masing titik dan sisi adalah sebagai berikut:

𝑤 𝑣1 =𝑛 + 1

2

𝑤 𝑣2 = 2

𝑤 𝑣𝑖 =

𝑛 + 4 + 𝑖

2 𝑖 = 3, 5, 7, … , 𝑛

𝑖 + 1

2 𝑖 = 4, 6, 8, … , 𝑛 − 1

𝑤 𝑣𝑛+1 = 1

𝑤 𝑣𝑛+2 =𝑛 + 5

2

𝑤 𝑒1,2 = 2𝑛 + 3

𝑤 𝑒𝑖 ,𝑖+1 = 2𝑛 + 3 − 𝑖 𝑖 = 2, 3, 4, … , 𝑛 − 1

𝑤 𝑒1,𝑛 = 𝑛 + 3

(a) 𝐶4 + 2𝐴1 (b) 𝐶6 + 2𝐴1


27

𝑤 𝑒1,𝑛+1 = 2𝑎 + 4

𝑤 𝑒2,𝑛+2 = 2𝑎 + 2 (Yuliyanto, 2012:71).

2.5. Kerangka Berpikir

Sejauh ini telah dipelajari teori terkait definisi tentang graf, pelabelan

graf, serta hasil dari penelitian sebelumnya. Berdasarkan apa yang telah

dipelajari tersebut akan diselidiki apakah pelabelan total ajaib sisi kuat

(strong edge magic total labeling) berlaku pada graf sikel dengan

tambahan 𝑛 anting, 𝑛 ≥ 3, 𝑛 ganjil dan akan ditentukan interval nilai

konstanta ajaib c, serta akan diselidiki bagaimana rumus nilai label titik

dan sisi pada pelabelan total ajaib sisi kuat pada graf sikel dengan

tambahan 𝑛 anting, 𝑛 ≥ 3 dan 𝑛 ganjil untuk nilai konstanta ajaib 𝑐

dengan pola tertentu.


28

BAB III

HASIL PENELITIAN DAN PEMBAHASAN

3.1. Pelabelan Total Ajaib Sisi Kuat (Strong Edge Magic Total Labeling)

pada Graf Sikel dengan Tambahan 𝒏 Anting

Graf sikel dengan tambahan n anting merupakan pengembangan dari

graf sikel 𝐶𝑛 dengan menambahkan n buah titik diluar 𝐶𝑛 yang masing-

masing dihubungkan dengan tepat satu titik pada 𝐶𝑛 oleh sebuah sisi. Graf

sikel dengan tambahan n anting dilambangkan dengan 𝐶𝑛 + 𝑛𝐴1.

Gambar 3.1 Graf Sikel dengan Tambahan n Anting

Pada 𝐶𝑛 + 𝑛𝐴1 terdapat 𝑛 buah titik dan 𝑛 buah sisi pada 𝐶𝑛 serta 𝑛

buah titik di luar 𝐶𝑛 dan 𝑛 buah sisi yang yang masing-masing

menghubungkan sebuah titik di luar 𝐶𝑛 dengan tepat satu titik pada 𝐶𝑛 .

Titik dan sisi yang menjadi anting pada graf sikel tersebut merupakan titik

ke 𝑛 + 1, 𝑛 + 2, 𝑛 + 3, … , 2𝑛, serta garis ke 𝑛 + 1, 𝑛 + 2, 𝑛 + 3, … , 2𝑛,

sehingga banyak titik dan sisi pada 𝐶𝑛 + 𝑛𝐴1 adalah 4𝑛.

(a) 𝐶4 + 4𝐴1 (b) 𝐶𝑛 + 𝑛𝐴1

𝑒𝑛 ,2𝑛

𝑣8

𝑣4 𝑣3 𝑒7

𝑣1 𝑣2

𝑣6

𝑣5 𝑒1,2

𝑒2,3

𝑒3,7 𝑒3,4

𝑒1,4

𝑒1,5

𝑒3,4

𝑒2,6

𝑣2

𝑣3

𝑣2𝑛

𝑣2𝑛−1

𝑣𝑛+1

𝑣𝑛+3

𝑣𝑛+2

𝑣𝑛−1

𝑣𝑛

𝑣1

𝑒1,𝑛+1

𝑒2,𝑛+2

𝑒2,3

𝑣1,2

𝑒3,𝑛+3

𝑒1,𝑛

𝑒𝑛−1,2𝑛−1

𝑒𝑛−1,𝑛

𝑒1,2


29

Pada 𝐶𝑛 + 𝑛𝐴1 bobot setiap sisi yang dilambangkan dengan 𝑤𝑡(𝑒𝑖 ,𝑗 )

ditentukan dengan rumus berikut:

𝑤𝑡 𝑒𝑖 ,𝑗 =

𝑤(𝑣𝑖) + 𝑤 𝑒𝑖 ,𝑖+1 + 𝑤(𝑣𝑖+1)

𝑤(𝑣𝑖) + 𝑤 𝑒𝑖 ,1 + 𝑤(𝑣1)

𝑤(𝑣𝑖) + 𝑤 𝑒𝑖 ,𝑛+𝑖 + 𝑤(𝑣𝑛+𝑖)

Pada pelabelan total ajaib sisi pada 𝐶𝑛 + 𝑛𝐴1 terdapat n label titik yang

dihitung tiga kali karena bersisian dengan tepat tiga sisi yaitu label titik

𝑣1 , 𝑣2 , 𝑣3, … , 𝑣𝑛 , dan n label titik yang dihitung satu kali karena bersisian

dengan tepat satu sisi yaitu label titik 𝑣𝑛+1 , 𝑣𝑛+2 , 𝑣𝑛+3, … , 𝑣2𝑛 , sedangkan

semua label sisi dihitung satu kali. Akibatnya:

𝑆𝑤 = 𝑆𝑒 + 3 𝑤(𝑣𝑖)

𝑛

1

+ 𝑤 𝑣𝑖

2𝑛

𝑛+1

𝑆𝑤 = 𝑆𝑒 + 𝑤 𝑣𝑖

2𝑛

1

+ 2 𝑤(𝑣𝑖)

𝑛

1

𝑆𝑤 = 𝑆𝑒 + 𝑆𝑣 + 2 𝑤(𝑣𝑖)

𝑛

1

dengan 𝑆𝑤 merupakan jumlah semua bobot sisi, 𝑆𝑒 merupakan jumlah

semua label sisi, dan 𝑆𝑣 merupakan jumlah semua label titik.

Berdasarkan Definisi 2.2.1, karena banyak titik dan sisi pada 𝐶𝑛 + 𝑛𝐴1

adalah 4𝑛, akibatnya label titik dan sisi untuk graf tersebut adalah

1, 2, 3, … , 4𝑛. Sedangkan banyak sisinya adalah 2𝑛, akibatnya 𝑆𝑤 = 2𝑛. 𝑐

atau penjumlahan berulang nilai konstanta ajaib 𝑐 sebanyak 2𝑛:

𝑆𝑤 = 𝑆𝑒 + 𝑆𝑣 + 2 𝑤(𝑣𝑖)

𝑛

1

𝑖 = 1, 2, 3, … , 𝑛 − 1

𝑖 = 1, 2, 3, … , 𝑛

𝑖 = 𝑛


30

2𝑛. 𝑐 = (1 + 2 + 3 + ⋯ + 4𝑛) + 2 𝑤(𝑣𝑖)

𝑛

1

2𝑛𝑐 = 2𝑛 4𝑛 + 1 + 2 𝑤 𝑣𝑖

𝑛

1

… (𝟑. 𝟏)

Berdasarkan Definisi 2.2.2, label titik dari 𝑣1, 𝑣2, 𝑣3, … , 𝑣2𝑛 adalah

1, 2, 3, … , 2𝑛, dan berdasarkan persamaan (3.1) hasil perhitungan

ditentukan dari yaitu jumlah nilai label titik 𝑣1 , 𝑣2, 𝑣3, … , 𝑣𝑛 .

Terdapat tiga kemungkinan memilih 𝑛 buah label untuk 𝑣1 , 𝑣2, 𝑣3 , … , 𝑣𝑛

yaitu:

1. Jika dipilih 𝑛 buah label dengan susunan 1,2,3, … , 𝑛 maka akan

menghasilkan jumlah nilai label dengan nilai terkecil.

2. Jika dipilih 𝑛 buah label dengan susunan 𝑛 + 1, 𝑛 + 2, 𝑛 + 3, … ,2𝑛

maka akan menghasilkan jumlah nilai label dengan nilai

terbesar.

3. Jika dipilih 𝑛 sebarang bilangan dari 1, 2, 3, … , 2𝑛 maka akan

menghasilkan jumlah nilai label dengan nilai antara yang

terkecil dan yang terbesar.

Berdasarkan tiga kemungkinan di atas, diperoleh hasil sebagai berikut:

1) Jika 𝑣1 , 𝑣2, 𝑣3, … , 𝑣𝑛 diberi label 1,2,3, … , 𝑛, akibatnya:

𝑤 𝑣𝑖

𝑛

1

= 1 + 2 + 3 + ⋯ + 𝑛

𝑤 𝑣𝑖

𝑛

1

=𝑛

2 𝑛 + 1 … (𝟑. 𝟐)

𝑤 𝑣𝑖

𝑛

1

( 𝑤 𝑣𝑖

𝑛

1

)

( 𝑤 𝑣𝑖

𝑛

1

)

( 𝑤 𝑣𝑖

𝑛

1

)


31

Substitusi persamaan (3.2) ke persamaan (3.1):

2𝑛𝑐 = 2𝑛 4𝑛 + 1 + 2.𝑛

2(𝑛 + 1)

𝑐 =2𝑛 4𝑛 + 1 + 𝑛(𝑛 + 1)

2𝑛

𝑐 =2 4𝑛 + 1 + (𝑛 + 1)

2

𝑐 =9𝑛 + 3

2

2) Jika 𝑣1 , 𝑣2, 𝑣3, … , 𝑣𝑛 diberi label 𝑛 + 1, 𝑛 + 2, 𝑛 + 3, … ,2𝑛,

akibatnya:

𝑤 𝑣𝑖

𝑛

1

= 𝑛 + 1 + 𝑛 + 2 + 𝑛 + 3 + ⋯ + 2𝑛

𝑤 𝑣𝑖

𝑛

1

=𝑛

2 3𝑛 + 1 … (𝟑. 𝟑)

Substitusi persamaan (3.3) ke persamaan (3.1):

2𝑛𝑐 = 2𝑛 4𝑛 + 1 + 2.𝑛

2(3𝑛 + 1)

𝑐 =2𝑛 4𝑛 + 1 + 𝑛(3𝑛 + 1)

2𝑛

𝑐 =2 4𝑛 + 1 + (3𝑛 + 1)

2

𝑐 =11𝑛 + 3

2


32

3) Jika 𝑣1 , 𝑣2, 𝑣3, … , 𝑣𝑛 diberi label 𝑛 sebarang bilangan dari

1, 2, 3, … , 2𝑛, akibatnya:

9𝑛 + 3

2≤ 𝑐 ≤

11𝑛 + 3

2

Dari kemungkinan 1) , 2) dan 3) diperoleh nilai konstanta ajaib c terletak

pada interval:

9𝑛 + 3

2≤ 𝑐 ≤

11𝑛 + 3

2 … 𝟑. 𝟒

Tabel 3.1 berikut menyatakan hubungan antara nilai n dan konstanta

ajaib c yang terbentuk pada pelabelan total ajib sisi kuat pada 𝐶𝑛 + 𝑛𝐴1.

Tabel 3.1 Interval Nilai c pada Pelabelan Total Ajaib Sisi Kuat pada

𝐶𝑛 + 𝑛𝐴1

n ganjil n genap

n interval nilai c kemungkinan

nilai c n interval nilai c

kemungkinan

nilai c

3 15 ≤ 𝑐 ≤ 18 15, 16, 17, 18 4 19,5 ≤ 𝑐 ≤ 23,5 20, 21, 22, 23

5 24 ≤ 𝑐 ≤ 29 24, 25, 26, 27,

28, 29 6 28,5 ≤ 𝑐 ≤ 34,5

29, 30, 31, 32, 33, 34

7 33 ≤ 𝑐 ≤ 40 33, 34, 35, 36, 37, 38, 39, 40

8 37,5 ≤ 𝑐 ≤ 45,5 38, 39, 40, 41, 42, 43, 44, 45

9 42 ≤ 𝑐 ≤ 51 42, 43, 44, 45, 46, 47, 48, 49,

50, 51 10 46,5 ≤ 𝑐 ≤ 56,5

47, 48, 49, 50, 51, 52, 53, 54,

55, 56

11 51 ≤ 𝑐 ≤ 62 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62

12 55,5 ≤ 𝑐 ≤ 67,5 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67

13 60 ≤ 𝑐 ≤ 73

60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71

72, 73

14 64,5 ≤ 𝑐 ≤ 78,5

65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76,

77, 78

… … … … … …

Pada skripsi ini akan dibahas pelabelan total ajaib sisi kuat pada

𝐶𝑛 + 𝑛𝐴1 untuk 𝑛 ≥ 3 dan n ganjil dengan nilai konstanta ajaib 𝑐 =9𝑛+3

2


33

dan 𝑐 =11𝑛+3

2. Peneliti tidak melakukan penelitian untuk pelabelan total

ajaib sisi kuat pada 𝐶𝑛 + 𝑛𝐴1 untuk 𝑛 genap, maupun pelabelan total ajaib

sisi kuat pada 𝐶𝑛 + 𝑛𝐴1 untuk 𝑛 ganjil dengan pola yang lain, misalnya

untuk nilai konstanta ajaib dengan nilai 9𝑛+5

2,

9𝑛+7

2,

9𝑛+9

2, … ,

11𝑛+1

2,

11𝑛+3

2.

Teorema 3.1

Graf sikel dengan tambahan n anting memenuhi pelabelan total ajaib sisi

kuat untuk 𝑛 ≥ 3 dan 𝑛 ganjil dengan nilai konstanta ajaib terletak pada

interval 9𝑛+3

2≤ 𝑐 ≤

11𝑛+3

2.

Bukti:

Berdasarkan Definisi 2.2.2, label titik dari 𝑣1, 𝑣2, 𝑣3, … , 𝑣2𝑛 adalah

1, 2, 3, … , 2𝑛, dan berdasarkan persamaan (3.1) hasil perhitungan

ditentukan dari yaitu jumlah nilai label titik 𝑣1 , 𝑣2, 𝑣3, … , 𝑣𝑛 .

Terdapat tiga kemungkinan memilih 𝑛 buah label untuk 𝑣1 , 𝑣2, 𝑣3 , … , 𝑣𝑛

yaitu:

1) Jika dipilih 𝑛 buah label dengan susunan 1,2,3, … , 𝑛 akibatnya

.

2) Jika dipilih 𝑛 buah label dengan susunan 𝑛 + 1, 𝑛 + 2, 𝑛 + 3, … ,2𝑛

akibatnya .

3) Jika dipilih 𝑛 sebarang bilangan dari 1, 2, … , 2𝑛 akibatnya

𝑤 𝑣𝑖

𝑛

1

𝑐 =9𝑛 + 3

2

𝑐 =11𝑛 + 3

2

9𝑛 + 3

2≤ 𝑐 ≤

11𝑛 + 3

2


34

Dari 1), 2), dan 3) diperoleh bahwa nilai konstanta ajaib pada

pelabelan total ajaib sisi kuat pada graf sikel dengan tambahan 𝑛

anting untuk 𝑛 ≥ 3 dan 𝑛 ganjil terletak pada interval

□

3.2. Pelabelan Total Ajaib Sisi Kuat pada 𝑪𝒏 + 𝒏𝑨𝟏 untuk 𝒏 ≥ 𝟑 dan n

Ganjil dengan 𝒄 =𝟗𝒏+𝟑

𝟐

Dalam penelitian ini diambil salah satu pola pelabelan yang

memenuhi pelabelan total ajaib sisi kuat pada 𝐶𝑛 + 𝑛𝐴1 untuk 𝑛 ≥ 3 dan 𝑛

ganjil dengan nilai konstanta ajaib 𝑐 =9𝑛+3

2 seperti yang ditunjukkan pada

tabel 3.2 berikut.

Tabel 3.2 Nilai Label Titik dan Sisi pada Pelabelan Total Ajaib Sisi Kuat

pada 𝐶𝑛 + 𝑛𝐴1 untuk 𝑛 ≥ 3 dan 𝑛 Ganjil dengan 𝑐 =9𝑛+3

2

3 5 7 9 11 13 …

1 1 1 1 1 1 1 …

2 3 4 5 6 7 8 …

3 2 2 2 2 2 2 …

4 5 6 7 8 9 …

5 3 3 3 3 3 …

6 7 8 9 10 …

7 4 4 4 4 …

8 9 10 11 …

9 5 5 5 …

10 11 12 …

11 6 6 …

12 13 …

13 7 …

…

…

𝑛 𝑣𝑖

9𝑛 + 3

2≤ 𝑐 ≤

11𝑛 + 3

2


35

3 5 7 9 11 13 …

𝑛 + 1 6 10 12 18 18 26 …

𝑛 + 2 5 9 9 17 13 25 …

𝑛 + 3 4 8 13 16 19 24 …

𝑛 + 4

7 10 15 14 23 …

𝑛 + 5

6 14 14 20 22 …

𝑛 + 6

11 13 15 21 …

𝑛 + 7

8 12 21 20 …

𝑛 + 8

11 16 19 …

𝑛 + 9

10 22 18 …

𝑛 + 10

17 17 …

𝑛 + 11

12 16 …

𝑛 + 12

15 …

𝑛 + 13

14 …

…

…

3 5 7 9 11 13 …

1,2 11 19 27 35 43 51 …

2,3 10 18 26 34 42 50 …

3,4 17 25 33 41 49 …

4,5 16 24 32 40 48 …

5,6 23 31 39 47 …

6,7 22 30 38 46 …

7,8 29 37 45 …

8,9 28 36 44 …

9,10 35 43 …

10,11 34 42 …

11,12 41 …

12,13 40 …

…

…

1, 𝑛 12 20 28 36 44 52 …

3 5 7 9 11 13 …

1, 𝑛 + 1 8 13 20 23 32 33 …

2, 𝑛 + 2 7 11 19 19 31 27 …

3, 𝑛 + 3 9 14 18 24 30 34 …

4, 𝑛 + 4 12 17 20 29 28 …

5, 𝑛 + 5 15 16 25 28 35 …

𝑛 𝑒𝑖 ,𝑖+1

𝑛 𝑒𝑖 ,𝑛+𝑖

𝑛 𝑣𝑖


36

3 5 7 9 11 13 …

6, 𝑛 + 6 15 21 27 29 …

7, 𝑛 + 7 21 26 26 36 …

8, 𝑛 + 8 22 25 30 …

9, 𝑛 + 9 27 24 37 …

10, 𝑛 + 10 23 31 …

11, 𝑛 + 11 33 38 …

12, 𝑛 + 12 32 …

13, 𝑛 + 13 39 …

…

…

Dari tabel di atas, pelabelan total ajaib sisi kuat pada 𝐶𝑛 + 𝑛𝐴1 untuk

𝑛 ≥ 3 dan 𝑛 ganjil dengan nilai konstanta ajaib 𝑐 =9𝑛+3

2 dapat dibagi

menjadi dua pola pelabelan yaitu untuk 𝑛 = 2𝑘 + 1, 𝑘 = 1, 3, 5, … dan

𝑛 = 2𝑘 + 1, 𝑘 = 2, 4, 6, … dengan rumus sebagai berikut:

1. Nilai label titik dan sisi untuk 𝑛 = 2𝑘 + 1, 𝑘 = 1, 3, 5, …

𝑤 𝑣𝑖 =

𝑖 + 1

2 𝑖 = 1, 3, 5, … , 𝑛

𝑛 + 𝑖 + 1

2 𝑖 = 2, 4, 6, … , 𝑛 − 1


3𝑛 + 𝑖 + 2

2 𝑖 = 1, 3, 5, … , 𝑛 − 2

2 𝑛 + 1 + 𝑖

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

𝑛 + 1 𝑖 = 𝑛

𝑤 𝑒𝑖 ,𝑖+1 = 4𝑛 − 𝑖 𝑖 = 1, 2, 3, … , 𝑛 − 1

𝑤 𝑒1,𝑖 = 4𝑛 𝑖 = 𝑛

𝑤 𝑒𝑖 ,𝑛+𝑖 = 3𝑛 − 𝑖 𝑖 = 1, 2, 3, … , 𝑛 − 13𝑛 𝑖 = 𝑛



37

Berikut ditunjukkan bahwa bobot masing-masing sisi pada 𝐶𝑛 + 𝑛𝐴1,

𝑛 ≥ 3, 𝑛 = 2𝑘 + 1, 𝑘 = 1, 3, 5, … dengan pola pelabelan di atas adalah

konstan yaitu 9𝑛+3

2.

i) Untuk 𝑖 = 1, 3, 5, … , 𝑛 − 2

𝑤𝑡 𝑒𝑖 ,𝑖+1 = 𝑤(𝑣𝑖) + 𝑤 𝑒𝑖 ,𝑖+1 + 𝑤(𝑣𝑖+1)

=𝑖 + 1

2+ 4𝑛 − 𝑖 +

𝑛 + (𝑖 + 1) + 1

2

=𝑖 + 1

2+

8𝑛 − 2𝑖

2+

𝑛 + (𝑖 + 1) + 1

2

=8𝑛 + 𝑛 + 𝑖 − 2𝑖 + 𝑖 + 1 + 1 + 1

2

=9𝑛 + 3

2

ii) Untuk 𝑖 = 2, 4, 6, … , 𝑛 − 1


=𝑛 + 𝑖 + 1

2+ 4𝑛 − 𝑖 +

𝑖 + 1 + 1

2

=𝑛 + 𝑖 + 1

2+

8𝑛 − 2𝑖

2+

𝑖 + 1 + 1

2

=𝑛 + 8𝑛 + 𝑖 − 2𝑖 + 𝑖 + 1 + 1 + 1

2

=9𝑛 + 3

2

iii) Untuk 𝑖 = 𝑛

𝑤𝑡 𝑒𝑖 ,1 = 𝑤(𝑣𝑖) + 𝑤 𝑒𝑖 ,1 + 𝑤(𝑣1)

=𝑖 + 1

2+ 4𝑛 +

1 + 1

2 , 𝑖 = 𝑛


38

=𝑛 + 1

2+

8𝑛

2+

2

2

=𝑛 + 8𝑛 + 1 + 2

2

=9𝑛 + 3

2

iv) Untuk 𝑖 = 1, 3, 5, … , 𝑛 − 2

𝑤𝑡 𝑒𝑖 ,𝑛+𝑖 = 𝑤(𝑣𝑖) + 𝑤 𝑒𝑖 ,𝑛+𝑖 + 𝑤(𝑣𝑛+𝑖)

=𝑖 + 1

2+ 3𝑛 − 𝑖 +

3𝑛 + 𝑖 + 2

2

=𝑖 + 1

2+

6𝑛 − 2𝑖

2+

3𝑛 + 𝑖 + 2

2

=6𝑛 + 3𝑛 + 𝑖 − 2𝑖 + 𝑖 + 1 + 2

2

=9𝑛 + 3

2

v) Untuk 𝑖 = 2, 4, 6, … , 𝑛 − 1


=𝑛 + 𝑖 + 1

2+ 3𝑛 − 𝑖 +

2 𝑛 + 1 + 𝑖

2

=𝑛 + 𝑖 + 1

2+

6𝑛 − 2𝑖

2+

2𝑛 + 2 + 𝑖

2

=𝑛 + 6𝑛 + 2𝑛 + 𝑖 − 2𝑖 + 𝑖 + 1 + 2

2

=9𝑛 + 3

2


39

vi) Untuk 𝑖 = 𝑛


=𝑖 + 1

2+ 3𝑛 + 𝑛 + 1 , 𝑖 = 𝑛

=𝑛 + 1

2+

6𝑛

2+

2𝑛 + 2

2

=𝑛 + 6𝑛 + 2𝑛 + 1 + 2

2

=9𝑛 + 3

2

2. Nilai label titik dan sisi untuk 𝑛 = 2𝑘 + 1, 𝑘 = 2, 4, 6, …

𝑤 𝑣𝑖 =

𝑖 + 1

2 𝑖 = 1, 3, 5, … , 𝑛

𝑛 + 1 + 𝑖

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

𝑤 𝑣𝑛+𝑖 = 2𝑛 − 𝑖 + 1 𝑖 = 1, 2, 3, … , 𝑛

𝑤 𝑒𝑖 ,𝑖+1 = 4𝑛 − 𝑖 𝑖 = 1, 2, 3, … , 𝑛 − 1

𝑤 𝑒1,𝑖 = 4𝑛 𝑖 = 𝑛


5𝑛 + 𝑖

2 𝑖 = 1, 3, 5, … , 𝑛

4𝑛 + 𝑖

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

Berikut ditunjukkan bahwa bobot masing-masing sisi pada 𝐶𝑛 + 𝑛𝐴1,

𝑛 ≥ 3, 𝑛 = 2𝑘 + 1, 𝑘 = 2, 4, 6, … dengan pola pelabelan di atas adalah

konstan yaitu 9𝑛+3

2.


40

i) Untuk 𝑖 = 1, 3, 5, … , 𝑛 − 2


=𝑖 + 1

2+ 4𝑛 − 𝑖 +

𝑛 + (𝑖 + 1) + 1

2

=𝑖 + 1

2+

8𝑛 − 2𝑖

2+

𝑛 + (𝑖 + 1) + 1

2

=8𝑛 + 𝑛 + 𝑖 − 2𝑖 + 𝑖 + 1 + 1 + 1

2

=9𝑛 + 3

2

ii) Untuk 𝑖 = 2, 4, 6, … , 𝑛 − 1


=𝑛 + 𝑖 + 1

2+ 4𝑛 − 𝑖 +

𝑖 + 1 + 1

2

=𝑛 + 𝑖 + 1

2+

8𝑛 − 2𝑖

2+

𝑖 + 1 + 1

2

=𝑛 + 8𝑛 + 𝑖 − 2𝑖 + 𝑖 + 1 + 1 + 1

2

=9𝑛 + 3

2


𝑤𝑡 𝑒𝑖 ,1 = 𝑤(𝑣𝑖) + 𝑤 𝑒𝑖 ,1 + 𝑤(𝑣1)

=𝑖 + 1

2+ 4𝑛 +

1 + 1

2 , 𝑖 = 𝑛

=𝑛 + 1

2+

8𝑛

2+

2

2


41

=𝑛 + 8𝑛 + 1 + 2

2

=9𝑛 + 3

2

iv) Untuk 𝑖 = 1, 3, 5, … , 𝑛


=𝑖 + 1

2+

5𝑛 + 𝑖

2+ 2𝑛 − 𝑖 + 1

=𝑖 + 1

2+

5𝑛 ∓ 𝑖

2+

4𝑛 − 2𝑖 + 2

2

=5𝑛 + 4𝑛 + 𝑖 + 𝑖 − 2𝑖 + 1 + 2

2

=9𝑛 + 3

2

v) Untuk 𝑖 = 2, 4, 6, … , 𝑛 − 1


=𝑛 + 𝑖 + 1

2+

4𝑛 + 𝑖

2+ 2𝑛 − 𝑖 + 1

=𝑛 + 𝑖 + 1

2+

4𝑛 + 𝑖

2+

4𝑛 − 2𝑖 + 2

2

=𝑛 + 4𝑛 + 4𝑛 + 𝑖 + 𝑖 − 2𝑖 + 1 + 2

2

=9𝑛 + 3

2

Teorema 3.2


kuat untuk 𝑛 ≥ 3 dan 𝑛 ganjil dengan konstanta ajaib 𝑐 =9𝑛+3

2.


42

Bukti:

Perhatikan ilustrasi pelabelan berikut yang dikonstruksi berdasarkan

pola pelabelan pada kasus 1 dan 2 di atas.

Gambar 3.2 Ilustrasi Pelabelan Total Ajaib Sisi Kuat

pada 𝐶𝑛 + 𝑛𝐴1, 𝑛 ≥ 3, 𝑛 = 2𝑘 + 1, 𝑘 = 1, 3, 5, … , 𝑐 =9𝑛+3

2

𝑣2𝑛−2

𝑣2𝑛−1

𝑣𝑛+1

𝑣𝑛

𝑣1

𝑣2

𝑣𝑛+3

𝑣2𝑛 𝑣𝑛+2

𝑣𝑛+4

𝑣𝑛−2 𝑣4

𝑣𝑛−1 𝑣3

1

2

𝑛 + 3

2

2𝑛 − 1

2

𝑛 + 1

2

𝑛 + 5

2

𝑛

3𝑛 + 3

2

3𝑛 + 1

2

𝑛 + 1

3𝑛 + 5

2

𝑛 + 2

𝑛 + 3 2𝑛

3𝑛 − 1

4𝑛 − 2 3𝑛 + 1

4𝑛 4𝑛 − 1

4𝑛 − 3

3𝑛 − 2

3𝑛 − 3

3𝑛 − 4 2𝑛 + 2

3𝑛

2𝑛 + 1

3𝑛 + 2


43


pada 𝐶𝑛 + 𝑛𝐴1, 𝑛 ≥ 3, 𝑛 = 2𝑘 + 1, 𝑘 = 2, 4, 6, … , 𝑐 =9𝑛+3

2

Pada kedua konstruksi di atas dapat dilihat bahwa label titik 𝑤(𝑣𝑖)

adalah bilangan bulat positif 1, 2, 3, … , 2𝑛 dengan label titik 𝑣1 , 𝑣2, 𝑣3, … , 𝑣𝑛

adalah 1, 2, 3, … , 𝑛, sedangkan label sisi 𝑤(𝑒𝑖 ,𝑗 ) adalah bilangan bulat positif

2𝑛 + 1, 2𝑛 + 2, … , 4𝑛. Bobot pada masing-masing sisi konstan yaitu 9𝑛+3

2

(pembahasan pada halaman 36-41). Hal ini memenuhi syarat kasus 1 pada

Teorema 3.1, sehingga terbukti bahwa graf sikel dengan tambahan n anting

5𝑛 + 1

2

4𝑛 − 1

-1 1

4𝑛 1

𝑛 + 3

2

2 𝑛

𝑛 + 1

2

2𝑛

2𝑛 − 1 𝑛 + 1

2𝑛 − 2 𝑛 + 2

4𝑛 − 2

-1 1

5𝑛 − 1

2

5𝑛 + 3

2

2𝑛 + 1 3𝑛

𝑣𝑛+1

𝑣1

𝑣𝑛 𝑣2

𝑣𝑛−1 𝑣3

𝑣𝑛+3

𝑣2𝑛

𝑣2𝑛−1

𝑣𝑛+2

3𝑛 + 1


44

memenuhi pelabelan total ajaib sisi kuat untuk 𝑛 ≥ 3 dan 𝑛 ganjil dengan

konstanta ajaib 𝑐 =9𝑛+3

2. □

Contoh:

Pelabelan total ajaib sisi kuat pada 𝐶𝑛 + 𝑛𝐴1 untuk 𝑛 = 7, 𝑐 =9(7)+3

2 = 33.

𝑤 𝑣1 =1 + 1

2= 1

𝑤 𝑣2 =7 + 2 + 1

2= 5

𝑤 𝑣3 =3 + 1

2= 2

𝑤 𝑣4 =7 + 4 + 1

2= 6

𝑤 𝑣5 =5 + 1

2= 3

𝑤 𝑣6 =7 + 6 + 1

2= 7

𝑤 𝑣7 =7 + 1

2= 4

𝑤 𝑣8 =3(7) + 1 + 2

2= 12

𝑤 𝑣9 =2 8 + 2

2= 9

𝑤 𝑣10 =3(7) + 3 + 2

2= 13

𝑤 𝑣11 =2 8 + 4

2= 10

𝑤 𝑣12 =3(7) + 5 + 2

2= 14

𝑤 𝑣13 =2 8 + 6

2= 11

𝑤 𝑣14 = 7 + 1 = 8

𝑤 𝑒1,2 = 4 7 − 1 = 27

𝑤 𝑒2,3 = 4 7 − 2 = 26

𝑤 𝑒3,4 = 4 7 − 3 = 25

𝑤 𝑒4,5 = 4 7 − 4 = 24

𝑤 𝑒5,6 = 4 7 − 5 = 23

𝑤 𝑒6,7 = 4 7 − 6 = 22

𝑤 𝑒1,7 = 4 7 = 28

𝑤 𝑒1,8 = 3 7 − 1 = 20

𝑤 𝑒2,9 = 3 7 − 2 = 19

𝑤 𝑒3,10 = 3 7 − 3 = 18

𝑤 𝑒4,11 = 3 7 − 4 = 17

𝑤 𝑒5,12 = 3 7 − 5 = 16

𝑤 𝑒6,13 = 3 7 − 6 = 15

𝑤 𝑒7,14 = 3 7 = 21


45

Gambar 3.4 Pelabelan Total Ajaib Sisi Kuat pada 𝐶7 + 7𝐴1, 𝑐 = 33

Pelabelan total ajaib sisi kuat pada 𝐶𝑛 + 𝑛𝐴1 untuk 𝑛 = 5, 𝑐 =9(5)+3

2 = 24.

𝑤 𝑣1 =1 + 1

2= 1

𝑤 𝑣2 =5 + 2 + 1

2= 4

𝑤 𝑣3 =3 + 1

2= 2

𝑤 𝑣4 =5 + 4 + 1

2= 5

𝑤 𝑣5 =5 + 1

2= 3

𝑤 𝑣6 = 2 5 − 1 + 1 = 10

𝑤 𝑣7 = 2 5 − 2 + 1 = 9

𝑤 𝑣8 = 2 5 − 3 + 1 = 8

𝑤 𝑣9 = 2 5 − 4 + 1 = 7

12

11

8

13

9

10 14

1

2

5

3

4

6

7

20

26 22

28 27

25

24

19

18

17 16

21

15

𝑣𝑛+1

𝑣𝑛

𝑣1

𝑣2

𝑣𝑛+3 𝑣2𝑛−1


𝑣𝑛+5 𝑣𝑛+4

𝑣5 𝑣4

𝑣6 𝑣3

23


46

𝑤 𝑣10 = 2 5 − 5 + 1 = 6

𝑤 𝑒1,2 = 4 5 − 1 = 19

𝑤 𝑒2,3 = 4 5 − 2 = 18

𝑤 𝑒3,4 = 4 5 − 3 = 17

𝑤 𝑒4,5 = 4 5 − 4 = 16

𝑤 𝑒1,5 = 4 5 = 20

𝑤 𝑒1,6 =5(5) + 1

2= 13

𝑤 𝑒2,7 =4(5) + 2

2= 11

𝑤 𝑒3,8 =5(5) + 3

2= 14

𝑤 𝑒4,9 =4(5) + 4

2= 12

𝑤 𝑒5,10 =5(5) + 5

2= 15


13

19

-1 1

20 1

4

2 5

3

10

9 6

8 7

18

-1 1

17

-1 1 12 14

11 15

𝑣𝑛+1

𝑣1

𝑣𝑛 𝑣2

𝑣4 𝑣3

𝑣𝑛+3

𝑣2𝑛

𝑣𝑛+4

𝑣𝑛+2

16


47

3.3. Pelabelan Total Ajaib Sisi Kuat pada 𝑪𝒏 + 𝒏𝑨𝟏 untuk 𝒏 ≥ 𝟑 dan n

Ganjil dengan 𝒄 =𝟏𝟏𝒏+𝟑

𝟐

Dalam penelitian ini diambil salah satu pola pelabelan yang memenuhi

pelabelan total ajaib sisi kuat pada 𝐶𝑛 + 𝑛𝐴1 untuk 𝑛 ≥ 3 dan 𝑛 ganjil

dengan nilai konstanta ajaib 𝑐 =11𝑛+3

2 seperti yang ditunjukkan pada tabel

3.3 berikut.

Tabel 3.3 Nilai Label Titik dan Sisi pada Pelabelan Total Ajaib Sisi Kuat

pada 𝐶𝑛 + 𝑛𝐴1 untuk 𝑛 ≥ 3 dan 𝑛 Ganjil dengan 𝑐 =11𝑛+3

2

3 5 7 9 11 13 …

1 4 6 8 10 12 14 …

2 6 9 12 15 18 21 …

3 5 7 9 11 13 15 …

4

10 13 16 19 22 …

5

8 10 12 14 16 …

6

14 17 20 23 …

7

11 13 15 17 …

8

18 21 24 …

9

14 16 18 …

10

22 25 …

11

17 19 …

12

26 …

13

20 …

…

…

𝑛 + 1 2 4 6 8 10 12 …

𝑛 + 2 1 3 5 7 9 11 …

𝑛 + 3 3 2 4 6 8 10 …

𝑛 + 4

1 3 5 7 9 …

𝑛 + 5

5 2 4 6 8 …

𝑛 + 6

1 3 5 7 …

𝑛 + 7

7 2 4 6 …

𝑛 + 8

1 3 5 …

𝑛 + 9

9 2 4 …

𝑛 𝑣𝑖


48

3 5 7 9 11 13 …

𝑛 + 10

1 3 …

𝑛 + 11

11 2 …

𝑛 + 12

1 …

𝑛 + 13

13 …

…

…

3 5 7 9 11 13 …

1,2 8 14 20 26 32 38 …

2,3 7 13 19 25 31 37 …

3,4 12 18 24 30 36 …

4,5 11 17 23 29 35 …

5,6

16 22 28 34 …

6,7

15 21 27 33 …

7,8

20 26 32 …

8,9

19 25 31 …

9,10

24 30 …

10,11

23 29 …

11,12

28 …

12,13

27 …

…

…

1, 𝑛 9 15 21 27 33 39 …

3 5 7 9 11 13 …

1, 𝑛 + 1 12 19 26 33 40 47 …

2, 𝑛 + 2 11 17 23 29 35 41 …

3, 𝑛 + 3 10 20 27 34 41 48 …

4, 𝑛 + 4

18 24 30 36 42 …

5, 𝑛 + 5

16 28 35 42 49 …

6, 𝑛 + 6

25 31 37 43 …

7, 𝑛 + 7

22 36 43 50 …

8, 𝑛 + 8

32 38 44 …

9, 𝑛 + 9

28 44 51 …

10, 𝑛 + 10

39 45 …

11, 𝑛 + 11

34 52 …

12, 𝑛 + 12

46 …

13, 𝑛 + 13

40 …

…

…

𝑛 𝑒𝑖 ,𝑖+1


𝑛 𝑣𝑖


49

Dari tabel di atas, pelabelan total ajaib sisi kuat pada 𝐶𝑛 + 𝑛𝐴1 untuk

𝑛 ≥ 3 dan 𝑛 ganjil dengan nilai konstanta ajaib 𝑐 =11𝑛+3

2 memiliki nilai

label titik dan sisi dengan rumus sebagai berikut:

𝑤 𝑣𝑖 =

2𝑛 + 𝑖 + 1

2 𝑖 = 1, 3, 5, … , 𝑛

3𝑛 + 𝑖 + 1

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

𝑤 𝑣𝑛+𝑖 = 𝑛 − 𝑖 𝑖 = 1, 2, 3, … , 𝑛 − 1𝑛 𝑖 = 𝑛

𝑤 𝑒𝑖 ,𝑖+1 = 3𝑛 − 𝑖 𝑖 = 1, 2, 3, … , 𝑛 − 1

𝑤 𝑒1,𝑖 = 3𝑛 𝑖 = 𝑛


7𝑛 + 𝑖 + 2

2 𝑖 = 1, 3, 5, … , 𝑛 − 2

6𝑛 + 𝑖 + 2

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

3𝑛 + 1 𝑖 = 𝑛

Berikut ditunjukkan bahwa bobot masing-masing sisi pada 𝐶𝑛 + 𝑛𝐴1

untuk 𝑛 ≥ 3 dan 𝑛 ganjil dengan pola pelabelan di atas adalah konstan

yaitu 11𝑛+3

2.

i) Untuk 𝑖 = 1, 3, 5, … , 𝑛 − 2


=2𝑛 + 𝑖 + 1

2+ 3𝑛 − 𝑖 +

3𝑛 + (𝑖 + 1) + 1

2

=2𝑛 + 𝑖 + 1

2+

6𝑛 − 2𝑖

2+

3𝑛 + (𝑖 + 1) + 1

2

=2𝑛 + 6𝑛 + 3𝑛 + 𝑖 − 2𝑖 + 𝑖 + 1 + 1 + 1

2


50

=11𝑛 + 3

2

ii) Untuk 𝑖 = 2, 4, 6, … , 𝑛 − 1


=3𝑛 + 𝑖 + 1

2+ 3𝑛 − 𝑖 +

2𝑛 + 𝑖 + 1 + 1

2

=3𝑛 + 𝑖 + 1

2+

6𝑛 − 2𝑖

2+

2𝑛 + 𝑖 + 1 + 1

2

=3𝑛 + 6𝑛 + 2𝑛 + 𝑖 − 2𝑖 + 𝑖 + 1 + 1 + 1

2

=11𝑛 + 3

2


𝑤𝑡 𝑒𝑖 ,1 = 𝑤(𝑣𝑖) + 𝑤 𝑒𝑖 ,1 + 𝑤(𝑣1)

=2𝑛 + 𝑖 + 1

2+ 3𝑛 +

2𝑛 + 1 + 1

2 , 𝑖 = 𝑛

=2𝑛 + 𝑛 + 1

2+

6𝑛

2+

2𝑛 + 2

2

=3𝑛 + 6𝑛 + 2𝑛 + 1 + 2

2

=11𝑛 + 3

2

iv) Untuk 𝑖 = 1, 3, 5, … , 𝑛 − 2


=2𝑛 + 𝑖 + 1

2+

7𝑛 + 𝑖 + 2

2+ 𝑛 − 𝑖

=2𝑛 + 𝑖 + 1

2+

7𝑛 + 𝑖 + 2

2+

2𝑛 − 2𝑖

2


51

=2𝑛 + 7𝑛 + 2𝑛 + 𝑖 + 𝑖 − 2𝑖 + 1 + 2

2

=11𝑛 + 3

2

v) Untuk 𝑖 = 2, 4, 6, … , 𝑛 − 1


=3𝑛 + 𝑖 + 1

2+

6𝑛 + 𝑖 + 2

2+ 𝑛 − 𝑖

=3𝑛 + 𝑖 + 1

2+

6𝑛 + 𝑖 + 2

2+

2𝑛 − 2𝑖

2

=3𝑛 + 6𝑛 + 2𝑛 + 𝑖 + 𝑖 − 2𝑖 + 1 + 2

2

=11𝑛 + 3

2

vi) Untuk 𝑖 = 𝑛


=2𝑛 + 𝑖 + 1

2+ 3𝑛 + 1 + 𝑛 , 𝑖 = 𝑛

=2𝑛 + 𝑛 + 1

2+

6𝑛 + 2

2+

2𝑛

2

=2𝑛 + 𝑛 + 6𝑛 + 2𝑛 + 1 + 2

2

=11𝑛 + 3

2

Teorema 3.3


kuat untuk 𝑛 ≥ 3 dan 𝑛 ganjil, dengan konstanta ajaib 𝑐 =11𝑛+3

2.


52

Bukti:

Perhatikan ilustrasi pelabelan berikut yang dikonstruksi berdasarkan

pola pelabelan di atas.


pada 𝐶𝑛 + 𝑛𝐴1, 𝑛 ≥ 3, 𝑛 Ganjil, 𝑐 =11𝑛+3

2

Pada konstruksi di atas dapat dilihat bahwa label titik 𝑤(𝑣𝑖) adalah

bilangan bulat positif 1, 2, 3, … , 2𝑛 dengan label titik 𝑣1 , 𝑣2 , 𝑣3, … , 𝑣𝑛 adalah

𝑛 + 1, 𝑛 + 2, 𝑛 + 3, … ,2𝑛, sedangkan label sisi 𝑤(𝑒𝑖 ,𝑗 ) adalah bilangan bulat

positif 2𝑛 + 1, 2𝑛 + 2, … , 4𝑛. Bobot pada masing-masing sisi konstan yaitu

3𝑛 − 1

2

2𝑛

𝑣𝑛+1

𝑣𝑛

𝑣1

𝑣2

𝑣𝑛+3


𝑣𝑛+4

𝑣𝑛−2 𝑣4

𝑣𝑛−1 𝑣3

𝑣2𝑛−2

2𝑛 + 2 3𝑛 + 5

2

𝑛 − 1

𝑛 − 4

𝑛 − 3

𝑛 − 2 𝑛

2

1

𝑛 + 1

3𝑛 + 1

2

𝑛 + 2

3𝑛 + 3

2

7𝑛 + 3

2

3𝑛 − 2 2𝑛 + 1

3𝑛 3𝑛 − 1

3𝑛 − 3

𝑣2𝑛−1

3𝑛 + 2

7𝑛 + 5

2

3𝑛 + 3 4𝑛

3𝑛 + 1

7𝑛 + 1

2


53

11𝑛+3

2 (pembahasan pada halaman 49-51). Hal ini memenuhi syarat kasus 2

pada Teorema 3.1, sehingga terbukti bahwa graf sikel dengan tambahan n

anting memenuhi pelabelan total ajaib sisi kuat untuk 𝑛 ≥ 3 dan 𝑛 ganjil

dengan konstanta ajaib 𝑐 =11𝑛+3

2. □

Contoh:

Pelabelan total ajaib sisi kuat pada 𝐶𝑛 + 𝑛𝐴1, 𝑛 = 5, 𝑐 =11(5)+3

2= 29.

𝑤 𝑣1 =2 5 + 1 + 1

2= 6

𝑤 𝑣2 =3(5) + 2 + 1

2= 9

𝑤 𝑣3 =2 5 + 3 + 1

2= 7

𝑤 𝑣4 =3(5) + 4 + 1

2= 10

𝑤 𝑣5 =2 5 + 5 + 1

2= 8

𝑤 𝑣6 = 5 − 1 = 4

𝑤 𝑣7 = 5 − 2 = 3

𝑤 𝑣8 = 5 − 3 = 2

𝑤 𝑣9 = 5 − 4 = 1

𝑤 𝑣10 = 5

𝑤 𝑒1,2 = 3 5 − 1 = 14

𝑤 𝑒2,3 = 3 5 − 2 = 13

𝑤 𝑒3,4 = 3 5 − 3 = 12

𝑤 𝑒4,5 = 3 5 − 4 = 11

𝑤 𝑒1,5 = 3 5 = 15

𝑤 𝑒1,6 =7(5) + 1 + 2

2= 19

𝑤 𝑒2,7 =6(5) + 2 + 2

2= 17

𝑤 𝑒3,8 =7(5) + 3 + 2

2= 20

𝑤 𝑒4,9 =6(5) + 4 + 2

2= 18

𝑤 𝑒5,10 = 3 5 + 1 = 16


54


19

14

-1 1

15 6

9

7 10

8

4

3 5

2 1

13

-1 1

12

-1 1 18 20

17 16

𝑣𝑛+1

𝑣1

𝑣𝑛 𝑣2

𝑣4 𝑣3

𝑣𝑛+3

𝑣2𝑛

𝑣𝑛+4

𝑣𝑛+2

11


55

BAB 1V

PENUTUP

4.1. Kesimpulan

Berdasarkan hasil dari penelitian yang telah dilakukan, dapat

disimpulkan bahwa:

1. Pelabelan total ajaib sisi kuat berlaku pada graf sikel dengan tambahan n

anting untuk 𝑛 ≥ 3 dan 𝑛 ganjil dengan nilai konstanta ajaib c terletak

pada interval 9𝑛+3

2≤ 𝑐 ≤

11𝑛+3

2.

2. Nilai label titik dan sisi untuk pelabelan total ajaib sisi kuat pada graf

sikel dengan tambahan n anting untuk 𝑛 ≥ 3 dan 𝑛 ganjil dengan nilai

konstanta ajaib 𝑐 =9𝑛+3

2 dan 𝑐 =

11𝑛+3

2 adalah sebagai berikut:

a. Untuk 𝑐 =9𝑛+3

2

1) 𝑛 = 2𝑘 + 1, 𝑘 = 1, 3, 5, …,

𝑤 𝑣𝑖 =

𝑖 + 1

2 𝑖 = 1, 3, 5, … , 𝑛

𝑛 + 𝑖 + 1

2 𝑖 = 2, 4, 6, … , 𝑛 − 1


3𝑛 + 𝑖 + 2

2 𝑖 = 1, 3, 5, … , 𝑛 − 2

2 𝑛 + 1 + 𝑖

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

𝑛 + 1 𝑖 = 𝑛

𝑤 𝑒𝑖 ,𝑖+1 = 4𝑛 − 𝑖 𝑖 = 1, 2, 3, … , 𝑛 − 1

𝑤 𝑒1,𝑖 = 4𝑛 𝑖 = 𝑛

𝑤 𝑒𝑖 ,𝑛+𝑖 = 3𝑛 − 𝑖 𝑖 = 1, 2, 3, … , 𝑛 − 13𝑛 𝑖 = 𝑛


56

2) 𝑛 = 2𝑘 + 1, 𝑘 = 2, 4, 6, …,

𝑤 𝑣𝑖 =

𝑖 + 1

2 𝑖 = 1, 3, 5, … , 𝑛

𝑛 + 1 + 𝑖

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

𝑤 𝑣𝑛+𝑖 = 2𝑛 − 𝑖 + 1 𝑖 = 1, 2, 3, … , 𝑛

𝑤 𝑒𝑖 ,𝑖+1 = 4𝑛 − 𝑖 𝑖 = 1, 2, 3, … , 𝑛 − 1

𝑤 𝑒1,𝑖 = 4𝑛 𝑖 = 𝑛


5𝑛 + 𝑖

2 𝑖 = 1, 3, 5, … , 𝑛

4𝑛 + 𝑖

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

b. Untuk 𝑐 =11𝑛+3

2

𝑤 𝑣𝑖 =

2𝑛 + 𝑖 + 1

2 𝑖 = 1, 3, 5, … , 𝑛

3𝑛 + 𝑖 + 1

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

𝑤 𝑣𝑛+𝑖 = 𝑛 − 𝑖 𝑖 = 1, 2, 3, … , 𝑛 − 1𝑛 𝑖 = 𝑛

𝑤 𝑒𝑖 ,𝑖+1 = 3𝑛 − 𝑖 𝑖 = 1, 2, 3, … , 𝑛 − 1

𝑤 𝑒1,𝑖 = 3𝑛 𝑖 = 𝑛


7𝑛 + 𝑖 + 2

2 𝑖 = 1, 3, 5, … , 𝑛 − 2

6𝑛 + 𝑖 + 2

2 𝑖 = 2, 4, 6, … , 𝑛 − 1

3𝑛 + 1 𝑖 = 𝑛


57

4.2. Saran

Untuk penelitian selanjutnya dapat dikembangkan hasil dari penelitian

ini antara lain:

1. Penelitian untuk menyelidiki pola pelabelan total ajaib sisi kuat pada

graf sikel dengan tambahan n anting, 𝑛 ≥ 3 dan 𝑛 ganjil untuk nilai

konstanta ajaib 9𝑛+3

2< 𝑐 <

11𝑛+3

2.

2. Penelitian untuk menyelidiki pelabelan total ajaib sisi kuat pada graf

sikel dengan tambahan n anting untuk 𝑛 ≥ 3 dan 𝑛 genap.


58

DAFTAR PUSTAKA

Chartrand, Gary & Ortrud R. Oellermann. 1993. Applied and Algorithmic Graph

Theory. New York: McGraw-Hill, Inc.

Goodaire, Edgar G., & Michael M. Parmenter. 1998. Discrete Mathematics with

Graph Theory. New York: Prentice-Hall, Inc.

Munir, Rinaldi. 2001. Matematika Diskrit. Bandung: Penerbit Informatika.

Septian, Cosmas W. 2011. Pelabelan Total Tak Ajaib Titik pada Graf Sikel

dengan Tambahan Satu Anting. Skripsi Pendidikan Matematika.

Yogyakarta: Universitas Sanata Dharma.

Suryadi H. S. 1996. Edisi I. Cetakan V. Teori Graf Dasar. Jakarta: Penerbit

Gunadarma.

Wallis, W. D. 2001. Magic Graph. New York: Hamilton Printing.

Yuliyanto, Benedictus D. 2012. Pelabelan Total Ajaib Sisi Kuat pada Graf Sikel

dengan Tambahan Dua Anting. Skripsi Pendidikan Matematika.

Yogyakarta: Universitas Sanata Dharma.


pelabelan total ajaib sisi kuat pada graf … · pelabelan total ajaib sisi kuat pada graf sikel...

Documents