Kode, GSR, dan Operasi Pada

BAB 2 Kode, GSR, dan Operasi Pada Graf 2.1

Ruang Vektor Atas F2

Ruang vektor V atas lapangan hingga F2 = {0, 1} adalah suatu himpunan V yang berisi vektor-vektor, termasuk vektor nol, bersama dengan operasi penjumlahan vektor dan perkalian skalar elemen V terhadap elemen dari F2 yang memenuhi kondisi berikut: 1. u + v ∈ V, ∀u, v ∈ V 2. u + v = v + u, ∀u, v ∈ V 3. u + (v + w) = (u + v) + w, ∀u, v, w ∈ V 4. ∃~0 ∈ V 3 ~0 + v = v, ∀v ∈ V 5. ∀u ∈ V ∃ − u ∈ V 3 u + (−u) = (−u) + u = 0 6. rv ∈ V, ∀r ∈ F2 , ∀v ∈ V 7. ∃1 ∈ V 3 1v = v, ∀v ∈ V 3

BAB 2 : Kode, GSR, dan Operasi Pada Graf 8. r(u + v) = ru + rv, ∀r ∈ F2 , ∀u, v ∈ V 9. (r + s)v = rv + sv, ∀r, s ∈ F2 , ∀v ∈ V 10. (rs)v = r(sv), ∀r, s ∈ F2 , ∀v ∈ V Suatu subhimpunan tak kosong U dari ruang vektor V ,U ⊆ V , merupakan subruang dari V jika dan hanya jika 1. untuk setiap u1 , u2 ∈ U , berlaku u1 + u2 ∈ U 2. untuk setiap k ∈ F2 dan u ∈ U, berlaku ku ∈ U Misalkan vektor-vektor v1 , v2 , . . . , vk ∈ F2n . Vektor w ∈ F2n dikatakan kombinasi linier dari v1 , v2 , . . . , vk jika w dapat dituliskan sebagai berikut: w = r1 v1 + r2 v2 + r3 v3 + . . . + rk vk , untuk suatu r1 , r2 , . . . , rk ∈ F2 . Selanjutnya himpunan semua kombinasi linier dari v1 , v2 , . . . , vk disebut span dari v1 , v2 , . . . , vk atau biasa dinotasikan sebagai span {v1 , v2 , . . . vk }. Kumpulan vektor v1 , v2 , . . . , vk dikatakan bebas linier jika kombinasi linier r1 v1 + r2 v2 + . . . + rk vk = 0 hanya dipenuhi oleh ri = 0 untuk i = 1, 2, . . . , k. Jika v1 , v2 , . . . vk tidak bebas linier maka kita katakan bahwa v1 , v2 , . . . vk bergantung linier. Himpunan vektor v1 , v2 , . . . , vk di V disebut basis untuk V jika 1. v1 , v2 , . . . , vk bebas linier 2. span {v1 , v2 , . . . , vk } = V Selanjutnya dimensi dari V adalah banyaknya elemen dari suatu basis V .

4

BAB 2 : Kode, GSR, dan Operasi Pada Graf

2.1.1

Vektor Eigen dan Nilai Eigen

Misalkan A sebuah matriks persegi. Definisi 2.1.1. vektor tak nol x¯ disebut vektor eigen dari A jika dan hanya jika terdapat bilangan (riil atau kompleks) λ sehingga:

A¯ x = λ¯ x. jika bilangan λ tersebut ada, maka λ disebut nilai eigen dari A dan vektor x¯ disebut vektor eigen yang bersesuaian dengan nilai eigen λ.

2.2

Kode atas F2

Suatu kode C atas F2 dengan panjang n merupakan subhimpunan tak hampa atas ruang vektor F2n , yaitu C = {(c1 , c2 , . . . , cn )|ci ∈ F2 , i = 1, 2, . . . , n}. Selanjutnya setiap unsur di kode C yaitu c = (c1 , c2 , . . . , cn ) ∈ C dinamakan katakode dari kode C. Unsur ci dinamakan koordinat ke-i dari katakode c. Jika setiap unsur pada katakode C bernilai nol, yaitu c = (0, 0, . . . , 0) maka kata tersebut dinamakan katakode nol atau biasa dinotasikan dengan 0C . Suatu kode C dinamakan kode linier jika kode tersebut merupakan subruang dari F2n , dengan kata lain kode C dinamakan kode linier jika kode tersebut tertutup terhadap penjumlahan dan perkalian skalar atas F2 . Contoh sederhana dari kode linier yaitu C = {000, 111}, karena: 000 + 000 = 000, 111 + 111 = 000, 000 + 111 = 111, 111 + 000 = 111 Untuk selanjutnya kode yang akan ditinjau adalah kode linier.

