DIMENSI METRIK PADA BEBERAPA KELAS GRAF
oleh DWI RIA KARTIKA M0112025
SKRIPSI ditulis dan diajukan untuk memenuhi sebagian persyaratan memperoleh gelar Sarjana Sains Matematika
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SEBELAS MARET SURAKARTA 2016
i
ABSTRAK Dwi Ria Kartika. 2016. DIMENSI METRIK PADA BEBERAPA KELAS GRAF. Fakultas Matematika dan Ilmu Pengetahuan Alam. Universitas Sebelas Maret. Misal G adalah graf connected dengan himpunan vertex V (G) dan himpunan edge E(G). Jarak antara vertex v1 dan v2 pada G yang dinotasikan dengan d(v1 , v2 ) adalah panjang path terpendek antara v1 − v2 . Jika W = {w1 , w2 , ..., wk } adalah subset dari G dan v ∈ V (G) maka representasi dari v terhadap W pasangan k terurut dapat dituliskan r(v | W ) = (d(v, w1 ), d(v, w2 ), ..., d(v, wk )). Himpunan W adalah himpunan pembeda dari G jika untuk setiap dua vertex yang berbeda menghasilkan representasi yang berbeda. Himpunan pembeda dengan kardinalitas terkecil dari V (G) disebut basis untuk G. Jumlah elemen pada basis di G disebut dimensi metrik pada G yang dinotasikan dengan dim(G). Pada penelitian ini, diperoleh dimensi metrik dari graf web Wn , graf friendship fn , graf generalized flower dengan G ∼ = Cm yang dinotasikan F L(G, m, n) dan graf hasil operasi amalgamasi edge Cn dan Km yang dinotasikan Cn ∗2 Km . Diperoleh dimensi metrik dari graf tersebut sebagai berikut. Dim(Wn ) = 2 untuk n ganjil dan dim(Wn ) = 3 untuk n genap, dim(fn ) = n untuk n ≥ 2, dim(F L(G, 3, n)) = 3 untuk n = 2, 3, dim(F L(G, 3, n)) = n untuk n ≥ 4, dim(F L(G, 4, n)) = 2n − 2 untuk n ≥ 4, dim(F L(G, m, n)) = m + 2n − 5 untuk m, n lainnya, dim(Cn ∗2 Km ) = 2 untuk n ≥ 3, m = 2, 3 dan dim(Cn ∗2 Km ) = m − 1 untuk n ≥ 3, m ≥ 3. Kata kunci: dimensi metrik, himpunan pembeda, graf web, graf friendship, graf generalized flower, graf Cn ∗2 Km
iii
ABSTRACT Dwi Ria Kartika. 2016. ON THE METRIC DIMENSION OF SOME FAMILIES OF GRAPHS. Faculty of Mathematics and Natural Sciences. Sebelas Maret University. Let G be a connected simple graph with the vertex set V (G) and the edge set E(G). The distance between vertices v1 and v2 in G, denoted by d(v1 , v2 ) is the length of a shortest v1 − v2 path. If W = {w1 , w2 , ..., wk } is a finite set of vertices of G and v ∈ V (G), then the representation of v with respect to W is the ordered k-pair r(v | W ) = (d(v, w1 ), d(v, w2 ), ..., d(v, wk )). The set W is called a resolving set for G if every two vertices of G have distinct representations. The resolving set with a minimum cardinality of V (G) is called a basis for G. The number of vertices in basis for G is called a metric dimension of G, denoted by dim(G). In this research, we determine the metric dimension of a web graph Wn , a friendship graph fn , a generalized flower graph with G ∼ = Cm , denoted by F L(G, m, n) and a graph resulting from the amalgamation edge operations Cn and Km , denoted by Cn ∗2 Km . We found the metric dimensions of these graphs as follows. Dim(Wn ) = 2 for n odd and dim(Wn ) = 3 for n even, dim(fn ) = n for n ≥ 2, dim(F L(G, 3, n)) = 3 for n = 2, 3, dim(F L(G, 3, n)) = n for n ≥ 4, dim(F L(G, 4, n)) = 2n − 2 for n ≥ 4, dim(F L(G, m, n)) = m + 2n − 5 for m, n others, dim(Cn ∗2 Km ) = 2 for n ≥ 3, m = 2, 3 and dim(Cn ∗2 Km ) = m − 1 for n ≥ 3, m ≥ 3. Keywords: metric dimension, resolving set, web graph, friendship graph, generalized flower graph, Cn ∗2 Km graph
iv
KATA PENGANTAR Puji syukur kepada Tuhan Yang Maha Esa atas limpahan berkat dan rahmatNya sehingga penulis dapat menyelesaikan skripsi ini. Ucapan terima kasih penulis sampaikan kepada 1. Prof. Drs. Tri Atmojo Kusmayadi, M.Sc., Ph.D. sebagai Pembimbing yang telah memberikan bimbingan materi, penulisan dalam skripsi ini, saran dan masukan dalam penulisan skripsi ini, 2. Drs. Siswanto, M.Si. sebagai Pembimbing Akademik atas bantuan dan motivasinya selama proses belajar hingga disusunnya skripsi ini, dan 3. seluruh teman-teman program studi matematika FMIPA UNS khususnya angkatan 2012. Semoga skripsi ini bermanfaat.
Surakarta, Mei 2016
Penulis
v
MOTO
Ketika kamu lelah dan ingin menyerah, ingatlah bahwa ada orang tua yang tidak pernah lelah berjuang demi kamu.
vi
PERSEMBAHAN
Karya ini dipersembahkan untuk kedua orang tua saya, kakak saya, serta teman-teman Program Studi Matematika angkatan 2012 atas segala doa, bantuan, dan motivasi yang telah diberikan selama ini.
vii
DAFTAR ISI
I
HALAMAN PENGESAHAN . . . . . . . . . . . . . . . . . . . . . . .
ii
ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iii
ABSTRACT
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iv
KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . . . .
v
MOTO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
PERSEMBAHAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vii
DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ix
DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . . . . .
x
DAFTAR NOTASI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xi
PENDAHULUAN
1
1.1
Rumusan Masalah . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.2
Tujuan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.3
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 pada Graf . . . . . . . . . . . . . . . . . . . . . .
7
2.2.3
Kelas-Kelas Graf . . . . . . . . . . . . . . . . . . . . . . .
9
2.2.4
Dimensi metrik . . . . . . . . . . . . . . . . . . . . . . . .
12
Kerangka Pemikiran . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.3
III METODE PENELITIAN
16 viii
IV PEMBAHASAN
17
4.1
Dimensi Metrik pada Graf Web . . . . . . . . . . . . . . . . . . .
17
4.2
Dimensi Metrik pada Graf Friendship . . . . . . . . . . . . . . . .
21
4.3
Dimensi Metrik pada Graf Generalized Flower F L(G, m, n) . . . .
23
4.4
Dimensi Metrik pada Graf Cn ∗2 Km . . . . . . . . . . . . . . . .
29
V PENUTUP
33
5.1
Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
5.2
Saran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
DAFTAR PUSTAKA
35
ix
DAFTAR GAMBAR
2.1
Graf A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2
Graf G (kiri) dan komplemen dari graf G (kanan) . . . . . . . . .
8
2.3
Graf G1 ,G2 dan G1 ∪ G2 . . . . . . . . . . . . . . . . . . . . . . .
8
2.4
G1 + G2 dan G1 × G2 . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.5
Operasi amalgamasi vertex G ∗ H dan operasi amalgamasi edge G ∗2 H . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.6
Graf complete Km . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.7
Graf web Wn
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.8
Graf friendship fn . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.9
Graf F L(G, m, n) . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
2.10 Graf Cn ∗2 Km . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
2.11 Graf H . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
4.1
Graf web W3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
4.2
Graf friendship f3 . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
4.3
Graf generalized flower F L(G, 3, 2) . . . . . . . . . . . . . . . . .
28
4.4
Graf C4 ∗2 K5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
x
DAFTAR NOTASI
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
uv
:
edge
(G, u)
:
terdapat vertex v dari graf G
deg (v)
:
degree vertex v
d(u, v)
:
jarak antara vertex u dan v
¯ G
:
komplemen dari graf G
∪
:
operasi union
+
:
operasi join
×
:
operasi cartesian product
∗
:
operasi amalgamasi vertex
∗2
:
operasi amalgamasi edge
∼ =
:
isomorfik
⊂
:
subhimpunan sejati
⊆
:
subhimpunan
∈
:
anggota
⌊x⌋
:
bilangan bulat terbesar yang lebih kecil atau sama dengan x
dim(G) :
dimensi metrik graf G
Pn
: graf lintasan ber-order n
Cn
: graf cycle ber-order n
Kn
:
graf lengkap ber-order n
xi
Wn
:
graf web ber-order 3n
fn
:
graf friendship ber-order 2n + 1
F L(G, m, n) :
graf generalized flower dengan G ∼ = Cm ber-order mn + 1
Cn ∗2 Km
graf hasil operasi amalgamasi edge Cn dan Km ber-order m + n − 2.
:
xii
