ANALISIS KETERKAITAN SEATL GRAF KONEKTIF DAN DISKONEKTIF SERTA APLIKASI DALAM PENGEMBANGAN KRIPTOSISTEM POLYALPHABETIC CIPHER

Abstract

Graf adalah salah salah kajian dalam matematika diskrit. Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek diskrit tersebut. Pelabelan graf merupakan suatu topik dalam teori graf. Objek kajiannya berupa graf yang secara umum direpresentasikan oleh titik dan sisi serta himpunan bagian bilangan cacah yang disebut label. Terdapat berbagai jenis tipe pelabelan dalam graf, salah satunya adalah pelabelan total super(a; d)- sisi antimagic (SEATL), dimana a bobot sisi terkecil dan d nilai beda. Hasil utama dari penelitian yang akan dibahas terkait dengan pelabelan total super (a; d)-sisi antimagic untuk sisi genap dan sisi ganjil yaitu lemma dan teorema, serta didalam penenilitian ini juga menggunakan teknik calouring dan berhasil mengeneralisasi keberadaan super edge antimagic total labeling pada sembarang tree dan sembarang graf apabila nilai kromatik numbernya maksimal 3 dan juga berhasil menjawab untuk d = 1 untuk sisi genap. Terdapat beberapa lemma dan teorema baru yang ditemukan secara eksperimental dalam penelitian ini. Contoh graf yang digunakan untuk pelabelan total super (a; d)-sisi antimagic dengan sisi ganjil yaitu shackle graf Kipas dengan notasi shack(F6;B2; n). Shackle graf kipas merupakan sebuah graf yang dinotasikan dengan dengan himpunan titik, V (shack(F6;B2; n)) = fxi; yj ; zi; 1 · i · n + 1 dan 1 · j · n + 2g dan sisi adalah E(shack(F6;B2; n)) = ffxiyi; 1 · i · n + 1g [ fxiyi+1; 1 · i · n + 1g [ fyjyj+1; 1 · j · n + 2g [ fyjzj ; 1 · j · n + 1g [ fyjzj¡1; 2 · j · n+1g[fzizi+1; 1 · i · n+1gg. Pada shackle graf kipas dihasilkan jV j = 3n+1. Sedangkan Jumlah sisi pada shackle graf kipas jEj = 6n¡1. Sehingga batas atas nilai beda yaitu d · 2. Untuk graf yang digunakan untuk pelabelan total super (a; d)-sisi antimagic dengan sisi genap yaitu graf H untuk mendapatkan EAV d=1 dan SEATL d=0,2. Graf H memiliki himpunan titik, V (H) = fxi; yi; zi; 1 · i · n + 1g dan sisi adalah E(H) = ffxiyi; 1 · i · n + 1g [ fyizi; 1 · i · n + 1g [ fyizi+1; 1 · i · ng [ fyiyi+1; 1 · i · ng [ fzixi+1; 2 · i · ng [ fzizi+1; 1 · i · ngg. Sedangkan untuk pelabelan titik (a,1)-sisi antimagic maka digunakan Graf K yaitu graf terhubung dengan himpunan vertex, V (K) = fxi; 1 · i · ng dan Sisi (edge) adalah E(K) = ffxixi+1; 1 · i · n ¡ 1g [ fyizi; 1 · i · n + 1g [ fyizi+1; 1 · i · ng [ fxnx1g [ fxixi+2; 2 · i · n ¡ 2g banyak titik jV j = n dan banyaknya sisi jEj = 2n ¡ 2. Selain itu, dikaji mengenai hubungan antara Super Edge Antimagic Total Labeling untuk graf konektif dan diskonektif. Sebelumnya juga telah dijabarkan mengenai pelabelan total super (a; d)-sisi antimagic dengan menggunakan teknik pewarnaan. Oleh karena itu, peneliti mengungkapkan bahwa adanya hubungan antara graf konektif dengan graf diskonektif yang memiliki bilangan kromatik sama dengan dua dan tiga, serta aplikasi SEATL dalam kriptogra¯. Metode yang digunakan dalam penelitian ini adalah deskriptif aksiomatik yaitu dengan menurunkan lema yang telah ada tentang nilai batas d dan lema untuk pelabelan graf saat d = 1. Teorema dan lema yang dihasilkan adalah sebagai berikut: 1. Teorema 4.1.1 Ada pelabelan titik (3; 1)-sisi antimagic pada shackle graf kipas shack(F6;B2; n) jika n ¸ 1. 2. Teorema 4.1.2 Ada pelabelan total super (9n + 3; 0)-sisi antimagic dan (3n+5; 2)-sisi antimagic pada shackle graf kipas shack(F6;B2; n) untuk n ¸ 1. 3. Teorema 4.1.3 Ada pelabelan total super (6n + 4; 1)-sisi antimagic pada shackle graf kipas shack(F6;B2; n) untuk n ¸ 1 4. Teorema 4.1.4 Ada pelabelan titik (4; 1)-sisi antimagic pada graf H yang bersisi genap jika n ¸ 1. 5. Teorema 4.1.5 Ada pelabelan total super (9n + 9; 0)-sisi antimagic dan (3n + 8; 2)-sisi antimagic pada graf H untuk n ¸ 1. 6. Lema 4.1.1 Misalkan ª merupakan sebuah himpunan bilangan ª = fc; c+ 1; c + 2; : : : ; c + k+1 2 ; c + k+1 2 ; c + k+3 2 ; c + k+5 2 ; ¢ ¢ ¢ ; c + kg, dengan k ganjil. Maka terdapat sebuah permutasi ¦(ª) dari anggota-anggota himpunan ª sehingga ª + ¦(ª) juga merupakan sebuah himpunan bilangan berurutan yaitu ª + ¦(ª) = f2c + k¡1 2 ; 2c + k+1 2 ; 2c + k+3 2 ; : : : ; 2c + 3k¡3 2 ; 2c + 3k¡1 2 g 7. Teorema 4.1.6 Ada pelabelan total super (2n + 2; 1)-sisi antimagic pada graf K untuk n ¸ 1. 8. Teorema 4.1.6 Ada pelabelan total super (2n + 2; 1)-sisi antimagic pada graf K untuk n ¸ 1. 9. Lema 4.1.2 Misalkan A adalah barisan A = f1; 2; 3; ¢ ¢ ¢ ; k; k+1g, k genap. Maka terdapat dua permutasi B(A) dan C(A) dari anggota A yaitu A + B(A);A+C(A);B(A)+C(A) membentuk barisan aritmatika yang berurutan. 10. Lema 4.1.3 Untuk n ¸ 3, bilangan kromatik dari shackle graf kipas adalah Âshack(F6;B2; n) = 3. 11. Teorema 4.1.7 Ada pelabelan titik ( 3m+3 2 ; 1)-sisi antimagic pada gabungan shackle graf kipas mshack(F6;B2; n) jika n ¸ 1. 12. Teorema 4.1.8 Ada pelabelan total super ( 18mn+3m+3 2 ; 0)-sisi antimagic dan ( 6mn+5m+5 2 ; 2)-sisi antimagic pada gabungan shackle graf kipas mshack(F6;B2; n) untuk n ¸ 1. 13. Teorema 4.1.9 Ada pelabelan total super (6mn+2m+2; 1)-sisi antimagic pada shackle graf kipas mshack(F6;B2; n) untuk n ¸ 1. 14. Lema 4.1.4 Untuk n ¸ 3, bilangan kromatik dari sisi genap graf H adalah 3. 15. Teorema 4.1.10 Ada pelabelan titik ( 5m+3 2 ; 1)-sisi antimagic pada gabungan graf H jika n ¸ 1. 16. Teorema 4.1.11 Ada pelabelan total super ( 18mn+15m+3 2 ; 0)-sisi antimagic dan ( 6mn+11m+5 2 ; 2)-sisi antimagic pada gabungan graf H untuk n ¸ 1. 17. Teorema 4.1.12 Ada pelabelan total super (2mn+2; 1)-sisi antimagic pada gabungan graf K untuk n ¸ 1. 18. Teorema 4.1.13 Misalkan G merupakan sebuah graf pohon dan G memiliki pelabelan titik (a; 1)-sisi antimagic maka gabungan saling lepasnya dari mG memiliki pelabelan titik (b; 1)-sisi antimagic. 19. Teorema 4.1.14 Misalkan G merupakan sebuah graf yang memiliki bilan- gan kromatik 3 dan G memiliki pelabelan titik (a; 1)-sisi antimagic maka gabungan saling lepasnya dari mG memiliki pelabelan titik (b; 1)-sisi an- timagic.