5

BAB 2 : Kode, GSR, dan Operasi Pada Graf

2.3

Bobot dan Jarak Kode

2.3.1

Bobot Katakode dan Bobot Kode

Misalkan c = (c1 , c2 , . . . , cn ) suatu katakode di C. Bobot Hamming dari katakode c adalah banyaknya digit tak nol dari c. Secara formal bobot Hamming katakode dari c yang dinotasikan dengan wtH (c) didefinisikan sebagai : wtH (c) = |{i|ci 6= 0, i = 1, 2, . . . , n}| Selanjutnya bobot dari suatu kode C merupakan bobot terkecil dari katakode tak nol di C, dinotasikan dengan wtH (C), dan secara formal didefinisikan sebagai: wtH (C) = min{wtH (c)|c 6= 0c , c ∈ C}

2.3.2

Jarak antar Katakode dan Jarak Kode

Misalkan v = (v1 , v2 , . . . , vn ) dan w = (w1 , w2 , . . . , wn ) merupakan dua buah katakode di C. Jarak Hamming dari v ke w adalah banyaknya posisi di v yang berbeda dengan w. Secara formal dinotasikan dengan dH (v, w)dan didefinisikan sebagai dH (v, w) = |{i|vi 6= wi , i = 1, 2, . . . , n}| Selanjutnya jarak dari kode C dinotasikan dengan dH (C), dan secara formal didefinisikan sebagai dH (C) = min{d(v, w)|v, w ∈ C, v 6= w, }

2.3.3

Hubungan Bobot dan Jarak

Jika C merupakan kode linier maka kita memiliki hubungan antara bobot dan jarak yaitu dH (C) = wtH (C).

6

BAB 2 : Kode, GSR, dan Operasi Pada Graf Bukti. misalkan x, y ∈ C maka dH (x, y) = wtH (x − y), karena C kode linier maka x − y ∈ C, sehingga dH (x, y) = wtH (x − y) = wtH (c), c ∈ C. Jika dH (x, y) minimum maka wtH (c) minimum, berdasarkan definisi dari bobot dan jarak kode, jelas bahwa dH (C) = wtH (C). Dengan demikian kita dapat mencari jarak suatu kode linier dari bobotnya. Selanjutnya kode linier C atas F2 dengan panjang n, dimensi k, dan jarak d ditulis sebagai kode [n, k, d].

2.3.4

Distribusi Bobot dan Pencacah Bobot

Misalkan C kode atas F2 dengan panjang n. Distribusi bobot dari kode C dinotasikan dengan At , didefinisikan sebagai At = |{c ∈ C|wtH (c) = t}|, 0 ≤ t ≤ n Yaitu banyaknya katakode di C dengan bobot t. Selanjutnya pencacah bobot dari kode C dinotasikan dengan WC (x, y), didefinisikan sebagai WC (x, y) =

2.4

Pn

i=0

Ai xn−i y i

Kode Dual

Misalkan v = (v1 , v2 , . . . , vn ) dan w = (w1 , w2 , . . . , wn ) dua buah katakode (di F2n ). Hasil kali dalam antara katakode v dan w dinotasikan dengan v.w, didefinisikan Pn sebagai v.w = i=1 vi wi (di F2 ). Kemudian kedua katakode tersebut dikatakan 0

(saling) ortogonal jika v.w = 0 (di F2 ). Selanjutnya katakode u ∈ C dikatakan ortogonal terhadap kode C jika u.c = 0 (di F2 ) untuk setiap c ∈ C. Definisi 2.4.1. Misalkan C kode atas F2 . Kode dual dari kode C, C ⊆ F2n , dinotasikan dengan C ⊥ , didefinisikan sebagai 7

BAB 2 : Kode, GSR, dan Operasi Pada Graf C ⊥ = {v ∈ F2n |v.c = 0 untuk setiap c ∈ C} selanjutnya kode C disebut swa-ortogonal apabila C ⊆ C ⊥ , dan disebut swadual apabila C = C ⊥ .

2.5

Matriks Pembangkit

Misalkan C ∈ F2n suatu kode atas F2 dengan panjang n. Definisi 2.5.1. Suatu matriks G yang memiliki n kolom dengan komponen-komponen atas F2 dikatakan sebagai matriks pembangkit dari kode C apabila baris baris dari G merupakan basis dari kode C.

2.6

Matriks Cek Paritas

