PELABELAN SELIMUT H-AJAIB SUPER PADA

GRAF Fn ⊙ Pm, Ln ⊙ Pm, DAN W3,m ⊙ Pm

oleh

RETIA KARTIKA DEWI

M0112070

ditulis dan diajukan untuk memenuhi sebagian persyaratan

memperoleh gelar Sarjana Sains Matematika

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS SEBELAS MARET

SURAKARTA

2017

i

PERNYATAAN

Nama : Retia Kartika Dewi

NIM : M0112070.

Menyatakan dengan sesungguhnya bahwa skripsi berjudul PELABELAN SELI-

MUT H-AJAIB SUPER PADA GRAF Fn⊙Pm, Ln⊙Pm, DAN W3,m⊙Pm adalah

betul-betul karya sendiri, bukan plagiat, dan belum pernah diajukan untuk mem-

peroleh gelar kesarjanaan pada suatu perguruan tinggi. Sepanjang pengetahuan

saya juga belum pernah ditulis atau dipublikasikan oleh orang lain, kecuali yang

secara tertulis diacu dalam naskah ini dan disebutkan dalam daftar pustaka.

Apabila di kemudian hari terbukti pernyataan ini tidak benar, maka saya

bersedia menerima sanksi akademik berupa pencabutan skripsi dan gelar yang

diperoleh dari skripsi tersebut.

Surakarta, Agustus 2017

Retia Kartika Dewi.

iii

ABSTRAK

RETIA KARTIKA DEWI, 2017. PELABELAN SELIMUT H-AJAIBSUPER PADA, GRAF Fn ⊙ Pm Ln ⊙ Pm, DAN W3,m ⊙ Pm. Fakultas Mate-matika dan Ilmu Pengetahuan Alam, Universitas Sebelas Maret.

Suatu graf sederhana G = (V,E) dikatakan memuat selimut H jika setiapedge dari e ∈ E(G) termuat dalam suatu subgraf dari G yang isomorfik terhadapH. Selanjutnya graf G yang memuat selimut-H dikatakan H-ajaib jika memuatfungsi bijektif f : V (G) ∪ E(G) → {1, 2, · · · , |V (G)| + |E(G)|} sehingga untuksetiap subgrafH ′ dariG yang isomorfik terhadapH berlaku f(H ′) =

∑v∈V f(v)×∑

e∈E f(e) = m(f), dengan m(f) adalah jumlahan ajaib. Selanjutnya, graf Gdisebut H-ajaib super jika f(V ) = {1, 2, · · · , |V (G)|}.

Penelitian ini bertujuan mencari selimut H-ajaib super pada korona antara:graf kipas dan graf lintasan (Fn ⊙ Pm) dengan n ≥ 4,m ≥ 3, dan graf tanggadan graf lintasan (Ln ⊙Pm), dengan n,m ≥ 3, serta graf kincir dan graf lintasan(W3,m ⊙ Pm) dengan m ≥ 3.

Hasil penelitian menunjukkan bahwa graf Fn ⊙ Pm adalah C3 ⊙ Pm-ajaibsuper untuk n ≥ 4 dan m ≥ 3, graf Ln ⊙ Pm adalah C4 ⊙ Pm-ajaib super untukm,n ≥ 3, dan graf W3,m ⊙ Pm adalah C3 ⊙ Pm-ajaib super untuk m ≥ 3.

Kata Kunci: Pelabelan selimut H-ajaib super, graf kipas, graf tangga, grafkincir, graf lintasan.

iv

ABSTRACT

Retia Kartika Dewi, 2017. H-SUPERMAGIC LABELING ON CORONAPRODUCT OF Fn ⊙ Pm, Ln ⊙ Pm, AND W3,m ⊙ Pm .Faculty of Mathematics and Natural Sciences, Sebelas Maret University.

A simple graph G = (V,E) admits an H-labeling if every edge e ∈ E(G) be-longs to a subgraph of G isomorphic to H. Furthermore, G contains H-labeling ifthere exists a bijection function f : V (G)∪E(G) → {1, 2, · · · , |V (G)|+ |E(G)|},such that for each subgraph H ′ of G isomorphic to H, f(H ′) =

