perpustakaan.uns.ac.id
digilib.uns.ac.id
PELABELAN SELIMUT H-AJAIB SUPER PADA KORONASI BEBERAPA KELAS GRAF DENGAN GRAF LINTASAN
oleh HARDINA SANDARIRIA M0112041
SKRIPSI
ditulis dan diajukan untuk memenuhi sebagian persyaratan memperoleh gelar Sarjana Sains Matematika
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SEBELAS MARET
commit to user SURAKARTA 2016 i
perpustakaan.uns.ac.id
digilib.uns.ac.id
commit to user
perpustakaan.uns.ac.id
digilib.uns.ac.id
ABSTRAK Hardina Sandariria, 2016. PELABELAN SELIMUT H -AJAIB SUPER PADA KORONASI BEBERAPA KELAS GRAF DENGAN GRAF LINTASAN. Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Sebelas Maret. Graf sederhana G = (V, E) memuat selimut H jika setiap sisi pada E memuat subgraf di G yang isomorfik dengan H. Andaikan suatu graf G = (V (G), E(G)) memiliki selimut-H, maka suatu fungsi bijektif f : V (G)∪E(G) → {1, 2, . . . , |V |+ |E|}, adalah pelabelan H-ajaib dari G jika terdapat bilangan bulat positif m(f ) yang disebut jumlah ajaib. Untuk suatu subgraf H = (V (H ), E (H )) dari G isomorfik ke H diperoleh f (H ) = f (v) + f (e) = m(f ), v∈V
e∈E
sehingga graf G disebut H-ajaib. Graf G adalah H-ajaib super dan jumlah ajaib super dinotasikan dengan s(f ) untuk f (V ) = {1, . . . , |V |}. Penelitian ini untuk mencari selimut H-ajaib super pada koronasi graf bintang, roda, dan gear dengan graf lintasan. Akan dibuktikan bahwa graf bintang korona lintasan Sn Pm dengan m ≥ 3 adalah Um,2 -ajaib super untuk sebarang n dan m ganjil atau m, n genap, graf roda korona lintasan Wn Pm adalah C3 Pm -ajaib super untuk m ≥ 3, dan graf gear korona lintasan Gn Pm adalah C4 Pm -ajaib super untuk n ganjil dan m ≥ 3. Kata kunci : selimut H-ajaib super, koronasi, graf lintasan, graf bintang, graf roda, graf gear, graf payung, graf siklus, Um,2 , C3 Pm , C4 Pm , Sn Pm , Wn Pm , Gn Pm
commit to user
iii
perpustakaan.uns.ac.id
digilib.uns.ac.id
ABSTRACT Hardina Sandariria, 2016. H -SUPERMAGIC COVERING ON CORONATION OF SOME CLASSES OF GRAPHS WITH A PATH. Faculty of Mathematics and Natural Sciences, Sebelas Maret University. A simple graph G = (V, E) admits an H-covering if every edge in E belongs to a subgraph on G that isomorphics to H. A graph G is H-magic if there is a total labeling f : V (G) ∪ E(G) → {1, 2, . . . , |V | + |E|}, such that each subgraph H = (V (H ), E (H )) on G satisfies f (v) + f (e) = m(f ), f (H ) = v∈V
e∈E
where m(f ) is a constant magic sum. A graph G is a H-supermagic covering if f (V ) = {1, . . . , |V |} and s(f ) is a constant supermagic sum. The research aims to study H-supermagic coverings on corona of a star graph with a path, a wheel graph with a path, and a gear graph with a path. We prove that corona a star graph with a path Sn Pm is an Um,2 -supermagic for m is odd or m, n are even and m ≥ 3, corona a wheel graph with a path Wn Pm is a C3 Pm -supermagic for m ≥ 3, and corona a gear graph with a path Gn Pm is a C4 Pm -supermagic for n odd and m ≥ 3. Keywords : H-supermagic covering, corona, path, star graph, wheel graph, gear graph, umbrella graph, cycle graph, Um,2 , C3 Pm , C4 Pm , Sn Pm , Wn Pm , Gn P m
commit to user
iv
perpustakaan.uns.ac.id
digilib.uns.ac.id
MOTO
Kebanggaan kita yang terbesar adalah bukan tidak pernah gagal, tetapi bangkit kembali setiap kali kita jatuh.
commit to user
v
perpustakaan.uns.ac.id
digilib.uns.ac.id
PERSEMBAHAN
Karya ini kupersembahkan untuk Alm. bapak, ibu, dan kakak saya.
commit to user
vi
perpustakaan.uns.ac.id
digilib.uns.ac.id
KATA PENGANTAR
Bismillahirrahmanirrahim, Segala puji dan syukur penulis panjatkan kepada Allah SWT yang telah melimpahkan rahmat-Nya sehingga penulis dapat menyelesaikan penulisan skripsi ini. Sholawat serta salam selalu dihaturkan kepada Nabi Muhammad SAW. Penulis menyadari bahwa terwujudnya skripsi ini berkat bantuan dan bimbingan dari berbagai pihak. Ucapan terima kasih penulis sampaikan kepada 1. Dra. Mania Roswitha, M.Si. dan Prof. Drs. Tri Atmojo Kusmayadi, M.Sc., Ph.D. sebagai pembimbing yang telah memberikan bimbingan materi serta penulisan dalam skripsi, saran, dan motivasi, dan 2. semua pihak yang telah memberikan bantuan, masukan, dan dukungan kepada penulis. Penulis berharap semoga skripsi ini dapat bermanfaat bagi semua pembaca.
Surakarta, September 2016
Penulis
commit to user
vii
perpustakaan.uns.ac.id
digilib.uns.ac.id
DAFTAR ISI
I
HALAMAN JUDUL . . . . . . . . . . . . . . . . . . . . . . . . . . . .
i
PENGESAHAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ii
ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iii
ABSTRACT
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iv
MOTO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
v
PERSEMBAHAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . . . .
vii
DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ix
DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . . . .
x
DAFTAR NOTASI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xi
PENDAHULUAN
1
1.1
Latar Belakang Masalah . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Perumusan Masalah
. . . . . . . . . . . . . . . . . . . . . . . . .
2
1.3
Tujuan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.4
Manfaat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
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
Kelas-kelas Graf . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2.3
Graf Isomorfik . . .commit . . . .to. user . . . . . . . . . . . . . . . . .
8
2.2.4
Operasi Korona pada Graf . . . . . . . . . . . . . . . . . .
8
viii
perpustakaan.uns.ac.id
2.3
digilib.uns.ac.id
2.2.5
Pelabelan Selimut Ajaib . . . . . . . . . . . . . . . . . . .
9
2.2.6
Teknik k-Seimbang Multihimpunan . . . . . . . . . . . . .
10
Kerangka Pemikiran . . . . . . . . . . . . . . . . . . . . . . . . .
11
III METODE PENELITIAN
12
IV PEMBAHASAN
13
4.1
Lema Pendukung . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
4.2
Penelitian Terdahulu . . . . . . . . . . . . . . . . . . . . . . . . .
16
4.3
Pelabelan Selimut Um,2 -ajaib Super pada Graf Sn Pm . . . . . .
18
4.4
Pelabelan Selimut C3 Pm -ajaib Super pada Graf Wn Pm . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5
20
Pelabelan Selimut C4 Pm -Ajaib Super pada Graf Gn Pm . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
V PENUTUP
24 27
5.1
Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
5.2
Saran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
DAFTAR PUSTAKA
28
commit to user
ix
perpustakaan.uns.ac.id
digilib.uns.ac.id
DAFTAR GAMBAR
2.1
Graf G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2
P3 adalah graf lintasan, S3 adalah graf bintang, U3,2 adalah graf payung, W4 adalah graf roda, dan G4 adalah graf gear
6
. . . . . .
7
2.3
Graf G1 isomorfik dengan graf G2 . . . . . . . . . . . . . . . . . .
8
2.4
Bentuk umum graf gear korona lintasan Gn Pm , graf roda korona lintasan Wn Pm , dan graf bintang korona lintasan Sn Pm . . .
9
4.1
Pelabelan selimut C3 -ajaib super pada graf roda W6 . . . . . . . .
18
4.2
Pelabelan selimut U4,1 -ajaib super pada graf S4 P4
. . . . . . .
20
4.3
Pelabelan selimut C3 P3 -ajaib super pada graf W6 P3 . . . . .
24
4.4
Pelabelan selimut C4 P3 -ajaib super pada graf G3 P3 . . . . .
26
commit to user
x
perpustakaan.uns.ac.id
digilib.uns.ac.id
DAFTAR NOTASI
G
:
graf G
u, v
:
titik
(u, v)
:
sisi
V (G)
:
himpunan titik dari graf G
E(G)
:
himpunan sisi dari graf G
|V (G)|
:
banyaknya titik dari graf G (order )
|E(G)|
:
banyaknya sisi dari graf G (size)
G∼ =H
:
graf G isomorfik dengan graf H
GH
:
operasi gabungan multihimpunan G dengan H
φ
:
fungsi isomorfisma
f (e)
:
pelabelan f pada sisi e
f (v)
:
pelabelan f pada sisi v
f (H)
:
pelabelan f yang menyatakan jumlah label pada sisi
k
dan titik graf G :
operasi gabungan multihimpunan X1 X2 . . . Xk
[a, b]
:
himpunan bilangan bulat positif dari a sampai b
:
operasi korona
∈
:
anggota
Sn
:
graf bintang yang memiliki n + 1 titik
Wn
:
graf roda yang memiliki n + 1 titik dan 2n sisi
Gn
:
Pm
:
graf gear yang memiliki 2n + 1 titik dan 3n sisi commit to user graf lintasan dengan n titik
i=1
Xi
xi
perpustakaan.uns.ac.id
x
:
digilib.uns.ac.id
bilangan bulat terkecil yang lebih besar atau sama dengan x (ceiling)
x
:
bilangan bulat terbesar yang lebih kecil atau sama dengan x (flooring)
2
:
akhir bukti
Sn Pm
:
graf hasil operasi korona pada graf bintang ber-order n + 1 dengan graf lintasan ber-order m
Wn P m
:
graf hasil operasi korona pada graf roda ber-order n + 1 dengan graf lintasan ber-order m
Gn Pm
:
graf hasil operasi korona pada graf gear ber-order 2n + 1 dengan graf lintasan ber-order m
Cn Pm
:
graf hasil operasi korona pada graf siklus ber-order n dengan graf lintasan ber-order m
commit to user
xii
