perpustakaan.uns.ac.id
digilib.uns.ac.id
PELABELAN SELIMUT (a, d) − CY CLE−TOTAL ANTI AJAIB SUPER PADA GRAF BUNGA MATAHARI, GRAF BROKEN FAN, DAN GRAF GENERALIZED FAN
oleh KHUNTI QONAAH M0111048
SKRIPSI ditulis dan diajukan untuk memenuhi sebagai persyaratan memperoleh gelar Sarjana Sains Matematika
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SEBELAS MARET SURAKARTA 2016 commit to user
i
perpustakaan.uns.ac.id
digilib.uns.ac.id
commit to user
ii
perpustakaan.uns.ac.id
digilib.uns.ac.id
ABSTRAK Khunti Qonaah. 2016. PELABELAN SELIMUT (a, d) − CY CLE−TOTAL ANTI AJAIB SUPER PADA GRAF BUNGA MATAHARI, GRAF BROKEN FAN, DAN GRAF GENERALIZED FAN. Fakultas Matematika dan Ilmu Pengetahuan Alam. Universitas Sebelas Maret. Suatu graf sederhana G = (V (G), E(G)) memuat (a, d) − H−anti ajaib super, jika terdapat fungsi f : V (G) ∪ E(G) → {1, 2, . . . , |V (G)| + |E(G)|}, sedemikian sehingga untuk setiap subgraf H ′ dari∑G yang isomorfik dengan selimut ∑ H, bobot H ′ adalah ω(H ′ ) = v∈V (H ′ ) f (v) + e∈E(H ′ ) f (e) membentuk barisan aritmatika {a, a + d, a + 2d, . . . , a + (t − 1)d} dengan a dan d adalah bilangan bulat positif dan t banyak subgraf dari G yang isomorfik dengan H. Kemudian graf G disebut (a, d) − H−anti ajaib super, jika f (V (G)) = {1, 2, . . . , |V (G)|}. Tujuan penelitian ini adalah menentukan pelabelan selimut (a, d) − H−anti ajaib super pada graf bunga matahari SFn , graf broken fan BF (m, n), dan graf generalized fan Fm,n . Hasil dari penelitian ini diperoleh pelabelan ( 29 n + 9, 1) − 2 C3 −anti ajaib super pada graf bunga matahari SFn dengan n genap ≥ 4, pelabelan (6(m + n) + 9, 1) − C3 −anti ajaib super pada graf broken fan BF (m, n) dengan m ≥ 2 dan n ≥ 2, dan pelabelan ( 23 mn + 92 m + 11 n + 52 , 1) − C3 −anti 2 ajaib super untuk n ganjil dan ( 32 mn + 4m + 11 n + 3, 1) − C3 −anti ajaib super 2 untuk n genap pada graf generalized fan Fm,n dengan m ≥ 3 dan n ≥ 2, serta pelabelan (mn + 92 m + 11 n + 72 , 2) − C3 −anti ajaib super untuk n genap dan 2 (mn + 92 m + 11 n + 3, 2) − C3 −anti ajaib super untuk n ganjil pada graf generalized 2 fan Fm,n dengan m ganjil ≥ 3 dan n ≥ 2. Kata kunci: (a, d)−cycle-anti ajaib super, graf bunga matahari, graf broken fan, graf generalized fan
commit to user
iii
perpustakaan.uns.ac.id
digilib.uns.ac.id
ABSTRACT Khunti Qonaah. 2016. SUPER (a, d) − CY CLE−ANTIMAGIC COVERING ON SUNFLOWER GRAPH, BROKEN FAN GRAPH, AND GENERALIZED FAN GRAPH. Faculty of Mathematics and Natural Sciences, Sebelas Maret University. A simple graph G = (V (G), E(G)) admits a super (a, d) − H−antimagic if there exists a function f : V (G) ∪ E(G) → {1, 2, . . . , |V (G)| + |E(G)|}, such that H ′ of G isomorphic to H, the H ′ weight, ω(H ′ ) = ∑ ∑ for every subgraph v∈V (H ′ ) f (v) + e∈E(H ′ ) f (e) constitutes an arithmatic progession {a, a + d, a + 2d, . . . , a+(t−1)d} where a and d are positive integers and t is the number of subgraphs G isomorfic to H. Furthermore, graph G is a super (a, d) − H−antimagic, if f (V (G)) = {1, 2, . . . , |V (G)|}. This research aims to find super (a, d) − H−antimagic covering on a sunflower graph SFn , a broken fan graph BF (m, n), and a generalized fan graph Fm,n . The results of the research show that a sunflower graph SFn admits a super ( 29 n+9, 1)−C3 −antimagic for n even ≥ 4, a broken fan BF (m, n) admits a super 2 (6(m+n)+9, 1)−C3 −antimagic for m ≥ 2 and n ≥ 2, and a generalized fan graph Fm,n for m ≥ 3 and n ≥ 2 admits a super ( 23 mn+ 92 m+ 11 n+ 25 , 1)−C3 −antimagic 2 for n odd and ( 32 mn+4m+ 11 n+3, 1)−C3 −antimagic for n even, and a generalized 2 fan graph Fm,n for m odd ≥ 3 and n ≥ 2 admits a super (mn + 92 m + 11 n + 27 , 2) − 2 C3 −antimagic for n even and super (mn + 92 m + 11 n + 3, 2) − C3 −antimagic for 2 n odd. Keywords: super (a, d)−cycle-antimagic, sunflower graph, broken fan graph, generalized fan graph
commit to user
iv
perpustakaan.uns.ac.id
digilib.uns.ac.id
PERSEMBAHAN
Skripsi ini saya persembahkan kepada Bapak, Ibu dan kakak-kakakku atas doa, semangat, dan pengorbanan yang diberikan.
commit to user
v
perpustakaan.uns.ac.id
digilib.uns.ac.id
KATA PENGANTAR
Segala puji dan syukur penulis panjatkan kepada Allah SWT yang telah melimpahkan rahmat dan karunia-Nya sehingga skripsi ini dapat selesai. Penulis menyadari bahwa dalam penulisan skripsi ini mendapat bimbingan, dukungan dan bantuan dari berbagai pihak. Oleh karena itu penulis mengucapkan terima kasih kepada 1. Dra. Mania Roswitha, M.Si. sebagai Pembimbing I, yang telah memberikan bimbingan materi dan penulisan dalam skripsi ini, dan 2. Drs. Pangadi, M.Si. sebagai Pembimbing II, yang telah memberikan bimbingan, saran, dan masukan dalam penulisan skripsi ini. Penulis berharap skripsi ini dapat bermanfaat bagi semua pihak.
Surakarta, Agustus 2016
Penulis
commit to user
vi
perpustakaan.uns.ac.id
digilib.uns.ac.id
Daftar Isi
HALAMAN JUDUL . . . . . . . . . . . . . . . . . . . . . . . . . . . .
i
HALAMAN PENGESAHAN . . . . . . . . . . . . . . . . . . . . . . .
iii
ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iii
ABSTRACT
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iv
PERSEMBAHAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
v
KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
I
DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ix
DAFTAR NOTASI DAN SIMBOL . . . . . . . . . . . . . . . . . . . .
x
PENDAHULUAN
1
1.1
Latar Belakang . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Perumusan Masalah
. . . . . . . . . . . . . . . . . . . . . . . . .
2
1.3
Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.4
Manfaat Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . .
3
II LANDASAN TEORI
4
2.1
Tinjauan Pustaka . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2
Teori-teori Penunjang . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2.1
Graf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2.2
Operasi pada Graf . . . . . . . . . . . . . . . . . . . . . .
7
2.2.3
Kelas-Kelas Graf . . . . . . . . . . . . . . . . . . . . . . .
8
2.2.4
Fungsi . . . . . . .commit . . . .to. user . . . . . . . . . . . . . . . . .
10
2.2.5
Graf Isomorfik . . . . . . . . . . . . . . . . . . . . . . . . .
11
vii
perpustakaan.uns.ac.id
2.3
digilib.uns.ac.id
2.2.6
Pelabelan Graf . . . . . . . . . . . . . . . . . . . . . . . .
11
2.2.7
Pelabelan Anti Ajaib . . . . . . . . . . . . . . . . . . . . .
12
2.2.8
Pelabelan Selimut Anti Ajaib . . . . . . . . . . . . . . . .
13
2.2.9
Multihimpunan k−Seimbang . . . . . . . . . . . . . . . . .
14
Kerangka Pemikiran . . . . . . . . . . . . . . . . . . . . . . . . .
15
III METODE PENELITIAN
17
IV HASIL DAN PEMBAHASAN
18
4.1
Lema-lema Pendukung . . . . . . . . . . . . . . . . . . . . . . . .
4.2
Pelabelan (a, d)−C3 −Anti Ajaib Super pada Graf Bunga Matahari SFn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3
19
Pelabelan (a, d) − C3 −Anti Ajaib Super pada Graf Broken Fan BF (m, n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4
18
23
Pelabelan (a, d)−C3 −Anti Ajaib Super pada Graf Generalized Fan Fm,n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
V Penutup
26 35
5.1
Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
5.2
Saran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
DAFTAR PUSTAKA
36
commit to user
viii
perpustakaan.uns.ac.id
digilib.uns.ac.id
Daftar Gambar
2.1
(a) Graf G dan (b) Subgraf dari graf G . . . . . . . . . . . . . . .
6
2.2
Graf H . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.3
Graf I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.4
Graf C4 dan komplemennya C 4 . . . . . . . . . . . . . . . . . . .
7
2.5
Union dan join dari dua graf . . . . . . . . . . . . . . . . . . . .
8
2.6
Graf bunga matahari SF6 . . . . . . . . . . . . . . . . . . . . . .
9
2.7
Graf broken fan BF (2, 3) . . . . . . . . . . . . . . . . . . . . . . .
9
2.8
Graf generalized fan F3,2 . . . . . . . . . . . . . . . . . . . . . . .
10
2.9
Graf G1 isomorfik dengan graf G2 . . . . . . . . . . . . . . . . . .
11
2.10 Pelabelan pada graf C4 . . . . . . . . . . . . . . . . . . . . . . . .
12
4.1
(125, 1) − C3 −anti ajaib super pada graf SF8 . . . . . . . . . . . .
23
4.2
(81, 1) − C3 −anti ajaib super pada graf BF (5, 7)
. . . . . . . . .
26
4.3
(114, 1) − C3 −anti ajaib super pada graf F7,5 . . . . . . . . . . . .
30
4.4
(97, 2) − C3 −anti ajaib super pada graf F7,5 . . . . . . . . . . . .
34
commit to user
ix
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 dari graf G
H
:
suatu selimut dari graf G
H′
:
suatu subgraf dari G yang isomorfik dengan selimut H
H1 , . . . , Hk
:
keluarga subgraf-subgraf G yang berbeda
m(f )
:
jumlah ajaib dari bobot suatu selimut
Cn
:
graf cycle dengan order n
SFn
:
graf bunga matahari dengan order 2n + 1
BF (m, n)
:
graf broken fan dengan order m + n + 1
Km
:
graf lengkap dengan order m
Pn
:
graf lintasan dengan order n
Fm,n
:
graf generalized fan dengan order m + n
Wn
:
graf roda dengan order n + 1
u, v
:
titik
e, uv
:
sisi
G
:
komplemen dari graf G
A∪B
:
operasi gabungan himpunan A dan himpunan B
A+B
:
join dari graf A dengan graf B
A×B
:
hasil kali dari graf A dengan graf B
A⊎B ⊎k i=1 Xi
:
operasi gabungan multihimpunan A dengan B
:
operasi gabungan multihimpunan X1 ⊎ X2 ⊎ . . . ⊎ Xk
∀
:
untuk setiap
∃
:
terdapat
commit to user
x
perpustakaan.uns.ac.id
digilib.uns.ac.id
|X| ∑ X
: banyaknya elemen dari himpunan X
f :A→B
: fungsi dari himpunan A ke himpunan B
G1 ∼ = G2
: graf G1 isomorfik dengan graf G2
[a, b]
: himpuan bilangan bulat positif mulai dari a sampai dengan b
mod
: operasi modulo
2
: akhir bukti
: jumlahan semua elemen dari himpunan X
commit to user
xi
