4 bab ii teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/bab ii_ari...

22
4 BAB II LANDASAN TEORI A. Graf Teori graf merupakan pokok bahasan yang sudah tua usianya namun memiliki banyak terapan sampai saat ini. Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graf adalah dengan menyatakan objek yang dinyatakan sebagai noktah, bulatan, atau titik, sedangkan hubungan antara objek dinyatakan dengan garis (Munir. 2007: 353). 1. Definisi graf Secara matematis, graf G didefinisikan sebagai pasangan himpunan (V, E), ditulis dengan notasi G = (V, E), yang dalam hal ini V adalah himpunan tak kosong dari simpul-simpul (vertices atau node) dan E adalah himpunan sisi (edge atau arcs) yang menghubungkan sepasang simpul. Dengan demikian bahwa V tidak boleh kosong sedangkan E boleh kosong, sehingga sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada minimal satu (Munir. 2007: 357). 4 Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Upload: tranminh

Post on 02-Mar-2019

218 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

4

BAB II

LANDASAN TEORI

A. Graf

Teori graf merupakan pokok bahasan yang sudah tua usianya namun

memiliki banyak terapan sampai saat ini. Graf digunakan untuk

merepresentasikan objek-objek diskrit dan hubungan antara objek-objek

tersebut. Representasi visual dari graf adalah dengan menyatakan objek yang

dinyatakan sebagai noktah, bulatan, atau titik, sedangkan hubungan antara

objek dinyatakan dengan garis (Munir. 2007: 353).

1. Definisi graf

Secara matematis, graf G didefinisikan sebagai pasangan himpunan

(V, E), ditulis dengan notasi G = (V, E), yang dalam hal ini V adalah

himpunan tak kosong dari simpul-simpul (vertices atau node) dan E adalah

himpunan sisi (edge atau arcs) yang menghubungkan sepasang simpul.

Dengan demikian bahwa V tidak boleh kosong sedangkan E boleh kosong,

sehingga sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun,

tetapi simpulnya harus ada minimal satu (Munir. 2007: 357).

4

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 2: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

5

2. Jenis-jenis graf

Graf dapat digolongkan menjadi beberapa jenis graf yang spesifik.

Jenis-jenis graf ini akan dijelaskan seperlunya untuk membatasi graf dan

menyamakan pengertian mengenai graf yang akan dipakai dan dibahas

pada penelitian ini.

Graf dapat dikelompokan menjadi beberapa kategori (jenis)

bergantung pada sudut pandang pengelompokannya. Pengelompokan graf

dapat dipandang berdasarkan ada tidaknya sisi ganda atau sisi kalang,

berdasarkan orientasi arah pada sisi atau berdasarkan jumlah simpul.

Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf,

maka secara umum graf dapat digolongkan menjadi dua jenis yaitu:

a. Graf sederhana

Graf sederhana adalah graf yang tidak mengandung gelang

maupun sisi ganda. Pada graf sederhana, sisi adalah pasangan tak-

terturut (unordered pairs). Jadi menuliskan sisi (u,v) sama saja dengan

(v,u). Dapat didefinisikan juga bahwa graf sederahana G = (V, E)

terdiri dari himpunan tak kosong simpul-simpul dan E adalah

himpunan pasangan tak-berurut yang berbeda yang disebut sisi.

Contoh graf sederhana:

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 3: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

6

Gambar 1. Graf sederhana

b. Graf tidak sederhana

Graf tak sederhana adalah graf yang mengandung sisi ganda atau

gelang. Ada dua macam graf tak sederhana yaitu graf ganda

(multigraph) dan graf semu (pseudograph). Graf ganda adalah graf

yang mengandung sisi ganda. Sisi ganda yang menghubungkan

sepasang simpul bisa lebih dari dua buah. Dapat juga didefinisikan,

graf ganda G = (V, E) terdiri dari himpunan tak kosong simpul-simpul

dan E adalah himpunan ganda (multiset) yang mengandung sisi ganda.

Contoh graf tak sederhana:

Gambar 2. Graf ganda

Sedangkan graf semu adalah graf yang mengandung gelang (loop).

Graf semu lebih umum daripada graf ganda, karena sisi pada graf

2 3

4

1

1

2 3

4

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 4: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

7

semu dapat terhubung ke dirinya sendiri. Contoh graf semu dengan e

adalah simbol edge atau busur;

Gambar 3. Graf semu

Sisi pada graf mempunyai orientasi arah. Berdasarkan orientasi arah

pada sisi, maka secara umum graf dibedakan atas dua jenis, yaitu:

a. Graf tak-berarah (undirected graph)

Graf yang sisinya tidak mempunyai orientasi arah disebut graf

tak-berarah. Pada graf tak berarah, urutan pasangan simpul yang

dihubungkan oleh sisi tidak diperhatikan. Jadi, (u, v) = (v, u) adalah

sisi yang sama.

Contoh graf tak berarah.

Gambar 4. Graf tak berarah

b. Graf berarah (direct graph atau digraph)

Graf yang tiap sisinya diberikan orientasi arah disebut sebagai graf

berarah. Sisi berarah dapat disebut busur (arc). Pada graf berarah, (u,

1

2

4

3

e 1 e 3e 4

e5e 7

e 8

3

1

4

2

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 5: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

8

v) dan (v, u) menyatakan dua buah busur yang berbeda, dengan kata

lain (u,v) ≠ (v,u). Simpul u dinamakan simpul asal (initial vertex) dan

simpul v dinamakan simpul terminal (terminal vertex) (Munir. 2007).

Sebuah graf berarah G terdiri dari:

i. Sebuah himpunan V = V(G) yang elemen-elemennya disebut

vertex, titik atau node.

ii. Suatu koleksi E = E(G) dari pasangan-pasangan vertex terurut yang

disebut busur atau edge berarah.

Dinotasikan G (V, E) bilamana ingin menegaskan dua bagian dari

G (Lipschuts. 2002: 97).

Definisi graf dapat diperluas sehingga mencakup graf ganda

berarah (directed multigraph). Pada graf ganda berarah, gelang dan

sisi ganda diperbolehkan ada (Munir. 2007).

Gambar 5. Graf berarah

Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf

dapat digolongkan menjadi dua jenis:

a. Graf berhingga (limited graph)

Graf berhingga adalah graf yang jumlah simpulnya mencapai n

berhingga. Sebuah graf berarah G yang dinotasikan G (V, E)

3

1

4

2

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 6: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

9

dikatakan berhingga jika himpunan V dari verteks-verteksnya dan

himpunan E dari busurnya (edge berarahnya) berhingga (Lipschuts.

2002: 97). Salah satu contoh graf berhingga antara lain pada Gambar 2

berupa graf ganda dimana jumlah simpulnya berhingga.

b. Graf tak-berhingga (unlimited graph)

Graf yang jumlah simpulnya n tidak berhingga banyaknya disebut

graf tak-berhingga.

3. Terminologi dasar

a. Bertetangga (Adjacent)

Pada graf berarah, sisi di (u, v) adalah busur maka u dikatakan

bertetangga dengan v dan v dikatakan tetangga dari u. Pada Gambar 5,

simpul 1 bertetangga dengan simpul 2 dan simpul 2 dikatakan

tetangga dari simpul 1.

b. Bersisian

Untuk sembarang sisi e = (u, v), sisi e dikatakan bersisian dengan

simpul u dan simpul v. Pada Gambar 1, sisi (2, 3) bersisian dengan

simpul 2 dan simpul 3, sisi (2, 4) bersisian dengan simpul 2 dan

simpul 4, tetapi sisi (1, 2) tidak bersisian dengan simpul 4.

c. Graf kosong (Null graph atau Empty graph)

Graf yang himpunan sisinya merupakan himpunan kosong disebut

grag kosong dan ditulis sebagi Nn yang dalam hal ini n adalah jumlah

simpul. Contoh graf kosong seperti di bawah ini:

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 7: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

10

Gambar 6. Graf kosong N5

d. Derajat (Degree)

Pada graf berarah, derajat suatu simpul dibedakan menjadi dua

macam untuk mencerminkan jumlah busur dengan simpul tersebut

