perpustakaan.uns.ac.id
digilib.uns.ac.id
PELABELAN SELIMUT H-AJAIB SUPER PADA GRAF BIPARTIT LENGKAP, GRAF BUKU, GRAF RODA T -LIPAT DAN GRAF BUNGA
oleh RACHEL WULAN NIRMALASARI WIJAYA NIM. M0110068
SKRIPSI ditulis dan diajukan untuk memenuhi sebagian persyaratan memperoleh gelar Sarjana Sains Matematika
JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SEBELAS MARET SURAKARTA
commit 2014 to user
perpustakaan.uns.ac.id
digilib.uns.ac.id
SKRIPSI
PELABELAN SELIMUT
- AJAIB SUPER PADA GRAF BIPARTIT
.FI
LENGKAP, GRAF BUKU, GRAF RODA T-LIPAT DAN GRAF BUNGA yang disiapkan dan disusun oleh
RACHEL WULAN NIRMALASARI WIJAYA
NIM. M0110068 dibimbing oleh Pembimbing
I
,b
-t:
_
Dra. Manih Roswitha, M.Si.
Titin Sri Martini, S.Si., M.Kom.
NIP. 19520628 198303 2 001
NIP. 197501202008t2 2 001
telah dipertahankan di depan Dewan Penguji pada hari Selasa, tanggal 28 Jan.uari2074
dan dinyatakan telah memenuhi syarat.
1.
Anggota Tim Penguji
Tanda Tangan
Prof. Tri Atmojo K., M.Sc., Ph.D.
1.
NIP. 19630826 198803 L 002
2.
Dr. Sri Subanti,
M.Si.
2.
NIP. 19581031 198601 2 001 Surakarta, 4 Februari 2014
ika dan Ilmu Pengetahuan Alam Matematika,
Ramelan, M.Sc. (Hons)., Ph.D.
NIP. 19610223 L9860t 1 001
commit to user
Irwan Susanto, S.Si., DEA.
NIP. 19710511 199512 1 001
perpustakaan.uns.ac.id
digilib.uns.ac.id
ABSTRAK Rachel Wulan Nirmalasari Wijaya . 2014. PELABELAN SELIMUT H AJAIB SUPER PADA GRAF BIPARTIT LENGKAP, GRAF BUKU, GRAF RODA T -LIPAT DAN GRAF BUNGA. Fakultas Matematika dan Ilmu Pengetahuan Alam. Universitas Sebelas Maret. Suatu graf G = (V, E) dikatakan memiliki sebuah selimut H-ajaib, dengan H adalah subgraf dari G, jika setiap sisi dalam E berada dalam sebuah subgraf dari G yang isomorfik terhadap H. Graf G merupakan H-ajaib jika terdapat suatu pelabelan total λ : V (G) E(G) → {1, 2, . . . ,|V (G)| + |E(G)|}, sedemikian sehingga setiap subgraf H = (V , E ) dari G akan isomorfik terhadap H dan berlaku def λ(H ) = λ(v) + λ(e) = m(λ), v∈V
e∈E
dengan m(λ) suatu jumlah ajaib yang konstan, sedangkan G dikatakan memiliki pelabelan selimut H-ajaib super bila label di titik adalah λ(V ) = {1, 2, ..., |V |} dengan s(λ) adalah jumlahan ajaib super. Tujuan penelitian ini adalah menentukan adanya pelabelan selimut H-ajaib super pada graf bipartit lengkap Km,n dengan H adalah Km,k , graf buku Bn dengan H adalah Bk , graf roda t-lipat Wn dengan H adalah roda k-lipat Wn dan pada graf bunga Fn dengan H adalah C3 . Selanjutnya diperoleh bahwa Km,n adalah Km,k -ajaib super dengan 3 ≤ m < n dan m ≤ k < n, Bn adalah Bk -ajaib super dengan 3 ≤ k < n, roda t-lipat Wn adalah roda k-lipat Wn -ajaib super dengan n ≥ 3 dan 2 ≤ k < t, dan Fn adalah C3 -ajaib super dengan n ≡ 3 (mod 4). Metodologi penelitian yang digunakan adalah studi literatur. Hasil dari penelitian ini adalah diperoleh pelabelan selimut Km,k -ajaib super pada graf bipartit lengkap Km,n dengan 3 ≤ m < n dan m ≤ k < n, Bk -ajaib super pada graf buku Bn dengan 3 ≤ k < n, roda k-lipat Wn -ajaib super pada graf roda t-tipat Wn dengan n ≥ 3 dan 2 ≤ k < t, serta C3 -ajaib super pada graf bunga Fn dengan n ≡ 3 (mod 4). Kata Kunci : pelabelan selimut H-ajaib super, graf bipartit lengkap, graf buku, graf roda t-lipat, graf bunga
commit to user iii
perpustakaan.uns.ac.id
digilib.uns.ac.id
ABSTRACT Rachel Wulan Nirmalasari Wijaya. 2014. H - SUPERMAGIC COVERING ON COMPLETE BIPARTITE GRAPH, BOOK GRAPH, T -FOLD WHEEL GRAPH AND FLOWER GRAPH. Faculty of Mathematics and Natural Sciences, Sebelas Maret University. A simple graph G = (V, E) admits a H-covering, where H is subgraph of G, if every edge in E belongs to a subgraph of G isomorphic to H. Graph G is Hmagic if there is a total labeling λ : V (G) E(G) → {1, 2, . . . , |V (G)| + |E(G)|}, such that each subgraph H = (V , E ) of G isomorphic to H and satisfying λ(H ) =
def
v∈V
λ(v) +
λ(e) = m(λ),
e∈E
where m(λ) is a constant magic sum. Additionaly, G admits H-supermagic if λ(V ) = {1, 2, ..., |V |} where s(λ) is a constant supermagic sum. This research aims to find H-supermagic covering on a complete bipartite graph Km,n where H is Km,k , a book graph Bn where H is Bk , a t-fold wheel graph Wn where H is k-fold wheel Wn and a flower graph Fn where H is C3 . Here, we find that a complete bipartite Km,n is Km,k -supermagic for 3 ≤ m < n and m ≤ k < n, a book graph Bn is Bk -supermagic for 3 ≤ k < n, a t-fold wheel graph Wn is k-fold wheel Wn -supermagic for n ≥ 3 and 2 ≤ k < t, and a flower graph Fn is C3 -supermagic for n ≡ 3 (mod 4). The method of this research is a literary study. The results show that a complete bipartite graph Km,n admits a Km,k supermagic covering for 3 ≤ m < n and m ≤ k < n, a book graph Bn admts a Bk -supermagic covering for 3 ≤ k < n, a t-fold wheel graph Wn admits a k-fold wheel Wn -supermagic covering for n ≥ 3 and 2 ≤ k < t, and a flower graph Fn admits a C3 -supermagic covering for n ≡ 3 (mod 4). Keywords : H-supermagic covering, complete bipartite graph, book graph, t-fold wheel graph, flower graph
commit to user iv
perpustakaan.uns.ac.id
digilib.uns.ac.id
PERSEMBAHAN
commit to user v
perpustakaan.uns.ac.id
digilib.uns.ac.id
DAFTAR ISI
HALAMAN JUDUL . . . . . . . . . . . . . . . . . . . . . . . . . . . .
i
PENGESAHAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ii
ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iii
ABSTRACT
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iv
PERSEMBAHAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
v
DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vii
DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
I
DAFTAR NOTASI DAN SIMBOL . . . . . . . . . . . . . . . . . . . .
ix
PENDAHULUAN
1
1.1 Latar Belakang Masalah . . . . . . . . . . . . . . . . . . . . . . .
1
1.2 Perumusan Masalah
. . . . . . . . . . . . . . . . . . . . . . . . .
3
1.3 Tujuan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.4 Manfaat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
II LANDASAN TEORI
4
2.1 Tinjauan Pustaka . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2 Teori-Teori Penunjang . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2.1
Pengertian Dasar Graf . . . . . . . . . . . . . . . . . . . .
6
2.2.2
Pemetaan . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2.3
Kelas Graf . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.2.4
Graf Isomorfik . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.2.5
Pelabelan Graf dan Bobot Graf . . . . . . . . . . . . . . .
10
2.2.6
Pelabelan Ajaib . . commit . . . . .to. user . . . . . . . . . . . . . . . .
11
vi
perpustakaan.uns.ac.id
2.2.7
digilib.uns.ac.id
Pelabelan Selimut Ajaib . . . . . . . . . . . . . . . . . . .
12
2.3 Kerangka Pemikiran . . . . . . . . . . . . . . . . . . . . . . . . .
13
III METODE PENELITIAN
14
IV HASIL DAN PEMBAHASAN
15
4.1 Pelabelan Ajaib Super pada Graf Bipartit Lengkap Km,n dengan Selimut-Km,k . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
4.2 Pelabelan Ajaib Super pada Graf Buku Bn dengan Selimut-Bk . .
21
4.3 Pelabelan Ajaib Super pada Graf Roda t-Lipat Wn dengan Selimut Roda k-Lipat Wn . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
4.4 Pelabelan Ajaib Super pada Graf Bunga Fn untuk n ≡ 3 (mod 4) dengan Selimut-C3 . . . . . . . . . . . . . . . . . . . . . . . . . . V PENUTUP
33 38
5.1 Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
5.2 Saran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
DAFTAR PUSTAKA
40
commit to user vii
perpustakaan.uns.ac.id
digilib.uns.ac.id
DAFTAR GAMBAR
2.1 Pelabelan selimut C4 -ajaib super dari graf bipartit lengkap K2,5 .
5
2.2 Graf bipartit lengkap K4,n . . . . . . . . . . . . . . . . . . . . . .
8
2.3 Graf buku Bn . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.4 Graf roda Wn (kiri) dan graf roda 3-lipat Wn (kanan) . . . . . . .
9
2.5 Graf helm Hn (kiri) dan graf bunga Fn (kanan) . . . . . . . . . .
9
2.6 Graf G1 , G2 dan G3 . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.7 Graf G (kiri) dan graf G yang telah diberi bobot (kanan) . . . . .
11
2.8 Pelabelan selimut C3 -ajaib super dari graf roda W4 . . . . . . . .
12
4.1 Graf bipartit lengkap K4,n . . . . . . . . . . . . . . . . . . . . . .
16
4.2 Pelabelan selimut Km,k -ajaib super dari graf bipartit lengkap K4,7
19
4.3 Pelabelan selimut Km,k -ajaib super dari graf bipartit lengkap K4,8
20
4.4 Graf buku Bn . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
4.5 Pelabelan selimut Bk -ajaib super dari graf buku B6 . . . . . . . .
24
4.6 Pelabelan selimut Bk -ajaib super dari graf buku B7 . . . . . . . .
25
4.7 Graf roda 3-lipat Wn . . . . . . . . . . . . . . . . . . . . . . . . .
27
4.8 Pelabelan selimut roda k-lipat W6 ajaib super dari graf roda 5-lipat W6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
4.9 Pelabelan selimut roda k-lipat W6 ajaib super dari graf roda 6-lipat W6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
4.10 Graf Bunga Fn . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
4.11 Graf Bunga F7
commit to user viii
perpustakaan.uns.ac.id
digilib.uns.ac.id
DAFTAR NOTASI DAN SIMBOL
G
:
graf G
G = (V, E)
:
graf G dengan himpunan titik V dan himpunan sisi E
V (G)
:
himpunan titik dari graf G
|V (G)|
:
order atau banyaknya titik dari graf G
E(G)
:
himpunan sisi dari graf G
|E(G)|
:
size atau banyaknya sisi pada graf G
H
:
suatu selimut pada pelabelan
H
:
suatu subgraf pada G yang isomorfik dengan H
H1 , H2 , . . . , Hk
:
keluarga dari subgraf-subgraf G yang berbeda
m(λ)
:
jumlah selimut ajaib
s(λ)
:
jumlah selimut ajaib super
Cn
:
cycle dengan panjang n
Km,n
:
graf bipartit lengkap
K1,n /Sn
:
graf bintang dengan daun sebanyak n
Pn
:
lintasan dengan panjang n
Bn
:
graf buku
Wn
:
graf roda dengan n + 1 titik
Hn
:
graf helm
Fn
:
graf bunga
G1 ∼ = G2
:
graf G1 isomorfik dengan graf G2
G1 G2
:
graf G1 tidak isomorfik dengan graf G2
wt
:
bobot pada suatu graf
λ
:
pelabelan ajaib pada graf G
2
:
akhir bukti
commit to user ix
