4
BAB II TINJAUAN PUSTAKA
Pada bab ini diberikan istilah-istilah dan definisi-definisi yang digunakan pada penelitian ini.
2.1 Konsep Dasar Graf
2.1.1 Graf Graf dapat merepresentasikan suatu kejadian, proses, peristiwa atau hal-hal lain yang saling berkaitan. Graf merupakan himpunan pasangan terurut (V, E) dimana V adalah himpunan vertex/titik dengan V ≠ Ø; dan E adalah himpunan edge/rusuk (Wibisono, 2010). Contoh graf yang merepresentasikan suatu jaringan ditunjukkan pada Gambar 2.1
Gambar 2.1 Contoh graf yang merepresentasikan suatu jaringan
5
2.1.2 Walk Walk adalah suatu barisan edge sedemikian rupa sehingga vertex terminal berimpit dengan vertex awal untuk 1≤ j ≤ k. Suatu walk dikatakan sederhana jika ia tidak mencakup edge yang sama dua kali (Liu, 1995). Contoh walk ditunjukkan pada Gambar 2.2.
Gambar 2.2 Walk dengan edge Ae1 Be2 Ce3 Ee4 Ge5 Fe6 Ce7
2.1.3 Path Menurut Wibisono (2010), path adalah walk dengan semua vertex yang berlainan, artinya vertex awal berbeda dengan vertex akhir dalam walk tersebut. Contoh path ditunjukkan pada Gambar 2.3.
Gambar 2.3 Path dengan walk Ae1 Be2 Ce3 Ee4 Ge5 Fe7 D
6
2.1.4 Tree (Pohon) Tree adalah graf terhubung yang tidak mengandung sirkuit (Deo, 1989). Sirkuit adalah suatu lintasan yang titik terminalnya berimpit dengan titik awalnya. Contoh tree ditunjukkan pada Gambar 2.4.
Gambar 2.4 Contoh Tree dengan 10 vertex
2.1.5 Graf Berarah Suatu graf berarah atau digrah, G terdiri dari. (i)
Suatu himpunan V=V(G) yang elemen-elemennya disebut titik atau garis.
(ii)
Suatu E=E(G) dari pasangan-pasangan titik terurut yang disebut busur atau garis berarah atau garis.
Graf berarah G dikatakan berhingga jika himpunan V dari titik-titiknya dan himpunan E dari busurnya (garis berarah) berhingga (Lipschutz dan Lipson, 2002).
7
2.1.6 Rooted Tree Rooted tree adalah suatu tree dengan ada satu titik yang indegree-nya nol (titik sumber). Setiap titik dapat dianggap atau dijadikan akar, titik yang dianggap sebagai akar ditandai dengan lingkaran yang mengelilingi titik tersebut (Wibisono, 2010). Contoh rooted tree dengan lima vertex terdapat pada Gambar 2.5.
Gambar 2.5 Root tree dengan lima vertex
2.1.7 Succesor (Succ) Setiap vertex i pada suatu tree (kecuali root = 0) merupakan initial vertex untuk tepat satu edge, sehingga dapat didefinisikan succ(i)=j adalah terminal vertex untuk edge ij dalam fungtional digraph (Amalia, 2010). Contoh succesor terdapat pada Gambar 2.5.
Gambar 2.6 Succesor(1)=6 adalah terminal vertex untuk edge 16
8
2.1.8 Indegree dan Outdegree
Indegree suatu titik adalah jumlah vertex yang masuk ke suatu titik. Sedangkan Outdegree suatu titik adalah jumlah rusuk yang keluar dari suatu titik. Titik yang indegree-nya = 0 disebut sumber (Wibisono, 2010).
2.1.9 Spanning Tree Suatu tree T dikatakan spanning tree dari graf terhubung G jika T adalah subgraf dari G dan memuat semua titik dari graf G (Deo, 1989).
2.2 Encoding dan Decoding Tree Kode Dandelion 2.2.1 Kode Dandelion
Menurut Amalia (2010), Kode Dandelion merupakan suatu tree yang memuat n vertex dengan label (0,1,2,….,n) dan edge yang menghubungkan setiap dua vertex memiliki bobot Bsucc(Vi). Vertex 0 (nol) merupakan root dalam tree tersebut. Bsucc(Vi) menggambarkan edge dan vertex vi sebagai tail ke vertex succ(vi) sebagai head. Tree merupakan fungsional digraf, dimana setiap vertex merupakan tail tepat satu edge vi succ(vi). Bsucc(Vi)
memudahkan dalam proses encoding dan decoding tree berarah.
Bsucc(Vi) digunakan untuk mewakili setiap edge awal yang menghubungkan vi ke succ(vi) yang kemudian digantikan dengan edge menghubungkan vi ke 1. Contoh Kode Dandelion terdapat pada Gambar 2.6.
9
Gambar 2.7 Kode Dandelion 2.2.2 Proses Encoding Tree dengan Kode Dandelion Langkah-langkah proses encoding tree pada kode Dandelion sebagai berikut. 1. Pada langkah i, hapus edge n-i+1 succ(n-i+1) dan tambahkan edge ni+11 dengan bobot Bsucc(n-i+1).(1≤ i ≤ n-1; n didefinisikan banyaknya vertex selain root 0). 2. Apabila terdapat edge 1 succ(1); edge succ(1)succ(succ(1)), … edge succ(…(succ(1)))n-i+1
sehingga
selama
proses
berlangsung
menyebabkan terbentuknya cycle, maka yang harus dilakukan adalah menghapus edge 1 succ(1) dan edge n-i+11, kemudian gantikan keduanya dengan edge 1succ(n-i+1) dan edge n-i+11 dengan memberi bobot Bsucc(1). Lanjutkan langkah (1) pada i berikutnya. 3. Proses selesai pada langkah i=n-1 4. Kemudian kode tersebut dibaca berdasarkan Naïve code dari vertex 2,3,…,n (sebagai pengganti dari successors setiap vertex).
10
Diagram alir encoding kode Dandelion ditunjukkan pada Gambar 2.7.
Mulai
For 1≤i≤n-1
m=succ(n-i+1); k=succ(1)
Hapus edge (n-i+1)m; Tambahkan edge (n-i+1)k dengan bobot Bm
ya
Menyebabkan cycle
Hapus edge nk; Tambahkan edge (n-i+1)1; Tambahkan edge 1m; Tambahkan edge(n-i+1)1 Dengan bobot Bk
tidak tidak
i=n-1 ya
For 2≤j≤n
Wj = Bobot setiap edge j1
Tulis Kode Dandelion=(w2,w3,…,wn)
Selesai Gambar 2.8 Diagram Alir Encoding Kode Dandelion
11
Contoh encoding kode Dandelion : Diberikan tree berarah dengan tujuh vertex dan enam edge yang ditunjukkan pada Gambar 2.9.
1 3 2
5 6 4
0
Gambar 2.9 Tree Berarah dengan 7 Vertex dan 6 Edge Langkah-langkah memperoleh kode Dandelion dari tree berarah di atas adalah. Langkah 1
:
hapus edge 64 dimana vertex (6) sebagai initial vertex dan vertex (4) sebagai successor dari vertex (6), kemudian tambahkan edge 61 dengan bobot B4. Kode Dandelion sementara yaitu (B4) seperti ditunjukkan pada Gambar 2.10.
5 6 B4
1 3 2
4
0 Gambar 2.10 Kode Dandelion Sementara (B4)
12
Langkah 2
:
hapus edge 56 dimana vertex (5) sebagai initial vertex dan vertex (6) sebagai successor dari vertex (5), kemudian tambahkan edge 51 dengan bobot B6. Kode Dandelion sementara yaitu (B6, B4) seperti ditunjukkan pada Gambar 2.11. 5 B6 1
6 B4
3 2
4 0 Gambar 2.11 Kode Dandelion Sementara (B6, B4) Langkah 3
:
hapus edge 40 dimana vertex (4) sebagai initial vertex dan vertex (0) sebagai successor dari vertex (4), kemudian tambahkan edge 41. Penambahan edge 41 menyebabkan terbentuknya cycle dikarenakan terdapat edge 12 dan edge 24. Dengan demikian, hapus edge 12 dan digantikan dengan edge 10 serta beri bobot B2 pada edge 41. Kode Dandelion sementara yaitu (B2, B6, B4) seperti ditunjukkan pada Gambar 2.12.
13
3
5 B6 1 6
2
B4
4 B2 5
2 3
B6
4 6
1
B4
0
0
Gambar 2.12 Kode Dandelion Sementara (B2, B6, B4) Langkah 4
:
hapus edge 32 dimana vertex (3) sebagai initial vertex dan vertex (2) sebagai successor dari vertex (2), kemudian tambahkan edge 31 dengan bobot B2. Kode Dandelion sementara yaitu (B2, B2 ,B6, B4) ditunjukkan pada Gambar 2.13. 2 4 B2
5 B6 6
3 B2 1
B4 0
Gambar 2.13 Kode Dandelion Sementara (B2, B2 ,B6, B4) Langkah 5
:
hapus edge 24 dimana vertex (2) sebagai initial vertex dan vertex (4) sebagai successor dari vertex (2), kemudian tambahkan edge 21 dengan bobot B4. Dengan demikian kode Dandelion yang diperoleh adalah (B4,B2, B2 ,B6,B4) = (4,2,2,6,4).
14
4 B2
5
3
B2 B6 6
1 B4
B4
2
0 Gambar 2.14 Kode Dandelion yang diperoleh (4,2,2,6,4) 2.2.3 Proses Decoding Tree dari Kode Dandelion Langkah-langkah mengkontruksi tree berarah dari kode Dandelion yaitu. 1. Konstruksi kode ke dalam bentuk graf dengan setiap vertex (2, 3, …, n) menuju 1 dan bobot setiap edge (21, 31, …, n1) adalah Bsucc(2), Bsucc(3), …, Bsucc(n). 2. Pada langkah i, hapus edge i+11 dan bobot Bsucc(i+1), kemudian tambahkan edge i+1succ(i+1).(1≤i≤n). 3. Apabila
terdapat
edge
succ(i+1)succ(succ(i+1)),
edge
succ
(succ(i+1))succ(succ(succ(i+1))), …, edge succ…(succ(i+1))(i+1) sehingga selama proses berlangsung menyebabkan terbentuknya cycle maka
yang
dilakukan
adalah
menghapus
edge
1succ(1)
dan
i+1succ(i+1), kemudian tambahkan edge 1succ(i+1) dan edge i+1succ(1). Lanjutkan langkah(2) pada i berikutnya. 4. Proses akan selesai pada langkah i=n-1.(n adalah banyaknya vertex, selain root 0 (nol).
15
Diagram alir decoding kode Dandelion ditunjukkan pada Gambar 2.15.
Mulai
Edge 10
For 2≤i≤n
Tambahkan edge i 1 dengan bobot Bsucc(i)
For 2≤i≤n
k=succ(i); m=succ(1)
Tambahkan edge i1 Hapus edge i1
tidak
ya
Menyebabkan cycle
Hapus edge ik dan edge 1m, Tambahkan edge 1m; Dan edge 1k
tidak
I=n ya
Selesai Gambar 2.15 Diagram Alir Decoding Kode Dandelion
16
Contoh decoding kode Dandelion : Diberikan kode Dandelion :(4,2,2,6,4) seperti ditunjukkan pada Gambar 2.16.
4 B2
5
3
B2 B6 6
1 B4
2
B4
0 Gambar 2.16 Tree Berarah dengan Kode Dandelion (4,2,2,6,4) Langkah-langkah mengkontruksi tree berarah dari kode Dandelion di atas adalah. Langkah 1
:
hapus edge 21 dan bobot B4. dimana vertex (4) sebagai successor dari vertex (2), dan tambahkan edge 24, seperti ditunjukkan pada Gambar 2.17. 2
4 5
3
B2
B2
B6 1 6
B4
0
Gambar 2.17 Tree Berarah dengan Kode Dandelion (2,2,6,4)
17
Langkah 2
:
hapus edge 31 dan bobot B2 dimana vertex (2) sebagai successor dari vertex (3), dan tambahkan edge 24, seperti ditunjukkan pada Gambar 2.18.
3 2 4 B2 5 B6 6
1 B4 0
Gambar 2.18 Tree dengan Kode Dandelion (2,6,4) Langkah 3
:
hapus edge 41 bobot B2 dimana vertex (2) adalah successor dari vertex (4), dan tambahkan edge 42. Penambahan edge 42 menyebabkan terbentuknya cycle dikarenakan terdapat edge 24. Dengan demikian, hapus edge 42 dan edge 10 kemudian gantikan keduanya dengan menambahkan edge 12 dan edge 40, seperti ditunjukkan pada Gambar 2.19. 3
5
B6
2 4 5
6
1 3
B4
B6 1
6
2
B4 4 0 Gambar 2.19 Tree dengan Kode Dandelion (6,4)
0
18
Langkah 4
:
hapus edge 51 dan bobot B6 dimana vertex (6) adalah successor dari vertex (5), dan tambahkan edge 56, seperti ditunjukkan pada Gambar 2.20.
5 6
1
B4
3 2
4
0 Gambar 2.20 Tree dengan Bobot Kode Dandelion (B4) Langkah 5
:
hapus edge 61 dan bobot B4 dimana vertex (4) adalah successor dari vertex (6), dan tambahkan edge 64. seperti ditunjukkan pada Gambar 2.21.
1 3 2
5 6 4
0
Gambar 2.21 Diperoleh Tree Berarah 7 Vertex dan 6 Edge
19
2.3 Metode Prototype
Prototyping adalah suatu proses untuk melakukan simulasi terhadap suatu sistem dan dapat dibuat dengan cepat. Prototyping juga merupakan suatu teknik analisis iteratif dimana user terlibat secara aktif dalam proses desain layar dan laporan. Hal ini nantinya akan dimanfaatkan suatu sarana untuk melakukan eksplorasi serta komunikasi lebih lanjut dalam proses desain. Kunci utama dari suatu prototyping adalah untuk membuat suatu desain awal dengan cepat dan disertai perubahan yang bisa jadi radikal serta nantinya akan menghasilkan suatu umpan balik, terutama dari pengguna, secara cepat untuk melakukan desain ulang di tahap berikutnya (Rizky, 2007).
Metode Prototype adalah versi sistem informasi atau bagian dari sistem yang sudah dapat berfungsi, tetapi dimaksudkan hanya sebagai model awal saja. Setelah beroperasi, prototype lebih jauh diperhalus hingga cocok sekali dengan kebutuhan penggunanya. Ketika rancangan telah difinalisasi, prototype dapat dikonversi menjadi sistem produksi yang jauh lebih baik (Laudon, 2008).
2.3.1 Tahapan Prototype Tahapan-tahapan prototype menurut Pressman (2001) adalah sebagai berikut. 1. Mendengarkan Pelanggan. Pada tahap ini dilakukan pengumpulan kebutuhan dari sistem dengan cara mendengar keluhan dari pelanggan. Untuk membuat suatu sistem yang sesuai kebutuhan,
maka
harus
diketahui
terlebih
dahulu
bagaimana sistem yang sedang berjalan untuk kemudian mengetahui masalah yang terjadi.
20
2. Merancang dan Membuat Prototype. Pada tahap ini, dilakukan perancangan dan pembuatan sistem prototype. Prototype yang dibuat disesuaikan dengan kebutuhan sistem yang telah didefinisikan sebelumnya dari keluhan pelanggan atau pengguna. 3. Uji coba Pada tahap ini, Prototype dari sistem diuji coba oleh pelanggan atau pengguna. Kemudian dilakukan evaluasi kekurangan-kekurangan dari kebutuhan pelanggan. Pengembangan kemudian kembali mendengarkan keluhan dari pelanggan untuk memperbaiki prototype yang ada.
Gambar 2.22 Tahapan Metode Prototype
2.4 PHP PHP (Hypertext Preprocessor) adalah bahasa pemrograman yang berjalan dalam suatu webserver yang berfungsi sebagai pengolah data pada suatu server (Madcoms, 2011).
21
PHP merupakan suatu produk open source, sehingga source code PHP dapat digunakan, diubah. Keunggulan PHP selain sifatnya yang open source adalah multi platform selain dapat dijalankan pada platform Linux, PHP juga dapat dijalankan dengan menggunakan Apache, dengan IIS pada Window NT atau PWS pada Windows 98 (Cahyanto, Dkk, 2013).