sebagai simpul asal dan jumlah busur dengan simpul tersebut sebagai

simpul terminal. Simpul yang berderajat satu disebut anting-anting

(pendant vertex). Pada Gambar 6, d(4) = 1, karena itu simpul 4 adalah

anting-anting.

Derajat siatu simpul pada graf berarah dinyatakan dengan din (v)

dan dout (v) yang dalam hal ini,

din (v) = derajat-masuk (in-dergee) = jumlah busur yang masuk ke

simpul v, sedangkan

dout (v) = derajat-keluar (out-dergee) = jumlah busur yang keluar dari

simpul v. Dan d(v) = din (v) + dout (v).

Dan sisi gelang pada graf berarah menyumbangkan 1 untuk

derajat-masuk dan satu untuk derajat-keluar. Contoh pada Gambar 5,

dapat diketahui:

1

2

3

4 5

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 8: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

11

din (1) = 2; dout (1) = 1

din (2) = 2; dout (2) = 3

din (3) = 1; dout (3) = 2

din (4) = 2; dout (4) = 1

Pada graf berarah G = (V, E) selalu berlaku hubungan

∑ ∑∈ ∈

==Vv Vv

outin EVdVd )()(

sehingga untuk contoh tersebut,

∑ ∑∈ ∈

==+++===+++=Vv Vv

outin EVdVd 71231)(72122)(

e. Lintasan (Path)

Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan

vn di dalam graf G ialah barisan berselang-seling simpul-simpul dan

sisi-sisi yang berbentuk vo, e1, v1, e2,,,, vn-1, en, vn sedemikian sehingga

e1 = (vo, v1,), e2 = (v1, v2,),,,, en = (vn-1, vn,) adalah sisi-sisi dari graf G.

Simpul dan sisi yang dilalui di dalam lintasan boleh berulang. Dan

sebuah lintasan dikatakan lintasan sederhana (simple path) jika semua

simpulnya berbeda (setiap sisi yang dilalui hanya satu kali). Lintasan

yang berawal dan berakhir pada simpul yang sama disebut lintasan

tertutup (closed path), sedangkan lintasan yang tidak berawal dan

berakhir pada simpul yang sama disebut lintasan terbuka (open path).

Contoh pada Gambar 1,

lintasan 1, 2, 4, 3 adalah lintasan sederhana, juga lintasan terbuka;

lintasan 1, 2, 4, 3, 1 adalah lintasan sederhana, juga lintasan tertutup;

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 9: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

12

lintasan 1, 2, 4, 3, 2 bukan merupakan lintasan sederhana, tetapi

termasuk lintasan terbuka.

Panjang lintasan adalah jumlah sisi pada lintasan tersebut.

Lintasan 1, 2, 4, 3 pada Gambar 1 memiliki panjang lintasan 3.

f. Siklus (Cycle) atau sirkuit (circuit)

Sirkuit atau siklus adalah lintasan yang berawal dan berakhir pada

simpul yang sama. Panjang sirkuit adalah jumlah sisi yang ada di

dalam sirkuit tersebut. Sebuah sirkuit dikatakan sirkuit sederhana

(simple circuit) jika setiap sisi yang dilalui berbeda. Contoh pada

Gambar 1, sirkuit sederhana ditunjukan oleh 1, 2, 3, 1, sedangkan 1, 2,

4, 3, 2, 1 bukan merupakan sirkuit sederhana, karena sisi (1, 2) dilalui

dua kali.

g. Terhubung (Connected)

Keterhubungan dua buah simpul adalah penting dalam graf. Dua

buah simpul u dan simpul v dikatakan terhubung jika terdapat lintasan

dari u ke v. Jika dua buah simpul terhubung maka pasti simpul yang

pertama dapat dicapai dari simpul yang kedua (Munir. 2007). Suatu

graf G dikatakan terhubung bila untuk setiap pasang simpul misalkan

vi dan vj di dalam himpunan V terdapat lintasan dari vi ke vj

(Lipschutz. 2002).

Jika setiap pasang simpul di dalam graf terhubung, maka graf

tersebut dapat dikatakan graf terhubung atau dengan kata lain graf tak

berarah G disebut graf terhubung (connected graph) jika untuk setiap

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 10: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

13

simpul u dan v di dalam himpunan V terdapat lintasan dari u ke v

(yang juga harus berarti ada lintasan dari u ke v). Jika tidak, maka G

disebut graf tak-terhubung (disconnected graph) (Munir. 2007: 371).

Pada Gambar 1 merupakan contoh graf terhubung, sedang untuk

contoh graf tak-terhubung antara lain:

Gambar 7. Graf tak-terhubung

Graf yang hanya terdiri atas satu simpul saja (tidak ada sisi) tetap

dikatakan terhubung, karena simpul tunggalnya terhubung dengan

dirinya sendiri. Pada graf berarah G dikatakan terhubung jika graf tak

berarahnya terhubung (graf tak berarah dari G diperoleh dengan

menghilangkan arahnya). Keterhubungan dua buah simpul pada graf

berarah dibedakan menjadi terhubung kuat dan terhubung lemah.

Dua simpul, u dan v pada graf berarah G disebut terhubung kuat

(strongly connected) jika terdapat lintasan berarah dari u ke v dan juga

sebaliknya lintasan berarah dari v ke u. Pada Gambar 8 (a), simpul 1

dan simpul 3 terhubung kuat karena terdapat lintasan dari 1 ke 3 (yaitu

1, 2, 3), begitu jug terdapat lintasan dari 3 ke 1 (yaitu 3, 4, 5, 1).

1

2 3

4 5

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 11: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

14

Jika u dan v tidak terhubung kuat tetapi terhubung pada graf tak

berarahnya, maka u dan v dikatakan terhubung lemah (weakly

connected). Pada Gambar 8 (b), simpul 1 dan simpul 3 terhubung

lemah karena hanya terdapat lintasan dari 3 ke 1 (yaitu 3, 5, 4, 1),

tetapi tidak ada lintasan dari 1 ke 3 (Munir. 2007: 372).

(a) (b)

Gambar 8. (a) Graf terhubung kuat, (b) Graf terhubung lemah

4. Lintasan dan Sirkuit Euler

Lintasan Euler adalah lintasan yang melalui setiap sisi di dalam graf

tepat satu kali. Bila lintasan tersebut kembali ke simpul asal, membentuk

lintasan tertutup (sirkuit), maka lintasan tertutup tersebut dinamakan

sirkuit Euler. Maka sirkuit Euler adalah sirkuit yang melewati masing-

masing sisi tepat satu kali.

Graf yang mempunyai sirkuit Euler disebut graf Euler (Eulerian

graph). Graf yang mempunyai lintasan Euler dinamakan juga graf semi

Euler (semi-Eulerian graph).

5

4 3

2

1

5

4 3

2

1

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 12: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

15

Syarat cukup dan perlu mengenai keberadaan lintasan Euler maupun

sirkuit Euler di dalam suatu graf ternyata sangat sederhana. Euler

menemukan syarat tersebut ketika memecahkan masalah jembatan

Konigsberg. Graf yang memiliki sirkuit Euler pasti mempunyai lintasan

Euler, tetapi tidak sebaliknya.

Lintasan dan sirkuit Euler juga terdapat pada graf berarah. Teorema

yang menyatakan syarat keberadaan lintasan dan sirkuit Euler pada graf

berarah dinyatakan dengan teorema berikut:

“Graf terhubung berarah G memiliki sirkuit Euler jika dan hanya jika G

terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar

sama. G memiliki lintasan Euler jika dan hanya jika G terhubung dan tiap

simpul memiliki derajat-masuk dan derajat-keluar sama kecuali dua

simpul, yang pertama memiliki derajat-keluar satu lebih besar derajat-

masuk, dan yang kedua memiliki derajat-masuk satu lebih besar dari

derajat-keluar”.

(Munir. 2007: 404 -

406)

Contoh graf yang menggambarkan lintasan dan sirkuit Euler.

Graf (a) Graf (b)

1

2 3

4

1

2 3

4

7

6

5

a b

cde

a

b c de

fg h

ijk

l

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 13: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

16

Gambar 9. Graf yang memiliki lintasan Euler dan Sirkuit Euler

Contoh lintasan Euler pada graf (a) adalah c, b, a, e, d.

Contoh sirkuit Euler pada graf (b) adalah a, d, j, l, k, I, h, g, f, e, c, b.

B. Rantai RNA (Ribonucleic acid)

1. Pengertian RNA

RNA merupakan singkatan dari Ribonucleic acid atau asam

ribonukleat. RNA dibentuk oleh DNA (Deoxyribonucleic acid) melalui

proses transkripsi (Syamsuri. 2004: 66). RNA merupakan rantai tunggal

polinukleotida (Aryulina. 2005: 66).

RNA adalah suatu polimer asam nukleotida dari empat ribonukleotida.

Tiap ribonukleotida terdiri dari gula pentose (D-ribose), molekul gugusan

pospat dan sebuah basa nitrogen (Suryo. 1994: 78).

Ada tiga macam RNA, yaitu RNA duta (RNA-d) atau RNA

messenger (mRNA), RNA ribosom (RNA-r) dan RNA transfer (RNA-t).

Semua RNA tersebut dihasilkan oleh DNA melalui proses transkripsi.

Sifat RNA adalah mudah terurai sehingga sel akan terus memproduksinya

(Sartini Bayu. 2008). Pada penelitian ini, rantai RNA yang dibahas adalah

jenis RNA duta (RNA-d) atau RNA messenger (mRNA).

2. Struktur RNA dan perbedaannya dengan DNA

Pada makhluk hidup tertentu, RNA-lah merupakan molekul genetika

keseluruhannya dan membawa segala pertanggung jawaban seperti yang

dimiliki DNA. Bentuk dari RNA adalah rantai tunggal yang ditempati oleh

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 14: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

17

gula ribosa, fosfat dan basa. Basa purin RNA terdiri dari Adenin (A) dan

Guanin (G), sedangkan basa pirimidin terdiri dari Sitosin (C) dan Urasil

(U) (Syamsuri. 2004).

Purin dan pirimidin yang berikatan dengan ribose membentuk suatu

molekul yang dinamakan ribonukleosida. RNA merupakan hasil

transkripsi dari DNA, sehingga RNA merupakan polimer yang jauh lebih

pendek dibanding DNA (Aryulina. 2005: 67).

Perbedaan antara RNA dengan DNA antara lain:

a. Mengenai ukuran dan bentuk

Pada umumnya molekul RNA lebih pendek daripada molekul

DNA. DNA terbentuk double helix (rantai ganda) dan merupakan

rantai panjang sedangkan RNA berbentuk single strand (rantai

tunggal) dan merupakan rantai pendek.

b. Mengenai susunan kimia

Molekul RNA juga merupakan polimer nukleotida, perbedaannya

dengan DNA antara lain: (1). Gula yang menyusun RNA bukan

dioksiribosa, melainkan ribose. (2). Basa pirimidin yang menyusun

RNA bukan timin melainkan Urasil (U), sedangkan basa purin antara

keduanya sama yakni Adenin (A) dan Guanin (G).

c. Mengenai Lokasinya

DNA umumnya terdapat di dalam nukleus dan ada pula yang

terdapat pada kloroplas dan mitokondria, sedangkan terdapatnya RNA

tergantung dari macamnya, yaitu:

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 15: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

18

1) RNA duta (RNAd), nama asingnya messenger RNA (mRNA)

