PELABELAN TOTAL TITIK AJAIB PADA COMPLETE GRAPH K n DENGAN n GANJIL Novi Irawati1 dan Robertus Heri2 1,2 Program Studi Matematika FMIPA, Universitas Diponegoro Jl. Prof. Soedarto, Tembalang-Semarang, 50275. Abstract. Let G be a graph consists of edges and vertex. A vertex-magic total labeling of a graph is a bijection map of union edges and vertex to the integers such that there exists a positive integer satisfying , for every elements of vertex. Then k is called a magic constant and G is called vertex-magic total graph. In this article, we consider a vertex-magic labeling of for odd with use an algorithm which is composed of a modified construction complete graph magic square algorithm. Keywords: vertex-magic total labeling, complete graph
1. PENDAHULUAN Graf merupakan pasangan himpunan titik dan himpunan sisi. Pengaitan titik-titik pada graf membentuk sisi dan dapat direpresentasikan pada gambar sehingga membentuk pola graf tertentu. Pola-pola yang terbentuk didefinisikan dan dikelompokkan menjadi kelas-kelas graf. Beberapa kelas graf menurut banyaknya sisi yang insiden terhadap titik antara lain graf reguler, yang derajat setiap titiknya adalah sama dan graf irreguler, yang derajat setiap titiknya ada yang tidak sama. Pelabelan graf merupakan suatu topik dalam teori graf. Objek kajiannya berupa graf yang secara umum direpresentasikan oleh titik dan sisi serta himpunan bagian bilangan asli yang disebut label. Pertama kali diperkenalkan oleh Sadlàčk (1964), kemudian Stewart (1966), Kotzig dan Rosa (1970). Pelabelan merupakan pemetaan injektif yang memetakan unsur himpunan titik dan atau unsur himpunan sisi ke bilangan asli yang disebut label. Pelabelan titik adalah pelabelan dengan domain himpunan titik, pelabelan sisi adalah pelabelan dengan domain himpunan sisi, dan pelabelan total adalah pelabelan dengan
136
, magic square
domain gabungan himpunan titik dan himpunan sisi. Pelabelan titik dan sisi dari graf bisa dilakukan dengan banyak cara. Salah satu cara yang bisa digunakan adalah melabelinya dengan bilangan. Ada banyak jenis pelabelan graf yang telah dikembangkan, diantaranya adalah pelabelan gracefull, pelabelan harmoni, pelabelan total tak beraturan, pelabelan ajaib, dan pelabelan anti ajaib. Dalam pengembangan pelabelan ajaib, dikenal pula pelabelan total titik-ajaib, pelabelan total titik ajaib super, pelabelan total sisiajaib, dan pelabelan total sisi-ajaib super. Hingga saat ini pemanfaatan teori pelabelan graf sangat dirasakan peranannya, terutama pada sektor sistem komunikasi dan transportasi, navigasi geografis, radar, penyimpanan data komputer, dan juga desain circuit gabungan pada komponen elektronik. Dalam perang di dunia modern ini penggunaan peluru kendali sudah tidak asing lagi. Penggunaan peluru kendali ini mengurangi perang secara fisik dalam jarak dekat, karena peluru kendali dapat diluncurkan dari jarak jauh. Dalam peluncurannya perlu diperhitungkan secara matang agar tepat sasaran. Untuk mengantisipasi kedatangan peluru kendali dari pasukan musuh, peluru kendali ini dapat di deteksi dengan menggunakan
Jurnal Matematika, Vol. 13, No. 3, Desember 2010 : 136-142
pendeteksi sinyal radar, sehingga dapat dilakukan antisipasi secepat mungkin. Selain untuk mendeteksi keberadaan peluru kendali baik yang akan diluncurkan ataupun yang datang dari musuh, deteksi sinyal radar ini juga digunakan untuk deteksi keberadaan pesawat tempur. Desain penting dari kode nonperiodik untuk sinyal radar dan peluru kendali ini ekuivalen dengan pelabelan pada complete graph, dimana setiap titik yang ada dihubungkan dengan satu sisi yang mempunyai label yang selalu berbeda. Label sisi ini menggambarkan jarak antar titik, sedangkan label titiknya merupakan posisi pada saat sinyal dikirimkan. Pada artikel ini, penulis melakukan kajian pelabelan total titik ajaib (vertex magic total labeling) pada salah satu subkelas graf reguler yaitu complete graph , dimana salah satu aplikasinya digunakan dalam desain penting dari kode nonperiodik untuk sinyal radar dan peluru kendali. 2. MASALAH Permasalahan yang akan dibahas dalam artikel ini adalah bagaimana memberikan pelabelan total titik ajaib pada complete graph K n , untuk n ganjil, dengan dasar penyusunan persegi ajaib. 3. PELABELAN TOTAL TITIK AJAIB PADA COMPLETE GRAPH K n DENGAN n GANJIL Pelabelan total titik ajaib complete graph dimana n ganjil, hampir sama dengan konstruksi persegi ajaib orde . Persegi ajaib orde adalah susunan bilangan dari 1 hingga , biasanya merupakan bilangan bulat yang berbeda dalam sebuah persegi, sedemikian sehingga bilangan di semua baris, semua kolom, dan kedua diogalnya mempunyai jumlah konstan yang sama. Persegi ajaib yang normal berisi bilangan bulat dari 1 hingga . Konstanta untuk satu persegi ajaib senantiasa tunggal (unik).
Perbedaan yang terjadi antara konstruksi persegi ajaib orde n dengan konstruksi pelabelan total titik ajaib complete graph , dimana ganjil terletak pada banyaknya bilangan yang akan mengisi elemen tabel. Jika dalam persegi ajaib bilangannya berupa 1 sampai n2 maka dalam pemberian label complete graph dimana ganjil menggunakan bilangan1 sampai . Theorema 3.1 [6] Terdapat pelabelan total titik ajaib pada complete graph dimana ganjil dan berlaku untuk semua ganjil. Bukti : Diberikan tabel untuk complete graph dengan berturutturut untuk baris dan kolom. Cara pemberian label pada complete graph dengan ganjil dapat menggunakan salah satu cara pembuatan persegi ajaib dengan orde . Perbedaan yang akan terjadi terletak pada banyaknya bilangan yang akan mengisi elemen tabel, jika persegi ajaib bilangannya berupa 1 sampai maka dalam pemberikan label complete graph dengan n ganjil menggunakan bilangan1 sampai . Untuk complete graph dengan tidak diperlukan langkah-langkah untuk melabelinya, sementara untuk diperlukan langkah-langkah sebagai berikut. Algoritma pelabelan total titik ajaib , dengan pada complete graph ganjil: Langkah 1 : Mulai pelabelan dari elemen aij =1, dengan dan Langkah 2 : Pilih elemen tabel dengan pergerakan ke arah tenggara (yaitu, dan ) satu posisi dari elemen sebelumnya dan diberi nilai dengan penambahan 1 hingga elemen yang belum terlabeli tidak ditemukan. Langkah 3 : Jika arah tenggara dari elemen sebelumnya sudah terisi, maka 137
Novi Irawati dan Robertus Heri (Pelabelan Total Titik Ajaib pada Complete Graph Kn dengan n Ganjil)
pilih elemen dengan pergerakan vertikal ke bawah dua kotak, kemudian ulangi langkah 2 sampai angka pelabelan mencapai bilangan . Langkah 4 : Jika angka pelabelan sudah mencapai bilangan , pilih garis diagonal utama yang telah terisi penuh dan berikan label yang sama terhadap label yang telah ada sehingga terbentuk simetris terhadap garis diagonal utama yang telah terisi penuh tersebut. Dalam langkah ini bilangan yang mengisi diagonal utama merupakan label untuk titik dalam graf dan untuk mempermudah label untuk titik diletakkan dalam baris pertama tabel yaitu dengan memindahkan nilai yang ada dalam diagonal utama ke baris pertama sedangkan untuk posisi yang diatasnya bergerak turun ke bawah.
Contoh 3.3. Se b a ga i i l us t r a s i di be r i ka n di be r i ka n c on t ohpe l a be l a nt ot a lt i t i ka j a i bcomplete graph .Ka r e n a b e r a r t ia n gka y a n g di gun a ka n da l a m pe l a b e l a na da l a h da r ia n gka1s a mpa i . De n ga nme mul a ide n ga ne l e me n pa da t a b e l3 da n de n ga n me n ggun a ka n l a n gka hb e r i kut ny adi pe r ol e h , 1 2 1
i / j 1
2
3
Gambar 1. Ha s i lt a b e ls e t e l a hl a ng k a h1
Lemma 3.2 [6] Pelabelan total titik ajaib dikatakan pelabelan total titik ajaib yang valid dari complete graph , dimana adalah bilangan ganjil jika konstanta
2 3
ajaibnya adalah Bukti: Pe r b e da a na n t a r a pe r s e gia j a i b de n ga n t a b e lpe l a b e l a ni nia da l a hdi ma n ada l a m pe r s e gia j a i br a n gea n gka ny ada r i1s a mpa i ,s e da n gka nda l a mpe l a b e l a na n gkay a n g di gun a ka na da l a h mul a ida r i1 s a mpa i .En t r iy a n gl a i n da pa tdi l i ha t j uml a hny a b e r kur a n g s e ba ny a k . De n ga n kon s t a n t a a j a i bda r ipe r s e gia j a i ba da l a h
De n ga nde mi ki a na ka ndi pe r ol e hkons t a n t a a j a i bda r ipe l a b e l a nt ot a lt i t i ka j a i bpa da complete graph , di ma n a a da l a h bi l a n ga nga nj i ls e b a ga ibe r i kut .
3
1 Gambar 2. Ha s i lt a b e ls e t e l a hl a ng k a h2
4 3
2 5 1
6
Gambar 3. Ha s i lt a b e ls e t e l a hl a ng k a h3
4
5
6
4
3
2
3
3
2
3
5
1
2
1
1
2
1
6
Gambar 4. Ha s i lt a b e ls e t e l a hl a ng k a h4
138
La b e lt i t i k
4
5
6
La b e ls i s i
3 2
3 1
2 1
Gambar 5. Ta b e lpe l a b e l a nt o t a lt i t i ka j a i bu n t u k .
J uml a h bi l a n ga n pe r kol om y a n g me r upa ka nkons t a n t aa j a i bun t ukpe l a b e l a n complete graph or de3( )a da l a hkons t a n y a n gs a ma ,y a i t ub e r j uml a h9. Pe n gga mba r a n pe l a be l a nt ot a lt i t i k a j a i b complete graph di b e r i ka npa da ga mb a rdi b a wa hi ni
Gambar 6. Pe l a b e l a nt o t a lt i t i ka j a i b complete graph
Pe l a b e l a nt ot a lt i t i ka j a i bun t uk me mpuny a ikon s t a n t aa j a i b()=9,y a n g me r upa ka npe nj uml a h a nda r is e b ua ht i t i t k da n duas i s iy a ng i ns i de nt e r h a da pt i t i k t e r s e b ut .Pa daGa mb a r3. 10da pa tdi l i ha t . b a h wani l a i Se b a ga i ma na de n ga n pe r s e gia j a i b or de ,pe l a b e l a nt ot a lt i t i ka j a i bj uga me mpuny a i be b e r a pa a l gor i t ma un t uk me ny us unny a . Al gor i t ma l a i n a da l a h s e b a ga i ma n a a l gor i t ma pe ny us un a n pe r s e gia j a i by a n gt e l a h di s e s ua i ka n. Na munda r i a l gor i t mape ny us una npe r s e gia j a i by a n g a da ha ny a a da b e be r a pa me t ode pe ny us un a n pe r s e gia j a i b or de n y a n g da pa t di gun a ka n un t uk me n gkon s t r uks i pe l a b e l a nt ot a lt i t i ka j a i b pa dacomplete di ma n a ga nj i l .Me t odet e r s e b ut graph a da l a h Me t ode 2 da n3 y a n g t e l a h di s e s ua i ka n .
139
3.1 Metode 2 Me t ode 2 y a n g di gun a ka n un t uk me ny us un s e b ua h pe r s e gi a j a i b da pa t di gun a ka nun t ukme ny us unpe l a b e l a nt ot a l t i t i ka j a i bcomplete graph di ma na ga nj i l . Na mun s e b e l umny a a l gor i t ma t e r s e b utpe r l u di s e s ua i ka n .Ya i t ua n gka y a n gdi guna ka na da l a h1s a mpa i , s e hi ngga me t ode i nida pa tdi ur a i ka n ke da l a ml a n gka h l a n gka hb e r i kut . Langkah 1 :Mul a ipe l a b e l a n de n ga n a n gka1 pa dakot a kt e pa tdia t a skot a k pus a t . Langkah 2 : Ge r a ka n da s a r un t uk me n gi s ikot a kk ot a kt e r s e b uty a i t utimur laut (↗), s a t u l a n gka hpa das a t uwa kt u. Un t uk e l e me ny a n gt e r pi l i hs e l a nj ut ny a , b e r i ka nni l a ide n ga npe n a mba ha n1da r i l a b e ls e b e l umny a . Langkah 3 :J i kakot a ky a n ga ka ndi i s i s uda ht e r i s ima ka ,b e r ge r a ks a t uv e r t i ka l ke atas dua kotak, ke mudi a nt e r uss e pe r t i s e b e l umny a s a mpa i a n gka pe l a b e l a n me n c a pa ibi l a n ga n . Langkah 4 : J i ka a n gka pe l a b e l a n s uda hme nc a pa ibi l a nga n ,Pi l i h ga r i s di a gon a lut a ma y a n gt e l a ht e r i s i pe n uh da n b e r i ka n l a be ly a n g s a ma t e r h a da pl a b e ly a n g t e l a ha da s e hi ngga t e r b e n t uk s i me t r i s t e r h a da p ga r i sdi a gon a lut a maa n gt e l a h t e r i s ipe n uht e r s e b ut .Da l a ml a n gka hi ni bi l a n ga ny a n g me n gi s idi a gon a lut a ma me r upa ka nl a b e lun t uk t i t i k da l a m gr a f da nun t ukme mpe r muda hl a be lun t ukt i t i k di l e t a kka nda l a mt a bl eb a r i spe r t a may a i t u de n ga nme mi nda h ka nni l a iy a n ga dada l a m di a gon a l ut a ma ke b a r i s pe r t a ma s e da n gka n un t uk p os i s iy a n g di a t a s ny a b e r ge r a kt ur unkeb a wa h . Contoh 3.4. Se b a ga i i l us t r a s i di be r i ka n di be r i ka n c on t ohpe l a be l a nt ot a lt i t i ka j a i bcomplete .Ka r e n a b e r a r t ia n gka graph y a n g di gun a ka n da l a m pe l a b e l a na da l a h da r ia n gka1s a mpa i .
No v iI r a wa t id a nRo be r t usHe r i( Pe l a b e l a nTo t a lTi t i kAj a i bp a d aCo mp l e t eGr a p hKnd e n g a nnGa nj i l )
Mi s a l ny a , b e r l a kuun t uks e muat i t i k. 1
Gambar 7. Ta b e lha s i ls e t e l a hl a ngk a h1
2 1 5 4 3 Gambar 8. Ta b e lha s i ls e t e l a hl a ngk a h2
6
2 1
5 4 3 Gambar 9. Ta b e lha s i ls e t e l a hl a ng ka h3
6
2 1 5 1 0 1 1 4 5 1 3 9 4 1 2 8 1 1 7 3
Label titik Label sisi
1 1 3 1 0 7 4
1 2 6 8 5 4
1 3 9 1 5 7
1 4 2 1 8 1 0
1 5 2 9 6 3
Gambar 10. Ta b e lha s i ls e t e l a hl a ng k a h4
Gambar 11 Pe l a b e l a nt o t a lt i t i ka j a i b complete graph
Pe l a b e l a nt ot a lt i t i ka j a i b un t uk de n ga n me n ggun a ka n me t ode 2 y a n gt e l a h di s e s ua i ka n .Kons t a n t aa j a i b ()= 35 y a ng di pe r ol e hda r ih a s i lpe nj uml a ha nl a b e lt i t i kda n l a b e ls i s iy a n gi ns i de n de n ga nt i t i kt e r s e b ut . 140
.Da ni ni
3.2 Metode 3 Sa ma h a l ny a de n ga n Me t ode 2 , Me t ode3 y a n gt e l a h di s e s ua i ka n da l a m pe ny us un a n pe r s e gi a j a i b j uga da pa t di gun a ka nun t ukme ny us unpe l a b e l a nt ot a l t i t i ka j a i b complete graph di ma n a ga nj i l .Pe ny e s ua i a ny a n gdi ma ks uda da l a h a n gka y a n g di gun a ka na da l a h1s a mpa i .Me t ode3i nida pa tdi ur a i ka nke da l a ml a n gka h l a n gka hb e r i kut . Langkah 1 :Mul a ipe l a b e l a n de n ga n a n gka1pa dakot a kt e pa tdib a wa hkot a k pus a t . Langkah 2 : Ge r a ka n da s a r un t uk me n gi s i kot a kk ot a k ke mudi a n me nj a di di a gon a lkeka na nba wa h( ↘) ,s a t ul a n gka h pa da s a t u wa kt u . Un t uk e l e me ny a n g t e r pi l i hs e l a nj ut ny a ,b e r i ka nni l a ide n ga n pe n a mba ha n1da r il a b e ls e b e l umny a . Langkah 3 :J i kakot a ky a n ga ka ndi i s i s uda ht e r i s ima ka ,b e r ge r a ks a t uv e r t i ka lke b a wa hduakot a k,ke mudi a nt e r uss e pe r t i s e b e l umny as a mpa ini l a ia n gkape l a b e l a n me n c a pa ibi l a n ga n . Langkah 4 : J i ka a n gka pe l a b e l a n s uda hme nc a pa ibi l a nga n ,Pi l i h ga r i sdi a gon a l ut a may a n gt e l a ht e r i s i pe n uh da n b e r i ka n l a be ly a n g s a ma t e r h a da pl a b e ly a n gt e l a ha da s e hi ngga t e r b e n t uks i me t r i st e r h a da pga r i sdi a gon a l ut a maa n gt e l a h t e r i s ipe n uht e r s e b ut .Da l a ml a n gka hi ni bi l a n ga ny a n g me n gi s idi a gon a lut a ma me r upa ka nl a b e lun t uk t i t i k da l a m gr a f da nun t ukme mpe r muda hl a be lun t ukt i t i k di l e t a kka nda l a mb a r i spe r t a mat a b e ly a i t u de n ga nme mi nda h ka nni l a iy a n ga dada l a m di a gon a l ut a ma ke b a r i s pe r t a ma s e da n gka n un t uk p os i s iy a n g di a t a s ny a b e r ge r a kt ur unkeb a wa h . Contoh 3.5. Se b a ga ii l us t r a s idi be r i ka n di b e r i ka nc on t ohpe l a b e l a nt ot a lt i t i ka j a i b r e n a b e r a r t i complete graph .Ka
Jurnal Matematika,Vo l .13 ,No .3,De s e mb e r2 0 1 0:1 3 6 1 4 2
a n gka y a n g di gun a ka n da l a m pe l a b e l a n a da l a hda r ia n gka1s a mpa i
4 5 6 7 1 2
1
3 Gambar 13 Tabel setelah langkah 2 Gambar 12 .Ta b e lha s i ls e t e l a hl a ngka h1
4 5 6 7 1 8
2 3
Gambar 14. Ta b e lha s i ls e t e l a hl a ngka h3
22 16 10 5 23 17 6 24 18 13 7 25 14 1 26 21 8 2 15 9
4
Label titik
11 12 19 20 27 3 28
Label sisi
22 5 16 13 10 21 4
23 5 6 17 14 11 15
24 16 6 7 18 8 12
25 13 17 7 1 19 9
26 10 14 18 1 2 20
27 21 11 8 19 2 3
28 4 15 12 9 20 3
Gambar 15. Ta b e lha s i ls e t e l a hl a n g k a h5
141
No v iI r a wa t id a nRo be r t usHe r i( Pe l a b e l a nTo t a lTi t i kAj a i bp a d aCo mp l e t eGr a p hKnd e n g a nnGa nj i l )
Gambar 16. Pe l a b e l a nt o t a lt i t i ka j a i bcomplete graph
4. PENUTUP Ar t i ke li ni me ma pa r ka n t e n t a n g pe l a b e l a nt ot a lt i t i ka j a i b pa dacomplete graph . Pe mba h a s a nny a me l i put i a l gor i t ma pe l a b e l a n da n pe n c a r i a n kon s t a n t aa j a i b da r ipe l a b e l a nt ot a lt i t i k a j a i b pa da compete graph un t uk ga nj i lda nge n a p.Al gor i t mape l a be l a nt ot a l t i t i ka j a i bun t ukcompete graph ,un t uk bi l a n ga n ga nj i l di s us un b e r da s a r ka n a l gor i t mape ny us una npe r s e gia j a i by a n g t e l a hdimodi f i ka s i . 5. DAFTAR PUSTAKA [ 1] . Ab us s a ki r , di a ks e s t a n gga l 3 Nov e mb e r 2008,Graph Labeling, Ab us s a ki r ’ sBl og. h t t p: / / a b us s a ki r . wor dpr e s s . c om/
142
[ 2] . Ga l l i a n ,J . A. ,( 2008) ,“ A Dy na mi c Sur v e y of Gr a ph La b e l i ng” . The Electronic Journal of Combinatorics 15. Mi nne s ot a . Uni t e d St a t e Of Ame r i c a . [ 3] . Ha r j u,Te r o. ,( 2007) ,Lecture Notes On Graph Theory. Fi nl a n d: De pa r t me n t of ma t h e ma t i c s Uni ve r s i t yOfTur ki . [ 4] . He n dr y De x t , di a ks e st a n gga l3 J a n ua r i 2010, Mengenal Magic Square, Ev e r y t hi n g Ab out Ma t h Bl og. h t t p: / / h e n dr y de x t . bl ogs pot . c om/ [ 5] . Li ps c h ut z , Se y mour a n d Li ps on , Ma r cl a r s . ,( 1992) ,“ 2000 Solved Problem in Discrete Mathematic” . Mc Gr a wHi l l ,I n c .Si n ga por e . [ 6] . Mc Douga l l , Mi l l e r , Sl a mi n ,a n d Wa l l i s ,( 2002) , .Vertex Magic Total Labeling of Graphs, Ut i l . Ma t h . , 61( 2002)3 21. [ 7] . Robi nJ .Wi l s ona n dJ ohnJ .Wa t ki ns , ( 1990) , Graph An Introductory Approach.J oh nWi l e y& Son s ,I n c . Ne wYor k. [ 8] . Sl a mi ne ta l . ,( 2006) ,”Ve r t e x Ma gi c Tot a l La b e l i ngs of Di s c onn e c t e d Gr a ph s ” : Journal of Prime Research in Mathematics Vol. 2(2006), 147156. [ 9] . St i n s on , Rob e r t . , ( 1992) , Contemporary Design Theory: A Collection of Surveys. J ohnWi l e y& Son s ,I n c .Ne wYor k .
