i
PELABELAN TOTAL TAK AJAIB TITIK KUAT ),( da PADA GRAF
SIKEL DENGAN TAMBAHAN n ANTING
HALAMAN JUDUL
SKRIPSI
Diajukan untuk Memenuhi Salah Satu Syarat
Memperoleh Gelar Sarjana Pendidikan (S.Pd.)
Program Studi Pendidikan Matematika
Oleh:
Lusia Deni Nur Reni
NIM: 151414004
PROGRAM STUDI PENDIDIKAN MATEMATIKA
JURUSAN PENDIDIKAN MATEMATIKA DAN ILMU PENGETAHUAN ALAM
FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN
UNIVERSITAS SANATA DHARMA
YOGYAKARTA
2019
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
ii
A SUPER ),( da VERTEX ANTIMAGIC TOTAL LABELING ON CYCLE
GRAPH WITH n EXTRA ARMS
A THESIS
Submitted as the Partial Fulfillment of the Requirements
to Obtain a Bachelor of Education Degree
on Mathematics Education Study Program
Written by:
Lusia Deni Nur Reni
Student ID: 151414004
MATHEMATICS EDUCATION STUDY PROGRAM
DEPARTEMENT OF MATHEMATICS AND SCIENCE EDUCATION
FACULTY OF TEACHER TRAINING AND EDUCATION
SANATA DHARMA UNIVERSITY
YOGYAKARTA
2019
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
iii
SKRIPSI
PELABELAN TOTAL TAK-AJAIB TITIK KUAT ),( da PADA GRAF
SIKEL DENGAN TAMBAHAN n ANTING
HALAMAN PERSETUJUAN PEMBIMBING
Disusun oleh:
Lusia Deni Nur Reni
NIM: 151414004
telah disetujui oleh:
Dosen Pembimbing Skripsi
Dominikus Arif Budi Prasetyo, M.Si. Tanggal, 15 Mei 2019
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
iv
SKRIPSI
PELABELAN TOTAL TAK-AJAIB TITIK KUAT ),( da PADA GRAF
SIKEL DENGAN TAMBAHAN n ANTING
LEMBAR PENGESAHAN
Dipersiapkan dan ditulis oleh:
Lusia Deni Nur Reni
NIM: 151414004
Telah dipertahankan di hadapan Panitia Penguji
Pada Tanggal: 24 Mei 2019
dan dinyatakan telah memenuhi syarat.
Susunan Panitia Penguji:
Nama Lengkap Tanda Tangan
Ketua : Marcellinus Andy Rudhito, S.Pd. ........................
Sekretaris : Beni Utomo, M.Sc. ........................
Anggota I : Dominikus Arif Budi Prasetyo, M.Si. ........................
Anggota II : Maria Suci Apriani, S.Pd., M.Sc. ........................
Anggota III : Cyrenia Novella Krisnamurti, M.Sc. ........................
Yogyakarta, Mei 2019
Fakultas Keguruan dan Ilmu Pendidikan
Universitas Sanata Dharma
Dekan,
Dr. Yohanes Harsoyo, S.Pd., M.Si.
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
v
HALAMAN PERSEMBAHAN
Dengan tulus karya ini saya persembahkan kepada:
Tuhan Yesus Yang Maha Kasih
Kedua Orangtuaku S. Rantono dan Sumarsih
Kakak dan adikku Suharni dan Herlinda Prameswaari
Partnerku Donny Lucky Ichsan dan Teman-teman seperjuangan
Bruder Yohanes Sarju, S.J. dan Bapak M. Tri Haryono
Program Studi Pendidikan Matematika
Universitas Sanata dharma
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
vi
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, 15 Mei 2019
Penulis,
Lusia Deni Nur Reni
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
vii
LEMBAR PERNYATAAN PERSETUJUAN
PUBLIKASI KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS
Yang bertanda tangan di bawah ini, saya mahasiswa Universitas Sanata Dharma:
Nama : Lusia Deni Nur Reni
Nomor Mahasiswa : 151414004
Demi pengembangan ilmu pengetahuan, saya memberikan kepada Perpustakaan
universitas Sanata Dharma karya ilmiah saya yang berjudul:
“PELABELAN TOTAL TAK-AJAIB TITIK KUAT ),( da PADA GRAF
SIKEL DENGAN TAMBAHAN n ANTING”
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 royalty kepada saya selama tetap
mencantumkan nama saya sebagai penulis.
Demikian pernyataan ini yang saya buat dengan sebenar-benarnya.
Dibuat di Yogyakarta
Pada tanggal: 15 Mei 2019
Yang menyatakan
Lusia Deni Nur Reni
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
viii
ABSTRAK
Lusia Deni Nur Reni. 2019. Pelabelan Total Tak Ajaib Titik Kuat ),( da pada
Graf sikel dengan Tambahan n Anting. Program Studi Pendidikan
Matematika, Jurusan Pendidikan Matematika dan Ilmu Pengetahuan Alam,
Fakultas Keguruan dan Ilmu Pendidikan, Universitas Sanata Dharma.
Pelabelan total merupakan pemetaan dengan domain titik dan sisi.
Pelabelan total tak ajaib titik dari ),( EVG merupakan pemetaan bijektif
|}|||,...,2,1{: evEVf dengan banyaknya titik || v dan banyaknya sisi || e
dan bobot setiap titik )(xwt , Vx berbeda. Bobot titik diperoleh dengan
menjumlahkan label titik tersebut dengan label semua sisi yang bersisian dengan
titik tersebut. Pada pelabelan total tak-ajaib titik ),( da himpunan bobot titiknya
membentuk suatu barisan aritmatika naik dengan suku pertama a dan beda d
dimana a dan d merupakan bilangan bulat positif. Pelabelan titik dikatakan kuat,
jika label-label sisinya |}|,...,2,1{ e dan label-label titiknya
|}|||,...,2||,1|{| evee .
Penelitian ini bertujuan untuk mengetahui keberlakuan pelabelan total tak-
ajaib titik kuat ),( da pada graf 1nACn dan mencari rumus umum atau pola
pelabelannya. Graf 1nACn merupakan perkembangan dari graf sikel )( nC yang
ditambahkan n titik di luar nC dan masing-masing titik terdapat tepat satu sisi yang
menghubungkan titik tersebut ke titik yang berbeda pada nC . Penelitian ini
merupakan penelitian studi pustaka dengan mengkaji beberapa penelitian
sebelumnya. Hasil penelitian ini menunjukkan bahwa pada graf 1nACn dapat
dilakukan pelabelan total tak-ajaib titik kuat ),( da dengan 3n , untuk nilai 1d
dengan 24 na dan 3d dengan 32 na .
Kata kunci: Graf, Pelabelan Total Tak-ajaib Titik Kuat ),( da , Graf Sikel dengan
Tambahan n Anting )( 1nACn
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
ix
ABSTRACT
Lusia Deni Nur Reni. 2019. A Super ),( da Vertex Antimagic Total Labeling on
the Cycle Graph with n Extra Arms. Mathematics Education Study Program,
Department of Mathematics and Science Education, Faculty of Teacher Training
and Education, Sanata Dharma Unversity.
Total labeling is a mapping which the domain are vertexs and edges.
Vertex antimagic total labeling on graph ),( EVG is the bijection mapping of
|}|||,...,2,1{: evEVf and the weights of vertex )(xwt , Vx on the graph
are diferent, where the number of the vertex || v and the number of the edges || e .
The weight of the vertex is obtained by summing the vertex label and all edge that
is incident with its vertex. In ),( da vertex antimagic total labeling, the set of vertex
weight forms a increase arithmatic sequences for the positif integers a and ,d in
which a is first integer and d is in the different aritmatic sequence. Vertex
antimagic total labeling is called super if the labels of the edges are |}|,...,2,1{ e
and the labels of the vertex are |}|||,...,2||,1|{| evee .
The purpose of this research is to know whether the super ),( da vertex
antimagic total labeling on graph 1nACn and to find its formula or its labeling
pattern. Graph 1nACn is the development of cycle graph )( nC which is added up
with n vertex out of nC and each vertex have one edge that connect the vertex with
the unique vertex in nC . This research is the library research where the researcher
reviewed some previous studies to obtain the supporting theories. The result of this
research showed that the cycle graph with n extra arm )( 1nACn imply a super
),( da vertex antimagic total labeling with 3n . For 1d with 24 na and
3d with 32 na .
Key words: Graph, a super ),( da vertex antimagic total labeling, the cycle graph
with n extra arm )( 1nACn
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
x
KATA PENGANTAR
Puji dan syukur kehadirat Tuhan Yang Maha Baik, atas segala kasih
karunia dan berkat-Nya yang melimpah, sehingga penulis dapat menyelesaikan
skripsi yang berjudul “Pelabelan Total Tak-Ajaib Titik Kuat ),( da pada Graf Sikel
dengan Tambahan n Anting” untuk memenuhi salah satu syarat memperoleh gelar
sarjana di Program Studi Pendidikan Matematika, Jurusan Pendidikan Matematika
dan Ilmu Pengetahuan Alam, Fakultas Keguruan dan Ilmu Pendidikan, Universitas
Sanata Dharma, Yogyakarta.
Selama penelitian dan penulisan skripsi ini, penulis mendapat berbagai
dukungan dan bantuan oleh banyak pihak. Oleh karena itu, penulis ingin
menyampaikan terimakasih kepada:
1. Bapak Dr. Harsoyo, S.Pd., M.Si., selaku Dekan Fakultas Keguruan dan Ilmu
Pendidikan Universitas Sanata Dharma Yogyakarta.
2. Bapak Dominikus Arif Budi Prasetyo, M.Si., selaku Dosen Pembimbing
Skripsi yang memberi inspirasi dalam memilih judul skripsi, memberi
bimbingan dan juga memberi motivasi dan semangat.
3. Bapak Marcellinus Andy Rudhito, S.Pd., selaku Ketua Jurusan Pendidikan
Matematika dan Ilmu Pengetahuan Alam.
4. Bapak Beni Utomo, M.Sc., selaku Ketua Program Studi Pendidikan
Matematika Universitas Sanata Dharma Yogyakarta.
5. Bruder Yohanes Sarju, S.J. dan Bapak M. Tri Haryono, selaku Ketua dan
Kayawan Administrasi Lembaga Kesejahteraan Mahasiswa yang selalu
mendukung, membantu dan menjadi perantara penulis sebagai penerima
beasiswa.
6. Bapak Febi Sanjawa, M.Sc., selaku Dosen Pembimbing Akademik yang
memberikan bimbingan selama penulis belajar disini.
7. Seluruh Dosen Program Studi Matematika yang telah banyak memberikan ilmu
pengetahuan dan bekal keterampilan.
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
xi
8. Orang tua saya S. Rantono dan Sumarsih, serta kakak adik saya Suharni dan
Herlinda Prameswaari yang selalu memberi doa, semangat dan dukungan
kepada penulis selama penyusunan skripsi ini.
9. Teman-teman beasiswa Bidikmisi, Cerdas Humanis, dan Driyarkara sebagai
teman seperjuangan yang saling memotivasi satu sama lain.
10. Seluruh teman-teman Pendidikan Matematika angkatan 2015 khususnya
Donny Lucky Ichsan, Patricia Josephine Barek Baba Tapobali, Petrus Kanisius
Abiyasa, Monica Anita Bunga Krisma dan seluruh teman-teman kelas A .
11. Keluarga dan teman-teman semuanya yang tidak dapat disebutkan satu persatu.
Penulis mengharapkan kritik saran yang membangun lewat penulisan
karya lain agar menjadi lebih bermanfaat. Akhir kata, Penulis berharap agar skripsi
ini dapat menambahkan ilmu yang bermanfaat bagi pembaca.
Yogyakarta, 15 Mei 2019
Penulis,
Lusia Deni Nur Reni
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
xii
DAFTAR ISI
HALAMAN JUDUL ................................................................................................ i
HALAMAN PERSETUJUAN PEMBIMBING .................................................... iii
LEMBAR PENGESAHAN ................................................................................... iv
HALAMAN PERSEMBAHAN ............................................................................. v
PERNYATAAN KEASLIAN KARYA ................................................................ vi
LEMBAR PERNYATAAN PERSETUJUAN ..................................................... vii
PUBLIKASI KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS ......... vii
ABSTRAK ........................................................................................................... viii
ABSTRACT ............................................................................................................. ix
KATA PENGANTAR ............................................................................................ x
DAFTAR ISI ......................................................................................................... xii
DAFTAR GAMBAR ........................................................................................... xiv
DAFTAR NOTASI .............................................................................................. xvi
BAB I PENDAHULUAN ....................................................................................... 1
A. Latar Belakang ............................................................................................. 1
B. Rumusan Masalah ........................................................................................ 2
C. Batasan Masalah........................................................................................... 3
D. Tujuan dan Manfaat Penelitian .................................................................... 3
E. Sistem Penulisan .......................................................................................... 3
BAB II LANDASAN TEORI ................................................................................. 5
A. Graf .............................................................................................................. 5
B. Pelabelan Graf ............................................................................................ 13
C. Graf Sikel dengan Tambahan 1 Anting ...................................................... 18
D. Graf Sikel dengan Tambahan 2 Anting ...................................................... 19
BAB III METODE PENELITIAN........................................................................ 21
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
xiii
BAB IV HASIL PENELITIAN DAN PEMBAHASAN ...................................... 22
A. Graf Sikel )( nC dengan Tambahan n Anting )( 1nACn .......................... 22
B. Perhitungan Dasar Pelabelan Total Tak-Ajaib Titik Kuat ),( da pada Graf
Sikel )( nC dengan Tambahan 𝑛 Anting )( 1nACn .................................. 25
C. Pelabelan Total Tak Ajaib Titik Kuat ),( da pada Graf 1nACn untuk
1d dan 3d .......................................................................................... 32
BAB V PENUTUP ................................................................................................ 54
A. Kesimpulan ................................................................................................ 54
B. Saran ........................................................................................................... 55
DAFTAR PUSTAKA ........................................................................................... 56
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
xiv
DAFTAR GAMBAR
Gambar 2. 1 Graf G ................................................................................................. 5
Gambar 2. 2 Graf Tak Berarah ............................................................................... 7
Gambar 2. 3 Graf Berarah ....................................................................................... 7
Gambar 2. 4 Graf Kosong ....................................................................................... 8
Gambar 2. 5 Graf tak Berhingga ........................................................................... 10
Gambar 2. 6 Graf Berbobot ................................................................................... 13
Gambar 2. 7 Graf 3C ............................................................................................. 14
Gambar 2. 8 Graf dengan Pelabelan Tak-Ajaib Titik ........................................... 16
Gambar 2. 9 13 1AC ............................................................................................ 18
Gambar 2. 10 14 1AC .......................................................................................... 18
Gambar 2. 11 15 1AC .......................................................................................... 19
Gambar 2. 12 11ACn .......................................................................................... 19
Gambar 2. 13 13 2AC .......................................................................................... 19
Gambar 2. 14 14 2AC ......................................................................................... 19
Gambar 2. 15 15 2AC ......................................................................................... 20
Gambar 2. 16 12ACn ......................................................................................... 20
Gambar 3. 1 Alur Penelitian.................................................................................. 21
Gambar 4. 1 Graf 13 3AC ................................................................................... 22
Gambar 4. 2 Graf 14 4AC ................................................................................... 23
Gambar 4. 3 Graf 15 5AC ................................................................................... 24
Gambar 4. 4 Graf 1nACn ................................................................................... 24
Gambar 4. 5 Pelabelan total tak ajaib titik kuat )1,14( pada 13 3AC .................. 33
Gambar 4. 6 Pelabelan total tak ajaib titik kuat )1,18( pada 14 4AC .................. 34
Gambar 4. 7 Pelabelan total tak ajaib titik kuat )1,22( pada 15 5AC ................ 35
Gambar 4. 8 Pelabelan total tak ajaib titik kuat (9,3) pada 13 3AC ................... 43
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
xv
Gambar 4. 9 Pelabelan total tak ajaib titik kuat (11,3) pada 14 4AC ................ 44
Gambar 4. 10 Pelabelan total tak ajaib titik kuat (13,3) pada 15 5AC .............. 45
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
xvi
DAFTAR NOTASI
: gabungan himpunan
: untuk setiap
: mendekati
∎ : akhir pembuktian
},...,,{ 21 ivvvV : himpunan titik pada graf
iv : titik ke-i
},...,,{ 21 ieeeE : himpunan sisi pada graf
)( jivve : sisi yang menghubungkan iv dan jv
),( EVG : graf dengan himpunan titik V dan himpunan sisi E
)( ivd : derajat titik iv
|| v : banyaknya titik pada graf
|| e : banyaknya sisi pada graf
vS : jumlah semua label titik
eS : jumlah semua label sisi
wS : jumlah semua bobot titik
)( ivwt : bobot titik iv
)( jivvwt : bobot sisi jivv
f : fungsi
)( ivf : label titik iv
)( jivvf : label sisi jivv
c : konstanta ajaib
nC : graf sikel dengan n titik
1A : anting pada graf
1nACn : graf sikel dengan tambahan n anting
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
1
BAB I
PENDAHULUAN
A. Latar Belakang
Pelabelan graf merupakan salah satu kajian dari graf. Pelabelan graf
memiliki peranan terutama dalam sektor sistem komunikasi dan transportasi,
penyimpanan data komputer, dan desain integrated circuit pada komponen
elektronik (Aman, Rido, 2013:61-62). Pelabelan graf merupakan pemetaan dari
unsur-unsur pada graf ke suatu bilangan positif atau bilangan non-negatif
(Wallis, W. D., 2001: 11). Pelabelan disini dilakukan pada graf sederhana dan
tak berarah. Kotzing dan Rosa (1970:451) mendefinisikan pelabelan ajaib
sebagai pelabelan total dimana labelnya merupakan bilangan bulat dari 1
sampai banyaknya unsur pada graf. Pelabelan ajaib ini merupakan generalisasi
dari persegi ajaib.
Pada tahun 1990, Hartsfield dan Ringel memperkenalkan konsep
mengenai pelabelan anti ajaib pada graf. Pelabelan anti ajaib dari suatu graf
merupakan pelabelan sisi dari suatu graf dengan bilangan bulat positif
|}|,...,2,1{ e sehingga setiap bobot titiknya berbeda, dimana bobot titiknya
didefinisikan sebagai jumlahan label sisi yang bersisian dengan titik tersebut.
Mereka sudah membuktikan bahwa terdapat pelabelan anti ajaib pada beberapa
graf, yaitu path nP , star nS , cycle nC , complete graph nK , wheel nW , dan
bipartite graph nK ,2 , 3n . Kemudian, pada tahun 1993, Bodendiek dan
Walter mendefinisikan konsep ),( da tak ajaib graf sebagai suatu pelabelan tak
ajaib yang bobot titiknya membentuk suatu barisan aritmatika dengan suku
pertama a dan beda d.
Selanjutnya, pada tahun 2003, Martin Baca, dkk. telah menunjukkan
keberlakukan pelabelan total tak ajaib titik untuk path, graf petersen, dan sikel
ganjil. Selain itu, telah banyak dilakukan penelitian untuk menunjukkan
keberlakuan pelabelan ajaib maupun tak ajaib pada graf, salah satunya
pelabelan pada graf yang berkaitan dengan graf sikel (cycle graph), seperti dua
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
2
graf sikel dengan banyak titik berbeda baru saja ditunjukkan oleh Prasetyo pada
tahun 2018 bahwa graf tersebut dapat dilakukan pelabelan total tak ajaib titik
super. Graf multicycle pmC telah ditunjukkan memenuhi ),( da vertex
antimagic total labelling oleh Prasetyo pada tahun 2012 dan telah ditunjukkan
bahwa graf tersebut bisa dilakukan pelabelan total tak ajaib sisi kuat oleh
Sanjaya pada tahun 2013. Selain itu, graf sikel dengan tambahan anting, seperti
graf sikel dengan tambahan satu anting telah ditunjukkan keberlakuan
pelabelan total ajaib titik oleh Septian pada tahun 2012, graf sikel dengan
tambahan dua anting telah ditunjukkan keberlakuan pelabelan total ajaib sisi
kuat oleh Yulianto pada tahun 2012 dan telah ditunjukkan keberlakuan
pelabelan total ajaib titik oleh Andriyani pada tahun 2014. Peneliti lainnya,
Kristianna pada tahun 2013 juga sudah membahas mengenai graf sikel dengan
tambahan n anting dan didapatkan bahwa graf tersebut dapat dilakukan
pelabelan total ajaib sisi kuat untuk 3n dan n ganjil.
Berdasarkan hasil dari penelitian-penelitian sebelumnya, penulis ingin
mengembangkan hasil penelitian yang dilakukan oleh Kristianna mengenai
graf sikel dengan tambahan n anting )( 1nACn . Kristianna telah menunjukkan
keberlakuan pelabelan total ajaib sisi kuat untuk 3n dan n ganjil namun
belum membuktikan mengenai keberlakuan pelabelan total tak ajaib titik kuat
pada graf tersebut dan belum ada peneliti yang melakukan penelitian tersebut.
Oleh karena itu, pada skripsi ini akan dibahas mengenai bentuk graf sikel
dengan tambahan n anting )( 1nACn , kemudian menentukan keberlakuan
pelabelan total tak ajaib titik kuat dan mencari pola pelabelan total tak-ajaib
titik kuat ),( da pada graf 1nACn .
B. Rumusan Masalah
Berikut ini merupakan rumusan masalah yang akan dibahas:
1. Apakah graf 1nACn memenuhi pelabelan total tak ajaib titik kuat?
2. Bagaimana pola pelabelan total tak-ajaib titik kuat ),( da pada graf
1nACn ?
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
3
C. Batasan Masalah
Pada penelitian ini, penulis membatasi penelitian dengan mencari salah satu
pola pelabelan total tak-ajaib titik kuat ),( da yang berlaku pada graf sikel
dengan tambahan n anting ( 1nACn ). Karena ada kemungkinan terdapat lebih
dari satu pola perumusan untuk ),( da yang sama.
D. Tujuan dan Manfaat Penelitian
Tujuan dan Manfaat penelitian ini yaitu:
1. Mengetahui keberlakuan pelabelan tak ajaib titik pada graf 1nACn .
2. Mentukan nilai dari suku pertama a dan beda d yang memenuhi pelabelan
total tak-ajaib titik kuat ),( da pada graf 1nACn .
3. Menentukan rumus umum/pola pelabelan tak ajaib titik pada graf 1nACn
.
E. Sistem Penulisan
Untuk mempermudah penulis maupun pembaca dalam mengkaji skripsi ini,
skripsi ini dibagi menjadi 5 bagian, yaitu:
BAB I PENDAHULUAN
Pada bab ini dipaparkan mengenai latar belakang, rumusan masalah,
tujuan dan manfaat penelitian, serta sistematika penulisan.
BAB II LANDASAN TEORI
Pada bab ini dipaparkan mengenai definisi-definisi graf dan
pelabelan graf yang digunakan dalam skripsi ini.
BAB III METODOLOGI PENELITIAN
Pada bab ini dipaparkan mengenai langkah-langkah penelitian.
BAB IV PEMBAHASAN
Pada bab ini dipaparkan mengenai graf 𝐶𝑛 + 𝑛𝐴1, perhitungan dasar
untuk menentukan pelabelan total tak ajaib titik kuat ),( da pada graf
𝐶𝑛 + 𝑛𝐴1 dan pola perumusan pelabelan.
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
4
BAB V PENUTUP
Pada bab ini dipaparkan mengenai kesimpulan dari pembahasan
yang telah diuraikan pada BAB IV dan dipaparkan juga saran-saran
yang berkaitan dengan pembahasan.
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
5
BAB II
LANDASAN TEORI
Berikut ini akan disajikan beberapa teori untuk mempermudah
pemahaman mengenai graf. Landasan teori ini dibagi menjadi 4 bagian, meliputi
graf, pelabelan graf, graf sikel dengan tambahan 1 anting, dan graf sikel dengan
tambahan 2 anting.
A. Graf
Berikut ini diberikan definisi graf dan istilah-istilah yang digunakan dalam
graf.
Definisi 2.1 (Rosen, Kenneth H., 2019:673)
Diberikan himpunan tak kosong titik },...,,{ 21 nvvvV dan himpunan sisi
},...,,{ 21 neeeE dengan ),( ji vve , Vvv ji , . Suatu himpunan G yang
terdiri dari V dan E disebut graf, yang dinotasikan dengan ),( EVG .
Berikut ini akan diberikan contoh mengenai suatu graf.
Contoh 2.1
Diberikan },,{ 321 vvvV dan )}(),(),(),(),{( 4231312111 vvvvvvvvvvE .
Graf tersebut dapat digambarkan seperti diagram berikut ini:
Gambar 2. 1 Graf G
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
6
Pada Gambar 2.1 dapat dilihat bahwa, gambar tersebut memiliki tiga
titik yang berarti memiliki himpunan tak kosong titik. Gambar tersebut juga
memiliki lima sisi yang berarti memiliki himpunan sisi. Selain itu, setiap sisi
memiliki titik yang terkait dengannya, sisi 1e terkait dengan satu titik yang
menjadi ujungnya dan sisi lainnya terkait dengan dua titik yang menjadi
ujungnya. Oleh karena itu, gambar tersebut memenuhi Definisi 2.1, sehingga
gambar tersebut dapat dikatakan sebagai suatu graf.
Berikut ini diberikan definisi graf tak berarah dan graf berarah.
Definisi 2.2 (Johnsonbaugh, Richard, 2009: 378)
Diberikan suatu gabungan himpunan V titik (vertices atau nodes) dan
himpunan E sisi (edges atau arcs) dimana setiap Ee dikaitkan dengan
sepasang titik dengan himpunan E diasumsikan sebagai himpunan berhingga
dan V diasumsikan sebagai himpunan tak kosong, maka:
1. Gabungan himpunan tersebut dinamakan graf tak berarah jika setiap
Ee dikaitkan dengan sepasang titik yang tidak berurutan. Jika terdapat
sisi e yang terkait dengan titik iv dan jv , maka dapat ditulis )( jivve
atau )( ijvve . Notasi )( jivv menunjukkan sisi diantara iv dan jv di graf
tak berarah dan bukan pasangan berurutan.
2. Gabungan himpunan tersebut dinamakan graf berarah (digraph) jika
setiap Ee dikaitkan dengan sepasang titik yang berurutan. Jika
terdapat sisi e yang terkait dengan titik iv dan jv , maka dapat ditulis
)( jivve , dimana menotasikan sisi dari iv ke jv .
Pada kajian ini, graf yang digunakan merupakan graf tak berarah.
Berikut ini akan diberikan contoh yang berkaitan dengan graf tak berarah dan
graf berarah.
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
7
Contoh 2.2
Diberikan suatu graf ),( EVG dengan },,{ 321 vvvV dan },,{ 321 eeeE
dimana ),( 211 vve ),( 232 vve ),( 313 vve jika graf ),( EVG tersebut
tidak diketahui bahwa graf tersebut adalah graf berarah maka graf ),( EVG
tersebut dapat digambarkan seperti pada Gambar 2.2. Namun, jika diketahui
bahwa graf tersebut graf berarah maka graf ),( EVG dapat digambarkan
seperti pada Gambar 2.3.
Gambar 2. 2 Graf Tak Berarah Gambar 2. 3 Graf Berarah
Berikut akan diberikan definisi graf kosong.
Definisi 2.3 (Munir, Rinaldi, 2001: 192)
Diberikan suatu graf yang himpunan sisinya merupakan himpunan kosong.
Graf tersebut disebut sebagai graf kosong (null graph atau empty graph) dan
disimbolkan nN , yang dalam hal ini n adalah banyaknya titik pada graf
tersebut.
Berikut ini akan diberikan contoh graf kosong.
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
8
Contoh 2.3
Gambar 2. 4 Graf Kosong
Graf pada Gambar 2.4 merupakan salah satu contoh dari graf kosong,
karena himpunan sisinya merupakan himpunan kosong.
Pada kajian ini, graf yang digunakan adalah graf sederhana. Untuk
menjelaskan definisi graf sederhana akan diberikan definisi loop dan garis
sejajar (paralel).
Definisi 2.4 (Siang, Jong Jek, 2009: 219)
Sisi yang hanya terkait dengan satu titik ujung disebut gelang atau loop.
Berikut ini akan diberikan contoh dari gelang atau loop.
Contoh 2.4
Pada Gambar 2.1 sisi 1e dinamakan gelang (loop), karena sisi 1e hanya terkait
dengan satu titik ujung yaitu 1v .
Definisi 2.5 (Siang, Jong Jek, 2009: 219)
Dua sisi berbeda ie dan je dengan ji yang terkait dengan titik ujung yang
sama disebut garis sejajar (paralel).
Berikut ini akan diberikan contoh garis sejajar (paralel).
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
9
Contoh 2.5
Pada Gambar 2.1, 3e dan 4e merupakan suatu sisi sejajar (paralel), karena sisi
3e dan 4e terkait dengan titik ujung yang sama yaitu, )( 313 vve dan
)( 314 vve .
Berikut ini diberikan definisi graf sederhana.
Definisi 2.6 (Siang, Jong Jek, 2009: 226)
Diberikan suatu graf yang tidak memiliki loop ataupun sisi paralel. Graf
tersebut disebut graf sederhana (simple graph).
Berikut ini akan diberikan contoh graf sederhana dan tak sederhana.
Contoh 2.6
Graf sederhana dapat dilihat pada Gambar 2.2 dan Gambar 2.3 karena pada
Gambar 2.2 dan Gambar 2.3 merupakan graf yang tidak memiliki loop dan sisi
paralel. Sedangkan Gambar 2.1 merupakan graf yang memiliki loop dan sisi
paralel, sehingga graf tersebut merupakan graf tak sederhana.
Pada peneitian ini, graf yang digunakan merupakan graf berhingga,
sehingga akan diberikan definisi dari graf berhingga dan tak berhingga.
Definisi 2.7 (Munir, Rinaldi, 2001: 183)
Diberikan graf yang banyaknya titiknya n berhingga. Graf tersebut disebut
graf berhingga.
Berikut ini akan diberikan contoh dari graf berhingga.
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
10
Contoh 2.7
Graf pada Gambar 2.1, Gambar 2.2, dan Gambar 2.3 merupakan contoh dari
graf beringga karena banyaknya titik pada graf tersebut berhingga, yaitu pada
ketiga graf tersebut banyaknya titik adalah 3.
Definisi 2.8 (Munir, Rinaldi, 2001: 183)
Diberikan graf yang banyaknya titiknya tidak berhingga. Graf tersebut disebut
graf tak berhingga.
Berikut akan diberikan contoh dari graf tak berhingga.
Contoh 2.8
Gambar 2. 5 Graf tak Berhingga
Berikut ini akan diberikan definisi mengenai derajat untuk
mendefinisikan graf sikel.
Definisi 2.9 (Siang, Jong Jek, 2009: 236)
Diberikan iv adalah titik dalam suatu Graf G.
1. Derajat titik iv (simbol ))( ivd adalah jumlah sisi yang berhubungan
dengan titik iv dan sisi suatu loop dihitung dua kali.
2. Derajat total G adalah jumlah derajat semua titik dalam G.
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
11
Berikut ini akan diberikan contoh mengenai derajat.
Contoh 2.9
Pada Gambar 2.1
5)( 1 vd , karena sisi yang berhubungan dengan titik 1v adalah ,2e ,3e ,4e dan
loop 1e
2)( 2 vd , karena sisi yang berhubungan dengan titik 2v adalah 2e dan 5e
3)( 3 vd , karena sisi yang berhubungan dengan titik 3v adalah ,3e ,4e dan 5e
Berikut ini akan diberikan definisi graf sikel.
Definisi 2.10 (S, Suryadi H., 1996: 31)
Diberikan graf dengan lintasan tertutup dengan derajat setiap titik yaitu dua.
Graf tersebut disebut graf sikel. Sikel dengan banyaknya titik n disebut Sikel-
n atau n-Cycle (disimbolkan nC ).
Berikut diberikan contoh dari Graf Sikel.
Contoh 2.10
Graf pada Gambar 2.2 dan Gambar 2.3 merupakan contoh dari graf sikel,
karena graf tersebut merupakan graf dengan lintasan tertutup dengan derajat
masing-masing titiknya 2)()()( 321 vdvdvd . Banyaknya titik pada graf
tersebut adalah 3, sehingga dapat disebut graf 3C .
Selanjutnya akan diberikan definisi bertetangga (adjacent) dan
bersisian (incident).
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
12
Definisi 2.11 (Munir, Rinaldi, 2001: 191)
Dua titik dikatakan bertetangga (adjacent) jika keduanya terhubung langsung
atau dapat dikatakan iv bertetangga dengan jv jika )( jivveEe .
Berikut akan diberikan contoh dua titik yang dikatakan bertetangga.
Contoh 2.11
Pada Gambar 2.1 titik 1v bertetangga dengan titik 2v dan 3v .
Definisi 2.12 (Munir, Rinaldi, 2001: 191)
Untuk sebarang sisi )( jivve , dikatakan e bersisian (incident) dengan titik
iv atau e bersisian dengan titik titik jv .
Berikut akan diberikan contoh sisi yang bersisian.
Contoh 2.12
Pada Gambar 2. 1 sisi 2e bersisian dengan titik 1v dan titik 2v .
Berikut ini akan diberikan definisi dari graf berbobot.
Definisi 2.13 (Munir, Rinaldi, 2001: 203)
Diberikan graf yang setiap sisinya diberi sebuah harga (bobot). Graf tersebut
disebut graf berbobot.
Bobot setiap sisi bisa menyatakan sebuah jarak antar kota, biaya perjalanan
antar dua kota, waktu tempuh, ongkos produksi, dan sebagainya. Berikut ini
diberikan contoh dari graf berbobot.
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
13
Contoh 2.13
Gambar 2. 6 Graf Berbobot
Pada Gambar 2.6
9)( 21 vvwt , karena pada sisi pada sisi 21vv bobotnya yaitu 9.
5)( 32 vvwt , karena pada sisi pada sisi 32vv bobotnya yaitu 5.
7)( 31 vvwt , karena pada sisi pada sisi 31vv bobotnya yaitu 7.
B. Pelabelan Graf
Pelabelan graf merupakan pemetaan suatu himpunan unsur-unsur
pada graf ke suatu himpunan bilangan. Terdapat beberapa macam pelabelan
graf, yaitu pelabelan dengan domain himpunan titik yang dinamakan pelabelan
titik, pelabelan yang domainnya sisi yang dinamakan pelabelan sisi dan
pelabelan yang domainnya titik dan sisi yang dinamakan pelabelan total. Pada
penelitian ini, akan digunakan pelabelan total atau pelabelan yang domainnya
titik dan sisi. Oleh karena itu, akan diberikan beberapa definisi mengenai
pelabelan total.
Berikut akan diberikan definisi bobot titik dan bobot sisi untuk
mendefinisikan pelabelan total.
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
14
Definisi 2.14 (Wallis, W.D., 2001:11)
Diberikan 𝐴 adalah sebuah himpunan bilangan bulat positif, yaitu
|}|||,...,2,1{ evA dan f merupakan sebuah fungsi yang memetakan
himpunan unsur-unsur pada graf, yaitu titik dan sisi ke himpunan A. Fungsi
tersebut dinotasikan dengan AEVf : dan untuk bobot titik dan bobot
sisi disimbolkan wt. Diberikan Vvv ji , dan jivv merupakan sisi pada graf
yang salah satu ujungnya di 𝑣𝑖, maka bobot titik dapat dicari dengan:
ji vv
jiii vvfvfvwt~
)()()(
Sedangkan bobot sisi dapat dicari dengan:
)()()()( jjiiji vfvvfvfvvwt
Berikut akan diberikan contoh menghitung bobot titik dan bobot sisi
pada suatu graf berbobot.
Contoh 2.14
Gambar 2. 7 Graf 3C
Untuk mencari bobot titik pada Gambar 2.7 tersebut dapat dilakukan
dengan menjumlahkan label titik tersebut dengan label sisi yang bersisian
dengan titik tersebut. Misalnya, bobot titik dengan label 1 dapat dicari dengan
menjumlahkan label tersebut yaitu 1 dan label-label sisi yang bersisian dengan
titik tersebut yaitu 5 dan 6 sehingga didapatkan bahwa bobot titik tersebut
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
15
adalah 12 ( 12651 ). Sedangkan, untuk mencari bobot sisi dapat
dilakukan dengan menjumlahkan label sisi tersebut dengan label titik-titik
ujung sisi tersebut. Misalnya, bobot sisi dengan label 6 dapat dicari dengan
menjumlahkan label sisi tersebut yaitu 6 dan label titik-titik ujung sisi tersebut
yaitu 1 dan 2, sehingga didapatkan bahwa bobot sisi tersebut adalah 9
)9216( .
Berikut ini akan diberikan definisi pelabelan total ajaib titik.
Definisi 2.15 (Wallis, W.D., 2001:65)
Suatu pemetaan bijektif f dari gabungan himpunan sisi dan himpunan titik ke
himpunan bilangan bulat |}|||,...,2,1{ ev disebut vertex magic total labeling
atau pelabelan total ajaib titik jika terdapat konstanta c sehingga untuk setiap
titik iv , cefvf ii )()( , dimana untuk semua ie yang bersisian dengan
iv . Konstanta h disebut magic constant untuk f. Selanjutnya, graf yang
memenuhi vertex magic total labeling disebut vertex magic total graph.
Berikut ini akan diberikan contoh pelabelan total ajaib titik pada
suatu graf.
Contoh 2.15
Dengan menggunakan Definisi 2.14, Graf pada Gambar 2.7 dapat dicari bahwa
bobot masing-masing titiknya adalah 12 yaitu:
bobot titik berlabel 1 12651 ,
bobot titik berlabel 2 12462 , dan
bobot titik berlabel 3 12543 . Oleh karena itu, graf pada Gambar 2.7
merupakan salah satu contoh dari pelabelan total ajaib titik (vertex magic total
labeling).
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
16
Berikut ini akan diberikan definisi mengenai pelabelan total tak ajaib
titik.
Definisi 2.16 (Baca, dkk., 2003:69)
Suatu pemetaan bijektif |}|||,...,2,1{: evEVf disebut vertex
antimagic total labeling atau pelabelan total tak-ajaib titik dari ),( EVG ,
jika bobot setiap titik ),( ivwt Vvi berbeda.
Berikut ini akan diberikan contoh pelabelan total tak ajaib titik pada
suatu graf.
Contoh 2.16
Gambar 2. 8 Graf dengan Pelabelan Tak-Ajaib Titik
Graf pada Gambar 2.8 merupakan salah satu contoh graf dengan
pelabelan total tak-ajaib titik, karena bobot setiap titik berbeda, yaitu:
bobot titik dengan label 1 12651 ,
bobot titik dengan label 2 11542 , dan
bobot titik dengan label 3 13643 .
Berikut akan diberikan definisi mengenai pelabelan total tak ajaib
yang bobot titiknya membentuk suatu barisan aritmatika naik atau pelabelan
total tak ajaib titik ),( da .
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
17
Definisi 2.17 (Baca, dkk., 2003:69)
Suatu pemetaan bijektif |}|||,...,2,1{: evEVf disebut ),( da vertex
antimagic total labeling atau pelabelan total tak-ajaib titik ),( da dari 𝐺 jika
himpunan bobot titik membentuk suatu barisan aritmatika naik
})1(,...,,{}|)({ dvdaaVvvwtW ii untuk a dan d bilangan bulat
positif.
Berikut ini akan diberikan contoh dari pelabelan total tak ajaib yang
bobot titiknya membentuk suatu barisan aritmatika naik (pelabelan total tak
ajaib titik ),( da ).
Contoh 2.17
Graf pada Gambar 2.8 juga merupakan contoh dari graf yang memiliki
pelabelan total tak-ajaib titik ),( da . Hal ini dikarenakan bobot-bobot titiknya
membentuk suatu barisan aritmatika naik yaitu dengan suku pertama 11a
dan beda 1d dengan bobot titik 11 pada titik berlabel 2, bobot titik 12 pada
titik berlabel 1, dan bobot titik 13 pada titik berlabel 3.
Berikut akan diberikan definisi pelabelan total tak-ajaib sisi kuat atau
super. Pada kajian ini, selanjutnya akan digunakan kata kuat untuk menyebut
pelabelan total tak-ajaib sisi kuat.
Definisi 2.18 (Gallian, Joseph A. 2018: 205)
Pelabelan total tak-ajaib sisi dari suatu graf ),( EVG dikatakan pelabelan
total tak-ajaib sisi kuat jika label titiknya |}|,...,2,1{ v dan label sisinya
|}|||,...,2||,1|{| evvv . Oleh karena itu, suatu pelabelan total tak ajaib
titik dapat dikatakan kuat jika label sisi-sisinya |}|,...,2,1{ e dan label titiknya
|}|||,...,2||,1|{| evee dengan || e banyaknya sisi dan || v banyaknya
titik pada graf tersebut.
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
18
Berikut akan diberikan contoh pelabelan kuat dan bukan pelabelan
kuat.
Contoh 2.18
Pada Contoh 2.17 telah ditunjukkan bahwa Gambar 2.8 merupakan pelabelan
total tak-ajaib titik )1,11( , tetapi pelabelan tersebut tidak bisa dikatakan sebagai
pelabelan total tak-ajaib titik kuat )1,11( . Hal ini dikarenakan label-label
titiknya }3,2,1{ sedangkan label sisinya }6,5,4{ , sehingga tidak sesuai dengan
Definisi 2.18. Gambar 2.8 juga merupakan graf dengan pelabelan total tak-
ajaib sisi )1,8( dengan, bobot sisi 8 pada sisi berlabel 5 yaitu 5+1+2, bobot sisi
9 pada sisi berlabel 4 yaitu 4+2+3, dan bobot sisi 10 pada sisi berlabel 6 yaitu
6+1+3. Selain itu, pelabelan ini juga disebut sebagai pelabelan total tak-ajaib
sisi kuat )1,8( , karena label titiknya }3,2,1{ dan label sisinya }6,5,4{ hal ini
memenuhi Definisi 2.18.
C. Graf Sikel dengan Tambahan 1 Anting
Graf sikel dengan tambahan satu anting merupakan perkembangan
dari graf sikel yang ditambahkan dengan satu titik diluar nC dan satu sisi yang
menghubungkan titik tersebut dengan titik pada nC . Graf ini dapat dinotasikan
dengan 1ACn . Berikut akan diberikan contoh graf sikel dengan tambahan 1
Anting.
Contoh 2.19
Gambar 2. 9 13 1AC Gambar 2. 10 14 1AC
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
19
Gambar 2. 11 15 1AC Gambar 2. 12 11ACn
D. Graf Sikel dengan Tambahan 2 Anting
Graf sikel dengan tambahan dua anting merupakan perkembangan
dari graf sikel yang ditambahkan dengan dua titik diluar nC dan masing-
masing terdapat sisi yang menghubungkan titik tersebut dengan titik yang
berbeda pada nC . Graf ini dapat dinotasikan dengan 12ACn . Berikut akan
diberikan contoh graf sikel dengan tambahan 1 Anting.
Contoh 2.20
Gambar 2. 13 13 2AC Gambar 2. 14 14 2AC
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
20
Gambar 2. 15 15 2AC Gambar 2. 16 12ACn
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
21
BAB III
METODE PENELITIAN
Metode penelitian yang digunakan dalam penelitian ini adalah penelitian
pustaka (Library Research). Dalam melakukan penelitian ini, akan dilakukan
beberapa tahapan kerja. Secara garis besar, tahapan tersebut yaitu:
1. Mengumpulkan berbagai literatur mengenai topik pelabelan graf, terutama
pelabelan tak-ajaib titik
2. Mempelajari literatur yang telah dikumpulkan sebelumnya
3. Membangun sebuah graf baru )( 1nACn
4. Menganalisa graf tersebut dengan menggunakan perhitungan dasar
5. Mencari pola dari pelabelan
6. Menetukan rumusan pelabelan untuk unsur dari graf (titik dan sisi)
Tahapan tersebut juga dapat di lihat dari gambar alur penelitian berikut ini:
Gambar 3. 1 Alur Penelitian
Mulai
Mengumpulkan berbagai literatur mengenai topik pelabelan graf, terutama pelabelan tak ajaib titik
Mempelajari literatur yang telah dikumpulkan
sebelumnya
Membangun sebuah graf baru
Menganalisa graf tersebut dengan
menggunakan perhitungan dasar
Mencari pola dari pelabelan
Menetukan rumusan pelabelan untuk unsur dari graf (titik dan sisi)
Selesai
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
22
BAB IV
HASIL PENELITIAN DAN PEMBAHASAN
Pada bab ini, peneliti menyajikan hasil penelitian dan pembahasan dalam
beberapa subbab. Pertama, menjelaskan mengenai graf sikel )( nC dengan
tambahan n anting )( 1nACn . Kedua, menentukan suku awal a dan beda d melalui
perhitungan dasar pelabelan tak-ajaib titik kuat. Ketiga, membentuk pelabelan total
tak-ajaib titik kuat yang berlaku pada graf sikel )( nC dengan tambahan n anting
)( 1nACn dengan beberapa contoh dan menentukan rumus pelabelan total tak-
ajaib titik kuat pada graf sikel )( nC dengan tambahan n anting )( 1nACn .
A. Graf Sikel )( nC dengan Tambahan n Anting )( 1nACn
Graf 1nACn merupakan pengembangan dari graf sikel nC yang
ditambahkan sebanyak n titik di luar sikel nC dan masing-masing titik terdapat
sisi yang menghubungkan titik tersebut ke titik yang berbeda pada nC . Berikut
merupakan contoh dari beberapa graf sikel dengan tambahan n anting
)( 1nACn .
Gambar 4. 1 Graf 13 3AC
Graf pada Gambar 4.1 merupakan salah satu contoh dari graf sikel
dengan tambahan n anting yaitu dengan 3n (graf 13 3AC ). Pada gambar
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
23
tersebut terlihat bahwa terdapat 3 titik pada sikel 3C dan 3 titik diluar sikel ,3C
sehingga banyaknya titik pada graf 13 3AC yaitu 63233 . Pada
gambar tersebut juga terlihat bahwa terdapat 3 sisi pada sikel 3C dan 3 sisi
diluar sikel 3C , sehingga banyaknya sisi pada graf 13 3AC yaitu
63233 .
Gambar 4. 2 Graf 14 4AC
Graf pada Gambar 4.2 merupakan salah satu contoh dari graf sikel
dengan tambahan n anting yaitu dengan 4n (graf 14 4AC ). Pada gambar
tersebut terlihat bahwa terdapat 4 titik pada sikel 4C dan 4 titik diluar sikel ,4C
sehingga banyaknya titik pada graf 14 4AC yaitu 84244 . Pada
gambar tersebut juga terlihat bahwa terdapat 4 sisi pada sikel 4C dan 4 sisi
diluar sikel 4C , sehingga banyaknya sisi pada graf 14 4AC yaitu
84244 .
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
24
Gambar 4. 3 Graf 15 5AC
Graf pada Gambar 4.3 merupakan salah satu contoh dari graf sikel
dengan tambahan n anting yaitu dengan 5n (graf 15 5AC ). Pada gambar
tersebut terlihat bahwa terdapat 5 titik pada sikel 5C dan 5 titik diluar sikel ,5C
sehingga banyaknya titik pada graf 15 5AC yaitu 105255 . Pada
gambar tersebut juga terlihat bahwa terdapat 5 sisi pada sikel 5C dan 5 sisi
diluar sikel 5C , sehingga banyaknya sisi pada graf 15 5AC yaitu
105255 .
Gambar 4. 4 Graf 1nACn
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
25
Graf pada Gambar 4.4 merupakan gambar graf sikel dengan tambahan
n anting secara umum (graf 1nACn ) Berdasarkan beberapa graf sebelumnya,
banyaknya titik dan sisi pada graf membentuk sebuah pola, yaitu 2n. Dari pola
tersebut, maka graf sikel ( nC ) dengan tambahan n anting )( 1nACn , memiliki
2n buah titik dan 2n buah sisi. Jadi, banyaknya unsur pada graf:
nnnev 422|||| (1)
dengan |𝑣| yaitu banyaknya titik pada graf 1nACn dan || e yaitu banyaknya
sisi pada 1nACn .
B. Perhitungan Dasar Pelabelan Total Tak-Ajaib Titik Kuat ),( da pada
Graf Sikel )( nC dengan Tambahan 𝒏 Anting )( 1nACn
Pada bagian ini, pembahasan mengenai perhitungan dasar pelabelan
total tak-ajaib titik kuat ),( da pada graf sikel )( nC dengan tambahan n anting
)( 1nACn dibagi menjadi beberapa bagian. Pertama, mencari jumlah semua
label. Kedua, mencari jumlah bobot titik. Ketiga, mencari batasan bobot titik
terkecil dan terbesar. Keempat mencari nilai beda d. Kelima, mencari batasan
nilai bobot titik terkecil a. Keenam, mencari nilai bobot terkecil a.
1. Jumlah Semua Label
Berdasarkan Definisi 2.16 pelabelan total tak ajaib titik merupakan
pemetaan bijektif dari setiap unsur pada graf (titik dan sisi) ke suatu
bilangan bulat positif |}|||,...,2,1{ ev . Dengan demikian, menggunakan
persamaan (1) dapat dicari jumlah semua label titik dan sisi )( ev SS pada
graf 1nACn dengan menjumlahkan semua label titik dan label sisi dari
satu sampai |)||(| ev , sehingga didapatkan:
|)||(|...21 evSS ev
n4...21
2
14n
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
26
)!214(!2
)!14(
n
n
)!14(2
)!14(4)14(
n
nnn
2
4)14( nn
nn 2)14( (2)
dimana vS yaitu jumlah semua label titik dan eS yaitu jumlah semua label
sisi.
2. Jumlah Bobot Titik
Berdasarkan Definisi 2.17 pada pelabelan total tak ajaib titik, bobot
titiknya membentuk barisan aritmatika akibatnya:
))12((...)2()( dnadadaaSw
))12(...2(2 dnddna
dnna ))12(...21(2
dn
na
2
22
dn
nna
)!22(!2
!22
dn
nnnna
)!22(2
)!22)(12(22
dnn
na2
)12(22
dnnna )12(2 (3)
Berdasarkan Definisi 2.14 pada pelabelan total tak ajaib titik,
bobot suatu titik dicari dengan menjumlahkan label titik tersebut dengan
label sisi yang memiliki ujung di titik tersebut, sehingga label titik dihitung
satu kali dan label sisi dihitung dua kali, akibatnya:
evw SSS 2
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
27
eevw SSSS )(
ew SnnS 2)14( (4)
Dengan mensubstitusikan persamaan (3) ke persamaan (4) akan
didapatkan:
eSnndnnna 2)14()12(2 (5)
Berdasarkan Definisi 2.18 yaitu tentang pelabelan kuat, label-
label untuk sisinya yaitu }2,...,2,1{ n dan label-label untuk titiknya yaitu
}4,...,22,12{ nnn . Oleh karena itu, persamaan (5) menjadi:
eSnndnnna 2)14()12(2
)2...21(2)14()12(2 nnndnnna
2
122)14()12(2
nnndnnna
)!212(!2
)!12(2)14()12(2
n
nnndnnna
)!12(2
)!12(2)12(2)14()12(2
n
nnnnndnnna
2
2)12(2)14()12(2
nnnndnnna
nnnndnnna )12(2)14()12(2
)12(2)14()12(2 nndna
dnnna )12()12(2)14(2
dnnna )12(12282
dnna )12(3102
2
)12(310 dnna
(6)
3. Batasan Bobot Titik Terkecil dan Terbesar
Bobot titik pada pelabelan total titik dihitung dari bobot titik
tersebut ditambah dengan bobot sisi yang bersisian dengan titik tersebut,
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
28
sehingga untuk mencari bobot terkecil ambil titik dengan sisi yang
bersisian paling sedikit. Pada graf 1nACn titik untuk menghitung bobot
terkecil dipilih titik pada anting graf, karena hanya terdapat 1 titik dan 1
sisi yang bersisian dengan titik tersebut. Pada pelabelan total tak ajaib titik
kuat label pada sisi terdiri dari bilangan bulat positif dari 1 sampai total sisi
maka untuk mencari batasan bobot titik terkecil diambil bilangan 1 untuk
label sisi dan 12 n untuk label titik, sehingga:
a bobot titik terkecil
22
121
na
na
Berbeda dengan mencari bobot titik terkecil yang menggunakan
titik dengan sisi yang bersisian paling sedikit, untuk mencari batasan bobot
terbesar, dipilih titik dengan sisi yang bersisian paling banyak. Pada graf
1nACn , titik untuk menghitung bobot terbesar dipilih titik pada sikel. Hal
ini dikarenakan titik pada sikel memuat 3 sisi yang bersisian dengan titik
tersebut. Selain itu, untuk menentukan bobot yang terbesar, ambil label-
label yang besar pula, akibatnya batasan bobot titik terbesar dapat dicari
dengan:
dna )12( bobot titik terbesar
310)12(
)22()12(24)12(
ndna
nnnndna
4. Batasan Nilai Beda d
Untuk mencari batasan nilai 𝑑, diambil nilai bobot titik terkecil 𝑎
yaitu, 𝑎 = 2𝑛 + 2. Dengan mensubstitusikan nilai 𝑎 = 2𝑛 + 2 ke batasan
bobot maka akan didapatkan:
310)12( ndna
310)12()22( ndnn
)22(310)12( nndn
58)12( ndn
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
29
412
58
n
nd
Jadi, didapatkan nilai 4d , sehingga kemungkinan nilai d-nya
adalah 1, 2, 3, atau 4.
5. Batasan Nilai Bobot Terkecil 𝒂
Selanjutnya akan dicari batasan nilai 𝑎 dengan 𝑑 ≤ 4
menggunakan batasan bobot titik terbesar,
a. Untuk 1d , diperoleh:
310)12( ndna
3101)12( nna
31012 nna
13210 nna
28 na
Jadi, batasan untuk nilai 𝑎 agar dapat dilakukan pelabelan yaitu
2822 nan .
b. Untuk 2d , diperoleh:
310)12( ndna
3102)12( nna
31024 nna
23410 nna
16 na
Jadi, batasan untuk nilai 𝑎 agar dapat dilakukan pelabelan yaitu
1622 nan .
c. Untuk 𝑑 = 3, diperoleh:
310)12( ndna
3103)12( nna
31036 nna
33610 nna
na 4
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
30
Jadi, batasan untuk nilai 𝑎 agar dapat dilakukan pelabelan yaitu
nan 422 .
d. Untuk 𝑑 = 4, diperoleh:
310)12( ndna
3104)12( nna
31048 nna
43810 nna
12 na
Batasan untuk nilai a yang didapatkan yaitu, 1222 nan .
Tetapi batasan tersebut tidak memungkinkan karena tidak ada nilai a
yang memenuhi batasan tersebut. Jadi, 4d tidak dapat dipakai
untuk melakukan pelabelan total titik kuat ),( da pada graf sikel )( nC
dengan tambahan n anting )( 1nACn .
6. Nilai bobot titik terkecil a
Pada persamaan (5) telah ditunjukkan bahwa
2
)12(310 dnna
dan berdasarkan hasil perhitungan a dan d
sebelumnya, maka pelabelan total tak ajaib titik kuat pada graf 1nACn
kemungkinan dapat dilakukan ketika 1d , 2d atau 3d , maka akan
dicari nilai a untuk 1d , 2d dan 3d dengan 3n .
a. Untuk 1d dengan 3n
2
)12(310 dnna
2
1)12(310
nna
2
12310
nna
2
48
na
24 na
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
31
Untuk 1d diperoleh 24 na . Nilai a tersebut memenuhi batasan
bobot titik yaitu 22 na . Jadi, pada graf sikel )( nC dengan
tambahan n anting )( 1nACn terdapat pelabelan total tak ajaib titik
kuat )1,24( n untuk 3n .
b. Untuk 2d dengan 3n
2
)12(310 dnna
2
2)12(310
nna
2
24310
nna
2
56
na
Untuk 2d diperoleh 2
56
na . Hal ini tidak memenuhi Definisi
2.16 bahwa label titiknya adalah bilangan bulat, karena nilai
2
56
na tidak mungkin menghasilkan nilai a bulat untuk setiap
3n . Jadi pada graf sikel )( nC dengan tambahan n anting )( 1nACn
tidak dapat dilakukan pelabelan total tak ajaib titik kuat dengan nilai
2d .
c. Untuk 3d dengan 3n
2
)12(310 dnna
2
3)12(310
nna
2
36310
nna
2
64
na
32 na
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
32
Untuk 3d diperoleh 32 na . Nilai a tersebut memenuhi batasan
bobot titik yaitu 22 na . Jadi, pada graf sikel )( nC dengan
tambahan 𝑛 anting )( 1nACn terdapat pelabelan total tak ajaib titik
kuat )3,32( n untuk 3n .
Nilai a yang memenuhi batasan bobot titik dan memenuhi definisi
pelabelan total tak ajaib titik hanya nilai a dengan 1d dan 3d , yaitu
24 na untuk 1d dan 32 na untuk 3d . Nilai a untuk 2d
tidak memenuhi karena didapatkan nilai yang tidak bulat, sehingga tidak
sesuai dengan Definisi 2.16 tentang pelabelan total tak ajaib titik. Oleh
karena itu, pasangan ),( da untuk pelabelan total tak-ajaib titik kuat dapat
dilakukan untuk pasangan )1,24( n dan )3,32( n .
C. Pelabelan Total Tak Ajaib Titik Kuat ),( da pada Graf 1nACn untuk
1d dan 3d
Terdapat dua macam pelabelan total tak ajaib titik kuat yang telah
didapatkan pada subbab sebelumnya dan akan dibahas pada bagian ini, yaitu:
pelabelan total tak ajaib titik kuat )1,24( n pada graf 1nACn dan pelabelan
total tak ajaib titik kuat )3,32( n pada graf 1nACn .
1. Pelabelan total tak ajaib titik kuat )1,24( n pada graf 1nACn
Berikut ini akan diperlihatkan pelabelan total tak ajaib titik kuat
pada beberapa graf 1nACn .
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
33
Gambar 4. 5 Pelabelan total tak ajaib titik kuat )1,14( pada 13 3AC
Pada gambar tersebut, dapat dilihat bahwa label untuk sisinya
}6,5,4,3,2,1{ dan label untuk titiknya }12,11,10,9,8,7{ . Bobot masing-
masing titiknya }19,18,17,16,15,14{ yaitu:
a. titik dengan label 12 adalah ,14212
b. titik dengan label 11 adalah ,15411
c. titik dengan label 10 adalah ,16610
d. titik dengan label 9 adalah ,175219
e. titik dengan label 8 adalah ,186318 dan
f. titik dengan label 7 adalah .195437
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
34
Gambar 4. 6 Pelabelan total tak ajaib titik kuat )1,18( pada 14 4AC
Pada gambar tersebut, dapat dilihat bahwa label untuk sisinya
}8,7,6,5,4,3,2,1{ dan label untuk titiknya }.16,15,14,13,12,11,10,9{ Bobot
masing-masing titiknya }25,24,23,22,21,20,19,18{ yaitu:
a. titik dengan label 16 adalah ,18216
b. titik dengan label 15 adalah ,19415
c. titik dengan label 14 adalah ,20614
d. titik dengan label 13 adalah ,21813
e. titik dengan label 12 adalah ,2272112
f. titik dengan label 11 adalah ,2383111
g. titik dengan label 10 adalah ,2465310 dan
h. titik dengan label 9 adalah .257549
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
35
Gambar 4. 7 Pelabelan total tak ajaib titik kuat )1,22( pada 15 5AC
Pada gambar tersebut, dapat dilihat bahwa label untuk sisinya
}10,9,8,7,6,5,4,3,2,1{ dan label untuk titiknya
}.20,19,18,17,16,15,14,13,12,11{ Bobot masing-masing titiknya
}31,30,29,28,27,26,25,24,23,22{ yaitu:
a. titik dengan label 20 adalah ,22220
b. titik dengan label 19 adalah ,23419
c. titik dengan label 18 adalah ,24618
d. titik dengan label 17 adalah ,25817
e. titik dengan label 16 adalah ,261016
f. titik dengan label 15 adalah ,2792115
g. titik dengan label 14 adalah ,28103114
h. titik dengan label 13 adalah ,2985313
i. titik dengan label 12 adalah ,3076512 dan
j. titik dengan label 11 adalah .3197411
Berdasarkan pada pelabelan tersebut, dapat diperoleh bahwa pada
graf 1nACn dapat dilakukan pelabelan total tak ajaib titik kuat ).1,24( n
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
36
Misalkan f merupakan fungsi pelabelan tersebut, maka konstruksi graf sikel
dengan tambahan n anting )1,24( n dengan label sisi sebagai berikut:
(Rumus 4.1)
nnni
ni
untuk
untuk
ni
inef i
2,...2,1
,...,2,1
2))1((2
2)1()12()(
dengan:
nnniuntuk
niuntuk
niuntuk
vv
vv
vv
e
nii
i
ii
i
2,...,2,1
1,...,2,1
)(
)(
)(
1
1
Sedangkan label titiknya sebagai berikut:
(Rumus 4.2)
nnniuntuk
niuntuk
iuntuk
nin
in
n
vf i
2,...2,1
,...,3,2
1
))1((4
)1(2
3
)(
Dengan menggunakan induksi matematis, akan ditunjukkan
bahwa konstruksi pelabelan graf sikel dengan tambahan n anting tersebut
berlaku untuk semua graf sikel dengan tambahan n anting dengan 3n .
Induksi Matematis
b. Akan ditunjukkan bahwa
nef i 2)(
untuk setiap i dengan 3n .
1) Untuk ni ,...,2,1
a) Langkah awal: Akan dibuktikan bahwa 1i benar
Pernyataan tersebut benar untuk 1i , karena
nnnef 2122)11()12()( 1
b) Langkah induksi: Jika ki benar maka akan dibuktikan
1 ki benar.
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
37
Misalkan pernyataan tersebut benar untuk ki dengan ,nk
yaitu:
nknknknef k 221222122)1()12()(
Untuk 1 ki , dengan nk , yaitu:
nknknef k 22122)1)1(()12()( 1
yang memperlihatkan bahwa pernyataan tersebut juga benar
untuk 1 ki , dengan nk .
2) Untuk nnni 2,...,2,1
a) Langkah awal: Akan dibuktikan bahwa 1 ni benar
Pernyataan tersebut benar untuk 1 ni , karena
nnnef 222)0(22))1()1((2)( 1
b) Langkah induksi: Jika ki benar maka akan dibuktikan
1 ki benar.
Misalkan pernyataan tersebut benar untuk ki dengan
nkn 21 , yaitu:
nnknknkef k 2222)1(22))1((2)(
Untuk 1 ki , dengan nkn 21 , yaitu:
nnknknkef k 22222)(22))1()1((2)( 1
yang memperlihatkan bahwa pernyataan tersebut juga benar
untuk 1 ki , dengan nk .
Dari 1) dan 2) terbukti bahwa
nef i 2)(
benar untuk setiap i dengan 3n ∎
c. Akan ditunjukkan bahwa
nvf i 2)(
untuk setiap i dengan 3n .
1) Untuk 1i
Jelas bahwa pernyataan tersebut benar untuk 1i , karena
nnvf 23)( 1
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
38
2) Untuk ni ,...,3,2
a) Langkah awal: Akan dibuktikan bahwa 2i benar
Pernyataan tersebut benar untuk 2i , karena
nnnvf 212)12(2)( 2
b) Langkah induksi: Jika ki benar maka akan dibuktikan
1 ki benar.
Misalkan pernyataan tersebut benar untuk ki dengan ,nk
yaitu:
nknknvf k 212)1(2)(
Untuk 1 ki , dengan nk , yaitu:
nknknvf k 22)1)1((2)( 1
yang memperlihatkan bahwa pernyataan tersebut juga benar
untuk 1 ki , dengan nk .
3) Untuk nnni 2,...,2,1
a) Langkah awal: Akan dibuktikan bahwa 1 ni benar
Pernyataan tersebut benar untuk 1 ni , karena
nnnnnvf n 24))1()1((4)( 1
b) Langkah induksi: Jika ki benar maka akan dibuktikan
1 ki benar.
Misalkan pernyataan tersebut benar untuk ki dengan
nkn 21 , yaitu:
nknnknnknvf k 21514))1((4)(
Untuk 1 ki , dengan nkn 21 , yaitu:
nknnknnknvf k 25114))1()1((4)( 1
yang memperlihatkan bahwa pernyataan tersebut juga benar
untuk 1 ki , dengan nk .
Dari 1), 2), dan 3) terbukti bahwa
nvf i 2)(
benar untuk setiap i dengan 3n ∎
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
39
Telah ditunjukkan bahwa konstruksi label untuk sisi tersebut
merupakan bilangan bulat positif {1,2,…, 2n} dan label untuk titik
}.4,...,22,12{ nnn Hal ini sesuai dengan Definisi 2.18 tentang pelabelan
kuat. Oleh karena itu, konstruksi pelabelan tersebut berlaku untuk setiap
.3n
Berikut akan diberikan contoh pelabelan total titik kuat pada graf
1nACn .
Contoh 4.1
a. Pelabelan totak tak ajaib titik kuat (14,1) pada graf 13 3AC
Graf pada Gambar 4.1 merupakan graf sikel dengan tambahan
n anting dengan 3n ( 13 3AC ) yang akan diberi label dengan bobot
titik terkecilnya 14 )14( a dan bedanya 1 )1( d menggunakan
konstruksi pelabelan graf yang telah didapatkan sebelumnya.
Label untuk sisi:
2)1()12()( inef i 3,2,1i
5052)11()1)3(2()( 1 ef
3252)12()1)3(2()( 2 ef
1452)13()1)3(2()( 3 ef
2))1((2)( nief i 6,5,4i
2202)44(22))13(4(2)( 4 ef
4222)45(22))13(5(2)( 5 ef
6242)46(22))13(6(2)( 6 ef
Label untuk titik:
nvf i 3)( 1i
9)3(3)( 1 vf
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
40
)1(2)( invf i 3,2i
716)12()3(2)( 2 vf
826)13()3(2)( 3 vf
))1((4)( ninvf i 6,5,4i
12012)44(12))13(4()3(4)( 4 vf
11112)45(12))13(5()3(4)( 5 vf
10212)46(12))13(6()3(4)( 6 vf
Dari perhitungan tersebut didapatlah graf berlabel seperti pada
gambar 4.5.
b. Pelabelan totak tak ajaib titik kuat (18,1) pada graf 14 4AC
Graf pada Gambar 4.2 merupakan graf sikel dengan tambahan
𝑛 anting dengan 4n ( 14 4AC ) yang akan diberi label dengan bobot
titik terkecilnya 18 )18( a dan bedanya 1 )1( d menggunakan
konstruksi pelabelan graf yang telah didapatkan sebelumnya.
Label untuk sisi:
2)1()12()( inef i 4,3,2,1i
7072)11()1)4(2()( 1 ef
5272)12()1)4(2()( 2 ef
3472)13()1)4(2()( 3 ef
1672)14()1)4(2()( 4 ef
2))1((2)( nief i 8,7,6,5i
2202)55(22))14(5(2)( 5 ef
4222)56(22))14(6(2)( 6 ef
6242)57(22))14(7(2)( 7 ef
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
41
8262)58(22))14(8(2)( 8 ef
Label untuk titik:
nvf i 3)( 1i
12)4(3)( 1 vf
)1(2)( invf i 4,3,2i
918)12()4(2)( 2 vf
1028)13()4(2)( 3 vf
1138)14()4(2)( 4 vf
))1((4)( ninvf i 8,7,6,5i
16016)55(16))14(5()4(4)( 5 vf
15116)56(16))14(6()4(4)( 6 vf
14216)57(16))14(7()4(4)( 7 vf
13316)58(16))14(8()4(4)( 8 vf
Dari perhitungan tersebut didapatlah graf berlabel seperti pada
gambar 4.6.
c. Pelabelan totak tak ajaib titik kuat (22,1) pada graf 15 5AC
Graf pada Gambar 4.3 merupakan graf sikel dengan tambahan
𝑛 anting dengan 5n ( 15 5AC ) yang akan diberi label dengan bobot
titik terkecilnya 22 )22( a dan bedanya 1 ( 1d ) menggunakan
konstruksi pelabelan graf yang telah didapatkan sebelumnya.
Label untuk sisi:
2)1()12()( inef i 5,4,3,2,1i
9092)11()1)5(2()( 1 ef
7292)12()1)5(2()( 2 ef
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
42
5492)13()1)5(2()( 3 ef
3692)14()1)5(2()( 4 ef
1892)15()1)5(2()( 5 ef
2))1((2)( nief i 10,9,8,7,6i
2202)66(22))15(6(2)( 6 ef
4222)67(22))15(7(2)( 7 ef
6242)68(22))15(8(2)( 8 ef
8262)69(22))15(9(2)( 9 ef
10282)610(22))15(10(2)( 10 ef
Label untuk titik:
nvf i 3)( 1i
15)5(3)( 1 vf
)1(2)( invf i 5,4,3,2i
11110)12()5(2)( 2 vf
12210)13()5(2)( 3 vf
13310)14()5(2)( 4 vf
14410)15()5(2)( 5 vf
))1((4)( ninvf i 10,9,8,7,6i
20020)66(20))15(6()5(4)( 6 vf
19120)67(20))15(7()5(4)( 7 vf
18220)68(20))15(8()5(4)( 8 vf
17320)69(20))15(9()5(4)( 9 vf
16420)610(20))15(10()5(4)( 10 vf
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
43
Dari perhitungan tersebut didapatlah graf berlabel seperti pada
Gambar 4.7.
2. Pelabelan total tak ajaib titik kuat )3,32( n pada graf .1nACn
Gambar 4. 8 Pelabelan total tak ajaib titik kuat (9,3) pada 13 3AC
Pada Gambar 4.8 tersebut, dapat dilihat bahwa label untuk sisinya
}6,5,4,3,2,1{ dan label untuk titiknya }12,11,10,9,8,7{ . Bobot masing-
masing titiknya }24,21,18,15,12,9{ yaitu:
a. titik dengan label 8 adalah ,918
b. titik dengan label 10 adalah ,12210
c. titik dengan label 12 adalah ,15312
d. titik dengan label 7 adalah ,186417
e. titik dengan label 9 adalah ,215439 dan
f. titik dengan label 11 adalah .2465211
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
44
Gambar 4. 9 Pelabelan total tak ajaib titik kuat (11,3) pada 14 4AC
Pada Gambar 4.9 tersebut, dapat dilihat bahwa label untuk sisinya
}8,7,6,5,4,3,2,1{ dan label untuk titiknya }.16,15,14,13,12,11,10,9{ Bobot
masing-masing titiknya }32,29,26,23,20,17,14,11{ yaitu:
a. titik dengan label 10 adalah ,11110
b. titik dengan label 12 adalah ,14212
c. titik dengan label 14 adalah ,17314
d. titik dengan label 16 adalah ,20416
e. titik dengan label 9 adalah ,238519
f. titik dengan label 11 adalah ,2665411
g. titik dengan label 13 adalah ,2976313 dan
h. titik dengan label 15 adalah .3287215
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
45
Gambar 4. 10 Pelabelan total tak ajaib titik kuat (13,3) pada 15 5AC
Pada Gambar 4.10 tersebut, dapat dilihat bahwa label untuk sisinya
}10,9,8,7,6,5,4,3,2,1{ dan label untuk titiknya
}.20,19,18,17,16,15,14,13,12,11{ Bobot masing-masing titiknya
}40,37,34,31,28,25,22,19,16,13{ yaitu:
a. titik dengan label 12 adalah ,13112
b. titik dengan label 14 adalah ,16214
c. titik dengan label 16 adalah ,19316
d. titik dengan label 18 adalah ,22418
e. titik dengan label 20 adalah ,25520
f. titik dengan label 11 adalah ,28106111
g. titik dengan label 13 adalah ,3176513
h. titik dengan label 15 adalah ,3487415
i. titik dengan label 17 adalah ,3798317 dan
j. titik dengan label 19 adalah .40109219
Berdasarkan pada pelabelan tersebut, dapat diperoleh bahwa pada
graf 1nACn dapat dilakukan pelabelan total tak ajaib titik kuat
).3,32( n Misalkan f merupakan fungsi pelabelan tersebut, maka
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
46
konstruksi graf sikel dengan tambahan n anting )3,32( n dengan label sisi
sebagai berikut:
(Rumus 4.3)
nnni
ni
untuk
untuk
ni
inef i
2,...2,1
,...,2,1)1(2)(
dengan:
nnniuntuk
niuntuk
niuntuk
vv
vv
vv
e
nii
i
ii
i
2,...,2,1
1,...,2,1
)(
)(
)(
1
1
Sedangkan label titiknya sebagai berikut:
(Rumus 4.4)
nnniuntuk
niuntuk
iuntuk
i
in
n
vf i
2,...2,1
,...,3,2
1
2
2)2()14(
12
)(
Dengan menggunakan induksi matematis, akan ditunjukkan
bahwa konstruksi pelabelan graf sikel dengan tambahan n anting tersebut
berlaku untuk semua graf sikel dengan tambahan n anting dengan 3n .
Induksi Matematis
a. Akan ditunjukkan bahwa
nef i 2)(
untuk setiap i dengan 3n .
1) Untuk ni ,...,2,1
a) Langkah awal: Akan dibuktikan bahwa 1i benar
Pernyataan tersebut benar untuk 1i , karena
nnnef 22)11(2)( 1
b) Langkah induksi: Jika ki benar maka akan dibuktikan
1 ki benar.
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
47
Misalkan pernyataan tersebut benar untuk ki dengan ,nk
yaitu:
nknknef k 212)1(2)(
Untuk 1 ki , dengan nk , yaitu:
nknknef k 22)1)1((2)( 1
yang memperlihatkan bahwa pernyataan tersebut juga benar
untuk 1 ki , dengan nk .
2) Untuk nnni 2,...,2,1
a) Langkah awal: Akan dibuktikan bahwa 1 ni benar
Pernyataan tersebut benar untuk 1 ni , karena
nnnef n 21)1()( 1
b) Langkah induksi: Jika ki benar maka akan dibuktikan
1 ki benar.
Misalkan pernyataan tersebut benar untuk ki dengan
nkn 21 , yaitu:
nnkef k 2)(
Untuk 1 ki , dengan nkn 21 , yaitu:
nnknkef k 21)1()( 1
yang memperlihatkan bahwa pernyataan tersebut juga benar
untuk 1 ki , dengan nk .
Dari 1) dan 2) terbukti bahwa
nef i 2)(
benar untuk setiap i dengan 3n ∎
b. Akan ditunjukkan bahwa
nvf i 2)(
untuk setiap i dengan 3n .
1) Untuk 1i
Jelas bahwa pernyataan tersebut benar untuk 1i , karena
nnvf 212)( 1
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
48
2) Untuk ni ,...,3,2
a) Langkah awal: Akan dibuktikan bahwa 2i benar
Pernyataan tersebut benar untuk 2i , karena
nnnvf 2142)22()14()( 2
b) Langkah induksi: Jika ki benar maka akan dibuktikan
1 ki benar.
Misalkan pernyataan tersebut benar untuk ki dengan nk
, yaitu:
nknknvf k 24242)2()14()(
Untuk 1 ki , dengan nk , yaitu:
nknknvf k 22242)2)1(()14()( 1
yang memperlihatkan bahwa pernyataan tersebut juga benar
untuk 1 ki , dengan nk .
3) Untuk nnni 2,...,2,1
a) Langkah awal: Akan dibuktikan bahwa 1 ni benar
Pernyataan tersebut benar untuk 1 ni , karena
nnnvf n 222)1(2)( 1
b) Langkah induksi: Jika ki benar maka akan dibuktikan
1 ki benar.
Misalkan pernyataan tersebut benar untuk ki dengan
nkn 21 , yaitu:
nkvf k 22)(
Untuk 1 ki , dengan nkn 21 , yaitu:
nkkvf k 222)1(2)( 1
yang memperlihatkan bahwa pernyataan tersebut juga benar
untuk 1 ki , dengan nk .
Dari 1), 2), dan 3) terbukti bahwa
nvf i 2)(
benar untuk setiap i dengan 3n ∎
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
49
Telah ditunjukkan bahwa konstruksi label untuk sisi tersebut
merupakan bilangan bulat positif {1,2,…, 2n} dan label untuk titik
}.4,...,22,12{ nnn Hal ini sesuai dengan Definisi 2.18 tentang pelabelan
kuat. Oleh karena itu, konstruksi pelabelan tersebut berlaku untuk setiap
.3n
Berikut akan diberikan contoh pelabelan total titik kuat pada graf
𝐶𝑛 + 𝑛𝐴1.
Contoh 4.2
a. Pelabelan totak tak ajaib titik kuat (9,3) pada graf 13 3AC
Graf pada Gambar 4.1 merupakan graf sikel dengan tambahan
n anting dengan 3n ( 13 3AC ) yang akan diberi label dengan bobot
titik terkecilnya 9 )9( a dan bedanya 3 )3( d menggunakan
konstruksi pelabelan graf yang telah didapatkan sebelumnya.
Label untuk sisi:
)1(2)( inef i 3,2,1i
606)11()3(2)( 1 ef
516)12()3(2)( 2 ef
426)13()3(2)( 3 ef
nief i )( 6,5,4i
134)( 4 ef
235)( 5 ef
336)( 6 ef
Label untuk titik:
12)( nvf i 1i
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
50
71)3(2)( 1 vf
2)2()14()( invf i 3,2i
110112)0()112(2)22()1)3(4()( 2 vf
92112)1()112(2)23()1)3(4()( 3 vf
ivf i 2)( 6,5,4i
8)4(2)( 4 vf
10)5(2)( 5 vf
12)6(2)( 6 vf
Dari perhitungan tersebut didapatlah graf berlabel seperti pada
Gambar 4.8.
b. Pelabelan totak tak ajaib titik kuat (10,3) pada graf 14 4AC
Graf pada Gambar 4.2 merupakan graf sikel dengan tambahan
𝑛 anting dengan 4n ( 14 4AC ) yang akan diberi label dengan bobot
titik terkecilnya 10 )10( a dan bedanya 3 )3( d menggunakan
konstruksi pelabelan graf yang telah didapatkan sebelumnya.
Label untuk sisi:
)1(2)( inef i 4,3,2,1i
808)11()4(2)( 1 ef
718)12()4(2)( 2 ef
628)13()4(2)( 3 ef
538)14()4(2)( 4 ef
nief i )( 8,7,6,5i
145)( 5 ef
246)( 6 ef
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
51
347)( 7 ef
448)( 8 ef
Label untuk titik:
12)( nvf i 1i
91)4(2)( 1 vf
2)2()14()( invf i 4,3,2i
150152)0()116(2)22()1)4(4()( 2 vf
132152)1()116(2)23()1)4(4()( 3 vf
114152)2()116(2)24()1)4(4()( 4 vf
ivf i 2)( 8,7,6,5i
10)5(2)( 5 vf
12)6(2)( 6 vf
14)7(2)( 7 vf
16)8(2)( 8 vf
Dari perhitungan tersebut didapatlah graf berlabel seperti pada
Gambar 4.9.
c. Pelabelan totak tak ajaib titik kuat (13,3) pada graf 15 5AC
Graf pada Gambar 4.3 merupakan graf sikel dengan tambahan
𝑛 anting dengan 5n ( 15 5AC ) yang akan diberi label dengan bobot
titik terkecilnya 13 )13( a dan bedanya 3 )3( d menggunakan
konstruksi pelabelan graf yang telah didapatkan sebelumnya.
Label untuk sisi:
)1(2)( inef i 5,4,3,2,1i
10010)11()5(2)( 1 ef
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
52
9110)12()5(2)( 2 ef
8210)13()5(2)( 3 ef
7310)14()5(2)( 4 ef
6410)15()5(2)( 5 ef
nief i )( 10,9,8,7,6i
156)( 6 ef
257)( 7 ef
358)( 8 ef
459)( 9 ef
5510)( 10 ef
Label untuk titik:
12)( nvf i 1i
111)5(2)( 1 vf
2)2()14()( invf i 5,4,3,2i
190192)0()120(2)22()1)5(4()( 2 vf
172192)1()120(2)23()1)5(4()( 3 vf
154192)2()120(2)24()1)5(4()( 4 vf
136192)3()120(2)25()1)5(4()( 4 vf
ivf i 2)( 10,9,8,7,6i
12)6(2)( 6 vf
14)7(2)( 7 vf
16)8(2)( 8 vf
18)9(2)( 9 vf
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
53
20)10(2)( 10 vf
Dari perhitungan tersebut didapatlah graf berlabel seperti pada
Gambar 4.10.
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
54
BAB V
PENUTUP
A. Kesimpulan
Berdasarkan hasil penelitian yang telah dilakukan, dapat disimpulkan bahwa:
1. Pelabelan total tak ajaib titik kuat ),( da dapat dilakukan pada graf sikel
)( nC dengan tambahan n anting )( 1nACn .
2. Pelabelan total tak ajaib titik kuat ),( da pada graf sikel )( nC dengan
tambahan n anting )( 1nACn untuk 3n dapat dilakukan dengan nilai
1d dan 3d .
a. Untuk 1d , diperoleh nilai awal bobot titik 24 na dan rumus
pelabelannya yaitu:
Label sisi:
nnni
ni
untuk
untuk
ni
inef i
2,...2,1
,...,2,1
2))1((2
2)1()12()(
dengan:
nnniuntuk
niuntuk
niuntuk
vv
vv
vv
e
nii
i
ii
i
2,...,2,1
1,...,2,1
)(
)(
)(
1
1
Label titik:
nnniuntuk
niuntuk
iuntuk
nin
in
n
vf i
2,...2,1
,...,3,2
1
))1((4
)1(2
3
)(
b. Untuk 3d , diperoleh nilai awal bobot titik 32 na dan rumus
pelabelannya yaitu:
Label sisi:
nnni
ni
untuk
untuk
ni
inef i
2,...2,1
,...,2,1)1(2)(
dengan:
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
55
nnniuntuk
niuntuk
niuntuk
vv
vv
vv
e
nii
i
ii
i
2,...,2,1
1,...,2,1
)(
)(
)(
1
1
Label titik:
nnniuntuk
niuntuk
iuntuk
i
in
n
vf i
2,...2,1
,...,3,2
1
2
2)2()14(
12
)(
B. Saran
Pembaca yang tertarik dapat melanjutkan dengan mencari keberlakuan
pelabelan total tak-ajaib sisi pada graf 1nACn atau pelabelan total tak-ajaib
titik pada graf lainnya yang belum diketahui keberlakuan pelabelannya. Selain
itu, penelitian ini juga dapat dikembangkan dengan pembuatan program,
misalnya Program Turbo Pascal maupun yang lainnya.
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
56
DAFTAR PUSTAKA
Aman, Rido. 2013. Pelabelan Total (a,d)-Titik Antiajaib Super Pada Graf Petersen
P(n,2) dengan N Ganjil, N ≥ 5. Jurnal Matematika UNAND. Vol 2 No. 1 P.
61-64.
Andriyani, Rini. 2014. Pelabelan Total Tak Ajaib Titik pada Graf Sikel dengan
Tambahan Dua Anting. Skripsi. Universitas Sanata dharma.
Baca, M., dkk. 2003. Vertex-Antimagic Total Labelings of Graphs. Discussiones
Mathematicae. Graph Theory 23 P. 67-83.
Gallian, Joseph A.. 2018. A Dynamic Survey of Graph Labeling. The electronic
Journal of Combinatorics. #DS6.
Johnsonbaugh, Richard. 2009. Discrete Mathematics (Seventh Edition). United
States of America: Pearson Practice Hall.
Kotzig, Anton & Alexander Rosa. 1970. Magic Valuations of Finite Graphs.
Canad. Math. Bull. Vol. 13 (4) P. 451-461.
Kristianna, Ayu. 2013. Pelabelan Total Ajaib Sisi Kuat pada Graf Sikel dengan
Tambahan 𝑛 Anting untuk 𝑛 ≥ 3 dan 𝑛 Ganjil. Skripsi. Yogyakarta:
Universitas Sanata Dharma.
Munir, Rinaldi. 2001. Matematika Diskrit. Bandung: Penerbit Informatika.
Prasetyo, D. A. B.. 2012. Vertex Antimagic Total Labeling pada Graph Multicycle.
Pythagoras Vol 7, No 1 P. 57-64.
---------------------. 2018. Pelabelan Total Tak-Ajaib Titik ),( da pada Graf Sikel
dengan Tambahan Dua Anting )2( 1ACp untuk 𝑑 = 3 dan 𝑑 = 4. Prosiding
Sendika. Vol. 4 No. 1 P. 190-195.
Prasetyo, D. A. B.. 2018. Pelabelan Total Tak-Ajaib Titik ),( da pada Graf Sikel
dengan Tambahan Dua Anting )2( 1ACp untuk 𝑑 = 3 dan 𝑑 = 4. Prosiding
Sendika. Vol. 4 No. 1 P. 190-195.
Rosen, Kenneth H.. 2019. Discrete Mathematics and Its Applications (Eighth
Edition). New York: McGraw-Hill Education.
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
57
Sanjaya, Ryan. 2013. Pelabelan Total Tak Ajaib Sisi Kuat pada Graf Multisikel
)( pmC . Yogyakarta: Universitas Sanata Dharma.
Septian, C. W.. 2012. Pelabelan Total Ajaib Titik pada Graf Sikel dengan
Tambahan Satu Anting. Skripsi. Yogyakarta: Universitas Sanata Dharma.
Siang, Jong Jek. 2009. Matematika Diskrit dan Aplikasinya pada Ilmu Komputer.
Yogyakarta: Penerbit Andi.
Wallis, W.D.. 2001. Magic Graph. Boston: Birkhauser
Yuliyanto, B. D.. 2012. Pelabelan Total Ajaib Sisi Kuat pada Graf Sikel dengan
Tambahan Dua Anting. Skripsi. Yogyakarta: Universitas Sanata Dharma.
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI