Super (a, d)-S3 Antimagic Total Dekomposisi Graf Helm dan untuk Pengembangan Ciphertext (Super (a, d)-S3 Antimagic Total Decomposition Helm Graph and its Aplication for a Criptosystem) K. Rosyidah1 , Dafik1,2 , S. Setiawani1 1 Department
of Mathematics Education- University of Jember 2 CGANT- University of Jember ifa−
[email protected];
[email protected];
[email protected] Abstract A graph G(V, E) has a H-Covering if every edge in E belongs to a subgraph of G isomorphic to H. The (a, d) − H antimagic covering on the G graph is a biijective functin of f : V (G) ∪ E(G) → {1, 2, ..., |V (G)| + |E(G)|} till all of P the H 0 subgraphs that isomorphic to H have weight w(H) = v²V (H 0 ) f (v) + P e²E(H 0 ) f (e) from an arithmatic sequence {a, a + d, a + 2d, ..., a + (t − 1)d}, where a and d is the positive integres and t is the number of all subgraphs H 0 isomorphic to H. Such a labeling is called super if f : V (G) → {1, 2, ..., |V (G)|}. This research aims to determine the super (a, d) − S3 antimagic total decomposition of Helm graph and also we will use it to develop chipertext from a secret message.
Keywords: Super (a, d) − S3 , Decomposition, Helm Graph, and ciphertext.
Pendahuluan Ilmu pengetahuan dan teknologi akan selalu berkembang seiring dengan kebutuhan manusia di era globalisasi. Salah satu ilmu pengetahuan yang selalu berkembang adalah teori graf. Teori Graf merupakan ilmu matematika yang pertama kali diperkenalkan oleh L. Euler, matematikawan asal Swiss pada tahun 1736. Idenya muncul sebagai upaya dalam menyelesaikan masalah jembatan Konigsberg menggunakan graf. Ide inilah yang mengundang banyak ilmuan mengembangkan Teori Graf untuk memecahkan berbagai masalah yang muncul dalam kehidupan sehari-hari. Salah satu masalah yang berkaitan dengan graf yang telah dikaji adalah dekomposisi graf. Penerapan dekomposisi graf sudah banyak digunakan dalam beberapa disiplin ilmu. Jika selimut−H dari graf G memiliki sifat yaitu sisi G termuat dalam tepat satu graf Hi untuk suatu i ∈ 1, 2, ..., k, maka selimut-H disebut dekomposisi-H. G dikatakan memuat dekomposisi−H atau G terdekomposisi atas H [1]. Super (a, d)H total dekomposisi diperoleh dengan melabeli titik sebuah graf, mencari bobot sisi super (a, d)-H [10], melebeli sisi graf H [7] [12], dan kemudian mencari bobot total
Super (a, d)-S3 Antimagic Total Decomposition Graf Helm for Development Ciphertext . . . 2
sisi super (a, d)-H antimagic total dekomposisi graf H. Graf yang digunakan dalam artikel ini adalah graf Helm. Graf Helm Hn adalah graf yang didapatkan dari sebuah graf roda Wn dengan menambahkan sisi anting-anting pada setiap titik pada sikel. [8] Teori pelabelan dekomposisi graf sangat bermanfaat untuk sektor transportasi, navigasi, sistem komunikasi, pengkodean dan lain-lain. Ilmu pengkodean sangat dibutuhkan untuk merahasiakan suatu pesan. Teknik untuk membuat pesan rahasia ini dikenal dengan kriptosistem. Kriptosistem merupakan suatu teknik menjaga keamanan data dan informasi agar tidak diketahui dan dibaca oleh pihak yang tidak berwenang. Ciphertext diperlukan karena semakin tingginya tingkat kriminalitas pengacakan kode rahasia. Oleh karena itu, penelitian ini akan membuat suatu ciphertext yang didasari pada pelabelan dekomposisi graf Helm Hn . Kalimat yang akan di ubah yaitu kalimat yang mengandung huruf saja. Jika terdapat kalimat yang mengandung angka maka angka tersebut akan di ubah ke dalam bentuk alfabet. Hasil penelitian terkait ini terdapat pada [5, 6, 4]. Artikel ini akan menjelaskan tentang dekomposisi dari graf Helm. Akan ditentukan kardinalitas dan teorema-teorema tentang super antimagic total dekomposisi, kemudian akan dikembangkan ke dalam pembuatan ciphertext. Dari uraian tersebut maka penulis menulis judul artikel ”Super (a, d)-S3 Antimagic Total Dekomposisi Graf Helm untuk Pengembangan Ciphertext”.
Lemma yang Digunakan Misalkan Hn = (V (Hn ), E(Hn )) adalah graf berhingga dengan |V (Hn )| = pG dan E(Hn ) = qG . Pelabelan pada Hn didefinisikan sebagai suatu fungsi yang memetakan elemen-elemen Hn ke suatu subhimpunan bilangan bulat positif. Daerah definisi dari fungsi ini dapat berupa himpunan titik, himpunan sisi, atau gabungan himpunan titik. Pelabelan tersebut berturut-turut disebut pelabelan titik, pelabelan sisi, atau pelabelan total. Selanjutnya, jumlah semua label yang berkaitan dengan satu elemen pada suatu graf dikatakan bobot dari elemen tersebut. [11], [16], [9], dan [5] Berdasarkan uraian diatas, Graf helm adalah graf yang memiliki V (Hn ) = {P }∪ {xi , yi , 1 ≤ i ≤ n}, E(Hn ) = {P xi , xi xi+1 , xi yi , 1 ≤ i ≤ n} ∪ {xn x1 }, pG = |V |=2n + 1, qG = |E|=3n, pHn = 4, dan qHn = 3. Lemma 1 [6] Jika graf Hn (V, E) adalah super (a, d) − S3 antimagic total dekomposisi maka (pG − pH )pH + (qG − qH )qH d≤ s−1 untuk s = |Hi |, pG = |V |, qG = |E|, pH = |V 0 |, qH = |E 0 | Bukti. (s − 1)d ≤ pH pG −
pH −1 2 pH
+ qH pG + qH qG −
qH −1 2 qH
−a
Super (a, d)-S3 Antimagic Total Decomposition Graf Helm for Development Ciphertext . . . 3
(s−1)d ≤ pH pG − pH2−1 pH +qH pG +qH qG − qH2−1 qH −( p2H + p2
q2
p2
p2H 2
+qH pG + q2H + q2
2 qH 2 )
(s − 1)d = pH pG − 2H + p2H + qH qG − 2H + q2H − ( p2H + 2H + q2H + 2H ) 2 (s − 1)d = pH pG + qH qG − p2H − qH 2 2 (s − 1)d = pH pG − pH + qH qG − qH (s − 1)d = (pG − pH )pH + (qG − qH )qH +(qG −qH )qH d ≤ (pG −pH )pHs−1 Jadi, untuk s = |Hi |, pG = |V |, qG = |E|, pH = |V 0 |, qH = |E 0 | terbukti bahwa +(qG −qH )qH d ≤ (pG −pH )pHs−1
Hasil Penelitian Dekomposisi Metode penelitian yang digunakan yaitu menentukan kardinalitas dari garf Helm, menentukan d untuk dekomposisi dari S3 , menentukan fungsi titik, fungsi bobot dekomposisi, fungsi sisi, fungsi bobot total dekomposisi, dan pembuatan ciphertext untuk suatu pesan rahasia. Berikut akan diuraikan hasil dari penelitian berupa teorema beserta pembuktiannya terkait dekomposisi graf untuk graf Helm dan juga suatu ciphertext yang didasari atas teorema tersebut. Theorem 1 Graf helm Hn memiliki super ( 31n+15 , 5)-S3 antimagic total dekompo2 sisi untuk n ≥ 3. Bukti. Labeli titik graf Helm Hn dengan fungsi f1 yang didefinikan sebagai berikut: f1 (P ) = 1 ½ n+i+2 2 ; 1 ≤ i ≤ n, untuk i ∈ ganjil f1 (xi ) = i+1 1 ≤ i ≤ n, untuk i ∈ genap 2 ; f1 (yi ) = n + i + 1; 1 ≤ i ≤ n Dengan mudah dapat dipahami bahwa f1 adalah merupakan fungsi bijektif yang memetakan f1 : V (Hn ) → {1, 2, . . . , 2n + 1}. Misal wf1 adalah bobot sisi super , 5)-S3 antimagic total dekomposisi graf helm Hn untuk n ≥ 3, maka dapat ( 31n+15 2 diturunkan sebagai berikut: wf1 =
3n + 4i + 9 ;1 ≤ i ≤ n 2
Kemudian labeli sisi graf Helm Hn dengan fungsi f yang didefinikan sebagai berikut: f1 (P xi ) = 2n + i + 1; 1 ≤ i ≤ n f1 (xi xi+1 ) = 3n + i + 11 ≤ i ≤ n f1 (xn x1 ) = 4n + 1
Super (a, d)-S3 Antimagic Total Decomposition Graf Helm for Development Ciphertext . . . 4
dan f1 (xi yi ) = 4n + i + 1; 1 ≤ i ≤ n Misal Wf1 adalah bobot total sisi super ( 31n+15 , 5)-S3 antimagic total dekompo2 sisi graf helm Hn untuk n ≥ 3, maka dapat diturunkan sebagai berikut: Wf1 =
21n + 10i + 15 ;1 ≤ i ≤ n 2
Dengan mudah dapat diuraikan untuk masing-masing i pada inerval 1 ≤ i ≤ n adalah Wf1 = { 21n+25 , 21n+35 , . . . , 31n+15 } Sehingga terbukti bahwa Graf helm Hn 2 2 2 31n+15 memiliki super ( 2 , 5)-S3 antimagic total dekomposisi untuk n ≥ 3. Theorem 2 Graf helm Hn memiliki super ( 19n+27 , 7)-S3 antimagic total dekompo2 sisi untuk n ≥ 3. Bukti. Labeli titik graf Helm Hn dengan fungsi f2 yang didefinikan sebagai berikut: f2 (P ) = 1 ½ n+i+2 2 ; 1 ≤ i ≤ n, untuk i ∈ ganjil f2 (xi ) = i+1 1 ≤ i ≤ n, untuk i ∈ genap 2 ; f2 (yi ) = n + i + 1; 1 ≤ i ≤ n Dengan mudah dapat dipahami bahwa f2 adalah merupakan fungsi bijektif yang memetakan f2 : V (Hn ) → {1, 2, . . . , 2n + 1}. Misal wf2 adalah bobot sisi super ( 19n+27 , 7)-S3 antimagic total dekomposisi graf helm Hn untuk n ≥ 3, maka dapat 2 diturunkan sebagai berikut: wf2 =
3n + 4i + 9 ;1 ≤ i ≤ n 2
Kemudian labeli sisi graf Helm Hn dengan fungsi f2 yang didefinikan sebagai berikut: f2 (P xi ) = 5n − 3i + 2; 1 ≤ i ≤ n f2 (xi xi+1 ) = 5n − 3i + 3; 1 ≤ i ≤ n f2 (xn x1 ) = 2n + 3 dan f2 (xi yi ) = 5n − 3i + 4; 1 ≤ i ≤ n , 7)-S3 antimagic total dekompoMisal Wf2 adalah bobot total sisi super ( 19n+27 2 sisi graf helm Hn untuk n ≥ 3, maka dapat diturunkan sebagai berikut: Wf2 =
33n − 14i + 27 ;1 ≤ i ≤ n 2
Dengan mudah dapat diuraikan untuk masing-masing i pada inerval 1 ≤ i ≤ n 19n+27 adalah Wf2 = { 33n+13 , 33n−1 } Sehingga terbukti bahwa Graf helm Hn 2 2 ,..., 2 19n+27 memiliki super ( 2 , 7)-S3 antimagic total dekomposisi untuk n ≥ 3.
Super (a, d)-S3 Antimagic Total Decomposition Graf Helm for Development Ciphertext . . . 5
Theorem 3 Graf helm Hn memiliki super ( 37n+9 2 , 11)-S3 antimagic total dekomposisi untuk n ≥ 3. Bukti. Labeli titik graf Helm Hn dengan fungsi f3 yang didefinikan sebagai berikut: f3 (P ) = 1 ½ n+i+2 2 ; 1 ≤ i ≤ n, untuk i ∈ ganjil f3 (xi ) = i+1 1 ≤ i ≤ n, untuk i ∈ genap 2 ; f3 (yi ) = n + i + 1; 1 ≤ i ≤ n Dengan mudah dapat dipahami bahwa f3 adalah merupakan fungsi bijektif yang memetakan f3 : V (Hn ) → {1, 2, . . . , 2n + 1}. Misal wf3 adalah bobot sisi super ( 37n+9 2 , 11)-S3 antimagic total dekomposisi graf helm Hn untuk n ≥ 3, maka dapat diturunkan sebagai berikut: wf3 =
3n + 4i + 9 ;1 ≤ i ≤ n 2
Kemudian labeli sisi graf Helm Hn dengan fungsi f3 yang didefinikan sebagai berikut: f3 (P xi ) = 2n + 3i − 1; 1 ≤ i ≤ n f3 (xi xi+1 ) = 2n + 3i; 1 ≤ i ≤ n f3 (xn x1 ) = 5n dan f3 (xi yi ) = 2n + 3i + 1; 1 ≤ i ≤ n Misal Wf3 adalah bobot total sisi super ( 37n+9 2 , 11)-S3 antimagic total dekomposisi graf helm Hn untuk n ≥ 3, maka dapat diturunkan sebagai berikut: Wf3 =
15n + 22i + 9 ;1 ≤ i ≤ n 2
Dengan mudah dapat diuraikan untuk masing-masing i pada inerval 1 ≤ i ≤ n 37n+9 adalah Wf3 = { 15n+31 , 15n+3 2 2 ,..., 2 } Sehingga terbukti bahwa Graf helm Hn 37n+9 memiliki super ( 2 , 11)-S3 antimagic total dekomposisi untuk n ≥ 3.
Aplikasi Tingkat kriminalitas pengacakan kode yang semakin meningkat membuat para pemilik pesan rahasia harus lebih waspada. Permasalahan ini adalah termasuk bagian aplikasi total dekomposisi dalam cryptography. Cryptography adalah sebuah teknik merubah dari plaintext (kalimat pesan) ke dalam ciphertext (kalimat rahasia yang akan dikembangkan)[15]. Ciphertext merupakan bentuk pesan yang tersandi ke bentuk lain yang tidak dapat dipahami [13] [14]. Misalnya pesan rahasia yang akan dikirim adalah ”20127 adalah PIN kartu kredit anda”. Pelabelan yang digunakan
Super (a, d)-S3 Antimagic Total Decomposition Graf Helm for Development Ciphertext . . . 6
untuk mengubah pesan tersebut yaitu pelabelan total dekomposisi pada graf Helm H9 dengan d = 7 (sesuai teorema 2). Setelah melabeli graf Helm, dilanjutkan dengan mendata huruf dan angka yang digunakan dalam pesan dengan mengabaikan spasi dan tanda baca. Angka yang digunakan dalam pesan di ubah dalam bentuk alphabet yaitu menjadi ”dua nol satu dua tujuh adalah PIN kartu kredit anda”. Huruf yang digunakan adalah a, d, e, h, i, j, k, l, n, o, p, r, s, t, dan u. Langkah awal untuk merubah huruf tersebut yaitu dengan diagram pohon yang berakar di label 1. Cabang dari label 1 disesuaikan dengan cabang di graf Helm (H9 ). Cabang tersebut diberi nama layer pertama. Layer kedua dimulai dari sebelah kiri cabang dari layer pertama. Jumlah cabang disesuaikan dengan jumlah huruf yang digunakan dalam pesan rahasia. Label sisi diletakkan di garis penghubung 2 titik (sesuai dengan label sisi pada graf Helm (H9 )). Letakkan huruf-huruf yang digunakan dalam pesan sesuai dengan abjad (abjad awal diletakkan di cabang kiri), dan urutkan label sisinya. Kemudian pesan rahasia dipecahkan dengan menerapkan teknik kriptosistem modulo 26 terhadap masingmasing hurufnya sehingga menjadi a = mod(4145, 26) = 11, d = mod(4142, 26) = 8, e = mod(4143, 26) = 9, h = mod(3539, 26) = 3, i = mod(3536, 26) = 0, j = mod(3537, 26) = 1, k = mod(2933, 26) = 21, l = mod(2930, 26) = 18, n = mod(2931, 26) = 19, o = mod(23, 26) = 23, p = mod(44, 26) = 18, r = mod(38, 26) = 12, s = mod(32, 26) = 6, t = mod(26, 26) = 0, dan u = mod(20, 26) = 20. Kemudian hasil modulo tersebut dikombinasikan dengan label titik terakhir untuk menghindari terjadinya kesamaan bilangan diantara ciphertext. Dituliskan sebagai berikut a = mod(611, 26) = 13, d = mod(78, 26) = 0, e = mod(129, 26) = 25, h = mod(73, 26) = 21, i = mod(80, 26) = 2, j = mod(141, 26) = 11, k = mod(821, 26) = 15, l = mod(918, 26) = 8, n = mod(1619, 26) = 7, o = mod(523, 26) = 3, p = mod(618, 26) = 20, r = mod(712, 26) = 10, s = mod(86, 26) = 8, t = mod(90, 26) = 12, u = mod(1020, 26) = 6. Kombinasi titik dan sisi tersebut di ubah dalam bentuk modulo 26, sehingga diperoleh ciphertext yaitu a=n, d=a, e=z, h=v, i=c, j=l, k=p, l=i, n=h, o=d, p=u, r=k, s=i, t=m, dan u=g. Oleh karena itu, dengan menggunakan proses substitusi pesan kedalam ciphertext tanpa spasi dan tanda baca, maka ciphertext dari pesan ”duanolsatuduatujuhadalahpinkartukreditanda” adalah ”agnhdiinmgagnmglgvnaninvuchpnkmgpkzacmnhan”.
Kesimpulan Berdasarkan hasil penelitian diatas, maka kita dapat menyimpulkan bahwa: • Graf helm Hn memiliki super ( 31n+15 , 5)-S3 antimagic total dekomposisi untuk 2 n ≥ 3. • Graf helm Hn memiliki super ( 19n+27 , 7)-S3 antimagic total dekomposisi untuk 2 n ≥ 3.
Super (a, d)-S3 Antimagic Total Decomposition Graf Helm for Development Ciphertext . . . 7
• Graf helm Hn memiliki super ( 37n+9 2 , 11)-S3 antimagic total dekomposisi untuk n ≥ 3. • Ciphertext untuk pelabelan dekomposisi graf Helm dengan d = 7 dari pesan ”duanolsatuduatujuhadalahpinkartukreditanda” adalah ”agnhdiinmgagnmglgvnaninvuchpnkmgpkzacmnhan”
References [1] A.E. Hader,A. N. M Salman, An AM -Supermagic Decomposition Of The Cartesian Product Of a Path and Sun, Artikel, 2013. [2] AK Purnapraja, R Hidayat, Cycle-Super Antimagicness of Connected and Disconnected Tensor Product of Graphs, Procedia Computer Science, 74, (2015), 9399 [3] Dafik, M. Miller, J. Ryan and M. Baˇca, Antimagic labeling of the union of stars, Australasian Journal of Combinatorics, 42 (2008), 4909-4915. [4] Dafik Dafik, A.I. Kristiana, S. Setiawani, K.M.F. Azizah, Generalized Shackled of Fans is a Super (a, d)-edge-antimagic Total Graph, Journal of Graph Labeling, Vol. 2, Issue 1, (2016), 59-68 [5] Dafik, M. Miller, J.Ryan and M.Baca, On super (a,d)-edge antimagic total labeling of disconnected graphs, Discrite Math, (To appear). [6] Dafik, Structural Properties and Labeling of Graphs, University of Ballarat, 2007. [7] Erni Novianti, Dekomposisi Cyclic dari Graf Lengkap, Graf Graceful, dan Aplikasinya dalam Telecommand Codes, Artikel, 2012. [8] Gallian, J.A. 2007. ”dynamic Survey DS6: Graph Labeling” Electronic J. Combinatorics. DS6. (online): http://mathword.wolfram.com/www.combinatorics.org/surveys/ds6.pdf. Diakses tanggal 27 Juni 2015. [9] Joseph A. Gallian, A Dynamic Survey of Graph Labeling, University of Minnesota, 1997. [10] M. Baca, Y. Lin, M. Miller and M.Z. Youssef, Edge-antimagic graphs, Discrete Math, 2007. [11] Nur Inayah, Pelabelan (a, d) − H-Anti Ajaib Pada Beberapa Kelas Graf, Disertasi, Not Publicated, Institut Teknologi Bandung, 2013. [12] Nur Rahmawati, Dekomposisi graf sikel, graf roda, graf gir dan graf persahabatan, Skripsi, Not Publicated, Universitas Negeri Surabaya, 2014.
Super (a, d)-S3 Antimagic Total Decomposition Graf Helm for Development Ciphertext . . . 8
[13] Ongko, Erianto. 2013. Aplikasi Pembelajaran Kriptografi Klasik dengan Visual Basic .NET. Medan: STMIK IBBI. [14] Palupi, Retno. 2008. Kriptosistem Kunci Asimetrik Menggunakan Algoritma Genetika Pada Data Citra. (Vol 1 No 1) [15] Pearson, E. 2006. Introduction To Cryptography With Coding Theory. America: United States of America [16] W.D. Wallis, E.T. Baskoro, M. Miller and Slamin, Edge-magic total labelings, Austral, J. Combin., 2000.
