SKRIPSI. Oleh Yuli Nur Azizah NIM

SUPER (a, d) − APO ANTI AJAIB TOTAL DEKOMPOSISI GRAF SHACKLE GENERALISASI ANTIPRISMA UNTUK PENGEMBANGAN CIPHERTEXT DAN KETERAMPILAN BERPIKIR TINGKAT TINGGI

SKRIPSI

Oleh Yuli Nur Azizah NIM 120210101077

PROGRAM STUDI PENDIDIKAN MATEMATIKA FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS JEMBER 2016

SUPER (a, d) − APO ANTI AJAIB TOTAL DEKOMPOSISI GRAF SHACKLE GENERALISASI ANTIPRISMA UNTUK PENGEMBANGAN CIPHERTEXT DAN KETERAMPILAN BERPIKIR TINGKAT TINGGI

SKRIPSI

diajukan guna melengkapi tugas akhir dan memenuhi salah satu syarat untuk menyelesaikan Program Studi Pendidikan Matematika (S1) dan mencapai gelar Sarjana Pendidikan

Oleh Yuli Nur Azizah NIM 120210101077

PROGRAM STUDI PENDIDIKAN MATEMATIKA FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS JEMBER 2016 i

HALAMAN PERSEMBAHAN Dengan menyebut nama Allah yang Maha Pengasih lagi Maha Penyayang, serta Sholawat dan salam atas Nabi Muhammad S.A.W, kupersembahkan suatu kebahagiaan dalam perjalanan hidupku teriring rasa terima kasih kepada: 1. Allah SWT, yang telah memberikan nikmat dan hadiah terindah dalam hidupku. Atas Rahmat dan Ridho-Nya lah saya dapat menjalani hidup; 2. Ibu tercinta Umi Kulsum dan Bapak Tercinta Alm. Hari Susiyanto yang senantiasa memberikan dorongan, semangat dan kasih sayang berlimpah serta cucuran keringat dan do’a yang tak pernah putus dalam mengiringiku meraih impian, juga Kakakku Endang Susilowati dan Ibnu Fajar terima kasih banyak atas support dan kasih sayangnya selama ini; 3. Bapak Prof. Drs. Dafik., M.Sc., Ph.D., selaku Dosen Pembimbing I dan Ibu Susi Setiawani, S.Si., M.Sc. selaku Dosen Pembimbing II yang telah meluangkan waktu, pikiran, dan perhatian dalam penulisan skripsi ini; 4. Seluruh pahlawanku tanpa tanda jasa dari taman SD Jrebeng Lor II, SMP Negeri 4 Probolinggo, SMA Negeri 3 Probolinggo, dan Dosen Pendidikan MIPA Program Studi Pendidikan Matematika UNEJ; 5. Keluarga besarku yang selalu memberikan senyuman dan kebahagian, khususnya 3 ponakanku tersayang Hafas, Hasby, dan Abil. Tak lupa juga saudarasaudaraku Isti, Dwi Nur, dan Afifah yang selalu bersama di Jember serta keluarga besar yang ada di Probolinggo; 6. Teman-teman seperjuanganku (CGANT): Ifa, Siska, Farah, Desy, Irma, Sinta, Mita, Tanti, dan Novri dan pencinta graf lainnya yang telah membagi ilmu dan pengalaman berharga; 7. Teman-teman Curcolan (Leli, Alfi, Vita, Dyas, Silvi) dan Pramuka SMA 3 Probolinggo yang selalu bersamaku dalam suka dan duka; 8. Teman-Teman Fractal Boxpory (Ifa, Retha, Cudin, Dahlan) dan seluruh mahasiswa Pendidikan Matematika Unej khususnya angkatan 2012; 9. Almamater Fakultas Keguruan dan Ilmu Pendidikan Universitas Jember; 10. Dan semua pihak yang pernah hadir dalam perjalanan hidupku. ii

HALAMAN MOTTO

"Sesungguhnya sesudah kesulitan itu ada kemudahan." (Q.S. Al-Insyirah :

6)

"Maka nikmat Tuhan kamu yang manakah yang kamu dustakan?." (Q.S. Ar-Rahman :

13)

"It’s not that i’m so smart, it’s just that i stay with problems longer." (Albert Einsten)

iii

HALAMAN PERNYATAAN Saya yang bertanda tangan di bawah ini: Nama : Yuli Nur Azizah NIM : 120210101077 Menyatakan dengan sesungguhnya bahwa skripsi yang berjudul:Super (a, d)− Apo Anti Ajaib Total Dekomposisi Graf Shackle Generalisasi Antiprisma untuk Pengembangan Ciphertext dan Keterampilan Berpikir Tingkat Tinggi adalah benar-benar hasil karya sendiri, kecuali jika dalam pengutipan substansi disebutkan sumbernya, dan belum diajukan pada instansi manapun, serta bukan karya jiplakan. Saya bertanggung jawab atas keabsahan dan kebenaran isinya sesuai dengan sikap ilmiah yang harus dijunjung tinggi. Demikian pernyataan ini saya buat dengan sebenarnya, tanpa adanya tekanan dan paksaan dari pihak manapun serta bersedia mendapat sanksi akademik jika ternyata di kemudian hari pernyataan ini tidak benar.

Jember, 21 Januari 2016 Yang menyatakan,

Yuli Nur Azizah NIM. 120210101077

iv

SKRIPSI

SUPER (a, d) − APO ANTI AJAIB TOTAL DEKOMPOSISI GRAF SHACKLE GENERALISASI ANTIPRISMA UNTUK PENGEMBANGAN CIPHERTEXT DAN KETERAMPILAN BERPIKIR TINGKAT TINGGI

Oleh

Yuli Nur Azizah NIM 120210101077

Dosen Pembimbing 1 : Prof. Drs. Dafik, M.Sc., Ph.D. Dosen Pembimbing 2 : Susi Setiawani, S.Si., M.Sc.

v

HALAMAN PENGAJUAN

SUPER (a, d) − APO ANTI AJAIB TOTAL DEKOMPOSISI GRAF SHACKLE GENERALISASI ANTIPRISMA UNTUK PENGEMBAMGAN CIPHERTEXT DAN KETERAMPILAN BERPIKIR TINGKAT TINGGI

SKRIPSI

Diajukan untuk dipertahankan di depan Tim Penguji sebagai salah satu persyaratan untuk menyelesaiakan Program Pendidikan Sarjana Jurusan Pendidikan Matematika dan Ilmu Pengetahuan Alam dengan Program Studi Pendidikan Matematika pada Fakultas Keguruan dan Ilmu Pendidikan Universitas Jember

Oleh: Nama

: Yuli Nur Azizah

NIM

: 120210101077

Tempat dan Tanggal Lahir : Probolinggo, 11 Juli 1994 Jurusan / Program Studi : Pendidikan MIPA / P. Matematika Disetujui oleh: Pembimbing I,

Pembimbing II,

Prof. Drs. Dafik, M.Sc, Ph.D. NIP. 19680802 199303 1 004

Susi Setiawani, S.Si., M.Sc. NIP. 19700307 199512 2 001 vi

HALAMAN PENGESAHAN Skripsi berjudul Super (a, d) − Apo Anti Ajaib Total Dekomposisi Graf Shackle Generalisasi Antiprisma untuk Pengembangan Ciphertext dan Keterampilan Berpikir Tingkat Tinggi telah diuji dan disahkan oleh Fakultas Keguruan Dan Ilmu Pendidikan pada: Hari

: Kamis

Tanggal : 21 Januari 2016 Tempat : Gedung 3 FKIP UNEJ Tim Penguji : Ketua,

Sekretaris,

Prof. Drs. Dafik, M.Sc, Ph.D. NIP. 19680802 199303 1 004

Susi Setiawani, S.Si., M.Sc. NIP. 19700307 199512 2 001

Anggota I,

Anggota 2,

Prof. Drs. Slamin, M.Comp.Sc., Ph.D. NIP. 19670420 199201 1 001

Arif Fatahillah, S.Pd., M.Si. NIP. 19820529 200912 1 003

Mengetahui, Dekan Fakultas Keguruan Dan Ilmu Pendidikan Universitas Jember

Prof. Dr. Sunardi, M.Pd NIP. 19540501 198303 1 005 vii

RINGKASAN Super (a, d) − Apo Anti Ajaib Total Dekomposisi Graf Shackle Generalisasi Antiprisma untuk Pengembangan Ciphertext dan Keterampilan Berpikir Tingkat Tinggi; Yuli Nur Azizah, 120210101077; 2016: 157 halaman; Program Studi Pendidikan Matematika, Jurusan Pendidikan Matematika dan Ilmu Pengetahuan Alam, Fakultas Keguruan dan Ilmu Pendidikan, Universitas Jember.

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 super (a, d) − H anti ajaib total dekomposisi, dimana a bobot total selimut terkecil dan d nilai beda antar bobot. Graf Shackle Generalisasi Antiprisma yang dinotasikan dengan shack(Apo , v, n) merupakan hasil dari operasi shackle pada graf generalisasi antiprisma pada penelitian ini shackle yang digunakan adalah shackle satu titik. Graf ini merupakan graf yang memiliki tiga expand pada indeks o, p, dan n sedangkan untuk diskonektif (gabungan terpisah) terdiri dari empat expand pada indeks o, p, n, dan m. Dimana nilai o yang dimaksudkan adalah banyaknya expand titik pada bagian lingkaran graf generalisasi antiprisma, nilai p adalah banyaknya expand lingkaran yang terbentuk pada setiap graf generalisasi antiprisma, nilai n adalah banyaknya graf antiprisma yang dishacklekan, dan nilai m adalah banyaknya copy-an dari graf shackle generalisasi antiprisma. Tujuan dari penelitian ini adalah untuk mengetahui apakah graf shackle generalisasi antiprisma memiliki super (a, d) − Apo anti ajaib total dekomposisi yang kemudian digunakan untuk menciptakan ciphertext. Selain itu diterapkan tahapan-tahapan yang terdapat pada Taksonomi Bloom hingga mencapai keterampilan berpikir tingkat tinggi. Metode yang digunakan dalam penelitian ini adalah desktiptif aksiomatik, yaitu dengan menurunkan teorema tentang dekomposisi graf dengan mengguviii

nakan metode partisi, kemudian diterapkan dalam super (a, d)−Apo anti ajaib total dekomposisi graf shackle generalisasi antiprisma shack(Apo , v, n) dan mshack(Aop , v, n). Hasil penelitian ini berupa lemma dan teorema baru mengenai super (a, d)−Apo anti ajaib total dekomposisi graf shackle generalisasi antiprisma shack(Apo , v, n) dan mshack(Apo , v, n) yaitu sebagai berikut: 1. Ada pelabelan super (18o2 n − 9on + 12o + n − 1, 6o) − Ao anti ajaib total dekomposisi pada graf Shack(Ao , v, n). 2. Ada pelabelan super (18o2 n − 7on + 10o − 2n + 2, 4o + 2) − Ao anti ajaib total dekomposisi pada graf Shack(Ao , v, n). 2 n−15on+21o+o2

3. Ada pelabelan super (( 35o

2

+ 4n − 4), o2 + 3o − 6) − Ao anti ajaib

total dekomposisi pada graf Shack(Ao , v, n). 4. Graf shackle generalisasi antiprisma Shack(Apo , v, n), o ≥ 3, p ≥ 2, n ≥ 2, memiliki super (a, d)−Apo anti ajaib total dekomposisi untuk d ∈ {0, 1, 2, . . . , 2(2op − o)}. 5. Graf shackle generalisasi antiprisma Shack(Apo , v, n), o ≥ 3, p ≥ 2, n ≥ 2, memiliki super (a, d) − Apo anti ajaib total dekomposisi dengan d ∈ {0, 1, 2, . . . , (op − 2)2 + (3op − 2o)2 + 2} yang memenuhi d = ±(op − 2 − t)2 ⊕ d(t) ⊕ (±(3op − 2o − r)2 ) ⊕ d(r) ⊕ ±2 dimana t = 0, 1, . . . , op − 2 dan r = 0, 1, . . . , 3op − 2o. 6. Diberikan super (a, d)-Apo anti ajaib total dekomposisi graf shackle generalisasi antiprisma konektif dengan d ∈ {0, 2, 4, 6, . . . , 2(2op − o)} sedemikian hingga graf shackle generalisasi antiprisma diskonektif mShack(Apo , v, n), o ≥ 3, p ≥ 2, n ≥ 2, m ≥ 2 memiliki super (b, d) − Apo anti ajaib total dekomposisi. 7. Diberikan super (a, d) − Apo anti ajaib total dekomposisi graf shackle generalisasi antiprisma Shack(Apo , v, n) dengan o ≥ 3, p ≥ 2, n ≥ 2 maka terdapat super (b, d) − Apo anti ajaib total dekomposisi graf shackle generalisasi antiprisma diskonektif mShack(Apo , v, n) dengan beda d ∈ {0, 2, 4, . . . , (op−2)2 + (3op−2o)2 +2} yang memenuhi d = d(t)⊕(op−2−t)2 ⊕d(r)⊕(3op−2o−r)2 +2 ix

dimana t = 0, 1, . . . , op − 2 dan r = 0, 1, . . . , 3op − 2o.

