nilai ketakteraturan sisi total pada graf hasil …lib.unnes.ac.id/37491/1/4111414023.pdfgabungan,...

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

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



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)


Definisi 2.2.2



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)


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


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


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.

http://www.rs.tus.ac.jp/egawa_60th_birtday/abstract/contributed_talk/suhadi_wido_saputro.pdf

http://www.rs.tus.ac.jp/egawa_60th_birtday/abstract/contributed_talk/suhadi_wido_saputro.pdf

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.

nilai ketakteraturan sisi total pada graf hasil …lib.unnes.ac.id/37491/1/4111414023.pdfgabungan,...

Documents