PELABELAN TOTAL TITIK AJAIB GRAF HASIL KALI KARTESIUS DARI GRAF SIKEL Maria Nita Kurniasari1 dan Robertus Heri2 1,2 Program Studi Matematika F.MIPA UNDIP Semarang Jl. Prof.Sudarto, S.H, Tembalang-Semarang Abstract. A vertex-magic total labeling of graph , with the vertices and the edges is the bijection from to the set of integers , and for each vertex in satisfying , is the vertex that adjacent with , then named a magic constant in . The sum of the label of and the labels of all edges incident to the is the same for all vertices of and named vertex-magic total graph. Vertex-magic total labeling of cartesian products of cycles, with the type , with and is odd are the labeling to the and the concept used to label is -vertex antimagic total labeling and to label it is used vertex magic total labeling of cycles, with the cycle is odd. Keywords : vertex-magic total labeling, cycle, cartesian products.
total tak beraturan, pelabelan ajaib, dan
1. PENDAHULUAN Pelabelan graf merupakan suatu pemetaan satu-satu yang memetakkan
ajaib
himpunan dari elemen-elemen graf ke
pelabelan, diantaranya adalah pelabelan
himpunan
positif,
total titik ajaib, pelabelan total sisi ajaib,
elemen-elemen graf itu sendiri meliputi
pelabelan total titik ajaib super, dan
himpunan
pelabelan
bilangan
titik,
bulat
himpunan
sisi,
terdapat
beberapa
total
sisi
ajaib
macam
super,
himpunan titik dan sisi. Pelabelan titik
sedangkan pada pelabelan anti ajaib
adalah
terdapat pelabelan total titik anti ajaib
pelabelan
graf
dimana
domainnya merupakan himpunan titik, pelabelan sisi adalah pelabelan graf dimana
domainnya
merupakan
dan pelabelan total sisi anti ajaib. Aplikasi dijumpai
pelabelan
dalam
graf
dapat
berbagai
bidang
dekomposisi
graf,
himpunan sisi, sedangkan pelabelan
diantaranya
total
merupakan
kriptografi, kristalografi x-ray, teori
gabungan himpunan titik dan sisi.
koding (coding theory), radar, disain
Terdapat beberapa jenis pelabelan pada
sirkuit dan disain jaringan komunikasi.
jika
domainnya
pelabelan
Pada artikel ini materi yang akan
gracefull, pelabelan harmoni, pelabelan
dikaji adalah mengenai pelabelan total
graf,
52
pelabelan anti ajaib. Dalam pelabelan
diantaranya
adalah
Jurnal Matematika Vol. 13, No.1, April 2010 : 52-60
titik ajaib pada graf hasil kali kartesius dari graf sikel, dimana graf yang akan dikaji disini adalah graf dengan sifat tidak terbatas, sederhana dan tidak
dengan k adalah suatu konstanta ajaib dan
adalah jumlah seluruh
berarah. Kelas graf yang akan dibahas
label sisi pada graf G.
merupakan kelas graf reguler, yaitu graf
Bukti :
yang derajat setiap titiknya adalah sama.
Misalkan
merupakan
jumlah
seluruh label titik pada graf G, maka 2. PEMBAHASAN a. Pelabelan total titik ajaib Diberikan graf titik
dengan himpunan
dan himpunan sisi
merupakan ke
pemetaan bilangan
. Jika
bijektif
titik yang berbeda, maka setiap label
dari
sisi akan dijumlahkan dengan kedua
positif
label titik yang adjacent pada sisi
merupakan
tersebut dan label setiap titik berbeda,
bulat
maka
pelabelan total titik ajaib dengan bobot pada titik x
Karena setiap sisi incident pada dua
diperoleh
didefinisikan sebagai : (1)
dengan titik
adalah titik yang
adjacent dengan titik
, maka
Teorema 2.2 Misalkan G sebuah graf
merupakan pelabelan total titik ajaib
dengan v titik dan e sisi. Jika G adalah
jika terdapat konstanta
graf total titik ajaib, maka konstanta
jadi untuk
setiap titik , nilai dari dimana ajaib dan
=
,
ajaib
terbatas dan berlaku
merupakan suatu konstanta disebut graf total titik Bukti :
ajaib. b. Batas-batas Konstanta Ajaib
Dari Lemma 2.1 diperoleh :
Lemma 2.1 Jika G adalah sebuah graf total titik ajaib dengan banyaknya titik
dan banyaknya sisi , maka 53
Maria Nita, Robertus Heri, SU (Pelabelan Total Titik Ajaib Graf Hasil Kali Kartesius dari Graf Sikel)
minimum akan diperoleh
Untuk suatu graf sikel dengan
jika 1 sampai e merupakan label sisi,
ganjil mempunyai bentuk pelabelan
sehingga diperoleh
sebagai berikut ,
untuk ,
untuk genap Sedangkan diperoleh
maksimum akan apabila
sampai
merupakan label sisi, sehingga diperoleh
,
untuk ganjil dengan merupakan titik pada graf sikel dan
merupakan sisi.
Teorema 2.3 Untuk setiap maka
graf
sikel
ganjil
mempunyai
pelabelan total titik ajaib dengan
Dengan demikian diperoleh bahwa
konstanta ajaib Bukti : Jika n ganjil, akan dibuktikan graf sikel mempunyai pelabelan total titik Jadi diperoleh bahwa konstanta ajaib terbatas pada interval
ajaib. Diambil
merupakan bilangan bulat
positif ganjil. Karena c. Pelabelan Total Titik Ajaib pada Graf Sikel dengan
Ganjil
ganjil, maka
pasti bilangan bulat positif. Dari Teorema 1 diperoleh
Graf sikel adalah graf yang memuat sikel tunggal. Graf sikel dengan dilambangkan
dengan
,
titik
dengan
bilangan bulat positif. Untuk setiap graf sikel
54
berlaku
maka
untuk diperoleh
dimana
Jurnal Matematika Vol. 13, No.1, April 2010 : 52-60
dan
3)
, untuk Untuk
Untuk
n
ganjil,
graf
sikel
Cn
mempunyai bentuk pelabelan sebagai
Untuk
berikut : ,
untuk
dilihat
bahwa
setiap
titik
maupun sisi pada graf Cn mempunyai ,
untuk genap
label
yang
berbeda,
sehingga
memenuhi pemetaan injektif Dari hasil diatas telah diketahui bahwa
,
untuk ganjil Akan dibuktikan
Dapat
pemetaan bahwa
bentuk
pelabelan diatas memenuhi pemetaan bijektif
merupakan injektif dan
domain
dari
adalah
pemetaan
himpunan titik dan sisi, sedangkan kodomain
berupa ,
dengan
himpunan n
merupakan
Sebelumnya akan dibuktikan bahwa
panjang sikel pada graf Cn, sehingga
bentuk pelabelan diatas memenuhi
banyak anggota domain sama dengan
pemetaan injektif
banyak anggota kodomain atau dapat
Diambil
dengan
ditulis =
1)
, Untuk
berhingga Karena pemetaan tersebut injektif dan Untuk 2) Untuk
banyak anggota domain sama dengan banyak
anggota
terbukti
bahwa
adalah
pemetaan
pelabelannya Untuk
kodomain, pemetaan
tersebut
surjektif
memenuhi
maka
maka
pemetaan
surjektif.
55
Maria Nita, Robertus Heri, SU (Pelabelan Total Titik Ajaib Graf Hasil Kali Kartesius dari Graf Sikel)
Karena
memenuhi
pemetaan
dimana
y
merupakan
titik
yang
injektif dan surjektif, maka pemetaan
adjacent dengan titik x. Pemetaan λ
tersebut merupakan pemetaan bijektif.
disebut sebagai pelabelan total titik anti
Selanjutnya untuk membuktikan bahwa
ajaib jika semua titik mempunyai
setiap titik pada pelabelan tersebut
konstanta ajaib yang berbeda dan
mempunyai konstanta ajaib yang sama,
himpunan konstanta ajaib dari semua
maka dengan menggunakan persamaan
titik
(1) diperoleh konstanta ajaib pada
aritmatika dengan suku pertama a dan
adalah
beda d. Jadi himpunan konstanta ajaib
-
yang
Untuk i genap
membentuk
suatu
barisan
terbentuk
adalah , untuk suatu
bilangan bulat positif a dan d, dimana -
Untuk i ganjil
dan Pelabelan total titik anti ajaib
-
pada graf
Untuk i = 0
dapat membentuk
pelabelan total titik ajaib dengan konstanta ajaib dengan Terlihat
bahwa
setiap
) jika nilai
.
titiknya
mempunyai konstanta ajaib yang sama,
e. Pelabelan Total Titik Anti Ajaib (a,d)
sehingga pelabelan tersebut merupakan
pada Graf Sikel
pelabelan total titik ajaib dengan
Teorema 2.4 Jika a dan b merupakan
konstanta ajaib
bilangan bulat positif, dan
k=
suatu bilangan bulat, maka terdapat suatu
d. Pelabelan Total Titik Anti Ajaib
pelabelan
total
dengan bobot titik x
didefinisikan sebagai
adalah
anti
ajaib
, dimana
merupakan label
ke himpunan bilangan bulat positif
titik pada
Suatu pemetaan bijektif λ dari
titik
dan
merupakan label sisi.
Bukti : 56
( atau biasa disebut
Jurnal Matematika Vol. 13, No.1, April 2010 : 52-60
Misalkan
merupakan suatu graf sikel
dengan titik
, dengan
dan sisi
dimana
bentuk
dan
sikel yang pertama disimbolkan dengan 3,
merupakan
himpunan bilangan bulat positif dan graf sikel yang kedua disimbolkan
pelabelannya sebagai berikut
dengan Cn, dengan
3,
merupakan
himpunan bilangan bulat positif ganjil,
untuk
sehingga bentuk umum dari graf hasil kali kartesius dari graf sikel adalah Cm
untuk
Cn. Istilah lain dari graf Cm untuk
Cn
adalah Torus Grids atau biasa disebut
Akan dibuktikan bahwa pelabelan diatas
juga Toroidal Grids.
memenuhi -
g. Pelabelan Total Titik Ajaib Graf
Untuk
Hasil Kali Kartesius dari graf sikel Pada pelabelan total titik ajaib graf hasil kali kartesius dari graf sikel, yaitu -
graf dengan bentuk umum Cm
Untuk
untuk
dan
Cn
ganjil digunakan
konsep pelabelan total titik anti ajaib untuk melabeli titik
dan sisi
untuk Sehingga diperoleh pelabelan total titik
dan pada
graf
sikel
anti ajaib dengan konstanta ajaib untuk
pertama, yaitu graf
, sedangkan
untuk melabeli sisi
untuk
dan f. Graf Hasil Kali Kartesius dari Graf
pada graf sikel yang kedua yaitu graf digunakan konsep pelabelan total
Sikel Graf
hasil
kali
kartesius
titik ajaib pada graf sikel dengan n
merupakan suatu graf yang dibentuk
ganjil, dan jumlah dari label titik
dari dua buah graf sikel, dimana graf
sisi
, dan sisi
, yang 57
Maria Nita, Robertus Heri, SU (Pelabelan Total Titik Ajaib Graf Hasil Kali Kartesius dari Graf Sikel)
adjacent
dengan
titik
merupakan
akan
memenuhi konsep pelabelan total titik
pemetaan yang bijektif.
ajaib pada graf sikel, dengan n ganjil.
Selanjutnya
Teorema 2.5 Untuk setiap
setiap
dan
mempunyai bobot yang sama.
ganjil, terdapat pelabelan total
titik ajaib pada graf
dengan
akan dibuktikan bahwa
titik
(i) Untuk
pada
graf
tersebut
, dan genap
konstanta ajaib
Bukti : Graf Cm
Cn mempunyai titik dan sisi
, sisi
, dimana dan
untuk
dan
ganjil. Diberikan
(ii) Untuk
dan genap
label graf sebagai berikut . , untuk , untuk
, untuk
genap
untuk
ganjil
(iii) Untuk
Dari bentuk pelabelan yang diperoleh langkah pertama adalah membuktikan bahwa
58
pemetaan
dan ganjil
Jurnal Matematika Vol. 13, No.1, April 2010 : 52-60
(iv) Untuk
sikel diperoleh suatu interval label
dan
titik
ganjil
, sisi
, dan sisi
beserta
nilai
konstanta
ajaib yang bersesuaian sebagai berikut.
1 λ λ λ 2 λ
Teorema 2.6 Untuk setiap dan
λ
ganjil, terdapat pelabelan total dengan
titik ajaib pada graf
λ
konstanta ajaib 3 λ λ
Teorema 2.7 Untuk setiap dan
ganjil, terdapat pelabelan total
titik ajaib pada graf
λ
dengan
konstanta ajaib
4 λ λ
Teorema dan
2.8
Untuk ganjil,
setiap λ
terdapat
pelabelan total titik ajaib pada graf dengan konstanta ajaib 3.
KESIMPULAN Berdasarkan
pembahasan
dapat
Bukti untuk Teorema 2.6, Teorema 2.7
disimpulkan bahwa graf hasil kali
dan Teorema 2.8 analog dengan bukti
kartesius dari graf sikel atau graf
Teorema 2.5, dan jika diberikan dalam bentuk tabel, maka pelabelan total titik
, banyaknya
dengan
menyatakan
baris,
menyatakan
ajaib graf hasil kali kartesius dari graf 59
Maria Nita, Robertus Heri, SU (Pelabelan Total Titik Ajaib Graf Hasil Kali Kartesius dari Graf Sikel)
banyaknya kolom dan
harus ganjil
[3]
Froncěk, D, Kovar, P and Kovarova, T. “ Vertex Magic Total
merupakan graf total titik ajaib. Pelabelan total titik ajaib
Labeling of Products of Cycles”.
graf hasil kali kartesius dari graf sikel
Australian
Journal
of
ganjil pada dasarnya adalah mencari
Combinatorics.
Volume
33,169-
label titik
181(2005).United
, sisi
, yang
merupakan titik dan sisi pada
dan
, yang merupakan sisi
sisi
. Pada pelabelan ini, konsep
yang digunakan untuk melabeli graf sikel pertama, yaitu
adalah dengan
menggunakan konsep pelabelan total dan untuk melabeli
titik anti ajaib
graf sikel kedua, yaitu
dengan
menggunakan konsep pelabelan total titik ajaib pada graf sikel dengan jumlah sikel ganjil, oleh sebab itu nilai harus ganjil.
4. DAFTAR PUSTAKA [1]
Cunningham, Magic”.
Daisy.
Electronic
Undergraduate
“Vertex
Journal
of
Mathematics.
Volume 9, 1 – 20 (2004). Furman University. [2] Gallian, J.A. “A Dynamic Survey of Graph Labeling”. The Electronic Journal
of
Combinatorics
15
(2008). Minnesota. United State Of America. 60
of
America. [4] Kovarova, Tereza. Tanpa tahun. “on vertex-magic
pada
State
total
labeling
of
products of cycles “ . OstravaPoruba.