Partisi untuk EAV pada graf lintasan konektif didefinisikan sebagai berikut. ( n P2,1 (k)

P

=

n P2,1 (k)

n P2,2 (k) P n P2,2 (k)

=

{ k+1 , e n+k e + 1}; 2 2

dengan k ≡ 1(mod 2)

{d n+k+1 e, k2 + 1}; 2

dengan k ≡ 0(mod 2)

d n+1 e 2

+ 1 + k;

1≤k≤n

= {k, k + 1} = 1 + 2k;

1≤k≤n

n Selain itu juga dihasilkan formula Partisi Pc,d (k) yang digunakan untuk c-

tuple, dimana antar tuple tidak memiliki anggota yang sama, didefinisikan sebagai berikut. n Pc,c (k) P n Pc,c (k)

= {(i − 1)n + k, 1 ≤ i ≤ c} =

c2 n−nc 2

+ ck,

dengan 1 ≤ k ≤ n

n Pc,c = {(k − 1)c + i; 1 ≤ i ≤ c} 2 (k) P n 2) Pc,c2 (k) = (c−c + c2 k; dengan 1 ≤ k ≤ n 2

Bila c ≡ 0 (mod 2) dan n ≡ 1 (mod 2) maka terdapat partisi yang dapat didefinisikan sebagai berikut   {(i − 1)n +     k−n    { 2 + in; Pc,n c (k) 2

P

Pc,n c (k) 2

=

=

k+1 ; 2

1 ≤ i ≤ c, i ≡ 0 (mod 2)}, k ≡ 1 (mod 2)

    { k+1−n + in;  2    {(i − 1)n + k ; 2 c (2cn 4

− n + 1) +

1 ≤ i ≤ c, i ≡ 1 (mod 2)} ∪

1 ≤ i ≤ c, i ≡ 1 (mod 2)} ∪ 1 ≤ i ≤ c, i ≡ 0 (mod 2)}, k ≡ 0 (mod 2) ck ; 2

dengan 1 ≤ k ≤ n

Terdapat suatu pelabelan untuk graf diskonektif dengan metode partisi yang dikembangkan dari pelabelan graf konektifnya yaitu partisi untuk EAV pada graf

x

lintasan yang didefinisikan sebagai berikut, (n,m)

n = m ⊗ (P2,2 (k) ª 1) ⊕ l P2,2 (lk ) P (n,m) l P n P2,2 (k ) = m( P2,2 (k) − 2) + 2l; dengan 1 ≤ k ≤ n,

1≤l≤m dan juga partisi untuk c-tuple, dimana antar tuple tidak memiliki anggota yang sama, didefinisikan sebagai berikut. (n,m)

= {i + c((k − 1)m + l − 1), 1 ≤ i ≤ c} Pc,c2 (lk ) P (n,m) l 2) Pc,c2 (k ) = (c−c + c2 ((k − 1)m + l); dengan 1 ≤ k ≤ n, 2 1≤l≤m (n,m) Pc,c (lk ) P (n,m) l Pc,c (k )

=m⊗ =m×

n (Pc,c (k) ª 1) ⊕ l P n ( Pc,c (k) − c) +

lc;

dengan 1 ≤ k ≤ n, 1≤l≤m

Selain itu juga didapatkan langkah penciptaan ciphertext yang menggunakan pelabelan graf. Adapun langkah-langkahnya adalah 1. Tentukan graf, pilihlah graf yang memiliki sisi lebih dari banyaknya karakter plaintext, misalkan s. 2. Labeli titik dan sisi. 3. Eliminasi sisi yang memiliki label fuv > |V | + s. 4. Membuat graf pohon dengan pangkal label titik terkecil, sedangkan akar selanjutnya mengikuti pola graf dan mulai dari kiri adalaha label titik yang lebih kecil sampai satu layer selesai kemudian dilanjutkan layer selanjutnya. Sisi yang sudah dieliminasi tidak perlu digunakan. 5. Cantumkan label sisi pada graf pohon sesuai pelabelan pada graf yang digunakan. Ubahlah bilangan tersebut menjadi bilangan mod s. 6. Pasangkan setiap karakter plaintext dengan sisi pada graf pohon. Pasangkan dengan cara diurutkan dari kiri mulai dari layer teratas. 7. Buatlah aturan untuk mentransformasi bilangan mod s ke karakter yang digunakan sebagai ciphertext. Berikut adalah aturan yang digunakan dalam xi

penelitian ini Aturan Julius Caesar 0

1

2

3

4

5

6

7

8

9

10

11

12

A

B

C

D

E

F

G

H

I

J

K

L

M

13 14 15 16

17

18

19

20

21

22

23

24

25

N

R

S

T

U

V

W

X

Y

Z

O

P

Q

Aturan pengkodean untuk bilangan mod 39 dengan simbol (mod 39)

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Kode

±

∓

×

÷

∗

?

◦

•

∝

∩

∪

]

u

t

∨

(mod 39)

15

16 17

18

19 20 21

22

23

24

25

26

27

28

29

Kode

∧

\

¦

4

ª

⊗

®

¯

°

†

(mod 39) Kode

o

5

/

.

⊕

30 31 32

33 34 35

36

37

38

‡

♦

¶

c ∞ °

q

♣

♥

♠

8. Buatlah tabel yang terdiri dari plaintext, label sisi yang bersesuaian dengan plaintext, (mod s) dari label sisi, dan ciphertext yang bersesuaian dengan (mod s). Enam macam super (a, d) − Apo anti ajaib total dekomposisi graf shackle generalisasi antiprisma yang digunakan untuk menciptakan ciphertext sehingga didapatkan lima macam ciphertext yang berbeda. Adapun ciphertext yang sudah dihasilkan adalah sebagia berikut 1. Pengembangan ciphertext dari super (812, 18) − Apo -anti ajaib total dekomposisi graf shack(A24 , v, 3) Plaintext

A

B

C

D

E

F

G

H

I

J

K

L

M

Ciphertext

H

X

V

G

Z

B

D

P

N

I

Y

A

W

Plaintext

N O

P

Q

R

S

T

U

V

W

X

Y

Z

Ciphertext

F

T

C

E

K

U

Q

O

R

L

M

S

J

xii

2. Pembangunan ciphertext dari super (819, 11) − Apo -anti ajaib total dekomposisi graf shack(A24 , v, 3) Plaintext

A

B

C

D

E

F

G

H

I

J

K

L

M

Ciphertext

Z

G

K

J

Y

C

H

M

N

F

S

W

L

Plaintext

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

Ciphertext

X

B

I

Q

P

E

U

V

O

A

D

T

R

3. Pembangunan ciphertext dari super (453, 8)−Apo -anti ajaib total dekomposisi graf shack(A23 , v, 3) Plaintext

A

B

C

D

E

F

G

H

I

J

K

L

M

Ciphertext

Z

J

M W

Y

K

O

V

T

F

C

Q

I

Plaintext

N O

P

Q

R

S

T

U

V

W

X

Y

Z

Ciphertext

X

N

U

S

H

B

P

E

R

D

A

G

L

4. Pembangunan ciphertext dari super (528, 52) − Apo -anti ajaib total dekomposisi graf shack(A23 , v, 4) Plaintext

A

B

C

D

E

F

G

H

I

J

K

L

M

Ciphertext

U W

Y

V

X

Z

B

I

K

A

C

E

L

Plaintext

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

Ciphertext

N

J

D

O

Q M

F

H

P

G

R

T

S

5. Pembangunan ciphertext dari super (1205, 102) − Apo -anti ajaib total dekomposisi graf shack(A33 , v, 3) Plaintext

A

B

C

D

E

F

G

H

I

J

K

L

M

Ciphertext

C

A

Y

D

K

B

I

Z

L

F

G

H

E

Plaintext

N O

P

Q

R

S

T

U

V

W

X

Y

Z

Ciphertext

S

Q

T

N

O

P

M

R

V

X

U

W

J

xiii

6. Ciphertext untuk alfabet, angka, dan tanda baca dikembangkan dari super (812, 18) − Apo -anti ajaib total dekomposisi graf shack(A24 , v, 3) Plaintext

A

B

C

D

E

F

G

H

I

J

K

L

M

Ciphertext

♦

⊕

u

∝

♣

⊗

¯

]

∪

†

∨

o

×

Plaintext

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

Ciphertext

♠

±

♥

ª ®

t

∩

q

∧

¦

5

∗

c °

Plaintext

0

1

2

3

4

5

6

7

8

9

sp.

,

.

Ciphertext

∞

◦

°

‡

\

4

/

¶

÷

•

?

.

∓

Kaitan antara keterampilan berpikir tingkat tinggi dengan super (a, d) − Apo anti ajaib total dekomposisi graf shackle generalisasi antiprisma yakni dalam penemuan teorema pada batas atas yang telah ditentukan, yaitu dimulai dari tahap mengingat meliputi mengingat istilah dan teorema yang terkait, mengenali graf yang akan digunakan, kemudian tahap memahami yang terdiri dari menjelaskan kesesuain graf shackle generalisasi antiprisma dan definisi dari graf shackle generalisasi antiprisma, selanjutnya tahap menerapkan yaitu menggunakan teorema batas atas untuk menunjukkan batas atas yang ada pada SHATD graf shackle generalisasi antiprisma, dan menerapkan teorema lainnya yang berkaitan, termasuk aturan-aturan yang berlaku dalam ilmu hitung. Tahap menganalisis meliputi memecah graf menjadi beberapa bagian berdasarkan polanya, mengkerangkakan pola untuk setiap bagian dalam bentuk partisi, dilanjutkan pada tahap mengevaluasi yaitu mengecek dan mengkaji ulang pola tersebut pada setiap ekspannya, mengecek pengkombinasian partisi pada setiap ekspannya, dan tahap mencipta yaitu memformulasikan partisi yang telah diperoleh dan memformulasikan a dan d yang diperoleh menjadi teorema yang baru. Hasil penelitian diharapkan dapat memberikan konstribusi terhadap berkembangnya pengetahuan baru dalam bidang teori graf, khususnya dalam ruang lingkup pelabelan graf dan bisa digunakan sebagai acuan oleh peneliti lain untuk meneliti super (a, d) − H anti ajaib total dekomposisi pada graf-graf khusus yang

xiv

lain. Selain itu, penelitian ini dapat dijadikan acuan untuk menciptakan soal tes kemampuan berpikir tingkat tinggi.

xv

KATA PENGANTAR Puji syukur ke hadirat Allah SWT atas segala rahmat dan karunia-Nya sehingga penulis dapat menyelesaikan skripsi yang berjudul Super (a, d) − Apo Anti Ajaib Total Dekomposisi Graf Shackle Generalisasi Antiprisma untuk Pengembangan Ciphertext dan Keterampilan Berpikir Tingkat Tinggi. Skripsi ini disusun untuk memenuhi salah satu syarat untuk menyelesaikan pendidikan strata satu (S1) pada Program Studi Pendidikan Matematika Fakultas Keguruan Dan Ilmu Pendidikan Universitas Jember. Pada kesempatan ini penulis mengucapkan terima kasih atas bantuan dan bimbingan dalam penyusunan skripsi ini, terutama kepada yang terhormat: 1. Dekan Fakultas Keguruan dan Ilmu Pendidikan Universitas Jember; 2. Ketua Jurusan Pendidikan MIPA Fakultas Keguruan dan Ilmu Pendidikan Universitas Jember; 3. Ketua Program Studi Pendidikan Matematika Fakultas Keguruan dan Ilmu Pendidikan Universitas Jember; 4. Ketua Laboratorium Komputer Program Studi Pendidikan Matematika Jurusan Pendidikan MIPA FKIP; 5. Dosen Pembimbing Akademik yang telah membimbing dan memberikan ilmunya; 6. Prof. Drs. Dafik, M.Sc., Ph.D. selaku Dosen Pembimbing I dan Susi Setiawani, S. Si., M.Sc. selaku Dosen Pembimbing II yang telah meluangkan waktu, pikiran, dan perhatian dalam penulisan skripsi ini; 7. Dosen dan Karyawan Fakultas Keguruan dan Ilmu Pendidikan Universitas Jember; 8. Semua pihak yang telah membantu terselesaikannya skripsi ini.

xvi

Semoga bantuan, bimbingan, dan dorongan beliau dicatat sebagai amal baik oleh Allah SWT dan mendapat balasan yang sesuai dari-Nya. Penulis juga menerima segala kritik dan saran dari semua pihak demi kesempurnaan skripsi ini. Semoga skripsi ini dapat bermanfaat. Jember, Januari 2016 Penulis

xvii

DAFTAR ISI HALAMAN JUDUL . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

HALAMAN PERSEMBAHAN . . . . . . . . . . . . . . . . . . . .

ii

HALAMAN MOTTO . . . . . . . . . . . . . . . . . . . . . . . . . .

iii

HALAMAN PERNYATAAN

. . . . . . . . . . . . . . . . . . . . .

iv

HALAMAN PENGAJUAN . . . . . . . . . . . . . . . . . . . . . .

vi

HALAMAN PENGESAHAN . . . . . . . . . . . . . . . . . . . . .

vii

RINGKASAN

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

viii

KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . . .

xvi

DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

xx

DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . . . xxii DAFTAR TABEL . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiii DAFTAR LAMBANG . . . . . . . . . . . . . . . . . . . . . . . . . . xxiv 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.1

Latar Belakang Masalah . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Rumusan Masalah . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.3

Batasan Masalah . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.4

Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.5

Manfaat Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . . . . .

6

2.1

Definisi dan Terminologi Dasar Graf . . . . . . . . . . . . . . . .

6

2.2

Jenis Graf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.3

Graf Khusus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.4

Operasi Graf

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.5

Pelabelan Graf . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2.6

Dekomposisi pada Graf . . . . . . . . . . . . . . . . . . . . . . . .

14

2.7

Aplikasi Graf . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.8