∑v∈V f(v) ×∑

e∈E f(e) = m(f) where m(f) is a magic sum. Then G is an H-supermagic iff(V ) = {1, 2, · · · , |V (G)|}.

This research aims to find H-super magic labeling on corona product, whi-ch: a fan graph with a path (Fn⊙Pm) where n ≥ 4,m ≥ 3, a ladder graph with apath (Ln ⊙Pm), where n,m ≥ 3, and a windmill graph with a path (W3,m ⊙Pm)where m ≥ 3.

The result show that Fn⊙Pm for n ≥ 4 and m3 ≥ 4 is C3⊙Pm-supermagic,a Ln ⊙ Pm for m,n ≥ 3 is C4 ⊙ Pm-supermagic, and W3,m ⊙ Pm for m ≥ 3 isC3 ⊙ Pm-supermagic.

Keywords : H-supermagic labeling, a fan graph, a ladder graph, a windmillgraph, a path.

v

PERSEMBAHAN

Karya ini kupersembahkan untuk

Ibu saya, almh.Tuti Suseno Widiyanti dan Bapak Triyono, yang tak

henti-hentinya mendoakan yang terbaik untuk saya.

Rio Widiyantoro dan Widya Dian Pratiwi yang menjadi penyemangat dalam

menyelesaikan skripsi ini.

vi

MOTO

Memang pekerjaan peneliti itu cari-cari masalah, tetapi juga

sesekali harus berani menyadari bahwa sebenarnya tidak ada

masalah dengan yang ditelitinya. Dan keyakinan demikian pada

gilirannya menyeretkan pada keyakinan macam lain lagi, yakni

bahwa ternyata tidak ada satu pun yang tidak bermasalah di

sekitar hidup kita. Ya, itulah Ilmu. Hidup ilmu! Hidup Masalah!

(Sapardi Djoko Damono : Hujan Bulan Juni)

Ilmu tidak akan diraih dengan mengistirahatkan badan

(bermalas-malasan).

(HR. MUSLIM)

vii

KATA PENGANTAR

Bismillahirrahmanirrahim,

Segala puji bagi Allah SWT atas segala rahmat dan hidayah-Nya, sehingga

penulis dapat menyelesaikan skripsi ini. Sholawat serta salam selalu dihaturkan

kepada Nabi Muhammad SAW. Penulis menyadari bahwa terwujudnya skripsi ini

berkat dukungan dan bimbingan dari berbagai pihak. Oleh karena itu, penulis

menghaturkan terima kasih kepada

1. Ibu Dra. Mania Roswitha, M. Si., sebagai Pembimbing I yang telah membe-

rikan bimbingan dan motivasi sehingga penulis dapat menyelesaikan skripsi

ini.

2. Ibu Titin Sri Martini, S.Si., M.Kom., sebagai Pembimbing II yang telah

memberikan bimbingan dan motivasi sehingga penulis dapat menyelesaikan

skripsi ini.

3. Keluarga, teman-teman MathTwelve, dan teman-teman LPM Kentingan

yang telah memberikan semangat dan motivasi dalam menyelesaikan skripsi

ini.

Penulis berharap semoga skripsi ini dapat bermanfaat bagi semua pembaca.

Surakarta, Agustus 2017

Penulis

viii

DAFTAR ISI

PENGESAHAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii

PERNYATAAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii

ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv

ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v

PERSEMBAHAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi

MOTO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii

KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . . . . viii

DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x

DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi

DAFTAR NOTASI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii

I PENDAHULUAN 1

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

1.2 Perumusan Masalah . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.4 Manfaat Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . 3

II LANDASAN TEORI 4

2.1 Tinjauan Pustaka . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.2 Teori Penunjang . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2.1 Pengertian Dasar Graf . . . . . . . . . . . . . . . . . . . . 5

2.2.2 Operasi pada Graf . . . . . . . . . . . . . . . . . . . . . . 7

2.2.3 Kelas-kelas Graf . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2.4 Fungsi dan Isomorfisma . . . . . . . . . . . . . . . . . . . 11

