NILAI KETAKTERATURAN SISI TOTAL PADA
GRAF HASIL KALI COMB DAN , SERTA
SUBDIVISI PADA HASIL KALI COMB DAN
Skripsi
Disusun sebagai salah satu syarat
Untuk memperoleh gelar Sarjana Sains
Program Studi Matematika
Oleh
Kholifa Septia Ulfa
4111414023
JURUSAN MATEMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS NEGERI SEMARANG
2019
ii
iii
iv
MOTTO DAN PERSEMBAHAN
MOTTO
“Surpass your limit. Right here, right now.” (Yami Sukehiro)
PERSEMBAHAN
Dengan penuh rasa syukur kepada Allah SWT, skripsi ini saya
persembahkan untuk:
1. Orang tua saya yang telah memberikan doa dan dukungan
2. Adik-adik saya yang selalu memberikan semangat, motivasi
dan dukungan.
3. Rekan jurusan Matematika Angkatan 2014 yang selalu
memberikan semangat.
4. Almamaterku tercinta.
v
PRAKATA
Puji syukur kehadirat Allah SWT yang telah melimpahkan nikmat serta hidayah-
Nya dan tak lupa sholawat serta salam senantiasa tercurah kepada Rasulullah
Muhammad SAW, sehingga penulis dapt menyelesaikan skripsi yang berjudul “Nilai
Ketakteraturan Sisi Total pada Graf Hasil Kali Comb dan , serta Subdivisi pada
Hasil Kali Comb dan ”. Skripsi ini disusun sebagai salah satu syarat untuk
memperoleh gelar Sarjana Program Studi Matematika Universitas Negeri Semarang.
Penyusun skripsi ini tidak lepas dari bimbingan serta dukungan dari berbagai
pihak, oleh sebab itu penulis ingin menyempaikan rasa terima kasih kepada:
1. Rektor Universitas Negeri Semerang yng telah memberikan kesempatan pada
peneliti untuk menuntut ilmu di Universitas Negeri Semarang.
2. Dekan FMIPA Universitas Negeri Semarang yang telah memberikan izin untuk
melaksanakan penelitian.
3. Ketua Jurusan Matematika yang telah memberikan izin untuk melaksanakan
penelitian.
4. Dr. Isnaini Rosyida, S.Si, M.Si selaku dosen pembimbing yang telah tulus dan
sabar membimbing dan memberikan pengarahan kepada penulis dalam
penyusunan skripsi ini.
5. Dr. Mulyono, M.Si. dan Dr. Tri Sri Noor Asih, S.Si., M.Si. selaku dosen penguji
yang sabar memberi pengarahan.
6. Bapak/Ibu dosen Jurusan Matematika atas seluruh ilmu yang telah diberikan
sehingga penulis dapat menyusun skripsi ini.
7. Teman-teman Matematika angkatan 2014 yang telah memberikan masukan-
masukan dalam menyusun skripsi ini.
8. Semua pihak yang telah membantu dalam penyusunan skripsi ini yang tidak
dapat disebutkan satu-persatu.
vi
Semoga skripsi ini senantiasa dapat memberikan manfaat kepada enulis maupun
kepada para pembaca, serta dapat memberikan manfaat pula bagi perkembangan
dunia pendidikan.
Semarang, Juli 2019
Penulis
vii
ABSTRAK
Ulfa, Kholifa Septia. 2019. Nilai Ketakteraturan Sisi Total Pada Graf Hasil Kali
Comb dan , serta Subdivisi pada Hasil Kali Comb dan . Skripsi, Program
Studi Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas
Negeri Semarang, Pembimbing: Dr. Isnaini Rosyida, S.Si, M.Si.
Kata Kunci: Pelabelan tak teratur sisi total, hasil kali comb, nilai ketakteraturan sisi
total, graf lintasan, graf cycle.
Misalkan adalah sebuah graf dan adalah bilangan bulat positif.
Pelabelan total pada graf G adalah suatu pemetaan { }
Bobot titik dinyatakan ∑ dan bobot sisi dinyatakan
dengan . Suatu pelabelan total dikatakan tak
teratur sisi total, jika bobot setiap sisi berbeda. Nilai ketakteraturan sisi total dari graf
dinotasikan dengan tes adalah nilai minimum atau label terbesar minimum
yang digunakan untuk melabeli graf dengan pelabelan tak teratur sisi total. Pada
penelitian ini diselidiki nilai ketakteraturan sisi total pada graf hasil kali comb
dan yang dinotasikan dengan serta subdivisi pada hasil kali comb dan
yang dinotasikan dengan . Hasil dari penelitian ini adalah tes(
⌈
⌉ dan tes ⌈ ⌉
viii
ABSTRACT
Ulfa, Kholifa Septia. 2019. On Total Edge Irregularity Strength of Comb Product
Graph and and Subdivision of Comb Product Graph and . Final Project,
Department of Mathematics, Faculty of Mathematics and Natural Sciences,
Universitas Negeri Semarang, Advisor: Dr. Isnaini Rosyida, S.Si, M.Si.
Keywords : Total edge irregular labelling, comb product, total edge irregularity
strength, path graph and cycle graph.
Let be a graph and be a positive integer. Total labelling on graph G
is a mapping { } The weight of vertex is represented by
∑ and the weight of edge is represented by
. A total labelling of is called edge irregular
total labelling, if the weight of every two distinct edges are different. The total
edge irregularity strength of , denoted by tes is the minimum positive integer
for which has a total edge irregular labelling . This research is investigated on
the total edge irregularity strength of the comb product graph and
and subdivision of comb product graph and . The result of this
research are tes( ⌈
⌉ and tes ⌈ ⌉
ix
DAFTAR ISI
PERNYATAAN................................................................................................................ii
PENGESAHAN...............................................................................................................iii
MOTTO DAN PERSEMBAHAN...................................................................................iv
PRAKATA........................................................................................................................v
ABSTRAK......................................................................................................................vii
ABSTRACT...................................................................................................................viii
DAFTAR ISI....................................................................................................................ix
DAFTAR GAMBAR........................................................................................................x
DAFTAR LAMPIRAN....................................................................................................xi
BAB 1 PENDAHULUAN.................................................................................................1
1.1 Latar Belakang Masalah..............................................................................................1
1.2 Rumusan Masalah........................................................................................................4
1.3 Batasan Masalah..........................................................................................................4
1.4 Tujuan Penelitian.........................................................................................................5
1.5 Manfaat Penelitian.......................................................................................................5
1.6 Sistematika Penyusunan Skripsi..................................................................................5
BAB 2 TINJAUAN PUSTAKA........................................................................................8
2.1 Konsep Dasar Graf......................................................................................................8
2.2 Jenis-Jenis Graf..........................................................................................................11
2.3 Pelabelan Graf...........................................................................................................20
BAB 3 METODE PENELITIAN....................................................................................29
BAB 4 HASIL PENELITIAN DAN PEMBAHASAN...................................................31
4.1 Graf Hasil Kali Comb dan ( )..............................................................31
4.2 Subdivisi pada Graf Hasil Kali Comb dan ( ...............................33
x
BAB 5 PENUTUP...........................................................................................................36
5.1 Simpulan....................................................................................................................36
5.2 Saran..........................................................................................................................36
DAFTAR PUSTAKA......................................................................................................37
LAMPIRAN....................................................................................................................40
xi
DAFTAR GAMBAR
Gambar Halaman
2.1. Graf G.........................................................................................................................8
2.2. Graf F........................................................................................................................10
2.3. Graf H.......................................................................................................................10
2.4. (a) Graf sederhana; (b) Bukan graf sederhana..........................................................11
2.5. Graf kosong .........................................................................................................12
2.6. Graf berarah..............................................................................................................13
2.7 Graf dan komplemennya .................................................................................13
2.8. (a) dan (b) graf terhubung; (c) bukan graf terhubung...............................................14
2.9. Graf lengkap.............................................................................................................15
2.10. Graf path.................................................................................................................15
2.11. Graf cycle................................................................................................................15
2.12. Graf berbobot..........................................................................................................16
2.13. Graf subdivisi.........................................................................................................16
2.14. (a) Graf ; (b) Graf ; (c) Graf ..............................................................17
2.15. (a) Graf ; (b) Graf ; (c) Graf ..............................................................18
2.16. (a) Graf ; (b) Graf ; (c) Graf ..............................................................19
2.17. (a) Graf ; (b) Graf ; (c) Graf ...................................................20
2.18. (1) pelabelan titik (2) pelabelan sisi (3) pelabelan total.........................................21
2.19. Pelabelan-3 total tak teratur sisi pada ................................................................22
2.20. Pelabelan total graf path ....................................................................................24
2.21. Pelabelan total graf path ....................................................................................25
2.22. Pelabelan total graf path ................................................................................25
2.23. Pelabelan total graf dan .........................................................................26
xii
2.24. Pelabelan total graf cycle ...................................................................................26
2.25. Pelabelan total graf cycle ...............................................................................27
3.1. Desain Penelitian......................................................................................................30
xiii
DAFTAR LAMPIRAN
Lampiran Halaman
1. Contoh pelabelan-11 total tak teratur sisi dari graf .......................................40
2. Contoh pelabelan-15 total tak teratur sisi graf ........................................41
3. Pelabelan pada graf hasil kali comb dan ........................................42
4. Pelabelan dari subdivisi pada graf hasil kali comb dan ( ) ............45
1
BAB 1
PENDAHULUAN
1.1. Latar Belakang
Teori graf sebagai salah satu cabang Matematika yang sudah ada sejak lebih
dari dua ratus tahun yang lalu pada tahun 1736, oleh matematikawan terkenal
asal Swiss, Euler. Teori graf mengalami perkembangan yang sangat pesat
dengan aplikasinya yang sangat luas dalam berbagai bidang ilmu seperti: Ilmu
Komputer, Teknik, Sains, bahkan Bisnis dan Ilmu Sosial. (Budayasa, 2007)
Teori graf merupakan salah satu cabang aplikasi matematika yang banyak
dipakai dalam kehidupan sehari-hari. Graf adalah bentuk representasi dari
beberapa objek beserta hubungannya, dengan memisalkan objek-objek tersebut
sebagai suatu titik, sedangkan hubungan antara objek dinyatakan dengan sisi.
Teori graf dapat digunakan untuk menggambarkan suatu keadaan, sehingga
dapat mengetahui pola dan memperhitungkan hal penting yang dibutuhkan untuk
menyelesaikan masalah.
Sampai saat ini berbagai macam topik penelitian terkait graf telah banyak
ditemukan. Salah satu dari topik tersebut adalah pelabelan. Ada berbagai macam
jenis pelabelan yang telah diperkenalkan, yaitu pelabelan titik, pelabelan sisi dan
pelabelan total. Jika domain dari fungsi (pemetaan) adalah titik, maka pelabelan
disebut pelabelan titik (vertex labeling), jika domainnya adalah sisi maka disebut
pelabelan sisi (edge labeling), jika domainnya titik dan sisi maka disebut
pelabelan total (total labeling).
2
Pelabelan tak teratur sisi total (total edge irregularity strength), yaitu
pemberian label bilangan bulat positif (label ini boleh dipakai berulang) pada
setiap elemen suatu graf dengan memperhatikan bobot sisi (jumlah label dari
sisi dan 2 titik yang bertetangga) yang harus berbeda. Wallis (2001) menyatakan
bahwa bobot (weight) dari elemen graf adalah jumlah dari semua label yang
berhubungan dengan elemen graf tersebut. Nilai ketakteraturan sisi total (total
edge irregularity strength) graf yang dinotasikan dengan tes adalah
minimum label terbesar yang digunakan untuk melabeli titik dan sisi graf
dengan pelabelan tak teratur sisi total (Baca, dkk, 2003).
Misalkan pelabelan { } , bobot sebuah titik dengan
pelabelan dari elemen graf adalah
∑
dan bobot sebuah sisi dengan pelabelan adalah
.
Pelabelan tak teratur total diperkenalkan oleh Martin Baca, dkk. (2003).
Mereka memperkenalkan dua jenis pelabelan tak teratur total, yaitu pelabelan
tak teratur titik total dan pelabelan tak teratur sisi total. Baca, dkk. (2003)
menyatakan bahwa pelabelan-k tak teratur sisi total pada graf dengan
himpunan titik tak kosong dan himpunan sisi adalah pelabelan
{ } sedemikian sehingga untuk setiap dua sisi yang berbeda
dan berlaku
.
3
Pelabelan tak teratur sisi total tampak mudah diterapkan pada berbagai
macam graf karena label yang diberikan boleh berulang meski bobotnya harus
berbeda. Namun, permasalahan yang perlu dikaji dalam pelabelan tak teratur sisi
total ini, yaitu bagaimana melabeli graf tersebut sedemikian hingga nilai
bilangan bulat positif terbesar yang dijadikan label adalah seminimum mungkin.
Nilai minimum dari bilangan bulat positif terbesar ini dinamakan nilai
ketakteraturan sisi total (total edge irregularity strength) dan dinotasikan dengan
tes .
Hingga kini dikenal beberapa operasi pada graf, diantaranya operasi join,
gabungan, kartesian, korona dan comb. Dengan mengoperasikan dua/lebih graf,
akan dihasilkan graf yang baru. Misalkan dan dua graf terhubung, titik
dari . Hasil kali comb antara graf dan , dinotasikan dengan adalah
graf yang didapat dengan mengambil satu kopian dari dan kopian dari
dan melekatkan kopian ke- dari pada titik ke titik ke- dari . Dari
definisi hasil kali comb, { } dan
dengan dan atau dan
(Saputro, S., dkk, 2013)
Pelabelan tak teratur sisi total sudah banyak diteliti oleh para ilmuwan
sebelumnya diantaranya Marzuki dkk. (2013) meneliti tentang nilai
ketakteraturan total graf sikel dan graf path. Indriati dkk. (2015) meneliti tentang
nilai ketakteraturan sisi total graf web dan graf-graf terkait. Ivanco dan Jendrol
(2006) meneliti tentang nilai ketakteraturan sisi total graf pohon. Rosyida (2019)
meneliti tentang nilai ketakteraturan sisi total dari beberapa graf rantai kaktus
4
dengan titik pendan. Corazon dan Riyanti (2016) meneliti tentang nilai
ketakteraturan titik total pada graf hasil kali comb dan dengan bilangan
ganjil. Corazon dan Febrinanda (2017) meneliti tentang nilai ketakteraturan total
dari graf hasil kali comb dan . Siddiqui dan Afzal (2011) meneliti tentang
nilai ketakteraturan titik total pada subdivisi graf bintang Tarawneh dkk.
(2016) meneliti tentang nilai ketakteraturan sisi total dari graf hasil kali corona
dengan paths. Jayanthi (2016) meneliti tentang nilai ketakteraturan sisi total dari
graf gabungan disjoin (disjoint union) pada graf roda rangkap (double wheel).
Siddiqui dkk. (2013) meneliti tentang nilai ketakteraturan sisi total dari graf
gabungan disjoin (disjoint union) pada graf helm (helm graphs).
Penelitian ini akan fokus pada nilai tes graf hasil kali comb dari dan ,
serta subdivisi pada hasil kali comb dan .
1.2. Rumusan Masalah
Berdasarkan latar belakang yang telah dipaparkan, diperoleh beberapa
rumusan masalah sebagai berikut:
1. Bagaimana nilai ketakteraturan sisi total dari graf hasil kali comb dan
?
2. Bagaimana nilai ketakteraturan sisi total dari graf subdivisi pada hasil kali
comb dan ?
1.3. Batasan Masalah
Berdasarkan rumusan masalah tersebut, maka batasan masalah pada
penelitian ini sebagai berikut:
1. Graf berhingga, sederhana dan tidak berarah.
5
2. Pelabelannya adalah pelabelan- tak teratur sisi total.
1.4. Tujuan Penelitian
Tujuan dari penelitian ini sebagai berikut:
1. Dapat menentukan nilai ketakteraturan sisi total dari graf hasil kali comb
dan .
2. Dapat menentukan nilai ketakteraturan sisi total dari graf subdivisi pada
hasil kali comb dan .
1.5. Manfaat Penelitian
Adapun manfaat dari penelitian ini sebagai berikut:
1. Memperdalam pengetahuan tentang pelabelan, khususnya pelabelan- tak
teratur sisi total pada graf hasil kali comb dan serta subdivisi dari
hasil kali comb dan .
2. Mengetahui penentuan nilai ketakteraturan sisi total dari suatu graf,
khususnya graf hasil kali comb dan serta subdivisi dari hasil kali
comb dan .
1.6. Sistematika Penyusunan Skripsi
Secara garis besar penulisan skripsi ini dibagi menjadi tiga bagian, yaitu
bagian awal, bagian pokok dan bagian akhir dengan penjelasan msing-masing
bagian berikut.
1. Bagian Awal
Bagian awal skripsi meliputi halaman judul, halaman kosong,
pernyataan keaslian tulisan, halaman pengesahan, motto dan
6
persembahan, kata pengantar, abstrak, daftar isi, daftar tabel, daftar
gambar dan daftar lampiran.
2. Bagian Pokok
Secara garis besar bagian pokok skripsi terdiri atas lima bab, yaitu:
BAB 1 PENDAHULUAN
Bab ini memuat latar belakang, rumusan masalah, batasan
masalah, tujuan penelitian, manfaat penelitian, dan
sistematika penyusunan skripsi.
BAB 2 TINJAUAN PUSTAKA
Bab ini memuat konsep-konsep yang dijadikan landasan
teori yang mendasari pemecahan masalah dalam penelitian
ini seperti graf, pelabelan graf, .
BAB 3 METODE PENELITIAN
Bab ini berisi tentang metode-metode yang digunakan
dalam penulisan skripsi.
BAB 4 HASIL PENELITIAN DAN PEMBAHASAN
Bab ini mengemukakan hasil penelitian dan pembahasan
terkait pelabelan- total tak teratur sisi dan nilai
ketakteraturan sisi total pada graf dovetail.
BAB 5 PENUTUP
Bab ini mengemukakan simpulan yang diperoleh dari hasil
telaah dan saran yang berkaitan dengan simpulan.
3. Bagian akhir
7
Bagian akhir berisi daftar pustaka dan lampiran yang mendukung
penulisan skripsi.
8
BAB 2
TINJAUAN PUSTAKA
2.1 Konsep Dasar Graf
Graf didefinisikan sebagai pasangan himpunan ditulis
dengan notasi yang dalam hal ini adalah himpunan tidak
kosong dari titik-titik ( atau ) dan adalah himpunan sisi
boleh kosong (edges atau arcs) yang menghubungkan sepasang titik.
(Munir, 2005)
Jumlah titik dari graf disebut order yang dinotasikan dengan ,
sedangkan jumlah sisi dari graf disebut size yang dinotasikan dengan .
Gambar 2.1 menunjukkan sebuah graf dengan himpunan titik dan
himpunan sisi yaitu { } dan
{ }. Dengan demikian order graf adalah
dan size graf adalah .
v1 v2
v3v4
Gambar 2.1. Graf
9
Dua titik dan dikatakan adjacent jika . Jika
, maka dan masing-masing dikatakan incident dengan
(Chartrand, 1986).
Pada Gambar 2.1. dapat dilihat bahwa titik adjacent dengan titik
dan , tetapi tidak adjacent dengan titik . Pada Gambar 2.1 dapat dilihat
juga bahwa sisi incident dengan titik dan , sisi incident
dengan titik dan , tetapi sisi tidak incident dengan titik
maupun titik .
Misal adalah sebuah graf. Sebuah jalan (walk) di adalah sebuah
barisan berhingga (tak kosong) = ( ) yang suku-
sukunya bergantian titik dan sisi, sedemikian hingga dan adalah
titik-titik akhir sisi untuk . Hal tersebut dikatakan sebuah jalan
dari titik ke titik atau jalan-( . Jika semua sisi dalam jalan
berbeda, maka disebut sebuah jejak (trail). (Budayasa, 2007:6)
Jika semua titik dalam jalan
berbeda, maka disebut lintasan (path).
(Budayasa, 2007)
Cycle adalah sebuah jejak tertutup (closed trail) yang titik awal dan
semua titik internalnya berbeda. Banyaknya sisi dalam suatu cycle disebut
panjang dari cycle tersebut. (Budayasa, 2007)
10
v1 e1 v2
e2
e3
v3e4v4
e5v5
e7
e8
e9
v6
e6
Gambar 2.2. Graf F
Walk :
Trail :
Path :
Cycle :
Sebuah loop merupakan sebuah sisi yang terhubung pada suatu titik
yang sama. Sisi rangkap adalah dua sisi atau lebih yang menghubungkan
pasangan titik yang sama.
v1 v2
v4
v3
e7
e2
e3
e1
e4
e5
e6
Gambar 2.3. Graf H
Pada Gambar 2.3 terlihat jelas bahwa sisi dan merupakan sisi
rangkap, karena sisi dan sisi menghubungkan pasangan titik yang
11
sama yaitu titik dan , sedangkan sisi merupakan loop karena sisi
terhubung dengan titik .
2.2 Jenis-jenis Graf
Menurut Johnsonbaugh (2001) suatu graf tanpa loop dan sisi rangkap
(parallel edge) disebut graf sederhana (simple graph). Graf pada Gambar
2.4 merupakan graf sederhana karena tidak memuat sisi maupun sisi
rangkap.
v4
v3
v2
v1
e4
e6v3
e7
e1
v4
v2
v1
e3
e2
e5
(a) (b)
Gambar 2.4. (a) Graf sederhana ; (b) Bukan graf sederhana
Graf pada Gambar 2.4 (a) merupakan graf sederhana, sedangkan
graf pada Gambar 2.4 (b) bukan graf sederhana karena mengandung loop
dan sisi rangkap. Sisi dan merupakan sisi rangkap karena
menghubungkan dua titik yang sama yaitu dan . Sedangkan sisi dan
merupakan loop karena masing-masing terhubung pada titik dan
Graf yang himpunan sisinya merupakan himpunan kosong disebut
sebagai graf kosong dan ditulis dengan yang dalam hal ini adalah
12
jumlah titik. Gambar 2.5 merupakan graf kosong dengan lima titik,
dinotasikan dengan . (Munir, 2005)
1
2
3
54
Gambar 2.5. Graf kosong
Suatu graf dikatakan berhingga jika banyaknya titik maupun sisi
pada graf jumlahnya berhingga. (Bondy and Murty, 1976).
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 adalah sisi yang sama. (Munir, 2005)
Graf berarah adalah himpunan berhingga tak kosong dari objek
yang disebut titik-titik dan suatu himpunan (bisa kosong) dari pasangan
berurutan dari titik-titik di graf yang disebut busur atau sisi berarah.
Himpunan titik dari graf dinotasikan dengan dan himpunan busur
dinotasikan dengan , Suatu graf berarah dengan { }
dan { } diilustrasikan pada Gambar 2.6, arah dari setiap
sisi digambarkan dengan tanda panah. (Chartrand, 1986)
13
u v
w
Gambar 2.6 Graf berarah
Komplemen graf yang dinotasikan dengan , adalah graf dengan
dan merupakan sisi dari jika dan hanya jika sisi tersebut
bukan sisi dari (Chartrand dan Oellermann, 1993). Gambar 2.7.
merupakan contoh graf dan .
K5 K5
Gambar 2.7 Graf dan komplemennya
Graf tak berarah disebut graf terhubung (connected graph) jika
untuk setiap pasang titik dan di dalam himpunan terdapat lintasan dari
ke (yang juga harus berarti ada lintasan dari ke ). Jika tidak, maka
disebut graf tak-terhubung (disconnected graph) (Munir, 2005:371)
14
a b
d
e
f
g
(a) (b)
(c)
p
u
q r
st
v w
xy
G1 G2
G3
c
Gambar 2.8. (a) dan (b) graf terhubung; (c) bukan graf terhubung
Graf pada Gambar 2.8. (c) ini terdiri dari himpunan titik
{ } dan himpunan sisi { }. Graf
ini merupakan graf tak terhubung karena tidak terdapat jalan dari ke ,
yang dihubungkan oleh sisi, sehingga terpisah menjadi dua komponen.
Bagian-bagian dari susunan graf yang menyebabkan grafnya tidak
terhubung maka bagian tersebut dinamakan komponen graf.
Graf lengkap (complete graph) dengan titik yang dinotasikan
dengan , adalah graf sederhana yang setiap titiknya adjacent (Fletcher et
al., 1991).
Gambar 2.9. merupakan contoh lima graf lengkap. Terlihat bahwa
setiap titik pada masing-masing graf tersebut adjacent.
15
K1 K2 K3 K4 K5
Gambar 2.9. Graf lengkap
Graf lintasan (path graph) yang dinotasikan dengan merupakan
graf terhubung sederhana yang membentuk lintasan yang terdiri dari titik
dan sisi dengan . Kedua titik ujung pada graf ini merupakan
pendant, yaitu titik dengan derajat sama dengan satu, sedangkan titik yang
lain berderajat dua (Umilasari, 2015).
v1 v2
v1 v2 v3
vm-1 vmv1 v2
P2:
P3:
Pm:
Gambar 2.10. Graf path
Graf cycle adalah graf terhubung sederhana yang memiliki titik
dengan setiap titiknya berderajat dua. Graf cycle dinotasikan dengan
dengan (Umilasari, 2015).
C3 C4 C5 C6
Gambar 2.11. Graf cycle
16
Graf berbobot adalah graf yang setiap sisinya diberi sebuah bilangan
yang disebut bobot (Boundy and Murty, 1976).
v1
v2
v3
v4
v5v6
2 3
5
8 1 7
9
4
Gambar 2.12. Graf berbobot
Gambar tersebut menunjukkan bahwa bobot masing-masing sisinya,
dinotasikan dengan ( ) adalah
.
Graf subdivisi (subdivision graph) dari graf G dinotasikan dengan
S(G) adalah suatu graf baru yang diperoleh dari subdivisi pada sisi di .
Subdivisi dari sisi dengan titik ujung dan menghasilkan sebuah graf
yang mengandung satu titik baru , dan menghasilkan dua sisi baru dan
. (Harrary, 1994)
Gambar 2.13 adalah contoh graf subdivisi pada graf .
u v
disubdivisi
u vw
Gambar 2.13. Graf subdivisi
17
Misalkan dan masing-masing adalah graf terhubung dan adalah
sebuah titik pada graf . Hasil kali comb antara graf dan , dinotasikan
dengan adalah graf yang didapat dengan mengambil satu kopian dari
dan kopian dari dan melekatkan kopian ke- dari pada titik
ke titik ke- dari . Dari definisi hasil kali comb, {
} dan dengan dan
atau dan (Saputro, S., dkk, 2013)
Gambar 2.14 adalah contoh graf dengan operasi comb.
a b
dc
w
xy
z
(a, w) (b, w)(d, w) (c, w)
(a, x)
(a, y) (a, z)(b, y)
(b, x)
(b, z)
(c, x)
(c, y)(c, z)(d, x)
(d, y)
(d, z)
(a) (b) (c)
Gambar 2.14. (a) Graf ; (b) Graf ; (c) Graf
Definisi 2.2.1
Misalkan dan masing-masing adalah graf terhubung dan adalah
sebuah titik pada graf . Hasil kali comb antara graf dan , dinotasikan
dengan adalah graf yang didapat dengan mengambil satu kopian
dari dan kopian dari dan melekatkan kopian ke- dari
pada titik ke titik ke- dari . Dari definisi hasil kali comb,
{ } dan
{ dan atau dan
} . Karena dan maka
18
Dengan
dan
Gambar 2.15 adalah contoh hasil kali comb dan dengan , dan
y5
x1 x2 x3
y3 y4
y1 y2
(a) (b)
(c)
(x1, y5)
(x1, y1)
(x1, y3) (x1, y4)
(x1, y2)
(x2, y3) (x2, y4)
(x2, y2)(x2, y1)
(x2, y5)
(x3, y1)
(x3, y3) (x3, y4)
(x3, y2)
(x3, y5)
Gambar 2.15. (a) Graf ; (b) Graf ; (c) Graf
Definisi 2.2.2
Misalkan dan masing-masing adalah graf terhubung dan adalah
sebuah titik pada graf . Hasil kali comb antara graf dan , dinotasikan
dengan adalah graf yang didapat dengan mengambil satu kopian
dari dan kopian dari dan melekatkan kopian ke- dari
pada titik ke titik ke- dari . Dari definisi hasil kali comb,
{ } dan
{ dan atau dan
} Karena dan maka
19
Dengan
dan
Gambar 2.16 adalah contoh hasil kali comb dan dengan , dan
x1 x2 x3
y7
y5 y6
y1y2
y3 y4
(a) (b)
(c)
(x1, y1)(x1, y2) (x2, y1)
(x1, y4) (x2, y3)(x1, y3)
(x1, y5) (x1, y6) (x2, y5) (x2, y6)
(x2, y4)
(x2, y2) (x3, y1)
(x3, y3)
(x3, y5) (x3, y6)
(x3, y4)
(x3, y2)
(x1, y7) (x2, y7) (x3, y7)
Gambar 2.16. (a) Graf ; (b) Graf ; (c) Graf
Definisi 2.2.3
Subdivisi pada Graf Hasil Kali Comb dan ( ) adalah suatu
graf baru yang diperoleh dari subdivisi pada setiap sisi di .
Subdivisi dari sisi dengan titik ujung dan menghasilkan
sebuah graf yang mengandung satu titik baru , dan menghasilkan dua sisi
baru yaitu dan Dari definisi subdivisi pada hasil kali comb,
{ | )
} dan {
{ }} Karena | ( )|
dan maka | ( )|
20
Dengan dan
Gambar 2.17 adalah contoh subdivisi pada graf hasil kali comb dan
dengan , dan titik subdivisi dan
x1 x2 x3
disubdivisi
x1 x2 x3z1 z2
y7
y5 y6
y1y2
y3 y4
z1 z2
(a) (b)
(c)
(x1, y1)(x1, y2) (x2, y1)
(x1, y4) (x2, y3)(x1, y3)
(x1, y5) (x1, y6) (x2, y5) (x2, y6)
(x2, y4)
(x2, y2) (x3, y1)
(x3, y3)
(x3, y5) (x3, y6)
(x3, y2)
(x1, y7) (x2, y7) (x3, y7)
Gambar 2.17. (a) Graf ; (b) Graf dan graf ; (c) Graf
2.3 Pelabelan Graf
Menurut Wallis (2001), pelabelan suatu graf adalah suatu pemetaan
yang membawa elemen-elemen graf ke bilangan-bilangan bulat positif atau
non negatif. Berdasarkan domain dari pemetaan ini ada tiga jenis pelabelan
yaitu pelabelan titik jika domainnya himpunan titik, pelabelan sisi jika
domainnya himpunan sisi atau pelabelan total jika domainnya himpunan
titik dan sisi. Pada pelabelan total Wallis juga menjelaskan bobot (weight)
dari graf adalah jumlah dari semua label yang berhubungan dengan elemen
graf tersebut. Bobot dari titik dengan pelabelan adalah
21
∑ , dan bobot dari sisi adalah
.
x
zy
x
zy1 2
1
1
1 2
(1) (2)
x
zy1
1 2
1
1
2
(3)
Gambar 2.18. (1) pelabelan titik (2) pelabelan sisi (3) pelabelan total
Berdasarkan definisi bobot sisi, Ba˘ca dkk. (2003) mendefinisikan
suatu jenis pelabelan yang disebut pelabelan-k tak teratur sisi total dengan
domain himpunan titik dan sisi sebagai berikut:
Definisi 2.3.1
Suatu pelabelan { } dikatakan pelabelan tak
teratur sisi total jika setiap dua sisi dan yang berbeda di
memenuhi , dengan dan
. Nilai minimum sehingga memiliki
pelabelan tak teratur sisi total disebut dengan nilai ketakteraturan sisi
total graf , disimbolkan dengan tes( ) .
Teorema 2.3.1 (Baca, 2003)
Misalkan G = (V(G), E(G)) graf dengan himpunan titik dan
himpunan tak kosong , maka
⌈
⌉
22
Bukti. Untuk menentukan batas atas, setiap titik di diberi label dan setiap sisi
dari secara terurut diberi label . Dengan menggunakan label
tersebut akan diperoleh untuk sembarang dua sisi dan yang
berbeda dari . Hal ini menunjukkan bahwa pelabelan tersebut adalah pelabelan
tak teratur sisi total dengan label terbesar , sehingga batas atas nilai
ketakteraturan sisi total yang dinotasikan dengan tes , adalah . Untuk batas
bawah, dimisalkan adalah pelabelan tak teratur sisi total yang optimal dari .
Bobot terbesar sisi dari , yaitu . Bobot tersebut merupakan
jumlah dari tiga label, sehingga setidaknya terdapat paling sedikit satu sisi atau
titik yang diberi label ⌈
⌉. Oleh karena itu, dapat disimpulkan bahwa batas
bawah tes adalah ⌈
⌉.
v1
v3v2
v5v4
v6
1
1
1
1
2
2
2
2
2
v7
2
33
3
3
Gambar 2.19. Pelabelan-3 total tak teratur sisi pada
23
Gambar 2.19 merupakan contoh graf yang titik dan sisinya diberi label
bilangan bulat positif sehingga disebut pelabelan total. Berdasarkan batas
bawah (1), diperoleh batas bawah tes ⌈
⌉ ⌈
⌉ Pelabelan
setiap titik pada yaitu
Sedangkan label setiap sisinya yaitu
Bobot setiap sisi pada Gambar 2.18 dapat ditentukan dengan menjumlahkan
label sisi dengan label titik yang incident dengan sisi tersebut. Bobot setiap
sisi graf tersebut yaitu
24
Berdasarkan pelabelan yang diberikan seperti pada Gambar 2.18 terlihat
bahwa bobot setiap sisi berbeda, yaitu
Inilah yang disebut pelabelan
tak teratur sisi total. Pelabelan yang dilakukan menghasilkan nilai minimum
dari label terbesar untuk titik dan sisi pada graf adalah , jadi
tes
Teorema 2.3.2 (Baca,2003)
Misalkan dan adalah Path dan Cycle, dengan sisi, maka
tes tes ⌈
⌉.
Bukti. Misal { } pada pelabelan total dan
Berdasarkan Teorema 2.3.1, tes ⌈
⌉, dimana { }.
Teorema diatas akan dibuktikan dengan induksi matematika untuk nilai
dasar yaitu maka label dari adalah satu untuk ketiga elemennya
(satu sisi dan dua titik diujungnya) seperti pada Gambar 2.19.
v1 v2e1
1 1 1
P1
Gambar 2.20. Pelabelan total graf path
Diperoleh label sebagai berikut:
Sehingga tes ⌈
⌉ ⌈
⌉ ⌈ ⌉
Jadi benar untuk ..........................................................................(i)
25
Asumsikan untuk dengan banyak sisi pada adalah
benar.
vk vk+1v1 v2e1
1 1 1 k k k
ek
Pk
Gambar 2.21. Pelabelan total graf path
Sehingga sisi di seperti pada Gambar 2.21 dilabeli dengan
maka tes ⌈
⌉
⌈
⌉ ⌈ ⌉ ⌈ ⌉ benar.
Akan dibuktikan untuk , tes .
vk vk+1v1 v2e1
1 1 1 k k k
ek vk+2ek+1
k+1 k
Pk+1
Gambar 2.22. Pelabelan total graf path
Untuk langkah-langkah induksi sisi-sisi dan titik-titik
diberi label seperti pada seperti pada Gambar 2.22, maka diperoleh
label untuk sisi sebagai berikut:
sehingga tes
⌈
⌉ ⌈
⌉ ⌈ ⌉
Jadi jika benar maka benar..........................................................(ii)
Dari (i) dan (ii) diperoleh tes ⌈
⌉ dengan sisi.................(iii)
26
1 1 1
2
2
1
1
2
2 2 2
1
11
2
2
1 1 1
1
2
2
23
Gambar 2.23. Pelabelan total graf dan
Misalkan adalah cycle . Pada Gambar 2.23
pelabelan optimal tak teratur dari dan dengan label dari
himpunan { }. Untuk nilai dasar karena cycle banyaknya sisi paling
sedikit tiga sisi maka pangkal induksi- dari cycle adalah
Dengan label sebagai berikut
sedemikian hingga tes ⌈
⌉ ⌈
⌉
Jadi benar untuk ........................................................................(iv)
vk-1
ek-1
vk
k
k+1
k
Ck
Gambar 2.24. Pelabelan total graf cycle
27
Asumsikan untuk dengan banyak sisi pada adalah
, dengan diberi label seperti pada
Gambar 2.24, maka diperoleh label sebagai berikut:
Sehingga tes ⌈
⌉ ⌈
⌉ ⌈
⌉
benar.
Akan dibuktikan untuk , tes
vk-1 vk
k
k+1
kx1
k+1
k
a
vk-1
vk
k
k+1 kx1
k+1
kx2
k+1k+1
b
vk-1
vk
k
k+1
kx1
k+2 kx2
k+1
k+1
x3
k+1k+1
c
Gambar 2.25. Pelabelan total graf cycle
Untuk mendapatkan pelabelan optimal dari sisi
dibagi menjadi dua (tiga atau empat, berturut-turut) sisi dengan
menambahkan satu titik baru yaitu (dua titik baru yaitu dan , atau
tiga titik baru yaitu dan , berturut-turut) diberi label seperti pada
Gambar 2.25, maka diperoleh label sebagai berikut:
28
a) Jika menambahkan satu titik baru yaitu seperti pada Gambar
2.25 a, maka
b) Jika menambahkan dua titik baru yaitu dan seperti pada
Gambar 2.25 b, maka
c) Jika menambahkan tiga titik baru yaitu dan seperti pada
Gambar 2.25 c, maka
Sedemikian hingga,
tes ⌈
⌉ ⌈
⌉ ⌈
⌉
Jadi jika benar maka benar...........................................................(v)
Dari (iv) dan (v) diperoleh tes ⌈
⌉ dengan sisi...............(vi)
Dari (iii) dan (vi) diperoleh tes tes ⌈
⌉, dengan sisi.
36
BAB 5
KESIMPULAN DAN SARAN
5.1. Kesimpulan
Dalam penelitian ini diperoleh dua kesimpulan, yaitu:
1. Nilai ketakteraturan sisi total dari graf hasil kali comb dan untuk
suatu bilangan bulat positif adalah tes( ⌈
⌉.
2. Nilai ketakteraturan sisi total dari subdivisi pada graf hasil kali comb
dan untuk suatu bilangan bulat positif adalah tes
⌈ ⌉
5.2. Saran
Penelitian ini masih terbatas pada graf hasil kali comb dan serta
subdivisi pada graf hasil kali comb dan . Penelitian ini dapat dikembangkan
untuk graf hasil kali comb dan serta graf hasil kali comb dan yang
lebih kompleks lagi, misal dan seterusnya
sampai .
37
DAFTAR PUSTAKA
Baca M., Jendrol, S., Miller, M., & Ryan, J. 2007. On Irregular Total Labeling.
Discrete Math (307):1378-1388.
Boundy, J. A., & Murty, U.S.R. 1976. Graph Theory with Applications. Ontario:
Departement of Combinatorics and Optization, University of Waterloo.
Budayasa, I. K. 2007. Teori Graf dan Aplikasinya. Surabaya: Unesa University
Press.
Chartrand, Gary & O. R. Oellermann. 1993. Applied and Algorithmic Graph
Theory. New York: McGraw-Hill Inc.
Chartrand, Gary. 1986. Introductory Graph Theory. New York: Dover
Publications Inc.
Corazon, C. M., & Riyanti, R. 2016. Nilai Total Ketakteraturan Titik Pada Graf
Hasil kali Comb Dan Dengan Bilangan Ganjil. Jurnal Sanis
Matematika dan Statistika. Vol. 2 No. 2: 39-47.
Fletcher, P., Hoyle, H., & Patty, C. W. 1991. Foundation of Discrete
Mathematics. Boston: PWS Kent Publishing Company.
Harary, F. 1994. Graph Theory. Michigan: Addison-Wesley Publishing Company.
Indriati, D., Widodo, Wijayanti, I. E., Sugeng, K. A., & Bača, M. 2015. On Total
Edge Irregularity Strength of Generalized Web Graphs and Related
Graphs. Mathematics in Computer Science (9):161-167
Ivančo, J., & Jendroˇl, S. 2006. Total Edge Irregularity Strength of
Trees Discussiones Math. Graph Theory (26): 449-456.
38
Jayanthi, P. 2016. Total Edge Irregularity Strength Of Disjoint Union Of Double
Wheel Graphs. Proyecciones Journal Of Mathematics (35): 251-262.
Johnsonbaugh, R. 2001. Discrete Mathematics. Fifth edition. New Jersey :
Prentice Hall.
Marzuki, C. C., Salman, A., & Miller, M. 2013. On Total Irregularity Strenth of
Cycles and Path. Far East Journal of Mathematical Sciences(FJMS)
1(82):1-21.
Marzuki, C. C., & Febrinanda, Y. 2017. Nilai Ketakteraturan Total dari Graf
Hasil Kali Comb dan . Jurnal Sains Matematika dan Statistika
Vol 3 No 2: 8-15
Rosyida, I., & Indriati, D. (2019). On Total Edge Irregularity Strength of Some
Cactus Chain Graphs With Pendant Vertices. Journal Of Physics
(1211):1-10
Saputro, S. W., Mardiana, N., & Purwasi, I. A. 2013. The Metric Dimension of
Comb Product Graph. Graph Theory Conference in Honor of Egawa
60th Birthday. Artikel ini didapat dari:
http://www.rs.tus.ac.jp/egawa_60th_birtday/abstract/contributed_talk/s
uhadi_wido_saputro.pdf.
Siddiqui, M. K., & Afzal, D. 2011. On tvs of Subdivision of Star . Australian
Journal of Basic and Applied Sciences. 5 (11): 2146-2156.
Siddiqui, M. K., & Afzal, D. 2013. On tes of Disjoint Union of Helm Graphs. J.
Math. Fund. Sci., (45): 163-171.
39
Tarawneh, I., Hasni, R., & Ahmad, A. 2016. On The Edge Irregularity Strength
Of Corona Product Of Graphs With Paths. Applied Mathematics E-
Notes (16):80-87.
Umilasari, R. 2015. Bilangan Dominasi Jarak Dua Pada Graf-Graf Hasil Operasi
Korona dan Comb. Fakultas Matematika dan Ilmu Pengetahuan Alam.
Surabaya: Institut Teknologi Sepuluh Nopember.
Wallis, W. D. 2001. Magic Graph. Boston: Birkhauser.