Fungsi dan Barisan Aritmatika

. . . . . . . . . . . . . . . . . . .

17

2.8.1

Fungsi . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.8.2

Barisan Aritmatika . . . . . . . . . . . . . . . . . . . . . .

18

xviii

2.9

Definisi, Aksioma, Teorema, Corollary, Konjektur, dan Open Problem 19

2.10 Keterampilan Berpikir Tingkat Tinggi . . . . . . . . . . . . . . .

20

3 METODE PENELITIAN . . . . . . . . . . . . . . . . . . . . . .

23

3.1

Metode Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

3.2

Definisi Operasional . . . . . . . . . . . . . . . . . . . . . . . . . .

23

3.2.1

Pelabelan Super (a, d) − Apo Anti Ajaib Total Dekomposisi

23

3.2.2

Graf Shackle Generalisasi Antiprisma Konektif . . . . . . .

24

3.2.3

Graf Shackle Generalisasi Antiprisma Diskonektif . . . . .

24

3.2.4

Indikator Pelabelan Super (a, d)−Apo Anti ajaib Total Dekomposisi Graf Shackle Generalisasi antiprisma . . . . . . . . .

25

3.3

Teknik Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

3.4

Observasi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

4 HASIL DAN PEMBAHASAN . . . . . . . . . . . . . . . . . . .

34

4.1

Graf Shackle Generalisasi Antiprisma Konektif . . . . . . . . . . .

4.2

Super (a, d) − Ao Anti Ajaib Total Dekomposisi Graf Shackle An-

4.3 4.4

35

tiprisma Konektif Shack(Ao , v, n) . . . . . . . . . . . . . . . . . .

36

Partisi dengan Menetapkan Beda d . . . . . . . . . . . . . . . . .

40

Super (a, d) −

Apo

Anti Ajaib Total Dekomposisi Graf Shackle Ge-

neralisasi Antiprisma Konektif Shack(Apo , v, n) . . . . . . . . . . .

45

4.5

Graf Shackle Generalisasi Antiprisma Diskonektif . . . . . . . . .

54

4.6

Partisi dengan Menetapkan Beda d untuk Graf Diskonektif . . . .

55

4.7

Super (a, d) − Apo Anti Ajaib Total Dekomposisi Graf Shackle Generalisasi Antiprisma Diskonektif mShack(Apo , v, n)

4.8

Pembangunan Ciphertext dari Super (a, d) −

. . . . . . . .

Apo -Anti

58

Ajaib Total

Dekomposisi Graf Shackle Generalisasi Antiprisma . . . . . . . . .

67

4.8.1

Metode Eliminasi . . . . . . . . . . . . . . . . . . . . . . .

67

4.8.2

Pembangunan Ciphertext Alfabet dari Super (812, 18) − Apo Anti Ajaib Total Dekomposisi Graf Shack(A24 , v, 3) . . . . . Pembangunan Ciphertext Alfabet dari Super (819, 11) − Apo Anti Ajaib Total Dekomposisi Graf Shack(A24 , v, 3) . . . . .

4.8.3

xix

69 71

4.8.4

Pembangunan Ciphertext Alfabet dari Super (453, 8) − Apo Anti Ajaib Total Dekomposisi Graf Shack(A23 , v, 3) . . . . .

4.8.5

Pembangunan Ciphertext Alfabet dari Super (528, 52) − Apo Anti Ajaib Total Dekomposisi Graf Shack(A23 , v, 4) . . . . .

4.8.6

79

Pembangunan Ciphertext Simbol dari Super (819, 11) − Apo Anti Ajaib Total Dekomposisi Graf Shack(A24 , v, 3) . . . . .

4.9

77

Pembangunan Ciphertext Alfabet dari Super (1205, 102) − Apo Anti Ajaib Total Dekomposisi Graf Shack(A33 , v, 3) . . .

4.8.7

74

82

Berfikir Tingkat Tinggi Dalam Super (a, d) − Apo Anti Ajaib Total Dekomposisi Graf Shackle Generalisasi Antiprisma dan Pengembangan Ciphertext . . . . . . . . . . . . . . . . . . . . . . . . . . .

84

4.9.1

Tahapan Mengingat

. . . . . . . . . . . . . . . . . . . . .

85

4.9.2

Tahapan Memahami . . . . . . . . . . . . . . . . . . . . .

86

4.9.3

Tahapan Menerapkan . . . . . . . . . . . . . . . . . . . . .

90

4.9.4

Tahapan Menganalisis . . . . . . . . . . . . . . . . . . . .

90

4.9.5

Tahapan Mengevaluasi . . . . . . . . . . . . . . . . . . . .

93

4.9.6

Tahapan Mencipta . . . . . . . . . . . . . . . . . . . . . .

99

4.10 Hasil dan Pembahasan . . . . . . . . . . . . . . . . . . . . . . . . 101 5 KESIMPULAN DAN SARAN . . . . . . . . . . . . . . . . . . . 111 5.1

Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

5.2

Saran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . . . 116 LAMPIRAN-LAMPIRAN . . . . . . . . . . . . . . . . . . . . . . . 120

xx

DAFTAR GAMBAR 2.1

Representasi graf pada permasalahan jembatan Konigsberg . . . .

6

2.2

Contoh graf secara umum . . . . . . . . . . . . . . . . . . . . . .

7

2.3

Contoh graf kosong N7 . . . . . . . . . . . . . . . . . . . . . . . .

7

2.4

Graf G isomorfis terhadap H . . . . . . . . . . . . . . . . . . . . .

8

2.5

Contoh graf sederhana, berhingga, dan tidak berarah . . . . . . .

8

2.6

(a) Contoh graf konektif; (b) contoh graf diskonektif . . . . . . . .

9

2.7

Contoh graf khusus . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.8

(a) Contoh graf shackle sisi; (b) contoh graf shackle titik . . . . .

11

2.9

Contoh pelabelan selimut dan dekomposisi . . . . . . . . . . . . .

14

2.10 Alur kerja cryptography . . . . . . . . . . . . . . . . . . . . . . . .

16

2.11 Contoh sifat fungsi khusus . . . . . . . . . . . . . . . . . . . . . .

18

2.12 Tahapan taksonomi Bloom . . . . . . . . . . . . . . . . . . . . . .

21

3.1

Graf shack(A34 , v, 2) . . . . . . . . . . . . . . . . . . . . . . . . . .

25

3.2

Graf 3shack(A34 , v, 2) . . . . . . . . . . . . . . . . . . . . . . . . .

26

3.3

Rancangan penelitian . . . . . . . . . . . . . . . . . . . . . . . . .

29

3.4

Observasi awal pada graf shack(A34 , v, 2) . . . . . . . . . . . . . .

30

3.5

Observasi awal pada graf 3shack(A34 , v, 2) . . . . . . . . . . . . . .

31

3.6

Observasi awal pada pembuatan ciphertext . . . . . . . . . . . . .

32

4.1

Super (812, 18) − Apo -anti ajaib total dekomposisi graf shack(A24 , v, 3) 69

4.2

Diagram pohon dari super (812, 18) − Apo anti ajaib total dekomposisi graf shack(A24 , v, 3) . . . . . . . . . . . . . . . . . . . . . . .

70

4.3

Super (819, 11) − Apo anti ajaib total dekomposisi graf shack(A24 , v, 3) 72

4.4

Diagram pohon dari super (819, 11) − Apo anti ajaib total dekomposisi graf shack(A24 , v, 3) . . . . . . . . . . . . . . . . . . . . . . .

73

4.5

Super (453, 8) − Apo anti ajaib total dekomposisi graf shack(A23 , v, 3) 75

4.6

Diagram pohon dari super (453, 8)−Apo anti ajaib total dekomposisi graf shack(A23 , v, 3) . . . . . . . . . . . . . . . . . . . . . . . . . .

4.7

75

Super (528, 52) − Apo anti ajaib total dekomposisi graf shack(A23 , v, 4) 77 xxi

4.8

Diagram pohon dari super (528, 52) − Apo anti ajaib total dekomposisi graf shack(A23 , v, 4) . . . . . . . . . . . . . . . . . . . . . . .

4.9

78

Super (1205, 102)−Apo anti ajaib total dekomposisi graf shack(A33 , v, 3) 80

4.10 Diagram pohon dari super (1205, 102) − Apo anti ajaib total dekomposisi graf shack(A33 , v, 3) . . . . . . . . . . . . . . . . . . . . . . .

80

4.11 Diagram pohon dari pengembangan ciphertext dari 39 karakter . .

84

4.12 Contoh Graf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

85

shack(Apo , v, n)

. . . . . . . . . . . . . . . . . . . . . . . . . .

86

4.14 Graf lintasan P4 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

91

4.15 Graf shack(A24 , v, 3) . . . . . . . . . . . . . . . . . . . . . . . . . .

91

4.16 Pelabelan himpunan titik pertama

. . . . . . . . . . . . . . . . .

92

4.17 Macam-macam partisi pelabelan . . . . . . . . . . . . . . . . . . .

92

4.18 Klasifikasi partisi himpunan titik pertama, d = 2 . . . . . . . . . .

94

4.19 Klasifikasi partisi himpunan titik pertama, d = 1 . . . . . . . . . .

94

4.13 Graf

2

4.20 Klasifikasi partisi, d = c . . . . . . . . . . . . . . . . . . . . . . .

96

4.21 Klasifikasi partisi, d = c . . . . . . . . . . . . . . . . . . . . . . .

96

c 2

. . . . . . . . . . . . . . . . . . . . . . .

97

4.23 Evaluasi bobot total selimut, d = 0 . . . . . . . . . . . . . . . . .

99

4.22 Klasifikasi partisi, d =

xxii

DAFTAR TABEL

2.1

Aturan Julius Caesar . . . . . . . . . . . . . . . . . . . . . . . . .

16

3.1

Pengembanganciphertext dari Gambar 3.6 . . . . . . . . . . . . .

33

4.1

Pengembangan ciphertext dari super (812, 18) − Apo anti ajaib total dekomposisi graf shack(A24 , v, 3) . . . . . . . . . . . . . . . . . . .

4.2

Pembangunan ciphertext dari super (819, 11) −

Apo

anti ajaib total

dekomposisi graf shack(A24 , v, 3) . . . . . . . . . . . . . . . . . . . 4.3

4.6 4.7

76

Pembangunan ciphertext dari super (528, 52) − Apo anti ajaib total dekomposisi graf shack(A23 , v, 4) . . . . . . . . . . . . . . . . . . .

4.5

73

Pembangunan Ciphertext dari Super (453, 8) − Apo Anti Ajaib Total Dekomposisi Graf Shack(A23 , v, 3) . . . . . . . . . . . . . . . . . .

4.4

71

Pembangunan ciphertext dari super

(1205, 102)−Apo

78

anti ajaib total

dekomposisi graf shack(A33 , v, 3) . . . . . . . . . . . . . . . . . . .

81

Aturan pengkodean untuk bilangan mod 39 dengan simbol . . . .

82

Proses penciptaan ciphertext dari super (819, 11) −

Apo -anti

ajaib

total dekomposisi graf shack(A24 , v, 3) . . . . . . . . . . . . . . . .

83

4.8

Ciphertext untuk alfabet, angka, dan tanda baca . . . . . . . . . .

83

4.9

Evaluasi pengeliminasian sisi . . . . . . . . . . . . . . . . . . . . .

99

xxiii

DAFTAR LAMBANG

G(V, E)

= Sebarang graf tak berarah dengan V adalah himpunan tak kosong dari semua titik dan E adalah himpunan sisi

Pn

= Graf Lintasan berorder n

Cn

= Graf Siklus berorder n

Apo

= Graf Generalisasi Antiprisma dengan Co × Pp

Shack(Apo , v, n) mShack(Apo , v, n)

= Graf Shackle titik dari generalisasi Antiprisma sebanyak n = Diskonektif dari Graf Shackle titik generalisasi Antiprisma sebanyak mcopy

V (G)

= Himpunan titik pada graf G

E(G)

= Himpunan sisi pada graf G

|V (G)|

= Banyaknya anggota himpunan titik pada graf G disebut order

|E(G)|

= Banyaknya anggota himpunan sisi pada graf G disebut size

d

= Nilai beda barisan bobot total dekomposisi

a

= Bobot selimut terkecil dari barisan bobot total dekomposisi

xi,j,k

= Titik ke-i dalam komponen ke-j pada shackle ke-k graf Shack(Apo , v, n)

xli,j,k

= Titik ke-i dalam komponen ke-j pada shackle ke-k dari copy ke-l gabungan graf mShack(Apo , v, n)

f (xi,j,k )

= Fungsi bijektif pelabelan titik graf konektif,Shack(Apo , v, n)

f (xli,j,k )

= Fungsi bijektif pelabelan titik graf diskonektif,mShack(Apo , v, n)

f (xi,j,k xi,j,k )

= Fungsi bijektif pelabelan sisi graf konektif,Shack(Apo , v, n)

f (xli,j,k xli,j,k )

= Fungsi bijektif pelabelan sisi graf diskonektif,mShack(Apo , v, n)

w(xi,j,k xi,j,k )

= Fungsi bobot sisi graf konektif,Shack(Apo , v, n)

w(xli,j,k xli,j,k )

= Fungsi bobot sisi graf diskonektif,mShack(Apo , v, n)

W (xi,j,k xi,j,k )

= Fungsi bobot total sisi graf konektif,Shack(Apo , v, n)

W (xli,j,k xli,j,k )

= Fungsi bobot total sisi graf diskonektif,mShack(Apo , v, n)

n Pc,d (k)