terdapat dalam nukleus. RNAd dicetak oleh salah satu pita DNA

yang berlangsung di dalam nukleus.

2) RNA pemindah (RNAp), nama asingnya transfer RNA (tRNA),

terdapat di dalam sitoplasma.

3) RNA ribosom (RNAr), nama asingnya ribosome RNA (rRNA),

terdapat terutama di ribosoma. Molekulnya berupa pita tunggal,

tidak bercabang.

d. Mengenai fungsinya

DNA berfungsi memberi informasi/keterangan genetika,

sedangkan fungsi RNA umumnya adalah membawa pertangggung

jawaban atas informasi/keterangan genetika.

(Suryo. 1994)

3. G-Enzyme dan U, C-Enzyme

Sesuatu yang digunakan untuk memotong baik itu rantai RNA

maupun DNA adalah enzim. Enzim adalah katalisator di dalam sel

makhluk hidup (Syamsuri. 2004: 26). Enzim lengkap yang dimaksudkan

dalam rekonstruksi rantai RNA adalah enzim-enzim yang memutus mata

rantai dari sebuah rantai RNA.

Seperti yang sudah diketahui bahwa rantai RNA tersusun atas basa

purin dan basa pirimidin yaitu Adenin (A), Guanin (G), Sitosin (C) dan

