Edge Anti-Magic Total Labeling dari
Cn plus m
Chairul Imron dan Suhud Wahyudi Jurusan Matematika Institut Teknologi Sepuluh Nopember Surabaya
[email protected],
[email protected] Abstract We will find edge anti-magic total labeling of graph Cn plus m , where m n2 . Cn plus m is a cycle graph with expanded m edges. Keyword: edge anti-magic total labeling, graph.
1. PENDAHULUAN Graph tak berarah G selanjutnya disebut graph G , didefinisikan sebagai pasangan terurut
G (V , E ) dengan V adalah himpunan hingga tak kosong
simpul dan E adalah himpunan bagian dari V V yang dinamakan dengan himpunan sisi. Graph Cn plus m dengan m n2 adalah graph cycle dengan n simpul dan n sisi serta m sisi tambahan yang menghubungkan antara simpulsimpul yang ada pada graph cycle, seperti pada Gambar 1.
Gambar 1. Graph C5 plus 2 , C7 plus 3 dan C9 plus 4 Pelabelan yang berkembang sekarang adalah pelabelan pada himpunan simpul, himpunan sisi, atau keduanya. Pelabelan tersebut biasanya dikenal dengan nama pelabelan simpul, pelabelan sisi, atau pelabelan total. Sedangkan evaluasi dari pelabelan terdiri tiga macam yaitu evaluasi simpul, evaluasi sisi atau evaluasi total yaitu evaluasi pada simpul dan sisi. Dari kedua istilah tersebut dikenal salah
1
satunya adalah pelabelan total sisi ajaib (edge magic total labeling) yaitu pelabelan total dan evaluasi pada sisi dari graph. Jumlah tersebut disebut angka ajaib, yang biasa dilambangkan dengan simbol huruf k. Pada tahun 2006 (Imron, 2006), telah dipublikasikan graph ajaib dari graph cycle, yang membahas bagaimana memberi label pada graph cycle sehingga graph cycle tersebut mempunyai sifat ajaib. Ide pelabelan ini dikenalkan pertama kali oleh Sedlacek (Sedlacek, 1963) pada 1960-an, selanjutnya diformulasikan oleh Kotzig dan Rosa (Rosa, 1970) pada tahun 1970-an. Perhatikan definisi tentang pelabelan dibawah ini. Pelabelan total sisi ajaib pada graph Cn plus m dengan m 1 telah diseminarkan di Names-2009 (Imron, 2009a), dengan m 2 telah diseminarkan di IICMA (Imron, 2009b), dan dengan m n2 telah diseminarkan di Seminar Nasional Universitas Jember
(Imron, 2010). Pada paper ini akan dibahas
pelabelan total sisi anti ajaib (edge anti-magic total labeling). Pelabelan total sisi anti-ajaib yakni pelabelan dimana jumlah label sisi dan label simpul-simpul yang menempel atau yang insiden pada sisi tersebut selalu tidak sama untuk setiap sisi. Hasil jumlah pada setiap sisi merupakan barisan aritmatika.
Definisi Pelabelan Pelabelan total sisi ajaib pada (p,q)-graph G adalah fungsi bijektif
:V (G) E (G) {1, 2, 3, .. , p q } sedemikian sehingga ada suatu bilangan konstan k dimana
(u ) (v) (uv) k dengan
u, vV dan uv E dan k dinamakan jumlahan ajaib dari graph G
(Wallis, 2001). Jika ( V (G )) {1, 2, 3, .. , p } maka graph G dinamakan pelabelan super total sisi ajaib (Enomoto, 1998), dan dikatakan pelabelan total sisi antiajaib, jika mapping g : E W juga bijektif, dengan
W {w (uv) | uv E(G)} {a, a d , a 2d , .., a (q 1)d } adalah himpunan bobot dari sisi di graph G atau bobot dari sisi-sisi
w (uv), uv E(G) adalah pasangan yang berbeda (Baca, 2000).
2
Tujuan dari penelitian ini antara lain memberi label graph Cn plus m dengan m n2 dengan bilangan bulat positif sehingga mempunyai sifat anti ajaib. Manfaat dari penelitian ini adalah menambah wawasan keilmuan tentang pelabelan graph dan kriptografi. Manfaat yang lain, dapat diterapkan untuk menyusun
skema
pembagian
rahasia
yang biasanya
digunakan
sistem
pengamanan elektronik yang digunakan dalam perbankan, dan jaringan komunikasi.
2. HASIL DAN PEMBAHASAN Graph Cn plus m dengan m n2 adalah sebuah graph cycle C n dengan menambah m sisi pada graph tersebut. Telah dipublikasikan graph C n plus satu (Imron, 2009a) dan C n plus dua (Imron, 2009b) yang menceriterakan tentang pelabelan total sisi ajaib. Paper ini akan membahas pelabelan total sisi anti-ajaib dari graph Cn plus m dengan m n2 . Sebelum mencari pelabelan total sisi antiajaib, dicari terlebih dahulu batas beda dari graph Cn plus m dengan m n2 . Bilangan beda yaitu bilangan positif yang membedakan antara jumlahan pada satu sisi dengan sisi yang lain, biasanya disimbolkan dengan huruf d . Secara umum graph Cn plus m dengan m n2 dapat dilihat pada Gambar 1. Hasil dari penelitian ini dituliskan dalam beberapa teorema.
Teorema 1: Graph Cn plus m dengan m n2 adalah graph cycle dengan tambahan m sisi adalah pelabelan total sisi anti-ajaib dengan d 4 .
Bukti: Perhatikan Gambar 1, jika S v adalah jumlah label pada simpul dan S e adalah jumlah label pada sisi. Untuk graph Cn plus m dengan m n2 , jumlah simpul adalah p n dan jumlah sisi paling banyak adalah q n m . Konstruksi graph
Cn plus m akan menyebabkan beberapa kemungkinan antara lain
3
a. satu simpul berderajat
m 2 , m simpul berderajat tiga dan sisanya
berderajat dua, atau b. 2m simpul berderajat tiga dan sisanya berderajat dua, atau yang lainnya. Dalam paper ini digunakan yang pertama, sehingga jumlah pelabelan untuk semua sisi adalah m
qk 2S v S e vi m v j 1
atau jumlah pelabelan dengan beda d dapat ditulis
(m n)k a (a d ) (a 2d ) (a (m n 1)d ) sehingga
(m n)(m n 1) 5n 2 4nm 2m 2 3n 6m (m n)a d 2 2 untuk bilangan awal terkecil, yaitu a 6 dan bilangan pada simpul berderajat besar juga kecil, diperoleh
(m n)(m n 1) 5n 2 4nm 2m 2 3n 6m d 6(m n) 2 2 atau
d
5n 2 4nm 2m 2 9n 6m n 2 m 2 2mn m n
atau d 4 . Disamping batasan beda dari pelabelan total sisi anti-ajaib dari graph
Cn plus m tersebut, ditemukan pula beberapa teorema tentang pelabelan total sisi anti-ajaib dengan beda satu, dua dan empat.
Teorema 2. Graph C n plus m dengan n 4 dan m n 3 adalah (2n 2,1) -pelabelan total sisi anti-ajaib. Bukti: Graph Cn plus m dengan n 4 dan m n 3 , banyaknya simpul adalah
p n dan banyaknya sisi adalah q n m . Konstruksi graph Cn plus m
4
diuraikan dalam dua bagian yaitu untuk n genap dan n gasal. Pertama untuk
n gasal, konstruksi graphnya seperti pada Gambar 2, yaitu x3
x2
x4
x(n+1)/2
xn-3
x1
xn-2
xn-1
xn
Gambar 2. Konstruksi graph Cn plus n 3 untuk n gasal Didefinisikan pelabelan pada simpul adalah
( xi ) i, dengan i 1, 2,, n dan pelabelan sisi sebagai berikut ( x1 x j ) 2(n 1) j dan ( xn x j ) n j dengan j 3, 5, 7,, (n 2)
( x1xn ) n 1 , ( x1 x2 ) 2n , dan ( xn xn1 ) 2n 1
( xt xt 1 ) 2n 2(t 1) dengan t 2, 3,,
( xl xl 1 ) 2l 1 dengan l
n 1 2
n 1 n 3 , ,, (n 2) 2 2
Berikut ini contoh pelabelan total sisi anti-ajaib dari C9 plus 6 seperti pada Gambar 3. 2
20
18
3
22 4
19
24
5
21 23 1
10
11
6 13
14 12
15
7 16
8
17
9
Gambar 3. Contoh (20,1) -pelabelan total sisi anti-ajaib
Sedangkan konstruksi untuk n genap dan
5
n 2
gasal seperti Gambar 4.
x1 en+m+4 x3
x5
en+m+3
xi
e2
xi+2
e1
e3
e5
xi+1
e4
xn-3
xn-1 en+m+2
en+m+5
en+m+1
x2 en+m+6 x4
x6
xi+3
xn-2
xn
Gambar 4. Konstruksi graph Cn plus m untuk n genap dan
n 2
gasal
dan pelabelan simpulnya, adalah ( xi ) i, dengan i 1, 2, , n dan pelabelan
(ei ) i, dengan i n 1, n 2,, 2n m . Sedangkan untuk
n 2
genap pelabelan sisi seperti pada Gambar 5, serta pelabelannya sama seperti
n 2
sisinya adalah
gasal. x1 en+m+4 x3
x5
en+m+3
xi-2 e2n+m xi e2n+m-1
xn-3
e3
e1
en+m+2
en+m+5 x2 en+m+6 x4
x6
xn-1
xi-1 e2
en+m+1 xn-2 xn
xi+1
Gambar 5. Konstruksi graph Cn plus m untuk n genap dan
n 2
genap
Berikut ini contoh pelabelan total sisi anti-ajaib dari C9 plus 6 seperti pada Gambar 6. 1 16
17 3 21 5 12 7
18
20
9
11
13
15
2 19 4 10 6 14 8
1 20
21 3 25 5 12 7 16 9
22
24
2 23 4
26
11
13
15
17
19
27 6 14 8 18 10
Gambar 6. Contoh (18,1) dan (22,1) -pelabelan total sisi anti-ajaib Berikut ini teorema yang lain, yaitu teorema untuk beda 2 dengan m n2 , Teorema 3. Graph C n plus m dengan n 4 gasal dan m n2 adalah (n 4, 2) -pelabelan total sisi anti-ajaib.
6
Bukti: Graph Cn plus m dengan n gasal dan m n2 , banyaknya simpul adalah
p n dan banyaknya sisi adalah q n m . Konstruksi graph Cn plus m seperti pada gambar di atas. Didefinisikan pelabelan pada simpul adalah
1 i untuk i gasal (vi ) 2 n 1 i untuk i genap 2 dan pelabelan sisi adalah
(v1vn ) n m (v2vn1 ) 2n m (vi vi 1 ) n m i (v1v j )
n
i 1, 2,, n 1
j 1 2
j 3, 5,, n 2 ( gasal)
Beberapa contoh dari pelabelan total sisi anti-ajaib dari graph Cn plus m dengan
n 5 , n 7 dan n 9 yang dapat dilihat pada Gambar 7. 1
1 8
7
4
3
4
6
11
11
10
12
9
16
5
7
9
2
15 5
2 10
12
8
17
13 3
6
14
1
13
14
6
5 21 22 9 12 20
10
2 11
16
4 19
15
8 18
3
17
7
Gambar 7. Contoh (n 4, 2) -pelabelan total sisi anti-ajaib Berikut ini teorema yang lain, yaitu teorema untuk beda 2 dengan m 1 , Teorema 4. Graph Cn plus m dengan n 4 gasal dan m 1 adalah (n 2, 4) -pelabelan total sisi anti-ajaib. Bukti: Graph Cn plus m dengan n gasal dan m 1 , banyaknya simpul adalah p n dan banyaknya sisi adalah q n 1 . Didefinisikan pelabelan pada simpul adalah
7
untuk i gasal 1 i n 1 i untuk i genap
(vi )
dan pelabelan sisi adalah
(v1vn3 ) 1 (v1vn ) 3 (vi vi 1 ) 2i 3,
i 1,2,, n 1
Beberapa contoh dari pelabelan super total sisi ajaib dari graph Cn plus m dengan
n 5 , n 7 dan n 9 yang dapat dilihat pada Gambar 8. 2
2 5
3 6
5
3
10
8 8
15
1
7
19 18
4
17
1 11
7
14 13
10 9
4
9 6
10
8
12
11
2
3
5
12 7
1
4 9
15 16 13
6
11
14
Gambar 8. Contoh (n 2, 4) -pelabelan total sisi anti-ajaib 3. KESIMPULAN Dari uraian diatas dapat diambil kesimpulan bahwa graph Cn plus m dengan
m n2 merupakan pelabelan total sisi anti-ajaib dengan beda satu, dua dan empat. Batasan beda agar graph Cn plus m dengan m n2 merupakan pelabelan total sisi anti ajaib adalah d 4 .
UCAPAN TERIMA KASIH Paper ini merupakan bagian dari hasil penelitian yaitu penelitian Hibah Fundamental sesuai surat Perjanjian Pelaksanaan Penelitian Fundamental Nomor: 0536/I2.7/PM/2010 tanggal 1 Mei 2010, oleh karena itu penulis mengucapkan banyak terima kasih atas dukungannya.
DAFTAR PUSTAKA Baca, M., F. Bertault, J.A. MacDougall, M. Miller, R. Simanjuntak and Slamin, (2000), Vertex-Antimagic Total Labelings of Graphs.
8
Chairul Imron, Bandung AS (2006), Magic Graph on Cycle, The First ICoMS, UNISBA, Bandung, 19-21 Juni 2006. Chairul Imron, Suhud Wahyudi (2009a), Critical Set of Edge Magic Total Labeling of Expanding Cycle Graph, Conference Internasional NAMES 2009, Banjarmasin 3-4 Juli 2009. Chairul Imron, Suhud Wahyudi (2009b), Critical Set of Edge Magic Total Labeling of Cycle Plus 2 Edges Graph, IICMA 2009, UGM, Jogjakarta 12-13 Oktober 2009. Chairul Imron, Suhud Wahyudi (2010), Super Edge-Magic Total Labeling of Graph Cn plus m, SemNas Matematika, UMM, Malang, 30 Januari 2010. Enomoto, H., A.S. Llado, T. Nakamigawa and G. Ringel (1998), Super EdgeMagic Graphs, SUT Jurnal of Mathematics, Vol. 34, No. 2, 105-109. J. Sedlacek, problem 27 (1964), Theory of Graphs and it's Applications, (Smolenice,1963), 163-164, Publ. House Czechoslovak Acad. Sci.,Prague. A. Kotzig and A. Rosa (1970), Magic Valuations of Finite Graph, Canad. Math. Bull. 13 , 451-461. W.D. Wallis (2001), Magic Graphs, Birkhauser, Boston.
9