= Fungsi suatu partisi yang memiliki canggota dan beda

P

d untuk antar jumlah anggota pada partisi ke-k n Pc,d (k)

n Cc,d (k) (n,m) l (k )

Pc,d

n = Jumlah setiap anggota pada Pc,d (k) P n = Konstanta dari Pc,d (k)

= Fungsi suatu partisi yang memiliki c anggota dan beda d untuk antar jumlah anggota pada partisi ke-k xxiv

P

(n,m) l (k ) (n,m) l Pc,d (k )

= Jumlah setiap anggota pada Pc,d P (n,m) l = Konstanta dari Pc,d (k )

w(fk )

= Bobot total selimut

Pc,d

(n,m) l (k )

xxv

BAB 1. PENDAHULUAN 1.1

Latar Belakang Masalah Ilmu pengetahuan dan teknologi berkembang seiring kemajuan zaman serta

munculnya permasalahan yang kompleks dalam kehidupan sehari-hari. Setiap manusia sering kali berupaya untuk menyelesaikan permasalahan yang ada, namun tidak semua masalah dapat diselesaikan dengan mudah. Diperlukan proses berpikir agar seseorang dapat menyelesaikan masalahnya. Oleh sebab itu, manusia tidak bisa lepas dari proses berpikir. Menurut Plato berpikir adalah berbicara dalam hati. Sedangkan menurut Dewey dalam Kowiyah, berpikir dimulai apabila seseorang dihadapkan pada suatu masalah dan menghadapi sesuatu yang menghendaki adanya jalan keluar. Geiles dalam Saragih berpendapat bahwa berpikir adalah berbicara sendiri dalam batin, yaitu mempertimbangkan, merenungkan, menganalisis, membuktikan sesuatu, menunjukkan alasan-alasan, menarik kesimpulan, meneliti sesuatu atau jalan pikiran, dan mencari bagaimana berbagai hal dapat berhubungan satu sama lain. Ini berarti, berpikir adalah proses pencarian kebenaran maupun kesimpulan yang terjadi dalam batin saat dihadapkan pada suatu permasalahan. Setiap manusia memiliki cara berpikir yang berbeda sesuai dengan keterampilan berpikirnya. Keterampilan berpikir dimulai dari berpikir tingkat rendah hingga berpikir tingkat tinggi. Keterampilan berpikir tingkat tinggi termasuk dalam ranah kognitif. Taksonomi Bloom merupakan teori yang membahas keterampilan berpikir tingkat tinggi. Tiga ranah aspek kognitif menurut taksonomi Bloom meliputi aspek analisa, aspek evaluasi, dan aspek mencipta.

Bloom juga mengklasifikasikan

ranah kognitif dalam enam tingkatan, yaitu pengetahuan (knowledge), pemahaman (comprehension), penerapan (application), analisis (analysis), sintesin (synthesis), dan evaluasi (evaluation). Taksonomi Bloom yang telah direvisi adalah mengingat, memahami, menerapkan, menganalisis, mengevaluasi, dan mencip1

2 takan. Keterampilan berpikir dimulai dari berpikir tingkat rendah hingga berpikir tingkat tinggi. Mengingat, memahami, dan menerapkan adalah kategori keterampilan berpikir tingkat rendah. Menganalisis, mengevaluasi, dan menciptakan termasuk kategori berpikir tingkat tinggi. Hal ini berarti untuk mencapai keterampilan tingkat tinggi tetap harus melewati tiga ranah dasar yaitu mengingat, memahami, dan menerapkan. Keterampilan berpikir tingkat tinggi atau High Order Thinking Skill (HOTS) merupakan salah satu keterampilan berpikir dalam pemecahan masalah. Keterampilan berpikir tingkat tinggi sangat diperlukan oleh semua orang agar dapat menyelesaikan setiap permasalahan. Salah satu ilmu yang memerlukan keterampilan berpikir tingkat tinggi adalah matematika. Contohnya yaitu kemampuan berpikir kreatif dan memecahkan masalah matematis. Matematika merupakan mother of sciene atau induk ilmu pengetahuan. Matematika juga disebut sebagai ilmu yang mendasari ilmu pengetahuan yang lain dan merupakan ilmu pengetahuan yang kompleks. Cabang ilmu matematika terdiri dari matematika aplikasi, matematika analisis, matematika ekonomi, matematika komputerisasi, matematika diskrit, matematika statistik, dan lain sebagainya. Salah satu cabang matematika adalah teori graf yang merupakan aplikasi dalam matematika diskrit. Sejak tahun 1736 banyak ilmuan mengembangkan teori graf untuk memecahkan berbagai masalah bahkan diberbagai bidang ilmu. Graf sudah banyak memecahkan masalah diantaranya masalah jaringan komunikasi, ilmu komputer, riset operasi, ilmu kimia, sosiologi, kartograph, teknik konstruksi, peningkatan keterampilan daya pikir dan sebagainya. Graf merupakan representasi viusal yang menyatakan objek sebagai noktah, bulatan, titik, atau vertex sedangkan hubungan antar objek dinyatakan dengan garis, sisi, atau edge. Salah satu topik dalam teori graf yang menarik adalah pelabelan graf. Pelabelan graf pertama kali muncul pada pertengahan tahun 1960-an yang diawali sebuah hipotesis oleh Ringel dan Rosa serta diperkenalkan oleh Sedlacek (1964) dan Stewart (1966). Pelabelan graf adalah pemetaan satu-satu dari himpunan elemen graf ke himpunan bilangan bulat positif. Elemen graf meliputi himpunan

3 titik, himpunan sisi, serta himpunan titik dan sisi. Berdasarkan elemen yang dilabeli, pelabelan graf dibagi menjadi tiga yaitu pelabelan titik, pelabelan sisi, dan pelabelan total. Pelabelan berkembang menjadi pelabelan gracefull, pelabelan harmoni, pelabelan total tak beraturan, pelabelan ajaib, dan pelabelan anti ajaib (anti ajaib). Pelabelan yang mengikuti selimut-H dari graf G disebut sebagai pelabelan selimut atau dikenal dengan pelabelan covering. Apabila selimut atau H−covering dari graf G termuat tepat satu graf Hi untuk suatu i ∈ {1, 2, 3, ˙,k}, maka selimut-H disebut dekomposisi. Graf generalisasi antiprisma Anm adalah graf yang dapat dihasilkan dengan melengkapi graf generalisasi prisma Cm ×Pn dengan menambahkan sisi vi,j+1 vi+1,j dari 1 ≤ i ≤ m − 1, 1 ≤ j ≤ n − 1, dan sisi vm,j+1 v1,j untuk 1 ≤ j ≤ n − 1. Graf generalisasi antiprisma merupakan graf khusus yang dikenal dengan nama generlized antiprism graph. Graf juga mengenal operasi graf yang terdiri dari Disjoint Union (G ∪ H), Joint (G + H), Cartesian Product (G¤H), Crown Product (G ¯ H), Symmetric Product (G ⊕ H), Tensor Product (G ⊗ H), Compotision (G[H]), Shackle, dan Amalgamasi. Penelitian ini akan lebih mengkaji operasi shackle, yaitu operasi graf yang menguhubungkan dua atau lebih graf dimana bila terdapat m graf yang dihubungkan maka terdapat m−1 penghubung yang berbeda. Graf shackle dipilih karena belum ada yang meneliti tentang shackle generalisasi antiprisma. Pelabelan dapat diaplikasikan dalam pengembangan ciphertext atau pesan rahasia. Ciphertext adalah bagian dari cryptosystem. Ciphertext dibuat agar pesan yang dikirimkan oleh pengirim tidak terbaca oleh orang lain selain penerima pesan yang dituju. Terdapat beberapa cara untuk mngubah pesan menjadi pesan rahasia, salah satunya adalah Caesar system yang menerapkan sistem (mod 26). Penelitian ini akan mengkaji keterkaitan antara menciptakan teorema dari pelabelan dekomposisi dari graf shackle generalisasi antiprisma yang akan diaplikasikan pelabelan dekomposisi untuk pengembangan ciphertext dengan keterampilan berpikir tingkat tinggi yang menggunakan acuan Taksonomi Bloom yang telah direvisi. Berdasarkan pada latar belakang tersebut maka dilakukan penelitian dengan judul ”Super (a, d)−Apo Anti Ajaib Total Dekomposisi Graf Shac-

4 kle Generalisasi Antiprisma untuk Pengembangan Ciphertext dan Keterampilan Berpikir Tingkat Tinggi”. 1.2

Rumusan Masalah Berdasarkan latar belakang di atas, maka dapat dirumuskan masalah dalam

penelitian ini yaitu: 1. bagaimana pelabelan super (a, d) − Apo anti ajaib total dekomposisi graf shackle generalisasi antiprisma konektif dan diskonektif? 2. bagaimana pengembangan ciphertext dengan menggunakan super (a, d)−Aop anti ajaib total dekomposisi graf shackle generalisasi antiprisma? 3. bagaimana kegunaan super (a, d) − Apo anti ajaib total dekomposisi graf shackle generalisasi antiprisma konektif dan diskonektif dalam mengasah keterampilan berpikir tingkat tinggi? 1.3

Batasan Masalah Untuk menghindari meluasnya permasalahan yang akan dipecahkan, maka

permasalahan penelitian ini dibatasi pada: 1. semua graf yang digunakan adalah graf sederhana, berhingga, tak trivial, dan tak berarah; 2. graf yang digunakan adalah graf well known dan hasil operasi shackle titik pada graf antiprisma sehingga graf shackle generalisasi antiprisma konektif disimbolkan shack(Apo , v, n) dan diskonektifnya disimbolkan dengan mshack(Apo , v, n) dengan n ≥ 2, m ≥ 2, o ≥ 3, dan p ≥ 2. Adapun maaksut dari beberapa simbol tersebut adalah o merupakan banyaknya titik pada graf siklus Co , p merupakan nilai graf lintasan Pp yang digunakan atau banyaknya graf Co pada setiap graf generalisasi antiprisma, n merupakan banyaknya graf generalisasi antiprisma yang dishackle, dan m merupakan banyaknya copy dari graf shack(Apo , v, n); 3. ciphertext dikembangkan dari 5 model super (a, d) − Apo anti ajaib total dekomposisi dari shack(Apo , v, n) yang sudah ditemukan. Ciphertext yang akan dikembangkan terdiri dari 5 macam ciphertext alfabet dan satu ciphertext simbol;

5 4. graf shackel generalisasi antiprisma konektif maupun diskonektif didekomposisikan terhadap graf generalisasi antiprisma Hi = H1 , H2 , . . . , Hn adalah dekomposisi dari graf G dimana Hi = Apo dan Hi isomorfis, dengan kata lain setiap dekomposisi isomorfis; 5. menggunakan Taksonomi Bloom yang telah direvisi. 1.4

Tujuan Penelitian Sesuai dengan rumusan masalah dan latar belakang di atas, maka tujuan

dari penelitian ini adalah sebagai berikut: 1. untuk mengetahui pelabelan super (a, d) − Apo anti ajaib total dekomposisi graf shackle generalisasi antiprisma konektif dan diskonektif; 2. untuk mengetahui pengembangan ciphertext dengan menggunakan super (a, d) − Apo anti ajaib total dekomposisi graf shackle generalisasi antiprisma; 3. untuk mengetahui kegunaan super (a, d) − Apo anti ajaib total dekomposisi graf shackle generalisasi antiprisma konektif dan diskonektif dalam mengasah keterampilan berpikir tingkat tinggi. 1.5

Manfaat Penelitian Manfaat yang diharapkan dari hasil penelitian ini adalah:

1. menambah pengetahuan baru dalam bidang teori graf mengenai dekomposisi graf salah satunya adalah pengembangan super (a, d) − Apo anti ajaib total dekomposisi graf shackle generalisasi antiprisma; 2. menambah wawasan baru dalam menciptakan keterampilan berpikir tingkat tinggi dalam dekomposisi graf shackle generalisasi antiprisma; 3. menambah pengetahuan baru tentang ciphertext dan mengubah plaintext (kalimat pesan) menjadi ciphertext (kalimat rahasia); 4. hasil penelitian ini diharapkan dapat digunakan sebagai perluasan ilmu atau pengembangan ilmu dalam masalah pelabelan super (a, d) − Apo anti ajaib total dekomposisi.

BAB 2. TINJAUAN PUSTAKA 2.1

Definisi dan Terminologi Dasar Graf Teori graf pertama kali muncul pada tahun 1736 ketika Leonard Euler men-

coba menyelesaikan masalah Jembatan Konigsberg yaitu jembatan di sebuah kota tua di Prusia Timur yang sekarang dikenal dengan sebutan Kalinigrad. Tujuh jembatan dibangun di atas sungai Pregel agar memungkinkan penghuni Konigsberg dapat berjalan dari satu kota ke kota yang lain. Pada saat itu orang-orang ingin membuat sebuah rute agar orang-orang dapat menyebrangi ketujuh jembatan satu kali saja, namun hal tersebut tidak membuahkan hasil. Leonard Euler berhasil menemukan penyelesaiannya dengan menggunakan graf dimana keempat kota itu sebagai titik (vertex) dan ketujuh jembatan sebagai sisi (edge) yang menghubungkan pasangan titik yang sesuai (Saoni, 2003).

Sumber: www.flickir.com

(b)

(a)

Gambar 2.1 Representasi graf pada permasalahan jembatan Konigsberg