Urasil (U). Pada kenyataannya, terdapat dua jenis enzim yang memutus

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 16: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

19

mata rantai RNA. Yang pertama disebut G-Enzyme. G-Enzyme ini berguna

untuk memutus rantai RNA tiap setelah mata rantai G dalam rantai RNA.

G-Enzyme ini akan memutus rantai RNA menjadi bagian-bagian yang

disebut dengan G-fragment. Sebagai contoh, salah satu rantai RNA

sebagai berikut:

UCGAGCUAGCGAAG

G-Enzyme akan memutusnya sehingga menjadi fragmen-fragmen yang

disebut G-fragment berupa UCG, AG, CUAG, CG, AAG.

Gambar 10. Proses pembentukan G-fragment

Enzim yang kedua disebut U, C-Enzyme. Enzim ini berguna untuk

memutus mata rantai RNA sedemikian sehingga rantai RNA tersebut akan

diputus menjadi fragmen-fragmen setiap setelah mata rantai U dan setiap

setelah mata rantai C. U, C-Enzyme ini akan memutus mata rantai RNA

menjadi bagian-bagian yang disebut dengan U, C-fragment. Sebagai

contoh untuk rantai RNA di atas, U, C-Enzyme akan memutusnya menjadi

fragmen-fragmen berupa U, C, GAGC, U, AGC, GAAG.

