DIMENSI PARTISI PADA GRAF ANTIPRISMA, GRAF MONGOLIAN TENT, DAN GRAF STACKED BOOK
oleh TIA APRILIANI M0112086
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 Tia Apriliani, 2016. DIMENSI PARTISI PADA GRAF ANTIPRISMA, GRAF MONGOLIAN TENT, DAN GRAF STACKED BOOK . Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Sebelas Maret. Misal G adalah graf terhubung dengan himpunan vertex V (G) dan S adalah himpunan bagian dari V (G). Jarak d(v, S) antara vertex v dan S di G adalah minimum jarak dari vertex v terhadap setiap vertex di S. Himpunan partisi Π disebut sebagai partisi pembeda dari graf G jika setiap vertex pada G memiliki jarak yang berbeda terhadap vertex di himpunan partisi Π. Kardinalitas minimum dari partisi pembeda disebut dimensi partisi. Graf antiprisma adalah graf reguler ber-degree 4 dengan jumlah vertex dan edge berturut-turut sebanyak 2n dan 4n. Tersusun atas Cn luar dan dalam, kemudian diantara keduanya dihubungkan oleh dua buah edge. Graf Mongolian tent adalah graf hasil kali Cartesian Pm × Pn , n bilangan ganjil, dan menambahkan satu vertex di atas grid kemudian menggabungkan setiap vertex ganjil pada baris pertama Pm × Pn dengan vertex tersebut. Graf stacked book adalah suatu graf hasil kali Cartesian Sm × Pn dengan Sm adalah graf bintang dengan m + 1 vertex dan Pn adalah path dengan n vertex. Dalam penelitian ini ditentukan dimensi partisi pada graf antiprisma, graf Mongolian tent, dan graf stacked book. Hasil penelitian menyatakan bahwa dimensi partisi pada graf antiprisma An adalah 4 untuk n ≥ 3. Dimensi partisi pada graf Mongolian tent terdiri dari empat kasus. Kasus pertama, pd(Mm,n ) adalah 3 untuk m ≥ 2, n = 3, 5; untuk m ≥ 2, n ≡ 1 mod 6, diperoleh pd(Mm,n ) adalah n+5 ; untuk m ≥ 2, 3 n ≡ 3 mod 6, diperoleh pd(Mm,n ) adalah n+3 ; dan untuk m ≥ 2, n ≡ 5 mod 6, 3 n+4 diperoleh pd(Mm,n ) adalah 3 . Diperoleh dimensi partisi pada graf stacked book Bm,n adalah m untuk m ≥ 3, n ≥ 2. Kata kunci: dimensi partisi, partisi pembeda, graf antiprisma, graf Mongolian tent, graf stacked book
iii
ABSTRACT Tia Apriliani, 2016. ON THE PARTITION DIMENSION OF AN ANTIPRISM GRAPH, A MONGOLIAN TENT GRAPH, AND A STACKED BOOK GRAPH. Faculty of Mathematics and Natural Sciences, Sebelas Maret University. Let G be a connected graph with vertex set V (G) and S is a subset in V (G). The distance d(v, S) between v and S is the minimum distance from v to every vertex in S. k-partition Π is called as resolving partition of G if every vertex in G have unique distance with respect to vertex in Π. The minimum cardinality of resolving partition is called a partition dimension. An antiprism graph is a 4-regular graph with 2n vertices and 4n edges. It consists of outer and inner Cn , while the two cycles connected by two edges. A Mongolian tent graph is the graph obtained from the graph Cartesian product Pm × Pn for odd n by adding an extra vertex above the graph and joining every other vertex of the top row to the additional vertex. A stacked book graph Bm,n for m ≥ 3, n ≥ 2 is defined as the graph Cartesian product Sm × Pn where Sm is a star graph and Pn is the path graph on m + 1 and n vertices, respectively. In this research, we determine the partition dimension of an antiprism graph, a Mongolian tent graph, and a stacked book graph. We obtain the results of this research as follows. The partition dimension of an antiprism graph An is 4 for n ≥ 3. The partition dimension of a Mongolian tent graph consists of four cases. The first case, pd(Mm,n ) is 3 for m ≥ 2, n = 3, 5; for m ≥ 2, n ≡ 1 mod 6, we have pd(Mm,n ) is n+5 ; for m ≥ 2, n ≡ 3 mod 6, we 3 n+3 obtain pd(Mm,n ) is 3 ; and the last case for m ≥ 2, n ≡ 5 mod 6, we obtain pd(Mm,n ) is n+4 . We obtain the partition dimension of a stacked book graph 3 Bm,n is m for m ≥ 3, n ≥ 2. Keywords : partition dimension, resolving partition, antiprism graph, Mongolian tent graph, stacked book graph
iv
PERSEMBAHAN
Karya ini kupersembahkan untuk ibu, bapak, adik, dan sahabat-sahabatku.
v
MOTO
Jika kamu berani bermimpi maka kamu harus berani mewujudkannya.
vi
KATA PENGANTAR
Bismillahirrahmanirrahim, Segala puji bagi Allah SWT atas segala rahmat dan hidayah-Nya, sehingga penulis dapat menyelesaikan skripsi ini. Sholawat serta salam selalu dihaturkan kepada Nabi Muhammad SAW. Penulis menyadari bahwa terwujudnya skripsi ini berkat dorongan, dukungan dan bimbingan dari berbagai pihak. Oleh karena itu penulis menghaturkan terima kasih kepada semua pihak yang telah membantu dalam penulisan skripsi ini, terutama kepada 1. Prof. Drs. Tri Atmojo Kusmayadi, M.Sc. Ph.D. sebagai Pembimbing yang telah memberikan bimbingan sehingga penulis dapat menyelesaikan skripsi ini, dan 2. Ardina Rizqy Rachmasari, Dwi Ria Kartika, dan Eka Ferawati sebagai teman diskusi yang telah membantu dan senantiasa memberikan semangat dalam menyelesaikan skripsi ini. Penulis berharap semoga skripsi ini dapat bermanfaat bagi semua pembaca.
Surakarta, Mei 2016
Penulis
vii
DAFTAR ISI
I
PENGESAHAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ii
ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iii
ABSTRACT
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iv
PERSEMBAHAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
v
MOTO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . . . .
vii
DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ix
DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . . . . .
x
DAFTAR NOTASI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xi
PENDAHULUAN
1
1.1
Latar Belakang Masalah . . . . . . . . . . . . . . . . . . . . . . .
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 pada Graf . . . . . . . . . . . . . . . . . . . . . .
7
2.2.3
Kelas-Kelas Graf . . . . . . . . . . . . . . . . . . . . . . .
8
2.2.4
Dimensi Partisi . . . . . . . . . . . . . . . . . . . . . . . .
10
Kerangka Pemikiran . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.3
viii
III METODE PENELITIAN
13
IV PEMBAHASAN
14
4.1
Dimensi Partisi pada Graf Antiprisma . . . . . . . . . . . . . . .
14
4.2
Dimensi Partisi pada Graf Mongolian Tent . . . . . . . . . . . . .
16
4.3
Dimensi Partisi pada Graf Stacked Book . . . . . . . . . . . . . .
25
V PENUTUP
29
5.1
Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
5.2
Saran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
DAFTAR PUSTAKA
30
ix
DAFTAR GAMBAR
2.1
Graf G merupakan graf terhubung . . . . . . . . . . . . . . . . . .
6
2.2
(a) Graf G1 dan G2 dan (b) union G1 dan G2 . . . . . . . . . . .
7
2.3
(a) join G1 dan G2 dan (b) hasil kali Cartesian G1 dan G2 . . . .
8
2.4
Graf antiprisma An . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.5
Graf Mongolian tent Mm,n . . . . . . . . . . . . . . . . . . . . . .
9
2.6
Graf stacked book Bm,n . . . . . . . . . . . . . . . . . . . . . . . .
10
2.7
Path P4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
4.1
Graf antiprisma A4 . . . . . . . . . . . . . . . . . . . . . . . . . .
15
4.2
Graf Mongolian tent M3,3 . . . . . . . . . . . . . . . . . . . . . .
24
4.3
Graf stacked book B3,3 . . . . . . . . . . . . . . . . . . . . . . . .
27
x
DAFTAR NOTASI
G
:
graf G
u, v
:
vertex
e
:
edge
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)
deg(v)
:
degree vertex v dari graf G
d(u, v)
:
jarak dari vertex u ke v pada graf G
d(v, S)
:
jarak dari vertex v terhadap himpunan bagian S pada graf G
∪
:
operasi union
+
:
operasi join
×
:
operasi hasil kali Cartesian
⊆
:
himpunan bagian
∈
:
anggota
⌈x⌉
:
bilangan bulat terkecil yang lebih besar atau sama dengan x (ceiling)
⌊x⌋
: bilangan bulat terbesar yang lebih kecil atau sama dengan x (flooring)
Si
:
kelas partisi ke-i
Π
:
partisi pembeda
|Π|
:
kardinalitas dari partisi pembeda
r(v|Π)
:
representasi jarak setiap vertex v terhadap Π
dim(G) :
dimensi metrik pada graf G
pd(G)
:
dimensi partisi pada graf G
Pn
: graf lintasan ber-order n
xi
Kn
: graf lengkap ber-order n
Cn
:
graf cycle ber-order n
Kr,s
:
graf bipartit lengkap ber-order r + s
Sm
:
graf bintang ber-order m + 1
An
:
graf antiprisma ber-order 2n
Mm,n
:
graf Mongolian tent ber-order mn + 1
Bm,n
:
graf stacked book ber-order mn + n
xii