Slamin (2009) menyatakan bahwa sebuah graf G merupakan himpunan (V (G), E(G)), dimana V (G) adalah himpunan berhingga tak kosong dari elemen yang disebut titik, dan E(G) adalah sebuah himpunan (boleh kosong) dari pasangan tak terurut uv dari titik-titik u, v ∈ V (G) yang disebut sisi. V (G) disebut himpunan titik dari G dan E(G) disebut himpunan sisi dari G. 6

7 Beberapa contoh graf secara umum dapat dilihat pada Gambar 2.2 v1

e2

v2 e3

e1 v4

e4

e2

v1 e1 v4

v3

v2

e5 e4

v2

e3 v3

v2

G2 (b)

G1 (a)

v2 G3 (c)

Gambar 2.2 Contoh graf secara umum

Berdasarkan definisi tersebut, dapat disimpulkan bahwa ada graf yang hanya terdiri dari titik saja. Graf semacam ini disebut sebagai graf kosong. Seperti yang dinyatakan oleh Saoni (2003) bahwa graf kosong adalah graf yang tidak mempunyai sisi. Graf kosong (empity graph) disebut juga graf nol (null graph) dan dinotasikan dengan Nn dengan n sebagai banyaknya titik dari N . Gambar 2.3 adalah contoh graf kosong. Sedangkan graf tidak trivial adalah graf yang terdiri dari sedikitnya dua titik. v1

v2 v6

v3

v7 v4

v5 N7

Gambar 2.3 Contoh graf kosong N7

Sebuah graf G terdiri dari dua himpunan yaitu himpunan titik V (G) dan himpunan sisi E(G), dimana himpunan sisi boleh himpunan kosong. Graf dinotasikan dengan G = (V (G), E(G)). JIka x dan y adalah titik yang termuat pada V (G) maka sisi yang menghubungkan titik x dan y dinotasikan dengan xy (Sugeng, 2005). Penomoran titik graf dapat menggunakan huruf, bilangan asli, atau huruf yang disertai bilangan asli. Aturan penomoran titik mengikuti karakteristik graf. Banyak titik pada graf disebut order |V (G)| = p dan banyak sisi disebut size |E(G)| = q. Penulisan himpunan titik dan himpunan sisi pada graf tidak selalu menyertakan notasi graf, terutama pada saat notasi graf simplicity maka dapat dituliskan V untuk V (G) dan E untuk E(G).

8 Melihat graf tidak hanya dari bentuknya saja, sebab ada graf yang bentuknya berbeda namun sebenarnya sama, graf seperti ini disebut sebagai isomorfis. Sebuah graf G dikatakan isomorfis terhadap graf H jika terdapat pemetaan satu-satu Φ menjaga ajensi. Jadi, (uv) ∈ E(G) jika dan hanya jika (Φ(v) ∈ E(H)) (Saoni, 2003). Untuk lebih jelas lihatlah Gambar 2.4. v1

v1 v5 v3

v4

v5

v2

v2

v4

H (a)

v3 G (b)

Gambar 2.4 Graf G isomorfis terhadap H

2.2

Jenis Graf Dari definisi graf secara umum, graf dikelompokkan lagi menjadi beberapa

jenis graf berdasarkan pada ada tidaknya gelang atau sisi ganda, jumlah simpul, dan orientasi arah pada sisi. Penelitian ini hanya membahas graf yang sederhana, berhingga, tidak berarah, konektif dan diskonektif. Graf sederhana adalah graf yang tidak mengandung gelang (loop) atau sisi ganda (lebih dari satu sisi penghubung antara dua titik) (Yulianti, 2008). Sedangkan sebuah graf dikatakan berhingga bila order n berhingga seperti yang pernah dinyatakan oleh Sugeng (2005). Selain itu, suatu graf dikatakan tak berarah apa bila graf tidak memiliki arah. Gambar 2.5 adalah gambar contoh graf sederhana, berhingga, sekaligus tidak berarah.

(a)

(b)

Gambar 2.5 Contoh graf sederhana, berhingga, dan tidak berarah

9 Sebuah graf terhubung (connected graph) atau graf konektif adalah graf yang terdapat sisi dari x ke y untuk setiap pasangan titik x, y ∈ V , sedangkan yang selainnya disebut tak terhubung atau diskonektif (disconnected). Untuk lebih memahami perhatikan Gambar 2.6.

(a)

(b)

Gambar 2.6 (a) Contoh graf konektif; (b) contoh graf diskonektif

2.3

Graf Khusus Graf khusus adalah graf yang memiliki keunikan dan karakteristik bentuk

khusus. Keunikan dari graf khusus adalah tidak isomorfis dengan graf lainnya. Karakteristik bentuknya adalah dapat diperbanyak sampai order n tetapi tetap simetris. Dari definisi graf secara umum, terdapat beberapa graf khusus salah satunya adalah graf generalisasi antiprisma Apo . Sebelum membahas tentang graf generalisasi antiprisma Apo akan disajikan definisi beberapa graf khusus yang digunakan dalam penelitian ini. Menurut Munir (2001), Graf siklus atau graf lingkaran dinotasikan dengan Cn adalah graf reguler yang berderajat dua, artinya pada graf siklus untuk setiap titiknya mempunyai derajat dua, sehingga dalam graf siklus jumlah titik dan jumlah sisinya sama. Graf siklus Cn hanya dapat dibentuk dengan n ≥ 3. Graf path (graf lintasan) dinotasikan dengan Pn adalah graf yang memiliki n − 1 sisi (Purwanto, 2006). Graf yang menjadi subgraf sekaligus merupakan pendekomposisi dari penelitian ini adalah graf generalisasi antiprisma. Graf generalisasi antiprisma merupakan graf yang dihasilkan melalui penambahan sisi pada graf generalisasi prisma. Lin Y, ddk, (2000) mengartikan graf generalisasi prisma adalah sebuah graf yang

10 terdiri dari sebuah siklus luar dengan n titik y1 , y2 , y3 , ..., yn dan sebuah siklus dalam dengan n titik x1 , x2 , x3 , ..., xn dan antara siklus luar dengan siklus dalam dihubungkan n jari-jari xi yi , i = 1, 2, 3, ..., n. Sedangkan graf generalisasi antiprisma Anm dapat dihasilkan dengan melengkapi graf prisma Cm × Pn dengan menambahkan sisi vi,j+1 vi+1,j dari 1 ≤ i ≤ m − 1, 1 ≤ j ≤ n − 1, dan sisi vm,j+1 v1,j untuk 1 ≤ j ≤ n − 1 (Sugeng, 2005). Contoh keempat graf tersebut dapat dilihat pada Gambar 2.7.

(a) Graf Siklus C6

(c) Graf Prisma P42

(b) Graf Path P4

(d) Graf Antiprisma A24

Gambar 2.7 Contoh graf khusus

2.4

Operasi Graf Operasi graf adalah beberapa cara untuk memperoleh graf baru dengan

melakukan suatu terhadap dua atau lebih graf. Operasi graf yang digunakan dalam penelitian ini adalah shackle graf dan gabungan graf. Menurut Maryati dkk (2010), graf belenggu atau yang sering disebut shackle dinotasikan dengan shack(G1 , G2 , . . . , Gn ) sebagai sebuah graf yang dibentuk dari n graf terhubung tak trivial G1 , G2 , . . . , Gn sehingga untuk setiap s, t ∈ [1, n] dengan |s − t| ≥ 2 berlaku Gs dan Gt tidak mempunyai titik yang sama, dan untuk setiap i ∈ [1, n − 1], Gt dan Gt+1 mempunyai tepat satu titik yang sama, disebut titik penghubung, dan k − 1 titik penghubung tersebut semuanya berbeda (Maryati dkk, 2010). Bila untuk setiap i ∈ [1, n], Gi isomorfis dengan graf H, maka shack(G1 , G2 , . . . , Gn ) dinamakan shackle dari graf H, dinotasikan

11 shack(H, n). Shackle memiliki beberapa macam tergantung penghubungnya, bila penghubungnya berupa titik maka disebut sebagai shackle titik dinotasikan dengan shack(H, v, n). Jika penghubungnya berupa sisi disebut shackle sisi dinotasikan dengan Shack(H, e, n). Contoh graf shackle dapat dilihat pada Gambar 2.8.

(a) Graf Shack(C5 , e, 3)

(b) Graf Shack(C4 , v, 3)

Gambar 2.8 (a) Contoh graf shackle sisi; (b) contoh graf shackle titik

Adawiyah (2014)menyatakan gabungan dari dua graf G1 dan G2 , dan dinotasikan dengan G1 ∪G2 , didefinisikan sebagai graf dengan himpunan titik V (G1 )∪ V (G2 ) dan himpunan sisi E(G1 ) ∪ E(G2 ). Dengan kata lain gabungan graf saling lepas adalah dua atau lebih graf yang tidak memiliki lintasan yang menghubungkan masing-masing anggota graf. Jika Gi dengan 1 ≤ i ≤ m dimana setiap Gi isomorfis dengan graf G maka gabungan graf saling lepas ini dinotasikan dengan mG = G1 ∪ G2 ∪ · · · ∪ Gm dimana m adalah banyaknya copy graf G. 2.5

Pelabelan Graf Pelabelan graf pertama kali dikenalkan oleh Sedl´acˇek tahun 1963 sebagai

perumusan ide bujur sangkar ajaib. Seiring berkembangnya zaman pelabelanpun semakin berkembang. Sebelum mengetahui macam-macam pelabelan graf lebih baik mengetahui definisi dari pelabelan graf. Misalkan G = (V (G), E(G)) adalah graf berhingga dengan |V (G)| = vG dan |E(G)| = eG . Pelabelan graf G didefinisikan sebagai suatu fungsi yang memetakan elemen-elemen G ke suatu subhimpunan bilangan bulat positif (Inayah, 2013). Pelabelan Graf menggunakan bilangan bulat positif. Fungsi yang memetakan merupakan fungsi injektif, sehingga tidak ada elemen titik maupun sisi yang memiliki label sama. Secara singkat, f : A → B adalah bijektif atau fungsi satu-satu jika f (a) = f (a0 ) maka a = a0 . Pelabelan dapat diberikan pada titik, sisi, atau titik dan sisi. Pelabelan

12 yang diberikan pada titik disebut pelabelan titik (vertex labeling), demikian juga jika pelabelan diberikan pada sisi disebut pelabelan sisi (edge labeling). Sedangkan pelabelan yang diberikan pada titik dan sisi disebut pelabelan total (total labeling). Pada pelabelan titik, dikenal istilah bobot sisi yaitu jumlah label dua titik yang menempel pada suatu sisi. Sedangkan pada pelabelan total, bobot sisi diartikan sebagai jumlah label sisi dan label dua titik yang menempel pada suatu sisi. Untuk membedakan kedua bobot sisi tersebut maka bobot sisi pada pelabelan total sering kali disebut sebagai bobot total sisi dan memiliki notasi yang berbeda. Bobot sisi dinotasikan dengan w sedangkan bobot total sisi dinotasikan dengan W . Awal mula pelabelan muncul istilah yang bdikenalkan adalah bobot titik yang berarti jumlah label sisi yang terkait pada setiap titik. Macam-macam pelabelan graf adalah sebagai berikut: Inayah (2013) menyebutkan bahwa Sedl´acˇek (1963) mendefinisikan suatu graf dikatakan ajaib jika sisi-sisinya dapat dilabeli dengan bilangan bulat positif sehingga jumlah label sisi yang terkait pada setiap titik selalu sama. Perkembangan pelabelan ajaib tidak hanya pada pelabelan sisi saja, namun dapat dikembangkan pada pelabelan titik maupun pelabelan total. Sehingga yang menjadi syarat dikatakan pelabelan ajaib adalah memiliki bobot titik, bobot sisi, maupun bobot total sisi yang sama atau memiliki beda d = 0. Pelabelan magic atau ajaib pada graf G disebut super magic apabila label yang digunakan merupakan bilangan berurutan. Graf super magic ini pertama kali diperkenalkan oleh Stewart. Sehingga dalam pelabelan magic terdapat berbagai macam pelabelan seperti, pelabelan sisi ajaib (Edge Magic Labeling), pelabelan titik ajaib (Vertex Magic Labeling), pelabelan total ajaib (Edge Magic Total Labeling), pelabelan super titik ajaib (Super Vertex Magic Labeling), pelabelan super sisi ajaib (Super Edge Magic Labeling), pelabelan super sisi total ajaib (Super Edge Magic Total Labeling). Pelabelan ajaib terus dikembangkan sehingga pada tahun 1990 Hartsfield dan Ringel memperkenalkan pelabelan anti ajaib (antimagic labeling). Definisi 2.5.1. (Pelabelan Anti Ajaib) Suatu graf G disebut anti ajaib, jika sisi-sisinya dapat dilabeli dengan {1, 2, . . . , eG } sehingga setiap titik mempunyai

