PELABELAN HARMONIOUS PADA GRAF TANGGA DAN GRAF KIPAS
Abstract
Pelabelan harmonious pada graf G dengan n titik dan m sisi adalah suatu
pemetaan satu-satu (injektif) dari himpunan titik V(G) ke himpunan bilangan bulat tak
negatif {0,1,2,3,…,m-1} sehingga setiap sisinya mendapat label penjumlahan dari
label titik yang bersisian pada sisi tersebut dalam bilangan modulo (m) yang berbeda
semua, yaitu: f(e)=f(uv)=[f(u)+f(v)] mod (m), dimana u dan v adalah titik yang
bersisian pada sisi tersebut. Sebuah graf G dikatakan harmonious jika dapat dilabeli
menurut aturan pelabelan harmonious. Tujuan penulisan skripsi ini adalah untuk
mengetahui apakah graf tangga dan graf kipas merupakan graf harmonious atau
bukan. Jika graf tangga dan graf kipas merupakan graf harmonious, maka
bagaimanakah perumusan pola titik dan sisinya. Graf tangga merupakan graf hasil
kali kartesius dari graf lintasan P
n
dan graf lintasan P
2
, yaitu
PP
merupakan graf yang dibentuk dari graf lintasan P
n
n
dan satu titik yang disebut titik
pusat yang adjacent dengan semua titik pada graf lintasan P
.
Metode yang digunakan dalam penelitian ini adalah metode deskriptif
aksiomatik yaitu pemaparan definisi dalam pelabelan harmonious yang digunakan
untuk menyelidiki apakah graf tangga dan graf kipas memungkinkan untuk dilabeli
dengan aturan pelabelan harmonious. Selanjutnya jika graf-graf tersebut
memungkinkan untuk dilabeli dengan aturan pelabelan harmonious, maka akan
dilanjutkan dengan metode Trial and Error. Metode Trial and Error yaitu mencoba
kemungkinan yang ada dalam melabeli titik pada graf tangga dan graf kipas dengan
n
2
. Graf kipas f
n
aturan pelabelan harmonious. Selanjutnya jika ditemukan label yang memenuhi
aturan pelabelan harmonious, maka dilanjutkan dengan metode pendeteksian pola,
dimana metode ini digunakan untuk merumuskan pola pelabelannya.
Diperoleh hasil bahwa graf tangga L
untuk n≥3 merupakan graf harmonious.
Rumusan pola titik u
f(u
f(v
i
i
)=
)=
sisi a
f(a
i
)=
2
1i
i
dan v
i
viii
n
pada graf tangga L
untuk i=1,3,5,…,n; f(u
2
23 in
i
, b
i
untuk i=1,3,5,…,n; f(v
dan c
i
n
2
1
i=1,2,3,...,n; f(c
dan v
i
i
i
)=
pada graf tangga L
i
)=
2
22 in
n
n
untuk n ganjil dengan n≥3 adalah
22
1 in
untuk i=2,4,6,…,n-1;
untuk i=2,4,6,…,n-1. Rumusan pola
untuk n ganjil dengan n≥3 adalah
mod(3n-2) untuk i=1,2,3,...,n-1; f(b
i
)=
i
n
2
35
pada graf tangga L
i
)=
i
n
2
)1(3
mod (3n-2) untuk
mod (3n-2) untuk i=1,2,3,...,n-1. Rumusan pola titik u
n
untuk n=4 adalah f(u
i
)={0,5,1,9} dan f(v
)={2,6,3,4}.
Rumusan pola sisi a
i
, b
i
dan c
i
pada graf tangga L
n
untuk n=4 adalah f(a
)={5,6,0},
f(a
L
n
i
)={2,1,4,3} dan f(a
i
)={8,9,7}. Rumusan pola titik titik u
untuk n genap dengan n≥6 untuk i=1,2,3 adalah f(u
untuk i=1; f(u
i
)=
1n
dan f(v
untuk i=3. Rumusan pola sisi a
n≥6 untuk i=1,2,3 adalah f(a
f(c
f(c
i
i
)=
)=
dan f(c
2
67n
2
109n
i
tangga L
)=
n
i
i
)=
, b
mod(3n-2) untuk i=1; f(a
i
i
mod(3n-2) untuk i=2; f(a
2
69n
2
43n
dan c
)=
i
untuk i=2; f(u
i
pada graf tangga L
2
87n
)=
mod(3n-2); f(b
2
47n
i
)=
i
i
i
dan v
)=
)=
mod(3n-2), f(b
2
25n
i
2
65n
2
25n
n
)=
i
i
i
i
pada graf tangga
dan f(v
dan f(v
i
i
)=
)=
12n
33n
untuk n genap dengan
2
89n
)=
mod(3n-2), f(b
mod(3n-2) untuk i=3. Rumusan pola titik titik u
untuk n genap dengan n≥6 untuk i=4,5,6,…,n adalah f(u
2
45n
i
)=
i
mod(3n-2) dan
mod(3n-2) dan
2
811n
dan v
i
i
)=
mod(3n-2)
pada graf
i
2
2
dan
i
f(v
i
)=
22
43 in
untuk i=4,6,8,…,n; f(u
i=5,7,9,…,n-1. Rumusan pola sisi a
dengan n≥6 untuk i=4,5,6,…,n adalah f(a
(3n-2) dan f(c
i
)=
2
825 in
hasil bahwa graf kipas f
n
ix
i
i
, b
)=
i
2
2 in
dan c
i
)=
i
2
1
dan f(v
i
)=
pada graf tangga L
i
n
3
2
mod (3n-2), f(b
mod (3n-2). Demikian juga untuk graf kipas f
2
43
)3(
n
n
untuk
i
n
untuk n genap
)=
2
823 in
untuk n≥2 adalah graf harmonious. Rumusan pola titik v
pada graf kipas f
f(v
i
)=
2
1 in
pola sisi a
f(a
i
)=
2
2in
i
2
1
n
untuk n ganjil dengan n≥3 adalah f(v
untuk i=1,3,5,…,n dan f(v
, dan b
i
pada graf kipas f
i
)=
n
n
untuk i=2,4,6,…,n-1. Rumusan
2
2i
i
n
mod
, diperoleh
)=0 untuk i=0;
untuk n ganjil dengan n≥3 adalah
mod (2n-1) untuk i=1,3,5,…,n; f(a
i=2,4,6,…,n-1 dan f(b
titik v
f(v
i
)=
i
pada graf kipas f
2
in
pola sisi a
f(a
i
)=
2
1
2
1in
i
i
)=
2
323 in
n
i
)=
2
22 in
mod (2n-1) untuk
mod (2n-1) untuk i=1,2,3,…,n-1. Rumusan pola
untuk n genap dengan n≥2 adalah f(v
untuk i=1,3,5,…,n-1 dan f(v
, dan b
i
pada graf kipas f
i
n
)=
n
untuk i=2,4,6,…,n. Rumusan
2
2i
i
)=0 untuk i=0,
untuk n ganjil dengan n≥3 adalah
mod (2n-1) untuk i=1,3,5,…,n-1; f(a
i=2,4,6,…,n dan f(b
i
)=
2
223 in
i
)=
2
22 in
mod (2n-1) untuk i=1,2,3,…,n-1.