ix

2.2.5 Pelabelan Ajaib Super . . . . . . . . . . . . . . . . . . . . 12

2.2.6 Teknik k-Seimbang Multihimpunan . . . . . . . . . . . . . 13

2.2.7 Teknik (k, δ)-Anti Seimbang Multihimpunan . . . . . . . . 13

2.3 Kerangka Pemikiran . . . . . . . . . . . . . . . . . . . . . . . . . 14

IIIMETODE PENELITIAN 15

IVHASIL DAN PEMBAHASAN 16

4.1 Lema-lema Pendukung . . . . . . . . . . . . . . . . . . . . . . . . 16

4.2 Pelabelan Selimut C3 ⊙ Pm-ajaib super pada graf Fn ⊙ Pm . . . . 20

4.3 Pelabelan Selimut C4 ⊙ Pm-ajaib super pada graf Ln ⊙ Pm . . . . 23

4.4 Pelabelan selimut C3 ⊙ Pm-ajaib super pada graf W3,m ⊙ Pm . . . 25

V PENUTUP 29

5.1 Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5.2 Saran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

DAFTAR PUSTAKA 30

x

DAFTAR GAMBAR

2.1 (a) G1 merupakan graf terhubung dan (b) G2 merupakan graf tidak

terhubung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.2 Graf G3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.3 (a) Graf G4 dan G5 (b) G4 ∪G5 (c) G4 +G5 (d) G5 ×G4. . . . . 8

2.4 Graf G5 ⊙G4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.5 Graf lintasan P4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.6 Graf kipas F3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.7 Graf tangga L4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.8 Graf kincir W3,2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.9 Graf G6 isomorfik dengan graf G7 . . . . . . . . . . . . . . . . . . 12

4.1 Pelabelan selimut C3 ⊙ P3-ajaib super pada graf F4 ⊙ P3. . . . . . 22

4.2 Pelabelan selimut C4 ⊙ P3-ajaib super pada graf L3 ⊙ P3 . . . . . 25

4.3 Pelabelan selimut C3 ⊙ P3-jaib super pada graf W3,3 ⊙ P3. . . . . 28

xi

DAFTAR NOTASI

G : graf G

H : subgraf dari graf G

R : relasi

(u, v) : vertex

e : edge

⊂ : himpunan bagian sejati (proper subset)

\{k2+ 1} : pengecualian untuk {k

2+ 1}

⊆ : himpunan bagian tidak sejati (improper subset)

V (G) : himpunan vertex dari graf G

E(G) : himpunan edge dari graf G

|V (G)| : banyaknya vertex dari graf G (order)

|E(G)| : banyaknya edge dari graf G (size)

m(f) : jumlahan ajaib

s(f) : jumlahan ajaib super

Σ : sigma

= : tidak sama dengan

δ : selisih pada jumlahan anti seimbang

ϕ : pemetaan

∈ : anggota

⌈ ⌉ : pembulatan ke atas (ceiling)

⌊ ⌋ : pembulatan ke bawah (flooring)

+ : join

⊎ : union plus

∪ : union

× : hasil kali product

⊙ : hasil operasi korona

N : himpunan bilangan alam

xii

C3 : graf cycle ber-order 3

C4 : graf cycle ber-order 4

Fn : graf kipas ber-order n

Ln : graf tangga ber-order n

Pm : graf lintasan ber-order m

Wn : graf roda ber-order n

Km,n : graf bipartit lengkap ber-order m+ n

K1,n : graf bintang ber-order n+ 1

W3,m : graf kincir yang terbentuk dari m-kopi graf cycle dengan order 3

C3 ⊙ Pm : graf operasi korona dari graf C3 dengan korona graf Pm

C4 ⊙ Pm : graf operasi korona dari graf C4 dengan korona graf Pm

Fn ⊙ Pm : graf operasi korona dari graf Fn dengan korona graf Pm

Ln ⊙ Pm : graf operasi korona dari graf Ln dengan korona graf Pm

W3,m ⊙ Pm : graf operasi korona dari graf W3,m dengan korona graf Pm

xiii