13 bobot titik yang berbeda (Hartsfield, 1990). Kemudian Bodendiek dan Walther pada tahun 1993 mengembangkan pelabelan anti ajaib sedemikian hingga bobot titik berbeda namun aritmatik, pelabelan sisi (a, d)-titik- anti ajaib ini disebut dengan pelabelan (a, d)-titik- anti ajaib ((a, d)-vertex antimagic labeling). Definisi 2.5.2. (Pelabelan (a, d)-Titik-Anti Ajaib) Pelabelan (a, d)-titik-anti ajaib adalah pelabelan pada sisi dengan fungsi injektif f dari E(G) ke {1, 2, . . . , eG } sedemikian hingga himpunan bobot titik di G adalah {a, a + d, a + 2d, . . . , a + (vG − 1)d} dengan a, d adalah bilangan bulat positif (Bodendiek dkk, 1993). Definisi tersebut menjelaskan bahwa a adalah bobot sisi pertama sedangkan d adalah beda. Beda antar bobot sisi menunjukkan bahwa himpunan bobot titik yang terbentuk merupakan barisan aritmatika dengan beda d. Seperti pada pelabelan ajaib maka pelabelan anti ajaib juga mempunyai pelabelan total yang dikembangkan oleh Simanjuntak dkk pada tahun 2000. Definisi 2.5.3. (Pelabelan Total (a, d)−Sisi Anti Ajaib) Pelabelan total (a, d)−sisi anti ajaib adalah fungsi injektif f : V (G)∪E(G) → {1, 2, 3, . . . , vG +eG } yang memenuhi himpunan bobot sisi {f (u) + f (uv) + f (V )|uv ∈ E(G)} = {a, a + d, a+2d, . . . , a+(eG −1)d} untuk suatu bilangan bulat positif a dan d (Simanjuntak dkk, 2000). Pelabelan total dapat dikatakan sebagai pelabelan super apabila jika titik diberi label lebih kecil daripada label sisi atau f (V (G)) = {1, 2, . . . , vG } dan label sisi melanjutkan label titik f (E(G)) = {vG + 1, vG + 2, . . . , vG + eG }. Namun perlu diketahui bahwa tidak semua graf memiliki pelabelan (a, d) sisi anti ajaib. Simanjuntak, dkk (2000) telah menunjukkan bahwa graf tertentu tidak mempunyai pelabelan total (a, d) sisi anti ajaib yang tertuang dalam teorema berikut. Teorema 2.5.1. Misalkan G adalah suatu graf yang semua titiknya berderajad ganjil. Jika eG ≡ 0 (mod 4) dan vG ≡ 2 (mod 4) maka G tidak memiliki pelabelan (a, d)sisi anti ajaib (Simanjuntak dkk, 2000).

14 2.6

Dekomposisi pada Graf Dekomposisi merupakan kelanjutan dari selimut sehingga sebelum mema-

hami dekomposisi perlu dipahami arti selimut pada graf. Inayah (2013) menyatakan bahwa selimut dari graf G adalah H = {H1 , H2 , H3 , . . . , Hk } keluarga dari G dengan sifat setiap sisi di G termuat pada sekurang-kurangnya satu graf Hi untuk setiap i ∈ {1, 2, . . . , k}. Jika untuk setiap i ∈ {1, 2, . . . , k}, Hi isomorfik dengan suatu subgraf H, maka H dikatakan suatu selimut-H dari G. Pelabelan kemudian dikembangkan melalui konsep selimut yang pertama kali diperkenalkan oleh Guti´errez dan Llad´o (2005) yang dikenal dengan pelabelan selimut−H ajaib. Selimut yang lebih khusus atau berkorespondensi satu-satu disebut sebagai dekomposisi. Jika selimut-H dari G memiliki sifat setiap sisi di G termuat tepat satu graf Hi untuk i ∈ {1, 2, . . . , k}, maka selimut H disebut dekomposisiH. Sehingga dapat dikatakan bahwa G terdekomposisi atas H atau G memuat dekomposisi-H. Gambar 2.9 memperjelas tentang perbedaan selimut dan dekomposisi dapat dilihat pada.

(a) Contoh pelabelan selimut-C3 pada graf W4

(b) Contoh pelabelan dekomposisi-P2 pada graf W4

Gambar 2.9 Contoh pelabelan selimut dan dekomposisi

Pada dekomposisi terdapat pula pelabelan yang berdasarkan pada dekomposisi graf baik pada pelabelan ajaib maupun anti ajaib. Terdapat teorema berkaitan dengan pelabelan berdasarkan dekomposisi pada graf:

15 Lemma 2.6.1. Jika sebuah graf G(V, E) adalah pelabelan selimut (a, d) − H anti (pG −pH )pH +(qG −qH )qH s−1 qG = |E|, pH = |V 0 |,

ajaib super maka d ≤

untuk s = |Hi |, H ⊆ G yang isomorfik

dengan H pG = |V |,

qH = |E 0 | (Dafik, 2014).

Teorema 2.6.1. Misalkan H adalah graf terhubung tak trivial dan k adalah bilangan bulat, k ≥ 2. Jika Shack(H, k) dengan k subgraf yang isomorfis terhadap H, maka shack(H, k) adalah super (a, d) − H−antimagic dari 1 ≤ d ≤ m + n (Inayah dkk, 2013). Teorema 2.6.2. Misalkan H adalah graf terhubung tak trivial dan k, p, dan m adalah bilangan bulat positif dimana k ≥ 2 dan p ≤ m. Jika shack(H, k) berisikan tepat k subgraf yang isomorfik terhadap H, maka shack(H, k) adalah super (a, d)H-antimagic dimana d = n2 − n + m − 2p (Inayah dkk, 2013). Merujuk pada karakteristik graf shack(Apo , v, n) bila di dekomposisikan terhadap Apo maka karakteristiknya akan sama dengan karakter graf path. Penelitian ini juga merujuk pada teorema berikut. Teorema 2.6.3. Misalkan G adalah sebuah graf (a, 1)−EAT. Maka mG, m ≥ 1 juga merupakan sebuah graf (b, 1)−EAT (Baˇca dkk, 2009). Kemudian Azizah dkk, melanjutkan penelitian tersebut sehingga terciptalah teorema Teorema 2.6.4. Misalkan G adalah sebarang graf pohon. G adalah graf (a, 1)−P2 anti ajaib covering dengan order sebanyak p dan sisi sebanyak q. m ≥ 3 dan m S ganjil, gabungan terpisah m i=1 Gi juga (b, 1)−P2 −anti ajaib covering (Azizah dkk, 2014). 2.7

Aplikasi Graf Graf sangat bermanfaat bagi kehidupan manusia sebab graf dapat diapli-

kasikan dalam berbagai kebutuhan. Saondi (2013) menjelaskan berbagai macam aplikasi graf yaitu dalam transparansi, komunikasi, pewarnaan peta, ikatan kimia, desain arsitektur. Beberapa aplikasi graf yang lain adalah untuk pengaturan jadwal, kristografi, astronomi. Akhir-akhir ini, aplikasi graf mulai dikembangkan

16 kembali yaitu pengembangan ciphertext. Proses pengembangan ini disebut sebagai cryptosystem yang di dalamnya menyangkut cryptography. Cryptography adalah berbagai skema yang mungkin untuk encryption dan decryption (Kak, 2015). Encryption adalah proses pengubahan plaintext (pesan yang akan dikirim) menjadi ciphertext (pesan rahasia) sedangkan decryption adalah proses untuk memperoleh kembali plainttext dari ciphertext. Dalam proses ini dibutuhkan sebuah kunci rahasia untuk mengatur beberapa atau semua yang digunakan dalam proses encryption maupun decryption. Adapun alur kerja dalam cryptography dapat dilihat pada Gambar 2.10.

Plainttext

Plainttext Kunci A

Kunci B Ciphertext

Encryption Algorithm

Saluran

Pengirim

Decryption Algorithm

Pengacau

Penerima

Gambar 2.10 Alur kerja cryptography

Terdapat banyak metode yang dapat digunakan untuk memperoleh chipertext seperti affine ciphers, vigenere ciphers, the one-time pad, Caesar system, dan sebagainya. Metode yang digunakan pada penelitian ini merupakan aplikasi pelabelan total dekomposisi. Metode ini merujuk pada Caesar system yaitu menggunakan sistem (mod 26), atau disebut dengan aturan Julius Caesar. Tabel 2.1: Aturan Julius Caesar 0

1

2

3

4

5

6

7

8

9

10

11

12

A

B

C

D

E

F

G

H

I

J

K

L

M

13

14

15

16

17

18

19

20

21

22

23

24

25

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

17

2.8 2.8.1

Fungsi dan Barisan Aritmatika Fungsi Fungsi seringkali disebut dengan pemetaan. Fungsi f dari himpunan X

ke himpunan Y dinotasikan dengan f : X → Y adalah aturan korespondensi satusatu yang menghubungkan setiap x²X dengan tepat satu ke anggota Y. Himpunan X disebut domain dari fungsi f sedangkan himpunan Y disebut kodomain dari fungsi f dan hasil atau range dari fungsi f adalah himpunan bagian dari Y . Menurut Susilo (2012) terdapat tiga sifat fungsi khusus, yaitu: 1. Fungsi Injektif Suatu fungsi f : X → Y disebut fungsi (pemetaan) injektif jika dan hanya jika untuk setiap x1 , x2 ²X berlaku apabila f (x1 ) = f (x2 ) maka x1 = x2 yaitu bila dua elemen dalam domain mempunyai bayangan (peta) yang sama, maka kedua elemen itu adalah elemen yang sama. Secara matematis dapat dinyatakan: f adalah fungsi injektif ⇔ (∀x1 , x2 ²X)f (x1 ) = f (x2 ) ⇒ x1 = x2 . Secara ekivalen, juga dapat dinyatakan bahwa: f adalah fungsi injektif ⇔ (∀x1 , x2 ²X), x1 6= x2 ⇒ f (x1 ) 6= f (x2 ) yaitu jika dua elemen dalam domain adalah dua elemen yang tidak sama, maka bayangan (peta) kedua elemen itu juga tidak sama. 2. Fungsi Surjektif Fungsi f : X → Y adalah fungsi surjektif jika dan hanya jika untuk setiap y²Y terdapat x²X sedemikian sehingga y = f (x), yaitu setiap elemen dalam kodomain mempunyai prabayangan (prapeta). Secara matematis dapat dinyatakan: f adalah fungsi surjektif ⇔ (∀y²Y )(∃x²X)y = f (x). 3. Fungsi Bijektif

18 Suatu fungsi f : X → Y disebut fungsi (pemetaan) bijektif jika dan hanya jika fungsi f tersebut adalah fungsi yang injektif dan sekaligus surjektif. Pada fungsi bijektif, setiap elemen dalam domain mempunyai tepat satu bayangan dan setiap elemen dalam kodomain juga mempunyai tepat satu prabayangan. Oleh karena itu, fungsi bijektif seringkali juga disebut korespondensi satu-satu. Contoh dari ketiga sifat fungsi khusus tersebut dapat dilihat pada Gambar 2.11. (X) 1 2 3

f(x)

(Y) w i s u

(X) (Y) f(x) 1 i 2 p 3 k 4

(X) 1 2 3 4

f(x) (Y) a m i n

d a (a) Fungsi Injektif

(b) Fungsi Surjektif

(c) Fungsi Bijektif

Gambar 2.11 Contoh sifat fungsi khusus

2.8.2

Barisan Aritmatika Barisan adalah suatu susunan bilangan yang dibentuk menurut suatu

urutan tertentu. Barisan aritmatika adalah suatu barisan yang memiliki beda (selisih) antaradua suku berurutan tetap (kostan). Barisan aritmatika yang digunakan dalam penelitian ini adalah barisan aritmatika ditingkat satu. Artinya suatu barisan yang antara dua suku berurutan memiliki beda tetap (konstan) pada tingkat pertama. Berikut adalah beberapa contoh barisan bilangan: 1. 1, 7, 13, 19, . . . 2. 101, 93, 85, . . . 3. 101, 113, 125, . . .

19 Berdasarkan contoh barisan tersebut, didapat bahwa untuk contoh 1, suku pertama (U1 ) = 1, suku kedua (U2 ) = 7 yang diperoleh dari suku pertama ditambah 6, dan seterusnya. Selisih dari setiap suku berurutan dari barisan ini adalah tetap, yaitu sebesar 6. Barisan ini disebut barisan aritmatika dan selisih yang tetap dari barisan ini disebut beda barisan yang dilambangkan dengan b. Demikian halnya dengan contoh 2 dan 3, disebut juga barisan aritmatika meskipun memiliki nilai beda yang tidak sama dengan contoh 1. Contoh 2 memiliki nilai beda b = −8, sedangkan contoh 3 memiliki beda b = 12. Rumus suku ke−n dari barisan aritmatika, yaitu jika suku pertama barisan aritmatika U1 disimbolkan a, maka diperoleh: U1 = a U2 − U1 = b ⇔ U2 = U1 + b = a + b U3 − U2 = b ⇔ U3 = U2 + b = (a + b) + b = a + 2b U4 − U3 = b ⇔ U4 = U3 + b = (a + 2b) + b = a + 3b dan seterusnya, sehingga diperoleh barisan aritmatika dalam bentuk: a, a + b, a + 2b, a + 3b, ..., a + (n − 1)b Dari barisan tersebut didapatkan bentuk umum rumus suku ke-n barisan aritmatika yaitu: Un = a + (n − 1)b. 2.9

Definisi, Aksioma, Teorema, Corollary, Konjektur, dan Open Problem Dalam dunia matematika tidak lepas dari aksioma, teorema, corollary, kon-

jektur, definisi, dan open problem. Keenam istilah tersebut memiliki arti yang berbeda. Definisi adalah pernyataan yang bernilai benar dan tidak perlu dibuktikan kebenarannya. Aksioma adalah proporsi yang diasumsikan benar dan tidak memerlukan pembuktian kebenaran lagi. Teorema adalah proporsi yang sudah dibuktikan kebenarannya. Teorema memiliki dua bentuk khusus yaitu lemma dan corollary (akibat). Lemma adalah teorema sederhana yang digunakan untuk membuktikan teorema lain. Lemma berguna untuk pembuktian proporsi yang lebih kompleks agar lebih mudah dipahami. Corollary adalah teorema yang dibentuk langsung dari teorema lain. Sedangkan konjektur adalah proporsi yang belum diketahui nilai kebenarannya. Open problem atau masalah terbuka adalah bebe-

