perpustakaan.uns.ac.id
digilib.uns.ac.id
PELABELAN SELIMUT CYCLE -ANTI AJAIB PADA GRAF DOUBLE CONES, GRAF FRIENDSHIP DAN GRAF GRID Pn × P3
oleh SURYA AJI NUGROHO M0109063
SKRIPSI ditulis dan diajukan untuk memenuhi sebagian persyaratan memperoleh gelar Sarjana Sains Matematika
JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SEBELAS MARET
commit to user SURAKARTA 2015
i
perpustakaan.uns.ac.id
digilib.uns.ac.id
commit to user
ii
perpustakaan.uns.ac.id
digilib.uns.ac.id
ABSTRAK Surya Aji Nugroho, 2015. PELABELAN SELIMUT CYCLE - ANTI AJAIB PADA GRAF DOUBLE CONES , GRAF FRIENDSHIP DAN GRAF GRID Pn × P3 . Fakultas Matematika dan Ilmu Pengetahuan Alam. Universitas Sebelas Maret. Sebuah graf sederhana G = (V (G), E(G)) memuat sebuah selimut H jika untuk setiap sisi dalam E(G) merupakan sisi dari suatu subgraf yang isomorfik dengan H. Misal terdapat sebuah fungsi bijektif ξ : V (G) ∪ E(G) → {1, 2, . . . , |V (G)|+|E(G)|} sedemikian sehingga untuk semua subgraf∑H ′ yang iso∑ morfik dengan H, bobot subgraf H ′ adalah w(H ′ ) = v∈V (H ′ ) ξ(v)+ e∈E(H ′ ) ξ(e). Bobot subgraf-subgraf tersebut membentuk barisan aritmatika a, a+d, a+2d, . . . , a + (t − 1)d dengan a dan d adalah bilangan bulat positif dan t adalah jumlah subgraf dari graf G yang isomorfik dengan H. Tujuan dari penelitian ini adalah untuk menentukan pelabelan selimut (a, d)-H-anti ajaib pada graf double cones, graf friendship, dan graf grid Pn × P3 . Hasil dari penelitian ini adalah terdapat pelabelan selimut C3 -anti ajaib pada graf double cones dengan d = 1, pelabelan selimut C3 -anti ajaib pada graf friendship dengan d = 2k − 1, j 2 − j + 2k − 1, (1 − 2k)2 , dan pelabelan selimut C4 -anti ajaib pada graf grid Pn × P3 dengan d = 1, 2, 4. Kata kunci: pelabelan selimut (a, d)-H-anti ajaib, double cones, friendship, grid
commit to user
iii
perpustakaan.uns.ac.id
digilib.uns.ac.id
ABSTRACT Surya Aji Nugroho, 2015. CYCLE-ANTI MAGIC COVERING OF DOUBLE CONES GRAPH, FRIENDSHIP GRAPH AND GRID GRAPH Pn × P3 . Faculty of Mathematics and Natural Sciences, Sebelas Maret University. A simple graph G = (V (G), E(G)) admits an H-covering if every edge in E(G) belongs to a subgraph of G that is isomorphic to H. Let a bijective function ξ : V (G)∪E(G) → {1, 2, . . . , |V (G)|+|E(G)|} all subgraphs ∑ such that for∑ ′ ′ ′ H isomorphic to H, the H -weights w(H ) = v∈V (H ′ ) ξ(v) + e∈E(H ′ ) ξ(e). The weights of the subgraphs constitute an arithmetic progression a, a + d, a + 2d, . . . , a + (t − 1)d where a and d are positive integers and t is the number of subgraphs of G isomorphic to H. The aim of this research is to study (a, d)-H-anti magic covering on double cones, friendship, and grid Pn × P3 . The results of this research are as follows. A double cones is (a, d)-C3 -anti magic with d = 1, a friendship is (a, d)-Ck -anti magic with d = 2k − 1, j 2 − j + 2k − 1, (1 − 2k)2 , and a grid Pn × P3 is (a, d)-C4 -anti magic with d = 1, 2, 4. Keywords: (a, d)-H-anti magic covering, double cones, friendship, grid
commit to user
iv
perpustakaan.uns.ac.id
digilib.uns.ac.id
MOTO
Bergerak untuk membuat orang lain tergerak.
commit to user
v
perpustakaan.uns.ac.id
digilib.uns.ac.id
PERSEMBAHAN
Karya ini saya persembahkan untuk bapak saya, Juwari dan mamak saya, Sri Hartini dan Agen Maria Hill.
commit to user
vi
perpustakaan.uns.ac.id
digilib.uns.ac.id
KATA PENGANTAR
Puji syukur kehadirat Allah SWT, raja semesta alam atas segala kemudahan dan karunia-Nya yang diberikan, akhirnya penulis dapat menyelesaikan laporan skripsi dengan baik dan lancar. Penulis menyadari bahwa penulisan laporan skripsi ini banyak mengalami kesulitan, namun berkat bantuan, petunjuk, dan bimbingan dari berbagai pihak baik moril maupun materiil, kesulitan-kesulitan dapat terselesaikan dengan baik. Oleh karena itu, dengan segala ketulusan dan kerendahan hati, penulis ingin mengucapkan terima kasih kepada Dra. Mania Roswitha, M. Si., pembimbing I dan Titin Sri Martini, S.Si., M.Kom., pembimbing II. Akhir kata, penulis berharap semoga laporan ini dapat memberikan manfaat bagi seluruh pihak yang membutuhkan. Surakarta, Januari 2015 Penulis
commit to user
vii
perpustakaan.uns.ac.id
digilib.uns.ac.id
DAFTAR ISI
I
HALAMAN JUDUL . . . . . . . . . . . . . . . . . . . . . . . . . . . .
i
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Perumusan Masalah
. . . . . . . . . . . . . . . . . . . . . . . . .
2
1.3
Tujuan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.4
Manfaat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
II LANDASAN TEORI
4
2.1
Tinjauan Pustaka . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2
Landasan Teori . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2.1
Pengertian Dasar Graf . . . . . . . . . . . . . . . . . . . .
5
2.2.2
Operasi-Operasi pada Graf . . . . . . . . . . . . . . . . . .
7
2.2.3
Kelas-Kelas Graf . . . . . . . . . . . . . . . . . . . . . . .
8
2.2.4
commit to user Pelabelan Selimut Anti Ajaib . . . . . . . . . . . . . . . .
10
2.2.5
Batas Atas d pada Pelabelan Selimut Anti Ajaib . . . . . .
11
viii
perpustakaan.uns.ac.id
2.3
digilib.uns.ac.id
2.2.6
Teknik Multihimpunan k-seimbang . . . . . . . . . . . . .
11
2.2.7
Teknik Multihimpunan (k, δ)-anti seimbang . . . . . . . .
12
Kerangka Pemikiran . . . . . . . . . . . . . . . . . . . . . . . . .
12
III METODE PENELITIAN
14
IV PEMBAHASAN
15
4.1
Pelabelan (a, d) - C3 - Anti Ajaib pada Graf Double Cones . . . .
20
4.2
Pelabelan (a, d) - Ck - Anti Ajaib pada Graf Friendship . . . . . .
22
4.3
Pelabelan (a, d) - C4 - Anti Ajaib pada Graf Grid . . . . . . . . .
26
V PENUTUP
31
5.1
Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
5.2
Saran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
DAFTAR PUSTAKA
32
commit to user
ix
perpustakaan.uns.ac.id
digilib.uns.ac.id
DAFTAR GAMBAR
2.1
Graf G dan graf H yang merupakan subgraf dari graf G . . . . . .
6
2.2
Graf G1 dan graf G2 yang isomorfik . . . . . . . . . . . . . . . . .
6
2.3
Graf G1 yang memiliki sisi ganda dan graf G2 yang memiliki loop
7
2.4
Graf dan komplemennya . . . . . . . . . . . . . . . . . . . . . . .
8
2.5
Union, join, dan product dari G1 dan G2 , dilambangkan dengan G3 = G1 ∪ G2 , G4 = G1 + G2 , dan G5 = G1 × G2 . . . . . . . . .
9
2.6
Graf double cones DCn dengan n = 4 dan n = 5 . . . . . . . . . .
10
2.7
Graf friendship Dkn dengan k = 3, n = 3 dan n = 4 . . . . . . . .
10
2.8
Graf grid P3 × P4 dan P3 × P5 . . . . . . . . . . . . . . . . . . . .
10
4.1
Pelabelan (52, 1)-C3 -anti ajaib pada graf double cones DC5 . . . .
22
4.2
Pelabelan (99, 7)-C4 -anti ajaib pada graf friendship D44 . . . . . .
25
4.3
Pelabelan (81, 19)-C4 -anti ajaib pada graf friendship D44 . . . . . .
25
4.4
Pelabelan (36, 49)-C4 -anti ajaib pada graf friendship D44 . . . . . .
26
4.5
Pelabelan (160, 1)-C4 -anti ajaib pada graf Pn × P3 . . . . . . . . .
28
4.6
Pelabelan (190, 2)-C4 -anti ajaib pada graf Pn × P3 . . . . . . . . .
29
4.7
Pelabelan (151, 4)-C4 -anti ajaib pada graf Pn × P3 . . . . . . . . .
30
commit to user
x
perpustakaan.uns.ac.id
digilib.uns.ac.id
DAFTAR NOTASI
V (G)
: himpunan titik dari graf G
E(G)
: himpunan sisi dari graf G
|V (G)| = vG
: banyaknya titik dari graf G (order )
|E(G)| = eG
: banyaknya sisi dari graf G (size)
u, v
: titik
e = (u, v)
:
⊆
: himpunan bagian
G
: komplemen dari graf G
G1 ∼ = G2
: graf G1 isomorfik dengan graf G2
G1 ∨ G2
:
G1 join G2
G1 × G2
:
G1 product G2
ξ, ϕ
: fungsi bijektif
Cn
: graf cycle dengan order n
Pn
: graf lintasan (path) dengan order n
DCn
: graf double cones dengan order n pada Cn
Dkn
: graf friendship dengan n cycle
≡
: kongruen
mod
: operasi modulo
∪
: operasi union
⊎
: operasi union plus
sisi yang ujung-ujungnya adalah titik u dan v
commit to user
xi
