BAB III ALJABAR HIPERGRAF
3.1 Hipergraf Definisi 1 Misalkan V = {v1, v2 ,..., vn } adalah himpunan hingga, dan misalkan
ε = {Ei , i ∈ I } adalah koleksi dari himpunan bagian dari V. Koleksi ε menjadi suatu hipergraf pada V jika Ei ≠ φ , i ∈ I dan
U Ei = V
dan H (V , ε ) disebut
i∈I
hipergraf. Elemen-elemen v1 , v 2 ,...v n disebut vertek dan himpunan-himpunan E1 , E 2 ,..., E n disebut hiperedge. Untuk menggambarkan Hiperedge Ei ,
Ei > 2 digambarkan
jika
sebagai kurva yang mengelilingi semua vertek Ei . Jika Ei = 2 digambarkan sebagai garis yang menghubungkan kedua vertek tersebut. Jika
Ei = 1
digambarkan sebagai loop seperti dalam suatu graf. Jelas, jika Ei = 2, i = 1,..., m hipergraf adalah graf[8]. E1
E4 v8
E5
v7 v5
v1 v2
v3 E2
E6
v4
v6
E3
Gambar 3 Hipergraf H (V , ε )
Dari hipergraf gambar 3 diatas diperoleh: (1) Hiperedge Ei adalah himpunan bagian dari V = {v1, v2 ,..., v8 } , yaitu E1 = {v1 , v 2 , v3 },
E 2 = {v1 , v 4 }, E3 = {v4 , v5 , v6 }, E 4 = {v2 , v5 , v7 }, E5 = {v7 , v8 }, E6 = {v5 } . diperoleh Ei ⊂ V ,
UE
i
Jadi
= V dan Ei ≠ φ ; (2) Dua vertek dikatakan bertetangga
i
12
(adjacent) dalam H = (V , E ) jika terdapat hiperedge Ei yang memuat kedua titik tersebut. Contoh : v1 bertetangga dengan v3 karena ∃{v1 , v3 } ⊂ E1 ; (3) Dua hiperedge dikatakan bertetangga (adjacent) jika irisannya bukan himpunan kosong. Contoh: E1 bertetangga dengan E4 karena E1 ∩ E4 = {v2 } ≠ φ ; dan (4) Hipergraf sederhana adalah hipergraf dengan semua hiperedge berbeda, yaitu
Ei ⊆ E j ⇒ i = j . Contoh: E6 ⊆ E4 ⇒ 6 ≠ 4 . Jadi hipergraf seperti gambar 3 bukan hipergraf sederhana, hipergraf tersebut dapat menjadi hipergraf sederhana jika hiperedge E6 dihilangkan dan vertek v5 boleh tidak dihilangkan. Definisi 2 Ukuran H = (V , E ) didefinisikan sebagai size ( H ) =
∑E
Ei ∈E
i
dimana
Ei adalah kardinalitas atau derajat dari hiperedge Ei i = 1, 2,..., m . Contoh: dari
hipergraf gambar 3 diperoleh: size( H ) = E1 + ... + E6 = 3 + 2 + 3 + 3 + 2 + 1 = 14 Definisi 3 Dalam H = (V , E ) , hiperedge disebut maximal, jika hiperedge tersebut
tidak termuat dalam hiperedge lain. Contoh: dari hipergraf gambar 3 diperoleh, semua hiperedge adalah maksimal kecuali E6 = {v5 } karena E6 termuat dalam hiperedge lain yaitu E3 dan E4 Hipergraf H = (V , E ) dapat direpresentasikan oleh matriks incidence ⎧ 1; vi ∈ E j , i = 1,2,..., n [eij ] ∋ eij ∈ {0,1}, eij = ⎨ ⎩0; vi ∉ E j , j = 1,2,..., m
dengan n baris menyatakan vertek dan m kolom menyatakan hiperedge. Dari hipergraf gambar 3 diperoleh matrik incidence sebagai berikut: ⎡1 ⎢1 ⎢ ⎢1 ⎢ [eij ] = ⎢0 ⎢0 ⎢0 ⎢ ⎢0 ⎢⎣0
1 0 0 0 0⎤ 0 0 1 0 0 ⎥⎥ 0 0 0 0 0⎥ ⎥ 1 1 0 0 0⎥ 0 1 1 0 1⎥ 0 1 0 0 0⎥ ⎥ 0 0 1 1 0⎥ 0 0 0 1 0 ⎥⎦
13
Dari matriks incidence E ( H ) diatas, jumlah dari elemen barisnya menyatakan derajat dari vertek, yaitu jumlah hiperedge yang dimiliki vertek tersebut. yaitu v1 = 2, v 2 = 2, v3 = 1, v 4 = 2, v5 = 3, v6 = 1, v7 = 2, v8 = 1 3.2 Hipergraf berarah
Hipergraf berarah adalah hipergraf dengan hiperedge berarah. Hiperedge berarah atau hiperarch adalah pasangan terurut E=(X,Y) dengan X adalah pangkal E dan Y ujung E. Selanjutnya, notasi T(E) adalah himpunan pangkal hiperedge E dan H(E) adalah himpunan ujung hiperedge E[13].
Gambar 4 Hipergraf berarah D (V , E )
Matriks incidenci dari hipergraf berarah D(V , E ) adalah matriks [aij ]
yang didefenisikan sebagai berikut: ⎧− 1 jika vi ∈ T ( E j ); i = 1,2,..., n ⎪ aij = ⎨1 jika vi ∈ H ( E j ); j = 1,2,..., m ⎪ 0 lainnya ⎩ Dari hipergraf berarah D (V , E ) gambar 4 diperoleh matrik incidence sebagai berikut:
14
0 0 0⎤ ⎡− 1 1 ⎢− 1 0 0 1 0 ⎥ ⎥ ⎢ ⎢1 0 0 0 0⎥ ⎢ 0 −1 1 0 0⎥ ⎥ [aij ] = ⎢ 0 1 1 0⎥ ⎢0 ⎢0 0 − 1 0 0 ⎥⎥ ⎢0 0 0 − 1 1⎥ ⎢ ⎢⎣ 0 0 0 0 − 1⎥⎦
3.3 Representasi Jaringan Metabolik Sebagai Hipergraf Berarah
Proses metabolisme dalam sel hidup dapat direpresentasikan oleh jaringan metabolic yang didefinisikan oleh metabolit dan sistem reaksi kimianya. Jaringan metabolic M ( X , ε ) dapat direpresentasikan oleh hipergraf berarah, dengan notasi
X menyatakan himpunan metabolit (vertek pada hipergraf berarah) dan notasi ε menyatakan himpunan reaksi kimia (hiperarc pada hipergraf berarah)[7]. Misalkan reaksi kimia: E1 : v1 → v2 + v3 , E2 : v2 → v4 , E3 : v4 → v5 ,
E4 : v3 + v6 → v5 yang dapat digambarkan sebagai jaringan metabolik M ( X , ε ) : V1
E1
V2
E2
V4
E3
v3
E4
v5
v6
Gambar 5 jaringan metabolik M ( X , ε )
Jaringan metabolik
M ( X , ε ) dapat direpresentasikan oleh matriks
stoikhiometri N = [nij ] dengan nij menyatakan koefisien stoikhiometri, masingmasing baris menyatakan metabolit vi dan masing-masing kolom menyatakan reaksi E j dengan
15
⎧ 1 jika vi ∈ E j + ; i = 1,2,..., n ⎪ nij = ⎨− 1 jika vi ∈ E j − ; j = 1,2,..., m ⎪ 0, lainnya ⎩ Dari jaringan metabolik M ( X , ε ) gambar 5 diperoleh: (1) Himpunan metabolit
X = {v1 , v2 , v3 , v4 , v5 , v6 } ;
(2)
Himpunan
reaksi
kimia
ε = {E1, E2 , E3 , E4 } dimana E j merupakan multiset ( E j − , E j + ) ; (3) Himpunan reaksi
E j− ⊆ X
educt
yang
terdiri
dari
E1− = {v1}, E2 − = {v2 }, E3− = {v4 }, E4 − = {v3 , v6 } ; dan (4) Himpunan reaksi E j+ ⊆ X
product
yang
terdiri
dari
E1+ = {v2 , v3}, E2 + = {v4 }, E3+ = {v5 }, E4 + = {v5 } [11]. Matriks stoikhiometri dari jaringan metabolik M ( X , ε ) gambar 5 adalah: ⎡− 1 0 0 0 ⎤ ⎢ 1 −1 0 0 ⎥ ⎢ ⎥ ⎢ 1 0 0 − 1⎥ N =⎢ 0 1 −1 0 ⎥ ⎢ ⎥ ⎢0 0 1 1⎥ ⎢ 0 0 0 − 1⎥ ⎣ ⎦
Selanjutnya definisikan operasi aljabar pada dua jaringan metabolik. misalkan M ' ( X ' , ε ' ) dan M " ( X " , ε " ) adalah dua jaringan metabolic maka: (1)
M '= M"
jika
dan
hanya
jika
X '= X"
M = M '∪M " = ( X '∪ X " , ε '∪ε ") ; (3) Irisan Difference
dan
ε ' = ε " ; (2) Gabungan
M = M'∩M"= ⎣ X'∩X",ε'∩ε"⎦ ; (4)
M = M '\M " = ⎣(sup p (ε '\ε " ), ε '\ε " )⎦ ; dan (5) Symmetric difference
M = M ' ∆M " = ⎣M '∪M "\ M '∩M "⎦ . Jaringan metabolik M ( X , ε ) disebut clean, jika sup ε = ∪{E E ∈ ε } =X dan notasi
⎣M ⎦ adalah operator clean dan
⎣M ⎦ = ( Suppε , ε ) [11]. Gambar 6 memberikan mengilustrasikan operasi dasar pada dua jaringan metabolik.
16
M’. Rickettsia Prowazekii
M”. Chlamydia trachomatis
(a).Union M '∪M "
(b).Intersection M '∩ M "
(c). Difference M '\M "
(d). Symmetric difference M ' ∆M "
Gambar 6 Operasi dari dua jaringan metabolik
17
Definisi 4 Jarak dari dua jaringan metabolik tak kosong M 1 dan M 2 didefinisikan
sebagai: d ( M 1 , M 2 ) =
M 1∆M 2 M1 ∪ M 2
= 1−
M1 ∩ M 2 M1 ∪ M 2
dengan
M
menyatakan
jumlah reaksi kimia yang terjadi dalam jaringan M ( X , ε ) . Teorema Untuk suatu jaringan metabolik M 1 , M 2 dan M 3 , memenuhi sifat
berikut: 1. 0 ≤ d ( M 1 , M 2 ) ≤ 1 2. d ( M 1 , M 2 ) = 0 ⇔ M 1 = M 2 3. d ( M 1 , M 2 ) = d ( M 2 , M 1 ) 4. d ( M 1 , M 3 ) ≤ d ( M 1 , M 2 ) + d ( M 2 , M 3 ) Bukti. Sifat 1-3 adalah akibat langsung dari definisi, Selanjutnya akan dibuktikan
sifat (4) yaitu memenuhi ketaksamaan segitiga. Misalkan m12 = M 1 ∩ M 2 , m23 = M 2 ∩ M 3 , m13 = M 2 ∩ M 3 , M 12 = M 1 ∪ M 2 , M 23 = M 2 ∪ M 3
dan M 13 = M 1 ∪ M 3 , maka diperoleh: d (M 1 , M 3 ) ≤ d (M 1 , M 2 ) + d (M 2 , M 3 ) ⇔ 1−
m m m12 + 1 − 23 ≥ 1 − 13 M 12 M 23 M 13
⇔ 1−
m m12 + 1 − 23 ≥ 1 M 12 M 23
⇔
m12 m23 + ≥1 M 12 M 23
⇔ M 12 M 23 ≥ m12 M 23 + m23 M 12 ⇔ M 12 M 23 ≥ m12 M 2 + m23 M 1
…(1)
Karena M 12 ≥ M 1 , M 23 ≥ M 2 maka diperoleh: M 12 M 23 ≥ M 1 M 2
...(2)
Pada jaringan metabolic M 1 , M 2 , M 3 , akan memenuhi pernyataan berikut: m12 + m23 ≤ M 2
...(3)
18
kasus 1: M 1 ≥ M 2
maka: M 1 M 2 ≥ m12 M 1 + m23 M 1 ≥ m12 M 2 + m23 M 1 berdasarkan persamaan (2), diperoleh: M 12 M 23 ≥ m12 M 2 + m23 M 1 Kasus 2: M 1 ≤ M 2 M 1 M 2 ≥ m12 M 2 + m23 M 2 ≥ m12 M 2 + m23 M 1
berdasarkan persamaan (2), diperoleh: M 12 M 23 ≥ m12 M 2 + m23 M 1 Berdasarkan
teorema
diatas,
maka
jarak
2
jaringan
metabolik,
d ( M 1 , M 2 ) memenuhi sifat metrik.
19