20 rapa masalah yang dapat secara akurat dinyatakan dan belum diselesaikan (tidak ada solusi untuk diketahui). 2.10

Keterampilan Berpikir Tingkat Tinggi Berpikir melibatkan manipulasi dan mentrasformasi informasi dan memori

(Santrock, 2008). Menurut Dewey (dalam Kowiyah, 2012) berpikir adalah suatu proses yang dimulai apabila seseorang dihadapkan pada suatu masalah dan menghadapi sesuatu yang menghendaki adanya jalan keluar sehingga yang bersangkutan harus memanfaatkan pengetahuan, pemahaman, atau ketermpilan yang dimilikinya. Sedangkan secara singkat Soemanto (1990) mengartikan berpikir adalah meletakkan hubungan antar bagian pengetahuan yang diperoleh manusia. Dapat disimpulakan bahwa berpikir adalah proses mengaitkan pengetahuan, pemahaman, dan keterampilan melalui transformasi informasi dan memori untuk mencari jalan keluar dari suatu masalah. Kemampuan berpikir setiap orang berbeda. Terdapat dua klasifikasi tingkat berpikir yaitu berpikir tingkat rendah dan berpikir tingkat tinggi. Kemampuan berpikir tingkat rendah (Lower Order Thinking Skill - LOTS) adalah kemampuan berpikir yang hanya menuntut seseorang untuk mengingat, memahami, dan mengaplikasikan suatu rumus atau hukum. Sedangkan, Berpikir tingkat tinggi (Higher Order Thinking Skill - HOTS) adalah keterampilan yang lebih dari sekedar mengingat, memahami, dan mengaplikasikan. Dewanto dalam Amalia(2013) berpendapat bahwa berpikir tingkat tinggi adalah suatu kapasitas diatas informasi yang diberikan, dengan sikap yang kritis untuk mengevaluasi, mempunyai kesadaran metakognitif dan memiliki kemampuan pemecahan masalah. Corebina, dkk, dalam Kawuwung (2011) mengatakan bahwa keterampilan berpikir tingkat tinggi dapat diketahui dari kemampuan kognitif seseorang pada tingkatan analisis, sintesis, dan evaluasi. Dari pendapat tersebut dapat disimpulkan, berpikir tingkat tinggi adalah proses berpikir yang mencapai tahap analisis, sintesis, dan evaluasi dan menciptakan suatu yang baru. Taksonomi Bloom dianggap sebagai dasar bagi proses berpikir. Sebelum direvisi, taksonomi Bloom meliputi pengetahuan, aplikasi, analisis, sintesis, dan evaluasi. Taksonomi Bloom mengalami revisi sehingga tahapannya menjadi mengin-

21

Sumber: amirafiza.blogspot.com

Gambar 2.12 Tahapan taksonomi Bloom

gat (remembering), memahami (understanding), menerapkan (applying), menganalisis (analysing), mengevaluasi (evaluating), dan menciptakan (creating). Tahapan taksonomi Bloom dapat dilihat pada Gambar 2.12, semakin rendah level berpikir seseorang semakin rendah pula kemampuan berpikirnya, bila semakin tinggi leval berpikirnya maka semakin tinggi keterampilan berpikirnya. Tiga level berpikir yang termasuk level rendah (LOTS) adalah mengingat, memahami, menerapkan, sedangkan menganalisis, mengevaluasi dan menciptakan adalah level tinggi dan tergolong HOTS. Utari (2013) menjelaskan setiap level berpikir sebagai berikut: 1. Mengingat adalah Kemampuan menyebutkan kembali informasi atau pengetahuan yang tersimpan di dalam ingatan. Kata kerja kuncinya: mendefinisikan, menyusun daftar, menjelaskan, mengingat, mengenali, menemukan kembali, menyatakan, mengulang, mengurutkan, menamai, menempatkan, menyebutkan. 2. Memahami adalah Kemampuan dalam memahami instruksi dan menegaskan pengertian makna ide atau konsep yang telah diajarkan baik dalam bentuk lisan, tertulis maupun grafik diagram. Kata kerja kuncinya: Menerangkan, menjelaskan, menterjemahkan, menguraikan, mengartikan, menafsirkan, me-

22 nginterpretasikan, mendiskusikan, menyeleksi, mendeteksi, melaporkan, menduga, mengelompokkan, memberi contoh, merangkum, menganalogikan, mengubah, memperkirakan. 3. Menerapkan adalah Kemampuan melakukan sesuatu dan mengaplikasikan konsep dalam situasi tertentu. Kata kerja kuncinya: memilih, menerapkan, melaksanakan, menggunakan, mendemonstrasikan, memodifikasi, menunjukkan, membuktikan, menggambarkan, memprogramkan, mempraktekkan. 4. Menganalisis adalah Kemampuan memisahkan konsep kedalam beberapa komponen dan menghubungkan satu sama lain untuk memperoleh pemahaman atas konsep tersebut secara utuh. Kata kerja kuncinya: mengkaji ulang, membedakan, membandingkan, memisahkan, menghubungkan, menunjukkan hubungan antara variabel, memecah menjadi beberapa bagian, menyisihkan menjadi beberapa bagian, mengorganisir, mengkerangkakan. 5. Mengevaluasi adalah Kemampuan menetapkan derajat sesuatu berdasarkan norma, kriteria atau patokan tertentu. Kata kerja kuncinya: menilai, mengevaluasi, menjustifikasi, mengecek, mengkritik, memprediksi, membenarkan, menyalahkan, menyeleksi. 6. Mencipta adalah Kemampuan memadukan unsur-unsur menjadi suatu bentuk yang utuh dan koheren, atau membuat sesuatu yang orisinil. Kata kerja kuncinya: merakit, merancang, menemukan, menciptakan, memperoleh, mengembangkan, memformulasikan, membangun, membentuk, membuat, melakukan inovasi, mendesain, menghasilkan karya.

BAB 3. METODE PENELITIAN 3.1

Metode Penelitian Penelitian ini menggunakan metode deskriptif aksiomatik yaitu metode me-

nurunkan aksioma atau teorema yang sudah ada kemudian diterapkan dalam pelabelan super (a, d) − H-anti ajaib total dekomposisi graf shackle generalisasi antiprisma baik berupa konektif maupun diskonektif. Tahap awal penelitian ini adalah menentukan nilai beda (d) pada graf tersebut, selanjutnya nilai beda diterapkan dalam super (a, d) − Apo anti ajaib total dekomposisi graf shackle generalisasi antiprisma. Menurunkan teorema untuk memperoleh pelabelan titik dan pelabelan sisi kemudian dilanjutkan dengan pendeteksian pola. Tujuan dari pendeteksian pola adalah untuk merumuskan pola pelabelan titik dan pelabelan sisi secara umum sehingga mendapatkan rumus pelabelan super (a, d) − Apo anti ajaib total dekomposisi graf shackle generalisasi antiprisma. Penelitian dimulai dari graf konektif terlebih dahulu dan dilanjutkan graf diskonektif. Penelitian ini juga menggunakan tahapan-tahapan taksonomi Bloom yang sudah direvisi yaitu mengingat, memahami, menerapkan, menganalisis, mengevaluasi, dan menciptakan. Setiap langkah dalam penelitian ini dikaitkan dengan tahapan taksonomi Bloom tersebut untuk mencapai keterampilan berpikir tingkat tinggi atau yang disebut HOTS (High Order Thinking Skill ). 3.2

Definisi Operasional Definisi operasional variabel digunakan untuk memberikan gambaran secara

sistematis dalam penelitian dan menghindari terjadinya perbedaan pengertian makna. Definisi variabel yang dimaksud adalah sebagai berikut: 3.2.1

Pelabelan Super (a, d) − Apo Anti Ajaib Total Dekomposisi Misal G = (V, E) adalah graf sederhana, hingga, dan tak berarah. Ke-

luarga dari subgraf G, yaitu £ = {H1 , H2 , . . . , Hn } dikatakan dekomposisi-H dari 23

24 G, jika semua subgraf tersebut isomorfis dengan graf H, E(Hi )∩E(Hj ) = Ø untuk i 6= j, dan ∪ni=1 E(Hi ) = E(G) (Hader dkk, 2013). Selanjutnya G disebut memiliki dekomposisi-H anti ajaib, jika G memiliki dekomposisi-H dan terdapat suatu pelabelan total f : V ∪ E → {1, 2, 3, . . . , |V | + |E|} sehingga untuk masing-masing P P subgraf Hi = (Vi , Ei ) berlaku v ∈ V if (v) + e ∈ Eif (e) konstan. Pelabelan super adalah pelabelan yang label titiknya lebih kecil dibandingkan label sisi. Sehingga f (v) = {1, 2, 3, ..., |V |} dan f (e) = {|V | + 1, |V | + 2, |V | + 3, ..., |V | + |E|} 3.2.2

Graf Shackle Generalisasi Antiprisma Konektif Graf shackle generalisasi antiprisma konektif dinotasikan shack(Apo , n)

dengan o, p, n bilangan bulat positif. Terdapat dua shackle yaitu shackle titik dan shackle sisi, namun pada penelitian ini digunakan shackle titik sehingga dinotasikan shackApo , v, n). Graf shack(Apo , v, n) memiliki titik sebanyak | V ( shack (Apo , v, n))| = n(op − 1) + 1 yaitu V (shack(Apo , v, n)) = {x1,p,1 , xi,j,k , 1 ≤ i ≤ o, 1 ≤ j ≤ p − 1, 1 ≤ k ≤ n} ∪ {xi,j,k , 2 ≤ i ≤ o, j = p, 1 ≤ k ≤ n}. Banyaknya sisi pada graf ini adalah |E(shack(Apo , v, n))| = no(3p − 2) yang terdiri dari E(shack(Apo , v, n)) = {xi,j,k xi+1,j,k , xi,j+1,k xi+1,j,k , 1 ≤ i ≤ o − 1, 1 ≤ j ≤ p − 1, 1 ≤ k ≤ n}

∪

{xi,j,k xi,j+1,k , 1 ≤ i ≤ o, 1 ≤ j ≤ p − 2, 1 ≤ k ≤

n} ∪ {xi,p,k xi+1,p,k , 1 ≤ i ≤ o − 2, 1 ≤ k ≤ n} ∪ {xi,j,k xi,j+1,k , 1 ≤ i ≤ o − 1, j = p − 1, 1 ≤ k ≤ n}

∪

{x1,p,k+1 x1,p,k , x1,p,k+1 x1,p−1,k , 1 ≤ k ≤

n−1} ∪ { xo,j−1,k−1 x1,j,k , xo−1,j,k−1 x1,j,k , j = p, 2 ≤ k ≤ n } ∪ { xo,p,n xo−1,p,n , xo,p,n x1,p,n , xo,p,n x1,p−1,n , xo,p,n xo,p−1,n } ∪ {xo,j,k x1,j,k , 1 ≤ j ≤ p − 1, 1 ≤ k ≤ n} ∪ {x1,j,k xo,j+1,k , 1 ≤ j ≤ p − 2, 1 ≤ k ≤ n}. Gambar 3.1 merupakan salah satu contoh graf shack(Apo , v, n). 3.2.3

Graf Shackle Generalisasi Antiprisma Diskonektif Graf shackle generalisasi antiprisma diskonektif atau gabungan saling

lepas adalah gabungan diskonektif sebanyak m salinan graf shackle generalisasi antiprisma yang dinotasikan mshack(Apo , v, n), mempunyai titik dan sisi berturutturut adalah |V (mshack(Apo , v, n))| = nm(op−1)+m dan |E (m shack (Apo , v, n))| = nom(3p−2). Himpunan titik dari graf tersebut adalah V ( m shack (Apo , v, n)) = {xl1,p,1 , xli,j,k , 1 ≤ i ≤ o, 1 ≤ j ≤ p−1, 1 ≤ k ≤ n, 1 ≤ l ≤ m}∪{xli,j,k , 2 ≤

25 x2,3,2

x3,3,1

x4,1,1 x3,1,1

x2,3,1

x1,1,1

x2,1,1 x2,2,1

x3,2,2

x2,2,2

x4,2,1

x3,2,1

x3,1,2,1 x4,1,2 x2,1,2 x1,1,2

x1,3,2

x1,2,1

x3,3,2

x4,2,2

x1,2,2 x4,3,2

x1,3,1

Gambar 3.1 Graf shack(A34 , v, 2)

i ≤ o, j = p, 1 ≤ k ≤ n, 1 ≤ l ≤ m}. Himpunan sisi dari graf tersebut adalah E(mshack(Apo , v, n)) = {xli,j,k xli+1,j,k , xli,j+1,k xli+1,j,k , 1 ≤ i ≤ o − 1, 1 ≤ j ≤ p − 1,

1 ≤ k ≤ n,

1 ≤ l ≤ m}

∪

{xli,j,k xli,j+1,k ,

1 ≤ i ≤ o,

p − 2,

1 ≤ k ≤ n,

1 ≤ l ≤ m}

∪

{xli,p,k xli+1,p,k ,

1 ≤ i ≤ o − 2,

k ≤ n,

1 ≤ l ≤ m}

∪