UCGAGCUAGCGAAG

G-Enzyme

UCG AG CUAG CG AAG

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 17: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

20

Gambar 11. Proses pembentukan U, C-fragment

C. Rekonstruksi Rantai RNA

Rekonstruksi adalah penyusunan ulang atau pembangunan kembali

sesuatu yang sudah ada. Sehingga dapat didefinisikan rekonstruksi rantai RNA

adalah penyusunan ulang atau pembangunan kembali rantai RNA yang

terputus.

Metode rekonstruksi rantai RNA yang dulu digunakan adalah cara

acak/manual yaitu dengan mencoba segala kemungkinan penyusunan yang

mungkin dapat dilakukan dari fragmen-fragmen yang diketahui tersebut.

Metode acak ini akan menghasilkan n! kemungkinan rantai RNA yang dicari,

dengan n adalah jumlah fragmen dari rantai RNA yang diketahui (Noorzaman.

2008). Untuk menentukan satu rantai RNA dari sekian kemungkinan rantai

RNA yang terjadi membutuhkan waktu yang cukup lama karena harus

mendefinisi dari sekian n! kemungkinan rantai RNA yang terjadi. Sebagai

contoh, diberikan beberapa G-fragment dan U, C-fragment berikut:

G-fragment : AG, UCG, CUAG, AAG, CG

U, C-fragment : U, C, GAGC, U, AGC, GAAG

UCGAGCUAGCGAAG

U,C-Enzyme

GAGC U AGC GAAG C U

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 18: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

21

Perlu diketahui dalam metode rekonstruksi cara acak/manual,

kedudukan antar fragmen dalam susunan fragmen adalah berbeda atau tidak

sama karena urutan di sini sangat diperhatikan karena akan berhubungan

dengan susunan/urutan basa pada rantai RNA yang nantinya akan memiliki

arti kode genetik yang berbeda pula. Misalnya: AG, UCG, CUAG, AAG, CG

≠ AG, UCG, AAG, CUAG, CG ≠ AAG, UCG, CUAG, AG, CG dan bentuk

lainnya.

Langkah pertama dalam metode rekonstruksi cara acak/manual adalah

membuat n! dari salah satu fragmen dan diusahakan yang mempunyai jumlah

