perpustakaan.uns.ac.id
digilib.uns.ac.id
DIMENSI METRIK PADA GRAF SUN, GRAF HELM DAN GRAF DOUBLE CONES
oleh BANGKIT JOKO WIDODO M0109015
SKRIPSI ditulis dan diajukan untuk memenuhi sebagian persyaratan memperoleh gelar Sarjana Sains Matematika
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SEBELAS MARET SURAKARTA 2013
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 Bangkit Joko Widodo, 2013. DIMENSI METRIK PADA GRAF SUN, GRAF HELM DAN GRAF DOUBLE CONES Fakultas Matematika dan Ilmu Pengetahuan Alam. Universitas Sebelas Maret. Graf G terdiri dari himpunan vertex V (G) = {v1 , v2 , ..., vn } dan himpunan edge E(G) = {e1 , e2 , ..., en }. Suatu graf G dikatakan terhubung jika terdapat lintasan yang menghubungkan setiap vertex pada G. Jarak antara dua vertex u dan v, dinotasikan d(u, v), adalah panjang lintasan terpendek dari vertex u ke v. Misalkan W = {w1 , w2 , ..., wn } adalah subhimpunan vertex-vertex dari graf terhubung G dan v ∈ V (G), representasi vertex v terhadap W didefinisikan sebagai k-pasang terurut r(v|W ) = (d(v, w1 ), d(v, w2 ), ..., d(v, wk )). Himpunan W dikatakan sebagai himpunan pembeda dari G jika untuk setiap dua vertex berbeda x, y ∈ V (G) berlaku r(x|W ) ̸= r(y|W ). Himpunan pembeda dengan kardinalitas terkecil disebut himpunan pembeda minimum atau basis dari G. Sedangkan banyaknya elemen dari suatu basis di G disebut dimensi metrik dari G, dinotasikan Dim(G). Dalam penelitian ini diperoleh dimensi metrik pada graf sun Sn , graf helm Hn dan graf double cones DCn . Kata kunci: dimensi metrik, himpunan pembeda, basis, graf sun, graf helm, graf double cones.
commit to user
iii
perpustakaan.uns.ac.id
digilib.uns.ac.id
ABSTRACT Bangkit Joko Widodo, 2013. METRIC DIMENSION OF SUN GRAPH, HELM GRAPH AND DOUBLE CONES GRAPH. Faculty of Mathematics and Natural Sciences, Sebelas Maret University. Let G be a graph with vertex set V (G) = {v1 , v2 , ..., vn } and edge set E(G) = {e1 , e2 , ..., en }. G is connected if there exists a path connecting every vertex in G. The distance between two vertices u and v, denoted by d(u, v), is the length of a shortest path from u to v in G. Let W = {w1 , w2 , ..., wn } be a subset of vertices in a connected graph G. For v ∈ V (G), a representation of v with respect to W is defined as the k-tuple r(v|W ) = (d(v, w1 ), d(v, w2 ), ..., d(v, wk )). The set W is called a resolving set of G if every two distinct vertices x, y ∈ V (G) satisfy r(x|W ) ̸= r(y|W ). The resolving set of G with minimum cardinality is called a minimum resolving set or basis of G and the cardinality of minimum resolving set is called metric dimension, denoted by Dim(G). In this research, we obtained the metric dimensions of a sun graph Sn , a helm graph Hn and a double cones graph DCn . Keywords: metric dimension, resolving set, basis, sun graph, helm graph, double cones graph.
commit to user
iv
perpustakaan.uns.ac.id
digilib.uns.ac.id
MOTO
Tidak boleh menyerah ketika keadaan sedang sulit.
commit to user
v
perpustakaan.uns.ac.id
digilib.uns.ac.id
PERSEMBAHAN
Karya ini kupersembahkan untuk Kedua orang tuaku, adikku Dyah Kartika Sari dan Viona Natalia yang selalu memberi semangat dan motivasi.
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 senantiasa memberikan rahmat dan hidayah-Nya sehingga penulis dapat menyelesaikan skripsi ini. Dalam penulisan skripsi ini, penulis memperoleh bantuan dari berbagai pihak. Penulis mengucapkan terima kasih kepada Bapak Drs. Tri Atmojo Kusmayadi, M.Sc, Ph.D dan Ibu Sri Kuntari, M.Si. sebagai Pembimbing I dan Pembimbing II yang telah memberikan bimbingan dan arahan baik penulisan maupun materi. Penulis juga mengucapkan terima kasih kepada teman-teman yang senantiasa memberikan dukungan, kritik, dan saran kepada penulis. Penulis berharap semoga skripsi ini dapat memberikan manfaat kepada semua pihak yang membutuhkan.
Surakarta, September 2013
Penulis
commit to user
vii
perpustakaan.uns.ac.id
digilib.uns.ac.id
DAFTAR ISI
HALAMAN JUDUL . . . . . . . . . . . . . . . . . . . . . . . . . . . .
i
PENGESAHAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ii
ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iii
ABSTRACT
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iv
MOTO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
v
PERSEMBAHAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . . . .
vii
DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
I
DAFTAR NOTASI DAN SIMBOL . . . . . . . . . . . . . . . . . . . .
xi
PENDAHULUAN
1
1.1
Latar Belakang Masalah . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Perumusan Masalah
. . . . . . . . . . . . . . . . . . . . . . . . .
2
1.3
Tujuan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.4
Manfaat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
II LANDASAN TEORI
3
2.1
Tinjauan Pustaka . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.2
Landasan Teori . . . . . . . . . . . . . . . . . . . . . . . . . . . .
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
Dimensi metrik . .commit . . . .to. user . . . . . . . . . . . . . . . . .
11
III METODE PENELITIAN
13 viii
perpustakaan.uns.ac.id
digilib.uns.ac.id
IV PEMBAHASAN
14
4.1
Dimensi metrik pada graf sun Sn . . . . . . . . . . . . . . . . . .
14
4.2
Dimensi metrik pada graf helm Hn . . . . . . . . . . . . . . . . .
18
4.3
Dimensi metrik pada graf double cones DCn . . . . . . . . . . . .
26
V PENUTUP
30
5.1
Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2
Graf G (kiri) dan komplemen dari graf G (kanan) . . . . . . . . .
8
2.3
Graf G1 dan G2 (kiri) dan Union G1 dan G2 (kanan) . . . . . . .
8
2.4 Join (kiri) dan product (kanan) dari G1 dan G2 . . . . . . . . . .
9
2.5
Graf sun S4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.6
(a) Graf wheel W4 (b) Graf helm H4 . . . . . . . . . . . . . . . .
10
2.7
Graf double cones DC3 . . . . . . . . . . . . . . . . . . . . . . . .
11
2.8
Graf G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
4.1
Graf sun Sn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
4.2
Graf helm Hn . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
4.3
Graf double cones DCn . . . . . . . . . . . . . . . . . . . . . . . .
26
commit to user
x
perpustakaan.uns.ac.id
digilib.uns.ac.id
DAFTAR NOTASI DAN SIMBOL
G
:
graf G
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)
u, v
:
vertex
e, uv
:
edge
deg v
:
degree dari vertex v
Cn
:
graf cycle dengan order n
Wn
:
graf wheel dengan order n + 1
Fn
:
graf fan dengan order n + 1
An
:
graf antiprism dengan order 2n
A∗n
:
graf antiprism related dengan order 3n
Kn
:
graf lengkap (complete) dengan order n
Kr,s
:
graf complete bipartite dengan order r + s
¯ G
:
komplemen dari graf G
∪
:
operasi union
+
:
operasi join
×
:
operasi product
⊂
:
himpunan bagian
∈
:
anggota
∼ =
:
isomorfik
Sn
:
graf sun dengan order 2n
Hn
:
graf helm dengan order 2n + 1
DCn
:
r(v|W )
:
graf double cones dengan order n + 2 commit to user representasi vertex v terhadap W
xi