{xli,j,k xli,j+1,k ,

1 ≤ i ≤ o − 1,

1 ≤ j ≤

j = p − 1,

1 ≤ 1 ≤

k ≤ n, 1 ≤ l ≤ m} ∪ {xl1,p,k+1 xl1,p,k , xl1,p,k+1 xl1,p−1,k , 1 ≤ k ≤ n − 1, 1 ≤ l ≤ m} ∪ {xlo,j−1,k−1 xl1,j,k , xlo−1,j,k−1 xl1,j,k , j = p, 2 ≤ k ≤ n, 1 ≤ l ≤ m} ∪ {xlo,p,n xlo−1,p,n , xlo,p,n xl1,p,n , xlo,p,n xl1,p−1,n , xlo,p,n xlo,p−1,n , 1 ≤ l ≤ m} ∪ {xlo,j,k xl1,j,k , 1 ≤ j ≤ p−1, 1 ≤ k ≤ n, 1 ≤ l ≤ m} ∪ {xl1,j,k xlo,j+1,k , 1 ≤ j ≤ p − 2, 1 ≤ k ≤ n, 1 ≤ l ≤ m}. Contoh mshack(Apo , v, n) dapat dilihat pada Gambar 3.2 3.2.4

Indikator Pelabelan Super (a, d) − Apo Anti ajaib Total Dekomposisi Graf Shackle Generalisasi antiprisma Indikator pelabelan super (a, d) − Apo anti ajaib total dekomposisi graf

shackle generalisasi antiprisma dari penelitian ini adalah: 1. Label Titik Label titik pada pelabelan super (a, d) − Apo anti ajaib total dekomposisi graf shackle generalisasi antiprisma adalah fungsi bijektif yang memetakan himpunan titik pada shackle generalisasi antiprisma V (G) ke bilangan bulat

26

x12,3,2

x13,3,1 x13,2,1

x14,1,1 x13,1,1

x12,3,1

x12,1,1

x12,2,1

x23,2,1

x32,3,1

x11,1,2

x22,3,2

x22,1,1 x21,3,1

x34,1,1 x33,1,1

x32,2,1

x11,2,2

x23,3,1 x24,2,1

x32,1,1 x31,3,1

x22,2,2

x21,2,1

x23,1,2 x22,1,2

x21,1,1 x21,3,2 x21,2,2

x21,1,2 x24,3,2

x13,2,2

x14,1,2

x13,3,2

x14,2,2

x23,2,2

x24,1,2

x23,3,2

x24,2,2

x32,3,2

x33,3,1 x33,2,1

x12,1,2

x11,1,1 x11,3,2 x11,2,1

x13,1,2

x14,3,2

x23,1,1

x22,2,1

x12,2,2

x11,3,1

x24,1,1

x22,3,1

x14,2,1

x34,2,1

x32,2,2

x32,1,2

x31,1,1 x31,3,2 x21,2,1

x33,1,2

x31,2,2

x31,1,2 x34,3,2

Gambar 3.2 Graf 3shack(A34 , v, 2)

x33,2,2

x34,1,2

x34,2,2

x33,3,2

27 {1, 2, . . . , |V (G)|}. 2. Label Sisi Label sisi melanjutkan pelabelan titik sehingga label sisi pada pelabelan super (a, d) − Apo anti ajaib total dekomposisi graf shackle generalisasi antiprisma adalah fungsi bijektif yang memetakan himpunan sisi pada shackle generalisasi antiprisma E(G) ke bilangan bulat {|V (G)| + 1, |V (G)| + 2, . . . , |V (G)| + |E(G)|}. 3. Label Dekomposisi Label dekomposisi pada pelabelan super (a, d)−Apo anti ajaib total dekomposisi graf shackle generalisasi antiprisma adalah fungsi bijektif yang memetakan himpunan titik dan sisi pada shackle generalisasi antiprisma V (G) ∪ E(G) ke bilangan bulat {1, 2, 3, . . . , |V (G)| + |E(G)|}. 4. Bobot Selimut Bobot selimut adalah jumlah label titik pada setiap selimut. Dalam penelitian ini, bobot selimut yang dicari adalah yang aritmatik. 5. Bobot Total Selimut Bobot Total Selimut adalah jumlah label titik dan sisi pada setiap selimut, dimana hasilnya harus aritmatik. 3.3

Teknik Penelitian Penelitian ini dilakukan pada graf shackle generalisasi antiprisma shack(Apo ,

v, n) baik konektif (tunggal) maupun diskonektif (gabungan saling lepas). Teknik penelitian sebagai berikut: 1. mengidentifikasi famili graf shack(Apo , v, n); 2. menentukan kardinalitas pada graf shack(Apo , v, n); 3. menentukan batas atas nilai beda d pada pada graf shack(Apo , v, n); 4. menentukan label titik dan sisi sehingga super (a, d) − Apo anti ajaib total dekomposisi menggunakan cara manual ataupun metode partisi; 5. apabila label titik dan sisi berlaku untuk beberapa graf baik secara heuristik maupun determination maka pelabelan dikatakan expandable;

28 6. menentukan fungsi bijektif label titik dan sisi pada graf shack(Apo , v, n); 7. mengembangkan fungsi bobot selimut dan fungsi bobot total sisi pada graf shack(Apo , v, n); 8. membuktikan kebenaran fungsi 9. menemukan teorema; 10. menciptakan ciphertext dengan cara mengaplikasikan pola pelabelan super (a, d) − Apo anti ajaib total dekomposisi pada graf shack(Apo , v, n); Penelitian ini menemukan berbagai pola pelabelan super anti ajaib total dekomposisi dengan berbagai nilai beda d yang ditentukan. Teknik penelitian graf diskonektif shackle generalisasi antiprisma sama seperti teknik penelitian yang dijelaskan di atas. Secara umum teknik penelitian disajikan dalam diagram alir pada Gambar 3.3. 3.4

Observasi Sebelum penelitian lanjutan pada shack(Apo , v, n) maupun mshack(Apo , v, n),

telah dilakukan observasi awal untuk nilai o, p, n, dan m tertentu sebagai pedoman untuk menduga pelabelan super (a, d) − Apo anti ajaib total dekomposisi serta menentukan pola pelabelannya. Ternyata setelah melakukan observasi awal, peneliti menemukan pola pelabelan titik pada shack(Apo , v, n) maupun mshack(Apo , v, n). Observasi awal yang dilakukan dikaitkan dengan proses berpikir tingkat tinggi berdasarkan taksonomi Bloom, sehingga tahapannya sebagai berikut: 1. mengingat definisi, teorema, dan lemma dari penelitian terkait yang sudah dibuktikan; 2. memahami definisi, teorema, dan lemma tersebut; 3. menggunakan definisi, teorema, dan lemma dalam proses mencari pelabelan titik dan pelabelan sisi graf shackle antiprisma; 4. menentukan graf yang akan digunakan yaitu dengan menetapkan o = 4,p = 2, n = 2, dan m = 3; 5. pelabelan dimulai dengan melabeli graf konektif;

29 (Mengingat) Identifikasi famili graf

Menghitung banyak titik |V |,

(Memahami)

sisi |E|, dan kardinalitas dari graf

(Menerapkan)

Menentukan batas atas nilai beda d

(Menganalisa) Menentukan label titik dan sisi Unexpandable (Mengevaluasi) Mengecek ke-expandable-an label Expandable Membuktikan kebenaran

Mengembangkan fungsi bijektif Salah

label titik dan sisi

Benar

Salah Membuktikan kebenaran

fungsi

Mengembangkan fungsi bobot total selimut

fungsi

(Mencipta)

Benar Teorema

Membentuk ciphertext

Keterangan : Aliran kegiatan utama Aliran pengecekan

Gambar 3.3 Rancangan penelitian

30 6. pelabelan dimulai dari pelabelan titik untuk cara melabelinya dapat dilihat pada Gambar 3.4; 7. dilanjutkan dengan melabeli sisi dengan cara bergantian dari sisi yang bersesuaian pada setiap shackle. Lihat Gambar 3.4 untuk memahami; 8. tahapan selanjutnya adalah pelabelan dekomposisi pada mshack(Apo , v, n) yang urutannya sama dengan cara konektif hanya saja bergantian dari setiap graf terpisah. Lihat Gambar 3.5. 6

5

50

78

26

38 12

77

70

58

71

43

42

16 41

69

49

22

40

56

18 57

10

68 36

25 76

11 51

72

79

8 24

1

21 23 44 60

13

47 17 67

34 63

75

7 74

15

35

28

54

66

46

19

9

48

62

45

64

52

30

33 65

61 32

2

39

73

29

14

59

20

37

4

53 27

31 55

3

Gambar 3.4 Observasi awal pada graf shack(A34 , v, 2)

Adapun langkah-langkah pembentukan ciphertext sebagai berikut: 1. Menentukan graf, pilihlah graf yang memiliki sisi lebih dari banyaknya karakter plaintext, misalkan 26. 2. Melabeli titik dan sisi menggunakan super (a, d)−H anti ajaib total dekomposisi. 3. Mengeliminasi sisi yang memiliki label fuv > |V | + 26 4. Membuat graf pohon dengan utama salah satu label titik, sedangkan akar selanjutnya mengikuti pola graf. Sisi yang sudah dieliminasi tidak perlu digunakan. 5. Mencantumkan label sisi pada graf pohon sesuai pelabelan pada graf yang digunakan. Mengubah bilangan tersebut menjadi bilangan mod 26.

31

13

16 144 72

155

236 116

73 40 145 213

34

83 31

223 103

199

180 37

84

212 169 61 222 179 64 200 156 131 132 121 120 102 55 67 104 19 4 10 46 117 115 58 130 133 181 198 118 166 211 119 154 224 49 143 52 237 178 201 43 25 167 210 22 28 82 85 105 71 70 114 225 157 142 234 7 1 235

168

148

17

14

232

159

219 99 88 35 208 195 186 38 173 41 62 65 149 231 197 160 172 209 124 125 135 136 68 100 20 11 111 59 47 113 98 56 5 137 134 185 170 207 123 122 194 220 147 233 50 53 158 197 44 171 206 23 26 182 29 89 86 101 110 74 221 161 75 230 146 8 2 76

77

112

87 32 218 183

18

15 228

163

152 215 108 95 80 91 81 92 36 204 33 191 177 42 188 39 227 214 164 66 153 63 176 187 128 129 205 139 140 192 107 60 109 6 21 48 96 12 94 57 69 174 127 126 138 141 189 203 190 229 54 51 216 151 162 202 24 175 186 193 45 30 27 78 79 93 90 106 97 165 150 226 217 3

9

Gambar 3.5 Observasi awal pada graf 3shack(A34 , v, 2)

32 6. Memasangkan setiap karakter plaintext dengan sisi pada graf pohon. Pemasangan diurutkan dari kiri mulai dari layer teratas. 7. Membuat aturan untuk mentransformasi bilangan mod 26 ke karakter yang digunakan sebagai ciphertext, aturan yang digunakan adalah aturan Julius Caesar. 8. Memubuat tabel yang terdiri dari plaintext, label sisi yang bersesuaian dengan plaintext, (mod 26) dari label sisi, dan ciphertext yang bersesuaian dengan (mod 26). Misalkan graf G adalah graf shack(A34 , v, 2). Pelabelan mengikuti pada Gambar 3.4. Pesan rahasia yang berbunyi ”TERIMA KASIH ATAS BIMBINGANNYA” akan dikirimkan. Maka perlu dibuat ciphertext untuk pesan ini menggunkan pelabelan graf shack(A34 , v, 2) kemudian dibuat diagram pohon seperti Gambar 3.6. 1 A 24 2

8

4 F 27

D 28

I 36

E 29 3

6

6

K 31 L 30

10

11

14

N 38 12

12

9 O 32

10

M 37

7

7

J 39

H 49

G 26

5

17

16 P 35 15

S 40

T 43

W 44

X 47

18

22

19

23

Y 45

U 41

Q 33

V 42

R 34 13

C 48

B 25

13

20

20

Z 46 21

21

Gambar 3.6 Observasi awal pada pembuatan ciphertext

33 Tabel 3.1: Pengembanganciphertext dari Gambar 3.6 Plaintext

A

B

C

D

E

F

G

H

I

J

K

L

M

Label Sisi

24

25

48

28

29

27

26

49

36

39

31

30

37

(Mod 26)

24

25

22

2

3

1

0

23

10

13

5

4

11

Ciphertext

Y

Z

W

C

D

B

A

X

K

N

F

E

L

Plaintext

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

Label Sisi

38

32

35

33

34

40

43

41

42

44

47

45

46

(Mod 26)

12

6

9

7

8

14

17

15

16

18

21

19

20

Ciphertext

M

G

J

H

I

O

R

P

Q

S

V

T

U

Sehingga didapatkan kode seperti pada Tabel 3.1. Bila terdapat plaintext ”TERIMA KASIH ATAS BIMBINGANNYA” kemudian hilangkan tanda baca sehingga pesan menjadi ”TERIMAKASIHATASBIMBINGANNYA” maka chipertext alfabetiknya adalah ”RDIKLYFYOKXYRYOZKLZKMAYMMTY”. Berdasarkan tahapan-tahapan tersebut, peneliti menemukan pelabelan total dekomposisi pada shack(Apo , v, n) dan mshack(Apo , v, n) secara berurutan beserta contoh pengaplikasiannya pada pengembangan ciphertext. Gambar 3.4 dan Gambar 3.5 merupakan hasil observasi awal pelabelan dekomposisi graf shackle generalisasi antiprisma konektif dan diskonektif dengan nilai d = 12. Peneliti dapat melanjutkan observasinya untuk pelabelan total dekomposisi graf shackle generalisasi antiprisma berdasarkan pada teknik penelitian dan taksonomi bloom yang telah direvisi.