fragmen yang lebih sedikit sehingga meminimalkan penyusunan

kemungkinan. Langkah kedua adalah menyusun kemungkinan rantai RNA

dari sekian banyak n! tersebut. Langkah terakhir adalah menemukan atau

menentukan kemungkinan rantai RNA yang terjadi yang apabila dipecah

dengan enzim yang lainnya akan menghasilkan fragmen yang sama dengan

fragmen dari enzim yang satunya yang sudah diketahui.

Sebagai contoh untuk fragmen di atas adalah sebagai berikut:

1. Membuat n! dari salah satu fragmen yang diketahui yang mempunyai

jumlah fragmen lebih sedikit, yakni G-fragment yang memiliki 5 buah

fragmen yang jauh lebih sedikit dibanding U, C-fragment. Maka akan

terdapat n! = 5! = 5 X 4 X 3 X 2 X 1 = 120 buah kemungkinan rantai

RNA.

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 19: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

22

2. Menyusun kemungkinan rantai RNA yang terjadi sebanyak n! atau 120

rantai yang membangun himpunan dari fragmen yang lain. Maka diperoleh

kemungkinan sebagai berikut:

1) AGUCGCUAGAAGCG

2) AGUCGCUAGCGAAG

3) AGUCGAAGCUAGCG

4) AGUCGAAGCGCUAG

5) AGUCGCGCUAGAAG

6) AGUCGCGAAGCUAG

7) AGCUAGUCGAAGCG

8) AGCUAGUCGCGAAG

9) AGCUAGAAGUCGCG

10) AGCUAGAAGCGUCG

11) AGCUAGCGUCGAAG

12) AGCUAGCGAAGUCG

13) AGAAGUCGCUAGCG

14) AGAAGUCGCGCUAG

15) AGAAGCUAGUCGCG

16) AGAAGCUAGCGUCG

17) AGAAGCGUCGCUAG

18) AGAAGCGCUAGUCG

19) AGCGUCGCUAGAAG

20) AGCGUCGAAGCUAG

21) AGCGCUAGUCGAAG

22) AGCGCUAGAAGUCG

23) AGCGAAGUCGCUAG

24) AGCGAAGCUAGUCG

25) UCGAGCUAGAAGCG

26) UCGAGCUAGCGAAG

27) UCGAGAAGCUAGCG

28) UCGAGAAGCGCUAG

29) UCGAGCGCUAGAAG

30) UCGAGCGAAGCUAG

31) UCGCUAGAGAAGCG

32) UCGCUAGAGCGAAG

33) UCGCUAGAAGAGCG

34) UCGCUAGAAGCGAG

35) UCGCUAGCGAGAAG

36) UCGCUAGCGAAGAG

37) UCGAAGAGCUAGCG

38) UCGAAGAGCGCUAG

39) UCGAAGCUAGAGCG

40) UCGAAGCUAGCGAG

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 20: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

25

41) UCGAAGCGAGCUAG

42) UCGAAGCGCUAGAG

43) UCGCGAGCUAGAAG

44) UCGCGAGAAGCUAG

45) UCGCGCUAGAGAAG

46) UCGCGCUAGAAGAG

47) UCGCGAAGAGCUAG

48) UCGCGAAGCUAGAG

49) CUAGAGUCGAAGCG

50) CUAGAGUCGCGAAG

51) CUAGAGAAGUCGCG

52) CUAGAGAAGCGUCG

53) CUAGAGCGUCGAAG

54) CUAGAGCGAAGUCG

55) CUAGUCGAGAAGCG

56) CUAGUCGAGCGAAG

57) CUAGUCGAAGAGCG

58) CUAGUCGAAGCGAG

59) CUAGUCGCGAGAAG

60) CUAGUCGCGAAGAG

61) CUAGAAGAGUCGCG

62) CUAGAAGAGCGUCG

63) CUAGAAGUCGAGCG

64) CUAGAAGUCGCGAG

65) CUAGAAGCGAGUCG

66) CUAGAAGCGUCGAG

67) CUAGCGAGUCGAAG

68) CUAGCGAGAAGUCG