Misalkan C ⊥ merupakan kode dual dari kode C atas F2 dengan panjang n. Definisi 2.6.1. Matriks H yang memiliki n baris dengan komponen-komponen atas F2 dikatakan sebagai matriks cek paritas dari kode C apabila kolom-kolom dari H merupakan basis dari kode C ⊥ .

2.7

Graf

Γ disebut graf tak berarah dengan n titik apabila Γ = (V, E) merupakan konfigurasi dari himpunan titik V dan himpunan sisi E, dimana setiap sisi menghubungkan sepasang titik. Dua buah titik dikatakan bertetangga jika terdapat sisi yang menghubungkan kedua titik tersebut. Suatu graf dikatakan sederhana jika graf tersebut tidak memiliki titik yang bertetangga dengan dirinya sendiri dan setiap dua pasang titik dihubungkan tepat oleh satu sisi, atau dengan kata lain graf tersebut tidak memiliki loop dan sisi ganda. 8

BAB 2 : Kode, GSR, dan Operasi Pada Graf Definisi 2.7.1. Matriks ketetanggaan dari suatu graf sederhana Γ = (V, E) adalah suatu matriks A = (aij )n(i,j=1) dengan entri sebagai berikut:    1, jika titik i dan j bertetangga aij =   0, jika titik i dan j tidak bertetangga

2.7.1

Graf Strongly regular

Graf strongly regular dengan parameter (n, k, λ, µ) adalah suatu graf sederhana dan tidak berarah dengan banyaknya titik n, derajat regular k, dengan sifat sebagai berikut: • setiap dua titik yang bertetangga memiliki tepat λ buah tetangga bersama • setiap dua titik yang tidak bertetangga memiliki tepat µ buah tetangga bersama Misalkan A merupakan matriks ketetanggaan dari GSR, maka A memenuhi persamaan berikut: A2 = kI + λA + µ (J − I − A)

(2.1)

dengan J merupakan matriks yang semua entrinya 1, (J − I − A) merupakan matriks ketetanggaan dari graf komplemennya, dan derajat k merupakan nilai eigen dari A dengan vektor eigen 1 maka A memiliki 2 nilai eigen yang lain yaitu r,s dengan (r ≥ s) dengan multiplisitas berturut-turut f dan g yang memenuhi: −rs = k −µ, r +s = λ−µ, (k − r) (k − s) = µ+n, n = f +g +1 dan k +f r +gs = 0 salah satu contoh dari graf strongly regular dapat dilihat pada gambar 2.1.

9

BAB 2 : Kode, GSR, dan Operasi Pada Graf

Gambar 2.1: Graf Srikhande, GSR (16,6,2,2)

2.8 2.8.1

Operasi-Operasi Graf Operasi gabungan (union)

Misalkan G1 (V1 , E1 ) dan G2 (V2 , E2 ) adalah dua buah graf yang tidak berarah. Maka gabungan dari G1 dan G2 dinotasikan oleh G1 ∪ G2 adalah sebuah graf dimana V (G1 ∪ G2 ) = V1 ∪ V2 dan E (G1 ∪ G2 ) = E1 ∪ E2 .

10

BAB 2 : Kode, GSR, dan Operasi Pada Graf

2.8.2

Operasi jumlah (join)

Misalkan G1 (V1 , E1 ) dan G2 (V2 , E2 ) adalah dua buah graf yang tidak berarah. Maka operasi jumlah dari kedua buah graf ini dinotasikan oleh G1 +G2 adalah graf dengan himpunan titik dari (G1 ∪ G2 ), dimana setiap titik yang berasal dari G1 bertetangga dengan semua titik yang berasal dari G2 .

2.8.3

Operasi kali(product)

Misalkan G1 (V1 , E1 ) dan G2 (V2 , E2 ) adalah dua buah graf yang tidak berarah. Maka operasi kali dari G1 dan G2 dinotasikan oleh G1 × G2 adalah sebuah graf dengan himpunan titik V1 ×V2 dimana dua buah titik (u1 , u2 ) dan (v1 , v2 ) ∈ V1 ×V2 dikatakan bertetangga di G1 × G2 jika dan hanya jika 1. u1 = v1 dan u2 v2 ∈ E2 2. u2 = v2 dan u1 v1 ∈ E1 G1 × G2 bersifat komutatif.

11

BAB 2 : Kode, GSR, dan Operasi Pada Graf

2.8.4

Line Graf

Diberikan sebuah graf G, maka line graf dari G atau dinotasikan dengan L(G) adalah sebuah graf sehingga 1. Setiap titik di L(G) merepresentasikan sisi di G 2. Dua buah titik di L(G) dikatakan bertetangga jika dan hanya jika sisi sisi di G yang berkorespondensi dengan titik tersebut berinsidensi di G

12