69) CUAGCGUCGAGAAG

70) CUAGCGUCGAAGAG

71) CUAGCGAAGAGUCG

72) CUAGCGAAGUCGAG

73) AAGAGUCGCUAGCG

74) AAGAGUCGCGCUAG

75) AAGAGCUAGUCGCG

76) AAGAGCUAGCGUCG

77) AAGAGCGUCGCUAG

78) AAGAGCGCUAGUCG

79) AAGUCGAGCUAGCG

80) AAGUCGAGCGCUAG

81) AAGUCGCUAGAGCG

82) AAGUCGCUAGCGAG

83) AAGUCGCGAGCUAG

84) AAGUCGCGCUAGAG

85) AAGCUAGAGUCGCG

86) AAGCUAGAGCGUCG

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 21: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

26

87) AAGCUAGUCGAGCG

88) AAGCUAGUCGCGAG

89) AAGCUAGCGAGUCG

90) AAGCUAGCGUCGAG

91) AAGCGAGUCGCUAG

92) AAGCGAGCUAGUCG

93) AAGCGUCGAGCUAG

94) AAGCGUCGCUAGAG

95) AAGCGCUAGAGUCG

96) AAGCGCUAGUCGAG

97) CGAGUCGCUAGAAG

98) CGAGUCGAAGCUAG

99) CGAGCUAGUCGAAG

100) CGAGCUAGAAGUCG

101) CGAGAAGUCGCUAG

102) CGAGAAGCUAGUCG

103) CGUCGAGCUAGAAG

104) CGUCGAGAAGCUAG

105) CGUCGCUAGAGAAG

106) CGUCGCUAGAAGAG

107) CGUCGAAGAGCUAG

108) CGUCGAAGCUAGAG

109) CGCUAGAGUCGAAG

110) CGCUAGAGAAGUCG

111) CGCUAGUCGAGAAG

112) CGCUAGUCGAAGAG

113) CGCUAGAAGAGUCG

114) CGCUAGAAGUCGAG

115) CGAAGAGUCGCUAG

116) CGAAGAGCUAGUCG

117) CGAAGUCGAGCUAG

118) CGAAGUCGCUAGAG

119) CGAAGCUAGAGUCG

120) CGAAGCUAGUCGAG

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010

Page 22: 4 BAB II Teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/BAB II_ARI PRASETIYOWATI_MATEMATIKA'10.pdf · Contoh graf sederhana: Aplikasi Sirkuit Euler...,

48

3. Menemukan rantai RNA dari 120 daftar kemungkinan tersebut yang

disusun oleh G-fragment, yang memiliki kesamaan urutan fragmen dengan

U, C-fragment (seperti yang diketahui), jika rantai RNA tersebut dipecah

oleh U, C-Enzyme. Dan ditemukan rantai RNA pada urutan ke- 26

(UCGAGCUAGCGAAG) yang mana rantai tersebut jika dipecah oleh U,

C-Enzyme menjadi U, C-fragment yaitu U, C, GAGC, U, AGC, GAAG,

seperti yang diketahui. Maka rantai RNA aslinya adalah

UCGAGCUAGCGAAG .

Rekonstruksi rantai RNA dengan cara acak/manual dapat dikatakan

efektif tergantung dari jumlah fragmen (dalam hal ini adalah n) yang

digunakan. Apabila semakin banyak jumlah fragmen yang akan digunakan

pada langkah pertama yaitu pada pembuatan n!, maka akan semakin banyak

pula penyusunan kemungkinan rantai RNA tersebut sehingga makna efektif

sebelumnya dapat berubah menjadi kurang efektif.

Selain itu, dapat pula terjadi kemungkinan rantai RNA yang unik

artinya tidak dapat ditemukan dari kesekian n! kemungkinan rantai yang

tersusun dari salah satu fragmen yang apabila rantai tersebut dipecah oleh

enzim lainnya tidak ditemukan fragmen dari enzim lainnya yang dimaksud.

Dengan kata lain, untuk fragmen yang unik maka rekonstruksi rantai RNA

tidak dapat dipecahkan dengan menggunakan cara acak/manual.

Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010