BAB 2 LANDASAN TEORI
Pada bab ini akan dibahas teori-teori pendukung dalam penelitian ini. Teori-teori yang digunakan antara lain adalah teori desain jaringan (Network Design Theory), metode yang digunakan di dalam penelitian ini, yaitu metode Transitive Closure, beberapa teori tentang entity relationship diagram dan teori flowchart.
2.1
Network Design Theory
2.1.1 Pengertian Jaringan Kata jaringan atau network sebenarnya memiliki banyak arti tergantung dari lingkup studi yang dimaksud. Kata network yang dimaksud disini berada dalam lingkup studi teknologi informasi yang memiliki definisi sebagai kumpulan dua atau lebih komputer yang masing-masing berdiri sendiri dan terhubung melalui sebuah teknologi. Hubungan antar komputer tersebut tidak terbatas berupa kabel tembaga saja, namun juga bisa melalui kabel serat kaca (fiber optic), gelombang microwave, infrared, bahkan melalui satelit (Tanenbaum, 2003). Kegunaan dari network itu sendiri banyak dan beragam tergantung dimana network itu digunakan, mulai dari sebagai instantmessaging
dan
hiburan
interaktif
di
rumah
sampai
resource-sharing
dan
videoconferencing di sebuah perusahaan. Beberapa manfaat dari jaringan adalah sebagai berikut.
8
Jaringan memungkinkan manajemen sumber daya lebih efisien
Jaringan membantu mempertahankan informasi agar tetap andal dan up-todate
Jaringan membantu mempercepat proses berbagi data (data sharing)
Jaringan memungkinkan kelompok kerja berkomunikasi dengan lebih efisien
Jaringan membantu usaha dalam melayani klien mereka secara lebih efektif
2.1.2 Konsep Jaringan Jaringan adalah suatu link yang menghubungkan antar node. Dalam konsep dasar dikenal istilah–istilah yang sering digunakan dalam jaringan, yaitu :
Titik menggambarkan simpul/node
Garis menggambarkan link/saluran.
Konsep Jaringan ini terdiri atas 2 bagian yaitu :
Undirected Network, dalam konsep jaringan ini jurusan/tujuan lintasan tidak dilihat.
Directed Network, dalam konsep jaringan ini jurusan/tujuan lintasan diperhatikan
2.1.3 Jenis-Jenis Jaringan Berdasarkan tipe transmisinya (Tanenbaum, 2003) network dapat dibagi menjadi dua bagian besar.
9
Broadcast Dalam broadcast network, komunikasi terjadi dalam sebuah saluran komunikasi yang digunakan secara bersama-sama, dimana data berupa paket yang dikirimkan dari sebuah komputer akan disampaikan ke tiap komputer yang ada dalam jaringan tersebut. Kemudian setiap komputer akan mencek apakah data tersebut ditujukan untuk dirinya berdasarkan data alamat yang ada dalam paket tersebut. Paket data hanya akan diproses oleh komputer tujuan dan akan dibuang oleh komputer yang bukan tujuan paket tersebut.
Point-to-point Sedangkan pada point-to-point network, komunikasi data terjadi melalui beberapa koneksi antar sepasang komputer, sehingga untuk mencapai tujuannya sebuah paket mungkin harus melalui beberapa komputer terlebih dahulu. Oleh karena itu, dalam tipe jaringan ini, pemilihan rute yang baik akan menentukan bagus tidaknya koneksi yang berlangsung.
Berdasarkan skalanya (Tanenbaum, 2003) network dapat diklasifikasikan menjadi enam macam.
Personal Area Network (PAN) PAN merupakan jaringan yang ditujukan untuk satu orang saja, contohnya mouse yang terhubung dengan komputer.
10
Local Area Network (LAN) LAN merupakan jaringan yang hanya mencakup beberapa kilometer saja di dalam satu areal tertentu yang tidak begitu luas, seperti jaringan dalam sebuah perusahaan atau jaringan dalam sebuah rumah
Metropolitan Area Network (MAN) Sebuah MAN, biasanya meliputi area yang lebih besar dari LAN, misalnya antar wilayah dalam satu propinsi. Dalam hal ini jaringan menghubungkan beberapa buah jaringan-jaringan kecil ke dalam lingkungan area yang lebih besar. MAN mencakup area geografis sebuah kota seperti jasa televisi kabel dalam sebuah kota.
Wide Area Network (WAN) Jaringan WAN inilah yang dipakai sebagai bagian dari objek penelitian skripsi ini. WAN merupakan jaringan yang mempunyai luas jangkauan yang sangat besar biasanya meliputi sebuah negara atau benua. Wide Area Network adalah jaringan yang lingkupnya biasanya sudah menggunakan sarana satelit ataupun kabel bawah laut.
Internetworking (Internet) Internet merupakan kumpulan jaringan yang terinterkoneksi antara jaringan yang satu dengan yang lainnya dengan menggunakan mesin yang disebut gateway untuk melakukan hubungan dan melaksanakan terjemahan yang diperlukan, baik pada hardware maupun softwarenya.
11
Jaringan tanpa kabel (Wireless) Jaringan tanpa kabel merupakan suatu solusi terhadap komunikasi yang tidak bisa dilakukan dengan jaringan yang menggunakan kabel. Saat ini jaringan tanpa kabel sudah marak digunakan dengan memanfaatkan jasa satelit.
2.1.4 Arsitektur dan Topologi Jaringan (Network Architecture and Topology) Beberapa faktor yang perlu diperhatikan dalam mendesain jaringan adalah sebagai berikut. Jaringan Interkoneksi Jaringan interkoneksi adalah suatu sistem komputer atau komunikasi yang tersebar termasuk dalam suatu sistem yang umum yang memperhatikan parameterparameter efisiensi tertentu berupa waktu dan biaya. Jaringan interkoneksi meupakan salah satu syarat untuk mendesain suatu jaringan. Topologi Jaringan Site-site/wilayah-wilayah dalam sistem terdistribusi dapat terhubung melalui berbagai macam cara yang ditentukan berdasarkan kriteria-kriteria sebagai berikut:
Biaya instalasi meliputi biaya menghubungkan site-site dalam sistem.
Biaya komunikasi meliputi besar waktu dan uang untuk mengirimkan pesan dari satu site ke site lainnya.
Ketersediaan/availabilitas, yaitu sampai sejauh mana data dapat diakses walaupun terdapat kegagalan pada beberapa link.
12 Macam-macam topologi jaringan yang paling sering digunakan adalah sebagai berikut.
Fully Connected Network Tiap site dalam Fully Connected Network terkoneksi secara langsung dengan situs lainnya. Link yang ada menjadi banyak dan menyebabkan biaya instalasi besar. Topologi jenis ini tidak praktis untuk diterapkan dalam sistem yang besar.
Gambar 2.1. Fully Connected Network Sumber: http://en.wikipedia.org/wiki/Image:NetworkTopologies.png
Partially Connected Network Link yang ada hanya antara beberapa site sehingga biaya instalasi menjadi lebih rendah. Namun, biaya komunikasi bisa menjadi lebih mahal. Misalkan, site A ingin mengakses data di site E, maka jalan yang ditempuh menuju site E harus melalui site B terlebih dahulu karena tidak ada link langsung dari site A ke site E. Semakin jauh jalan yang ditempuh, biaya komunikasi semakin mahal. Selain itu, availibilitas atau ketersediaan data kurang baik dibandingkan dengan Fully Connected Network. Misalkan, jika terjadi failure site atau kegagalan site di C maka akses ke site F menjadi tidak ada.
13 Partially connected network terdiri dari:
Tree-structured network. Biaya instalasi dan komunikasi pada topologi jenis ini biasanya rendah. Namun, jika terjadi failure link atau failure site maka pengaksesan data menjadi terhambat dan mengakibatkan availibilitas/ketersediaan menjadi rendah.
Gambar 2.2. Tree Structured Network Sumber: http://en.wikipedia.org/wiki/Image:NetworkTopologies.png
Star network. Biaya komunikasi rendah karena setiap site paling banyak mengakses dua link ke site lain. Namun, bila terjadi failure site di site pusat maka setiap site tidak akan dapat mengakses site lainnya sehingga availibilitas/ketersediaan pada topologi jenis star network rendah.
Gambar 2.3. Star Network Sumber: http://en.wikipedia.org/wiki/Image:NetworkTopologies.png
Ring network.
14 Biaya komunikasi tinggi karena jika ingin mengakses sebuah site bisa jadi harus menempuh banyak link. Misalnya, dari site A menuju site D, link yang dilewati sebanyak tiga buah. Ketersediaan pada topologi ring network lebih terjamin dibandingkan pada star network maupun pada tree-structured network.
Gambar 2.4. Ring Network Sumber: http://en.wikipedia.org/wiki/Image:NetworkTopologies.png Media Transmisi Data Media transmisi terbagi menjadi dua macam sebagai berikut.
Kabel (Wired) yang terdiri dari: Kabel pilin, yang dikenal dengan Unshielded Twisted Pair (UTP) dan Shielded Twisted Pair (STP)
Kabel Tembaga Kabel ini biasanya digunakan pada jaringan telepon.
Serat Optik (Fiber Optic) Kabel jenis ini mempunyai kecepatan pengiriman data sampai sepuluh kali lebih besar daripada kabel coax. Kabel serat optik dibuat dari serabut-serabut kaca (optical fibers) yang tipis dengan diameter sebesar diameter rambut manusia.
15
Kabel Coaxial Kabel coaxial merupakan kabel yang dibungkus dengan metal yang lunak dan mempunyai tingkat transmisi data yang lebih tinggi dibanding dengan kabel biasa tetapi harganya lebih mahal.
Media transmisi berupa kabel ini biasanya digunakan jika sumber data dan penerima data jaraknya tidak terlalu jauh atau masih di dalam area lokal.
Nirkabel (Wireless) yang terdiri dari:
Gelombang Mikro (Microwave) Sifat pemancaran dari gelombang mikro adalah line-of-sight, yaitu tidak boleh terhalang, misalnya karena ada gedung-gedung yang tinggi, bukit-bukit atau gunung-gunung. Gelombang mikro biasanya digunakan untuk jarak yang dekat-dekat saja. Untuk jarak yang jauh, harus digunakan stasiun relay yang berjarak 30 sampai 50 kilometer. Stasiun relay diperlukan karena untuk memperkuat sinyal yang diterima dari stasiun relay sebelumnya dan meneruskannya ke stasiun relay berikutnya.
Terrestrial Radio dan Terrestrial non-radio Terrestrial radio adalah gelombang yang mampu melakukan pengiriman sinyal melalui modulasi gelombang elektromagnetik. Gelombang ini melintas lewat udara dan maupun ruang hampa. Gelombang ini merambat sejajar dengan permukaan bumi. Sedangkan terrestrial non-radio adalah gelombang yang merambat sejajar dengan permukaan bumi namun tidak melalui udara.
16
Infrared (Infra merah) Infrared adalah gelombang cahaya infra merah yang dapat digunakan untuk proses transmisi data jarak yang relatif dekat.
Satelit Satelit adalah alat elektronik yang mengorbit bumi yang mampu bertahan sendiri dan gelombangnya merambat tidak sejajar/tidak dekat dengan permukaan bumi. Satelit diartikan sebagai repeater yang berfungsi untuk menerima sinyal gelombang microwave dari stasiun bumi, ditranslasikan frekeunsinya, kemudian diperkuat untuk dipancarkan kembali ke arah bumi sesuai dengan jangkauannya yang merupakan lokasi stasiun bumi tujuan atau penerima. Satelit berfungsi sebagai stasiun relay yang letaknya di luar angkasa. Satelit digunakan karena gelombang mikro tidak boleh terhalang maka untuk jarak yang jauh-jauh digunakan sistem satelit. Kategori satelit menurut bentuk orbit dan jaraknya, yaitu satelit LEO (Low Earth Orbit), satelit MEO (Medium Earth Orbit), dan satelit GEO (Geostationary Orbit). Dalam komunikasi GEO atau lebih dikenal dengan nama Geostationary Satellite (merupakan sistem komunikasi satelit yang paling banyak) posisi satelit adalah sekitar 36.000 km diatas bumi dan posisi satelit ini tidak berubah lokasinya, karena satelit ini mengikuti perputaran bumi, yang terjadi selama 24 jam.
Beberapa dari transmisi wireless ini digunakan untuk sumber data dan penerima data dengan jarak yang cukup jauh, salah satu contohnya adalah satelit.
17 Performance (Kinerja) Salah satu kebutuhan jaringan agar bisa berjalan dengan baik adalah kinerja/performance dari jaringan tersebut. Semakin tinggi kinerja jaringan dengan cost yang rendah menunjukkan bahwa semakin bagus jaringan tersebut. Kinerja jaringan diukur dalam dua kategori, yaitu:
Bandwidth/throughput (kapasitas kanal transmisi)
Latency/delay (waktu tunda)
Faktor-faktor lain yang perlu diperhatikan adalah sebagai berikut.
Naming and Name Resolution, yaitu bagaimana dua buah proses menempatkan/memposisikan satu sama lain dalam jaringan komunikasi.
Routing Strategies, yaitu bagaimana pesan dikirimkan melalui jaringan.
Packet Strategies, yaitu suatu strategi apakah paket dikirimkan secara individual atau sekuensial.
Connection Strategies, yaitu bagaimana dua proses mengirimkan pesan secara sekuensial.
Contention, yaitu bagaimana memecahkan masalah permintaan yang mengalami konflik.
A. Model Jaringan Ideal (Ideal Network Model) Menurut Aturan Lintasan/Jalur Jaringan (Network Path Principle) suatu jaringan yang ideal adalah jaringan yang mempunyai jalur/lintasan dengan bandwidth tinggi dan waktu tunda yang rendah (low-latency) diantara sistem.
18
Gambar 2.5. Model Jaringan Ideal Sumber: http://www.sterbenz.org/jpgs/tutorials/hsn/tut3-hsn-display.pdf
B. Bandwidth/Throughput (Kapasitas Kanal Transmisi) Bandwidth adalah jumlah bits data yang dapat ditransmisikan pada suatu jaringan dalam suatu periode waktu tertentu (Peterson and Davie, 2003, p40). Penentuan bandwidth berperan penting dalam menentukan kinerja suatu jaringan karena makin besar bandwidth yang digunakan makin mahal pula biaya yang dikeluarkan. Di dalam ruang lingkup digital, bandwidth adalah kemampuan maksimum dari suatu media untuk menyalurkan informasi/data dalam satuan waktu detik. Satuan yang digunakan adalah bits per second (bps), atau Bit per second (Bps), yang diartikan “dikirmkan sekian bit dalam setiap detiknya”. Bps berarti jumlah informasi yang terkirimkan dari suatu titik ke titik lainnya. Satuan lain yang digunakan adalah characters per second (cps), Kilobytes per second (Kbps), Megabytes per second (Mbps), Gigabytes per second (Gbps), dan seterusnya. Transmisi data dengan ukuran 1000 bps tidak dapat dikatakan lebih cepat dari transmisi data dengan ukuran 200 bps, tetapi dapat dikatakan bahwa lebih banyak data yang dapat dikirimkan pada satu unit waktu tertentu (detik/second). Misalkan, suatu jaringan yang mempunyai bandwidth 10 Mbps berarti dapat mengirimkan 10 juta bits data dalam setiap detik. Dalam suatu jaringan yang mempunyai 10 Mbps bandwidth, contohnya, membutuhkan waktu sekitar 0,1 microsecond ( s).
19 Bandwidth mempunyai tiga tipe berdasarkan arah transmisinya adalah sebagai berikut.
Transmisi satu arah (one way transmission) Tipe ini merupakan kanal transmisi yang hanya dapat membawa informasi data dalam bentuk satu arah saja, tidak bisa bolak balik. Siaran radio atau televisi merupakan contoh dari transmisi ini, yaitu sinyal yang dikirimkan dari stasiun pemancar hanya dapat diterima oleh pesawat penangkap siaran, tetapi pesawat penangkap siaran tidak dapat mengirimkan informasi balik ke stasiun pemancar.
Transmisi dua arah bergantian (two way transmission/half duplex) Two way transmission merupakan kanal transmisi di mana informasi data dapat mengalir dalam dua arah yang bergantian (satu arah dalam suatu saat tertentu), yaitu bila satu mengirimkan, yang lain sebagai penerima dan sebaliknya, tidak bisa serentak. Dengan transmisi dua arah bergantian maka dapat mengirim dan menerima data. Walkie talkie merupakan contoh dari transmisi dua arah bergantian, yaitu dapat mendengarkan atau berbicara secara bergantian.
Transmisi dua arah serentak (both-way transmission/full duplex) Both-way transmission merupakan kanal transmisi di mana informasi data dapat mengalir dalam dua arah secara serentak (dapat mengirim dan menerima data pada saat bersamaan). Komunikasi lewat telepon merupakan contoh dari transmisi dua arah serentak, yaitu dapat berbicara sekaligus mendengarkan apa yang sedang diucapkan oleh lawan bicara.
20 C. Latency/Delay (Waktu Tunda) Latency atau delay adalah lama waktu yang diperlukan untuk mengirimkan message dari satu ujung (end) ke ujung lainnya di dalam suatu jaringan (Peterson and Davie, 2003, p41). Latency mempunyai satuan ukuran berupa satuan waktu. Misalkan, suatu jaringan antar-benua (transcontinental) mempunyai latency/waktu tunda sebesar 24 miliseconds (ms), berarti sebuah message memerlukan waktu sebesar 24 ms untuk sampai ke ujung (end) Amerika Utara ke benua lainnya. Ada banyak situasi untuk mengetahui berapa lama mengirim suatu message dari satu ujung (end) jaringan ke ujung lainnya dan sebaliknya, daripada waktu tunda satu arah (one way latency). Bentuk pengukuran latency yang lain itu adalah Round-Trip Time (RTT). Round-Trip Time adalah waktu yg diperlukan suatu message utk mencapai tujuannya dan kembali ke pengirim/bolak balik (two ways). Latency tidak hanya tergantung pada topologi saja, tapi juga pada proses routing, flow control, dan juga desain dari routernya.
2.1.5
Langkah-langkah Mengoptimasi Jaringan Berikut beberapa langkah dalam mengoptimasi jaringan terbuka yang berbentuk
graph menjadi sebuah jaringan tertutup berbentuk graph.
Menentukan besar jarak antara satu node/site ke semua site lainnya berdasarkan keterangan koordinat site yang nantinya akan dijadikan acuan bagi penentuan besar Diameter dan menentukan waktu tunda jaringan (Network Latency).
Prinsip Waktu Tunda Jaringan (Network Latency Principle) Menurut Network Latency Principle (Sterbenz.org, 2006), waktu tunda suatu
jaringan utuh adalah jumlah dari semua waktu tunda dari setiap jalur/edge/path yang menghubungkan antar site/node. Keuntungan dari mengoptimalkan sebuah sambungan
21 (link) individu berkontribusi langsung dengan waktu tunda dari satu ujung ke ujung lainnya (end-to-end latency).
Gambar 2.6. Jalur Jaringan Menurut Waktu Tunda (Latency) Sumber: http://www.sterbenz.org/jpgs/tutorials/hsn/tut3-hsn-display.pdf
Topologi dan Geografi Waktu Tunda Jaringan Rumus unsur pokok dari waktu tunda jaringan (Network Latency). D = (h-1)ds + ∑hdi (2.1)
Keterangan: di = waktu tunda setiap path D = waktu tunda dari node asal ke node tujuan di dalam satu jaringan h = banyaknya hops antara node asal dengan node tujuan ds = switching delay = 1 ms (milisecond) Rumus waktu tunda jaringan ini dipengaruhi oleh faktor geografis dan topologi dari jaringan tersebut. Unsur geografisnya terletak pada waktu tunda (latency) berdasarkan kecepatan cahaya (di). Unsur topologinya dapat terlihat dari banyaknya hops dan switching delay (ds) jaringan tersebut. Waktu tunda jaringan bergantung pada besar jarak antara node sumber dengan node yang ingin dicapai atau lebih dikenal dengan nama diameter dan juga bergantung pada Round-Trip Time (RTT) dari suatu node/site asal menuju node tujuan. RTT adalah latency (di) yang sudah dihitung dengan kecepatan cahaya, sehingga besar di pada rumus sama dengan besar RTT pada tabel.
22 Dengan mengikuti Prinsip Diameter Jaringan (Network Diameter Principle) (Sterbenz.org, 2006), yaitu banyaknya loncatan-loncatan (hops) dari semua waktu tunda di semua path jaringan diatur oleh diameter dari jaringan tersebut. Maka untuk menentukan besarnya RTT, diperlukan data jarak antara site/node asal menuju site/node tujuan karena data jarak menunjukkan besarnya diameter jika dilihat melalui tabel. Switching delay ditentukan sebesar 1 ms oleh perusahaan dikarenakan jumlahnya yang sangat kecil. Suatu topologi jaringan harus dapat mempertahankan agar diameter tetap kecil. Sedangkan hops menunjukkan berapa banyak loncatan antara node asal dengan node tujuan yang diinginkan. Berikut tabel petunjuk hubungan antara besar Diameter (DIA) dan RTT (RoundTrip Time) yang akan menjadi pedoman dalam mencari besar waktu tunda antar site (D).
Gambar 2.7. Tabel Petunjuk Hubungan Diameter dengan RTT Sumber: http://www.sterbenz.org/jpgs/tutorials/hsn/tut3-hsn-display.pdf
Prinsip Hirarki Jaringan (Network Hierarchy Principle) Menurut Network Hierarchy Principle (sterbenz.org, 2006), penggunaan prinsip
hirarki dan pengelompokan untuk mengatur skala jaringan (network scale) dan kompleksitasnya, dan untuk mengurangi kelebihan pemakaian algoritma. Teknik hirarki ini merupakan teknik suatu teknik yang penting untuk mengontrol latency (waktu tunda) diameter jaringan dan penyatuan dan pengelompokan berdasarkan skala/tipenya. Teknik ini membagi jaringan menjadi kelompok-kelompok (clusters) berdasarkan syarat-syarat yang sudah ditentukan.
23
Gambar 2.8. Struktur Hirarki Menurut Skala Jaringan Sumber: http://www.sterbenz.org/jpgs/tutorials/hsn/tut3-hsn-display.pdf Aggregation, Isolation, Latency (Penyatuan, Pemisahan, Waktu Tunda) Teknik ini digunakan untuk meng-isolasi bandwidth di lapisan subnet yang berbeda dan juga untuk mengontrol diameter jaringan beserta waktu tundanya (latency).
Teknik hirarki untuk menyatukan (aggregate) dan memisahkan (isolation) bandwidth digunakan untuk mengatur penyatuan bandwidth di dalam inti jaringan, dan untuk memisahkannya menjadi
kelompok-kelompok
berdasarkan kepadatan lalu lintas (traffic) data lokal dari satu ke yang lainnya.
Teknik Hirarki untuk meminimisasi waktu tunda (latency) digunakan bersamaan dengan pengelompokan berdasarkan ukuran tertentu (cluster size) untuk memperkecil diameter jaringan dan akibat waktu tunda.
Gambar 2.9. Aggregation, Isolation, dan Latency Sumber: http://www.sterbenz.org/jpgs/tutorials/hsn/tut3-hsn-display.pdf
24 2.2
Teori Graph
2.2.1 Definisi Graph Graph merupakan struktur data yang paling umum. Jika struktur linear memungkinkan pendefinisian keterhubungan sekuensial antara entitas data, struktur data tree memungkinkan pendefinisian hirarkis, maka struktur graph memungkinkan pendefinisian keterhubungan tak terbatas antara entitas data. Definisi Graph (Munir, 2007, p356) adalah G = (V,E) dalam hal ini adalah suatu pasangan himpunan tak kosong dari simpul-simpul atau vertex-vertex V = {v1,v2,v3,...,vn} dan himpunan sisi atau edge E = {e1,e2,e3,...} yang digambarkan sebagai garis yang menghubungkan sepasang simpul/vertex.
Gambar 2.10. Contoh Graph Sumber: Munir, 2007, p356 G adalah graph dengan vertex-vertex V = {1, 2, 3, 4} dan kumpulan edge-edge E = {(1,2), (2,3), (1,3), (1,3), (2,4), (3,4), (3,4)} = {e1,e2,e3,e4,e5,e6,e7} Menurut Munir (2007, p357), graph dapat dikelompokkan menjadi beberapa kategori.
25 Berdasarkan ada tidaknya loop/sisi ganda pada graph:
Graph sederhana (Simple Graph), adalah sebuah graph yang tidak memiliki edge ganda (dalam satu pasangan vertex terdapat dua edge).
Graph ganda (Multigraph), adalah graph yang memiliki bisa lebih dari satu buah edge diantara sepasang vertex.
Graph semu (Pseudograph), adalah suatu graph yang mengandung loop (baik satu atau lebih) dan lebih dari satu buah edge (graph ganda) di antara sepasang vertex. Graph semu lebih umum daripada graph ganda, karena sisi/edge pada graph semu dapat terhubung ke dirinya sendiri.
Berdasarkan orientasi arah pada sisi/edge pada graph:
Graph tak berarah (Undirected Graph), adalah suatu graph yang memiliki edge/sisi yang tidak mempunyai orientasi arah. Urutan pasangan vertex yang dihubungkan oleh edge tidak diperhatikan.
Gambar 2.11. Contoh Undirected Graph Sumber: Munir, 2007,p 356
Graph berarah (Directed Graph/Digraph), adalah sebuah graph yang setiap sisi/edge-nya diberikan orientasi arah.
26
Gambar 2.12. Contoh Directed Graph Sumber: www.informatika.org/~rinaldi/Matdis/20062007/Makalah/Makalah0607-63.pdf Beberapa graph sederhana khusus, diantaranya:
Null Graph, adalah sebuah graph yang tidak memiliki edge atau himpunan sisinya merupakan himpunan kosong.
Complete graph, adalah graph sederhana yang setiap vertex-nya mempunyai edge ke semua vertex lainnya.
2.2.2 Terminologi Dasar Berikut beberapa terminologi dasar dari sebuah graph (Munir, 2007, p364).
Bertetangga (Adjacent) Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.
Bersisian (Incident) Untuk sembarang edge e = (u, v), edge e dikatakan bersisian dengan vertex u dan vertex v.
Derajat (Degree) Derajat suatu vertex adalah jumlah edge yang bersisian dengan edge tersebut. Notasinya adalah d(v). Pada graph berarah, derajat vertex dinyatakan dengan din(v) dan dout(v), yang dalam hal ini din(v) adalah derajat
27 masuk, yaitu jumlah busur yang masuk ke vertex v dan dout(v) adalah derajat keluar, yaitu jumlah busur yang keluar dari vertex v.
Lintasan (Path) Lintasan yang panjangnya n dari vertex awal v0 ke vertex tujuan vn di dalam sebuah graph adalah barisan berselang-seling edge-edge dan lintasan yang terbentuk adalah v0, e1, v1, e2, v2,....dan seterusnya.
Sirkuit (Circuit) Lintasan yang berawal dan berakhir di tempat (vertex) yang sama disebut sirkuit.
Graph berbobot (Weighted Graph) Weighted graph adalah graph yang setiap edge-nya diberi sebuah harga (bobot). Bobot pada tiap edge dapat berbeda-beda tergantung pada masalah yang dimodelkan. Bobot dapat menyatakan jarak antara dua buah kota, biaya perjalanan antara dua kota, waktu tempuh pesan (message) dari sebuah node/vertex komunikasi ke node/vertex komunikasi lain (dalam jaringan komputer).
Gambar 2.13. Directed Weighted Graph Sumber: www.acm.org
28 2.2.3 Representasi Graph Bila graph akan diproses dengan program komputer, maka graph harus direpresentasikan di dalam memori. Terdapat beberapa representasi yang mungkin untuk graph, tapi di sini hanya diberikan dua macam representasi yang sering digunakan, yaitu matriks incidence dan matriks adjacency. Matriks Bersisian (Incidence matrix) Matriks incidence menyatakan hubungan antara vertex dan edge. Misalkan G = (V,E) adalah graph dengan n vertex dan m buah edge. Matriks incidence G adalah matriks dwimatra berukuran n x m. Baris menunjukkan label vertex, sedangkan kolom menunjukkan label edge-nya. Bila matriks tersebut dinamakan A = [aij], maka aij = 1 jika vertex i bersisian/incidence dengan edge j, sebaliknya aij = 0 jika vertex i tidak bersisian dengan edge j. Matriks bersisian dapat digunakan untuk merepresentasikan graph yang mengandung edge ganda/gelang.
Gambar 2.14. Contoh Undirected Graph Sumber: www.hotlinkfiles.com/files/333140_d3mwg/Graph Theory Lecture Note Part1.pdf
Apabila graph pada Gambar 2.14. direpresentasikan dalam matriks incidence maka akan didapat suatu bentuk matriks incidence seperti yang terdapat pada Gambar 2.15.
29 v1 v2 v3 v4 v5 v6
A = [aij] =
v1
0 1010 0
v2
1 0011 1
v3
0 0010 0
v4
1 1101 0
v5
0 1010 0
v6
0 1000 0
Gambar 2.15. Matriks Incidence Matriks incidence seperti yang terdapat pada Gambar 2.15 tersebut dapat memudahkan penghitungan derajat dari setiap vertex. Vertex berderajat n berarti pada vertex tersebut terdapat n buah edge yang menghubungkannya dengan vertex yang lain. Pada matriks incidence tersebut apabila bernilai 1 maka vertex ke-i berhubungan dengan edge ke-j. Matriks Ketetanggaan (Adjacency Matrix) Matriks adjacency adalah representasi graph yang paling umum. Matriks adjacency adalah matriks yang menyatakan ada tidaknya edge yang menghubungkan antara vertex yang satu (vertex asal) dengan vertex yang lain (vertex tujuan). Misalkan G = (V,E) adalah graph dengan n vertex, n ≥ 1. Matriks adjacency G adalah matriks dwimatra berukuran n x n. Bila matriks tersebut dinamakan A = [aij], maka aij = 1 jika vertex i dan j bertetangga, sebaliknya aij = 0 jika vertex i dan j tidak bertetangga. Dengan kata lain, yaitu apabila terdapat edge yang menghubungkan antara vertex asal dan vertex tujuan maka matriks tersebut akan diisi nilai 1 dan sebaliknya apabila tidak terdapat edge yang menghubungkan vertex asal dan vertex tujuan maka matriks akan diisi nilai 0. Dalam sebuah directed graph atau graph yang memiliki arah, baris pada matriks
30 adjacency dinyatakan sebagai vertex asal dan kolomnya dinyatakan sebagai vertex tujuan.
Gambar 2.16. Contoh Directed Graph Sumber: Widharto, 2005, petra.ac.id Apabila graph berarah seperti yang terdapat pada Gambar 2.16 direpresentasikan dalam matriks adjacency maka matriks yang terbentuk adalah seperti yang terlihat pada Gambar 2.17.
Gambar 2.17. Matriks Adjacency Sumber: Widharto, 2005, petra.ac.id Dengan menggunakan matriks adjacency seperti yang terdapat pada Gambar 2.17 dapat diketahui vertex mana saja yang berhubungan dengan vertex asal. Selain itu matriks adjacency tersebut dapat dikembangkan sehingga bukan hanya menyimpan kondisi apakah ada edge yang menghubungkan atau tidak (1 atau 0), tetapi juga dapat menyimpan berapa panjang/weight edge dari vertex asal ke vertex tujuan atau menyimpan berbagai informasi lainnya.
31 2.2.4 Pencarian Shortest Path (Lintasan Terpendek) Persoalan mencari lintasan terpendek di dalam graph merupakan salah satu persoalan optimasi. Graph yang digunakan dalam pencarian lintasan terpendek adalah graph berbobot (weighted graph), yaitu graph yang setiap sisi/edge-nya diberikan suatu nilai/bobot. Bobot pada edge/sisi graph dapat menyatakan jarak antar kota, waktu pengiriman pesan, ongkos pembangunan, dan sebagainya. Asumsi yang digunakan di sini adalah bahwa semua bobot bernilai positif. Kata “terpendek” jangan selalu diartikan secara fisik sebagai panjang minimum, sebab kata “terpendek” berbeda-beda maknanya tergantung pada tipikal persoalan yang akan diselesaikan. Namun, secara umum “terpendek” berarti meminimisasi bobot pada suatu lintasan di dalam graph. Ada beberapa macam persoalan lintasan terpendek, antara lain.
Lintasan terpendek antara dua buah node/simpul/vertex tertentu (a pair shortest path).
Lintasan terpendek antara semua pasangan vertex (all pairs shortest path). Persoalan ini biasanya memakai algoritma Floyd-Warshall dan metode Transitive Closure sebagai solusi pemecahan masalah.
Lintasan terpendek dari vertex tertentu ke semua vertex yang lain (singlesource shortest path). Persoalan ini biasanya memakai algoritma Djikstra sebagai solusi pemecahan masalah.
Lintasan terpendek antara dua buah vertex yang melalui beberapa vertex tertentu (intermediate shortest path).
Dalam skripsi ini permasalahan yang dihadapi akan dicoba diselesaikan dengan metode transitive closure.
32 2.3
Metode Transitive Closure Permasalahan yang tengah dihadapi perusahaan mengenai traffic data pada
jaringan WAN pada area West Java sampai dengan West Papua adalah bagaimana agar lintasan lalu lintas data yang sudah ada sekarang ini menjadi lebih optimal baik dari segi cost/biaya yang dikeluarkan maupun waktu tunda/delay/latency pada saat mengirim maupun menerima paket data. Metode ini memenuhi syarat sebagai salah satu solusi pemecahan masalah karena inti dari metode ini adalah mencari tahu apakah terdapat lintasan (path) antar semua pasangan vertex-vertex. Karena metode ini merupakan bagian dari all pairs shortest path maka secara otomatis metode ini juga akan mencari lintasan terpendek di antara semua pasangan vertex, sehingga semua kemungkinan lintasan diantara semua node/vertex/site dapat dicari. Berikut akan dijelaskan diuraikan konsep dari metode transitive closure pada unweighted digraph (digraph tanpa bobot) dan juga pada weighted digraph, di mana setiap edge-nya mempunyai nilai/bobot.
2.3.1 Transitive Closure pada Unweighted Digraph Sebuah
directed
graph
(digraph)
dapat
merepresentasikan
semua
hubungan/connections dari semua kemungkinan site/wilayah, di mana vertex dan edge mewakili site dan lintasannya. Arah-arah lintasan diwakili oleh arah-arah yang terdapat pada edge-edge yang ada. Kenudian digunakan matriks adjacency sebagai representasi digraph yang dimaksud.
33
x2
x1
x4
x3
Gambar 2.18. Contoh Unweighted Directed Graph Sumber: www.petra.ac.id/~puslit/journals/request.php?PublishedID=INF05060207 Seperti yang sudah dijelaskan diatas, G adalah sebuah graph berarah (directed graph). Lalu disusun sebuah matriks B dimana baris dan kolom dari matriks melambangkan vertex-vertex pada graph secara berurutan. Nilai awal di baris ke-i dan kolom ke-j pada matriks B, yang dilambangkan dengan bij, bernilai 1 jika mempunyai sebuah edge (edge berarah) dari vertex ke-i menuju vertex ke-j dan bernilai 0 jika sebaliknya. Matriks B disebut matriks adjacency dari graph G. G sebagai directed graph terlihat pada Gambar 2.18 dan matriks adjacency dari G terlihat pada Gambar 2.19. Graph tersebut mempunyai 4 vertex (x1, x2, x3 dan x4) dan 5 edge berarah yang menghubungkan x1 ke x2, x1 ke x3, x1 ke x4, x3 ke x4 dan x4 ke x3.
x1 x2 x3 x4
x1 x 2 0 1 0 0 0 0 0 0
x3 x4 1 1 0 0 0 1 1 0
Gambar 2.19. Matriks Adjacency Graph G Sumber: www.petra.ac.id/~puslit/journals/request.php?PublishedID=INF05060207 Pada sebagian besar kasus seperti ini, label pada vertex tidak begitu penting. Misalkan matriks ditulis tanpa menggunakan label, maka representasi matriks pada Gambar 2.20 dapat direpresentasikan seperti gambar di bawah ini.
34 B
0 0 0 0
1 1 1 0 0 0 0 0 1 0 1 0
Gambar 2.20. Matriks Adjacency tanpa label Sumber: www.petra.ac.id/~puslit/journals/request.php?PublishedID=INF05060207 Misalkan terdapat n vertex, maka B2 dapat diperoleh dari operasi perhitungan berikut ini. B2 B B b11 b1n b11 b1n bn1 bnn bn1 bnn b112 b12n bn21 bnn2 n
Di mana b ij2 sup{min(bik , bkj )}. k 1
Operasi perhitungan ini dilakukan secara rekursif/ berulang-ulang sampai menghasilkan suatu rumus:
Bus Bu Bs untuk u , s {1,, n 2}, dan 2 u s n 1. (2.2) Sebagai contoh, diberikan matriks B sebagai matriks adjacency seperti yang sudah terlihat pada Gambar 2.20. B2 dapat dihitung dan memperoleh hasil dengan cara mengoperasikan matriks B dengan matriks B itu sendiri, seperti yang ditunjukkan oleh operasi perhitungan berikut ini.
35 B2 B B
0
0
0 0 0 0 0 0
1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0 1
0 0 0 0
1 1 1 0 0 0 0 0 1 0 1 0
Contoh perhitungan untuk mencari nilai dari matriks B derajat 2 pada baris 1 kolom 3: b132 sup{min( b11 , b13 ), min( b12 , b 23 ), min( b13 , b33 ), min( b14 , b 43 )} sup{min( 0,1), min(1,0), min(1,0), min(1,1)} sup{0,0,0, 1} 1
Perhatikan nilai b132 adalah 1 karena b14 dan b43 sama-sama bernilai 1, yang berarti bahwa ada sebuah edge yang menghubungkan vertex x1 ke vertex x4 dan dari vertex x4 ke vertex x3. Selanjutnya, terdapat 2 lintasan dari vertex x1 ke vertex x3. Jelasnya dapat terlihat bahwa bij2 1 jika dan hanya jika terdapat k sehingga min( bik , bkj ) 1 , atau dengan kata lain, terdapat sebuah edge dari vertex xi ke vertex xk dan dari vertex xk ke vertex xj. Perhitungan yang sama dilakukan untuk mendapatkan b242 , yaitu b242 sup{min(b21 , b14 ), min(b22 , b24 ), min(b23 , b34 ), min(b24 , b44 )} sup{min(0,1), min(0,0), min(0,1), min(0,0)} sup{0,0,0,0} 0
Jadi, b242 = 0 karena tidak ada edge dari vertex x2 ke vertex xk dan dari vertex xk ke vertex x4 untuk semua k. Dengan kata lain tidak ada 2 lintasan dari vertex x2 ke vertex x4..
36 Dapat disimpulkan bahwa bij2 =1 jika ada dua lintasan dari vertex xi ke vertex xj dan bij2 =0 jika tidak ada 2 lintasan dari vertex xi ke vertex xj. Suatu lintasan k dari vertex xi ke vertex xj untuk 1 k n dapat dibuktikan jika dan hanya jika
bijk =1. Transitive Closure dari matriks adjacency B dinyatakan sebagai
berikut.
b11T b1Tn BT T bnT1 bnn n 1
Di mana b Tij sup {b ijk }. k 1
(2.3) Adapun, b Tij 1 jika dan hanya jika terdapat paling sedikit satu lintasan dari vertex xi ke vertex xj. Sebagai contoh, relasi Transitive Closure untuk matriks adjacency B seperti yang terlihat pada gambar di bawah ini.
BT
0 0 0 0
1 1 1 0 0 0 0 1 1 0 1 1
Gambar 2.21 Transitive Closure untuk Matriks B Sumber: www.petra.ac.id/~puslit/journals/request.php?PublishedID=INF05060207 Sebagai contoh untuk mencari nilai baris 3 kolom 3 pada matriks Transitive Closure, yaitu: T 3 b33 sup{b33 , b332 , b33 } sup{0,1,0} 1 .
37 2.3.2 Transitive Closure Pada Weighted Digraph Salah satu penerapan metode transitive closure pada weighted digraph adalah untuk mencari lintasan terpendek dari site yang satu ke site yang lain dimana setiap edge mempunyai nilai/bobot dan juga mempunyai arah. Transitive closure menggunakan matriks adjacency untuk mencari ada tidaknya lintasan dari site yang satu ke site yang lain.
Matriks adjacency bernilai derajat satu untuk menyatakan ada tidaknya
penghubung dari site satu ke site lain dengan hanya melewati satu buah lintasan. Matriks adjacency derajat dua digunakan untuk menyatakan ada tidaknya penghubung dari site satu ke site lain dengan melewati dua buah lintasan dan seterusnya. Jika banyak vertex dinyatakan dengan n, maka jumlah total derajat matriks yang harus dicari adalah n-1 atau sejumlah daerah yang ada dikurangi satu. Setiap matriks adjacency pada transitive closure murni dapat berisi panjang lintasan, ongkos pengiriman, besar bandwidth (dalam hal jaringan komputer) dari suatu site ke site yang lain. Contoh perhitungan pencarian jalur terpendek dengan menggunakan metode transitive closure murni dimana pada setiap lintasan mempunyai arah dan bobot (sebagai contoh, bobot adalah panjang jalan dan dinyatakan dalam satuan km) adalah seperti yang terdapat pada Gambar 2.22.
Gambar 2.22. Graph berarah dengan bobot tertentu Sumber: Widharto, 2005, petra.ac.id
38 Dari graph yang terdapat pada Gambar 2.22 tersebut dapat disusun matriks adjacency derajat satu. Matriks derajat satu adalah matriks yang menyimpan informasi apakah terdapat lintasan yang menghubungkan antara site yang satu dengan site yang lain hanya dengan melewati satu buah lintasan. Apabila terdapat lintasan dari vertex A ke vertex B maka pada matriks tersebut ditulis bobot lintasan A-B (dalam hal ini adalah panjang jalan dari site A ke site B). Hal ini seperti yang terdapat pada Gambar 2.22. Semua panjang jalur yang terdapat pada Gambar 2.22 direpresentasikan dalam bentuk matriks adjacency derajat satu. Matriks adjacency derajat satu yang dibentuk dari graph tersebut dapat terlihat pada Gambar 2.23.
Gambar 2.23. Matriks Adjacency derajat satu Sumber: Widharto, 2005, petra.ac.id Setelah matriks derajat satu selesai dibuat, dilakukan proses pembuatan matriks derajat dua. Matriks derajat dua diperoleh dari proses antara matriks derajat satu dengan matriks derajat satu. Hal ini seperti yang terdapat pada Gambar 2.24
Gambar 2.24 Proses Matriks Derajat Satu dengan Matriks Derajat Satu Lainnya Sumber: Widharto, 2005, petra.ac.id
39 Langkah-langkah proses pembuatan matriks derajat dua adalah seperti yang terdapat pada Gambar 2.25 dan Gambar 2.26. Langkah pertama pada Gambar 2.25 adalah membandingkan baris pertama matriks derajat satu dengan kolom pertama matriks derajat satu lainnya. Nilai yang akan dihasilkan disimpan pada matriks derajat dua pada baris ke 1 dan kolom ke 1.
Gambar 2.25 Proses I Matriks Derajat Satu dengan Matriks Derajat Satu Lainnya Sumber: Widharto, 2005, petra.ac.id
Gambar 2.26 Proses II Matriks Derajat Satu dengan Matriks Derajat Satu Lainnya Sumber: Widharto, 2005, petra.ac.id Sedangkan hasil dari Gambar 2.26 dimana dilakukan proses antara baris ke satu matriks derajat satu dengan kolom ke dua matriks derajat satu lainnya disimpan pada matriks derajat dua pada posisi baris ke satu dan kolom ke dua. Semua isi matriks pada Gambar 2.24 tersebut diproses seperti yang terdapat pada Gambar 2.25 dan Gambar 2.26 tersebut.
40 Proses penghitungan matriks derajat dua untuk baris-baris dan kolom-kolom yang lain terdapat pada Gambar 2.27.1, 2.27.2, 2.27.3 dan 2.27.4. Pada penghitungan tersebut, dikatakan ada lintasan dari A ke B, apabila terdapat lintasan dari vertex/node A ke vertex yang lain dan dari vertex yang lain tersebut ke vertex B. Jadi pada proses penghitungan tersebut harus terdapat lintasan pada kedua belah pihak (baris ke n dan kolom ke m) untuk dapat mengatakan bahwa ditemukan sebuah lintasan dari A ke B yang melalui dua buah lintasan.
Gambar 2.27.1 Proses Penghitungan Matriks Derajat Dua Sumber: Widharto, 2005, petra.ac.id
41
Gambar 2.27.2 Proses Penghitungan Matriks Derajat Dua (lanjutan 2) Sumber: Widharto, 2005, petra.ac.id
Gambar 2.27.3 Proses Penghitungan Matriks Derajat Dua (lanjutan 1) Sumber: Widharto, 2005, petra.ac.id
42
Gambar 2.27.4 Proses Penghitungan Matriks Derajat Dua (lanjutan 3) Sumber: Widharto, 2005, petra.ac.id
Gambar 2.28 Hasil Matriks Derajat Dua Sumber: Widharto, 2005, petra.ac.id Hasil matriks derajat dua yang dibentuk dari operasi antara matriks derajat satu dengan matriks derajat satu lainnya adalah seperti yang terdapat pada Gambar 2.28. Matriks yang perlu dibentuk adalah matriks derajat satu hingga matriks derajat ke (n-1), di mana n adalah jumlah vertex/node/site yang terdapat pada peta. Oleh karena itu graph yang terdapat pada Gambar 2.22 perlu untuk digenerate mulai dari matriks derajat satu hingga matriks derajat ke lima. Perhitungan selanjutnya adalah menghitung matriks derajat tiga, yaitu matriks yang diperoleh dari proses antara matriks derajat dua dengan matriks derajat satu. Hal ini seperti yang terdapat pada Gambar 2.29
43
Gambar 2.29 Proses Matriks Derajat Tiga Sumber: Widharto, 2005, petra.ac.id Dari proses tersebut akan diperoleh matriks derajat tiga seperti yang terdapat pada Gambar 2.30 Matriks derajat tiga tersebut diproses lebih lanjut dengan matriks derajat satu untuk memperoleh matriks derajat empat. Proses ini seperti yang terdapat pada Gambar 2.31. Hasil dari proses tersebut terdapat pada Gambar 2.32.
Gambar 2.30 Hasil Matriks Derajat Tiga Sumber: Widharto, 2005, petra.ac.id
Gambar 2.31 Proses Matriks Derajat Empat Sumber: Widharto, 2005, petra.ac.id
44
Gambar 2.32 Hasil Matriks Derajat Empat Sumber: Widharto, 2005, petra.ac.id Setelah matriks derajat empat selesai dibuat, maka perlu juga disusun matriks derajat lima. Matriks derajat lima adalah matriks terakhir yang perlu dibuat. Hal ini sesuai dengan ketentuan bahwa matriks dibuat dari derajat satu hingga derajat ke (n-1) di mana dalam hal ini adalah matriks derajat satu hingga matriks derajat lima. Proses pembentukan matriks derajat lima dimana dilakukan dengan cara mengoperasikan matriks derajat empat dengan matriks derajat satu. Proses ini seperti yang terdapat pada Gambar 2.33. Sedangkan hasil dari matriks derajat lima terdapat pada Gambar 2.34.
Gambar 2.33 Proses Matriks Derajat Lima Sumber: Widharto, 2005, petra.ac.id
45
Gambar 2.34 Hasil Matriks Derajat Lima Sumber: Widharto, 2005, petra.ac.id Apabila ingin mengetahui lintasan terdekat dari site A ke site D, maka semua matriks yang ada dari matriks derajat satu hingga derajat lima tersebut dievaluasi untuk mendapatkan matriks transitive closure dimana merupakan hasil tersingkat dari semua matriks yang telah dibentuk. Seperti yang terdapat pada Gambar 2.35 pada matriks derajat satu dan derajat dua, tidak terdapat lintasan dari site A ke site D. Pada matriks derajat tiga, dapat diketahui bahwa site D dapat dicapai dari site A dengan melalui tiga buah lintasan dengan jarak total sebesar 20 (dalam km). Pada matriks derajat empat, terdapat jarak tersingkat dari site A ke site D sebesar 17 km. Sedangkan tidak terdapat lintasan dari site A ke site D yang melalui lima buah lintasan seperti yang terdapat pada matriks derajat lima. Dari semua matriks tersebut dapat ditentukan bahwa matriks transitve closure atau lintasan yang paling singkat adalah melalui 4 buah lintasan dengan jarak tempuh sepanjang 17 km. Hal ini seperti yang terdapat pada Tabel 2.1. Dari contoh perhitungan tersebut telah dapat dibuktikan bahwa metode transitive closure dapat digunakan untuk mencari jalur yang paling singkat.
46
Gambar 2.35 Matriks Derajat Satu Hingga Matriks Derajat Lima Sumber: Widharto, 2005, petra.ac.id Tabel 2.1 Hasil perhitungan matriks transitive closure Sumber: Widharto, 2005, petra.ac.id Derajat Matriks 1 2 3 4 5
Jarak Tersingkat Tidak terdapat jalur Tidak terdapat jalur 20 km 17 km Tidak terdapat jalur
M* = min (-, -, 20, 17,-) M* = 17 Kesimpulan dari perhitungan diatas adalah jarak minimum dari site A ke site D sebesar 17 km dengan melalui 4 buah lintasan, dikarenakan jarak minimum terdapat pada matriks derajat 4. Lintasan yang dilalui adalah lintasan A-B-C-E-D.
47 2.4.
Entity Relationship Diagram (ERD) Entity Relationship Diagram (ERD) adalah diagram yang dipakai untuk
mendokumentasikan data dengan mengidentifikasikan jenis entitas dan hubungannya. ERD merupakan peralatan pembuatan model data yang paling fleksibel dan dapat diadaptasi untuk berbagai pendekatan yang mungkin diikuti perusahaan dalam pengembangan sistem. ERD ini menggambarkan relasi atau hubungan antar entitas yang ada, dimana terdapat 2 jenis hubungan.
Obligatory: bila semua anggota dari suatu entitas harus berpartisipasi atau memiliki hubungan dengan entitas yang lain.
Non-obligatory: bila tidak semua anggota dari suatu entitas harus berpartisipasi atau memiliki hubungan dengan entitas yang lain.
Dalam menggambar ERD, ada beberapa komponen yang perlu diperhatikan, yaitu:
Entity/Entitas Entity
Gambar 2.36 Entity/Entitas Sumber: Widharto, 2005, petra.ac.id Entitas didefinisikan sebagai sesuatu yang mudah diidentifikasikan. Sebuah entitas dapat berupa obyek, tempat, orang, konsep atau aktivitas. Pada teknik penggambaran, entitas digambarkan dengan kotak segiempat. Setiap kotak diberi label berupa kata benda. Simbol entitas dapat dilihat pada Gambar 2.36.
48
Atribut Identifikasi dan deskripsi dari suatu entitas dijelaskan oleh atribut-atributnya (karakteristik entitas). Sebuah atribut didefinisikan sebagai penjelasan penjelasan dari entitas yang membedakannya dengan entitas yang lain. Selain itu, atribut juga merupakan sifat-sifat dari sebuah entitas. Sebagai contoh, entitas Proficiency mempunyai atribut IDProficiency, Name, dan atribut lainnya. Contoh atribut dapat dilihat pada Gambar 2.37
Proficiency IDProficiency Name Date Time
Gambar 2.37 Atribut Sumber: Widharto, 2005, petra.ac.id
Relasi Relasi adalah penghubung antara suatu entitas dengan entitas yang lain dan merupakan bagian yang sangat penting dalam mendesain database. Simbol relasi dapat dilihat pada Gambar 2.38
Gambar 2.38 Relasi Sumber: Widharto, 2005, petra.ac.id Ada tiga macam relasi sebagai berikut.
One-to-One Pada bentuk relasi one-to-one, satu anggota entitas memiliki hubungan dengan satu anggota entitas pada kelas yang berbeda. Simbol relasi one-toone dapat dilihat pada Gambar 2.39.
49
Gambar 2.39 Relasi One to One Sumber: Widharto, 2005, petra.ac.id •
One-to-Many Pada bentuk relasi one-to-many, satu anggota entitas bisa memiliki hubungan dengan beberapa anggota entitas pada kelas yang berbeda. Sama halnya dengan one-to-one, pada relasi yang satu ini juga terbagi ke dalam dua jenis hubungan, yaitu: obligatory dan non-obligatory. Simbol relasi one-to-many dapat dilihat pada Gambar 2.40.
Gambar 2.40 Relasi One-to-Many Sumber: Widharto, 2005, petra.ac.id •
Many-to-Many Pada bentuk relasi many-to-many, beberapa anggota entitas dapat memiliki hubungan dengan beberapa anggota entitas lainnya. Dalam relasi ini juga terdapat dua jenis hubungan, yaitu: obligatory dan non-obligatory. Simbol relasi many-to-many dapat dilihat pada Gambar 2.41
50
Gambar 2.41 Relasi Many-to-Many Sumber: Widharto, 2005, petra.ac.id Sebagai contoh, hubungan antara dosen dengan mata kuliah yang diajarkannya. Bentuk diagram dari hubungan tersebut dapat dilihat pada Gambar 2.42.
Gambar 2.42 Contoh ERD Sumber: Widharto, 2005, petra.ac.id Pada Gambar 2.42 Dosen dan Mata Kuliah merupakan entitas. Sedangkan Mengajar merupakan relasi antara Dosen dan Mata Kuliah. Dari contoh ini dapat terjadi beberapa relasi dengan kondisi-kondisi tertentu sebagai berikut. •
Seorang dosen hanya dapat mengajar satu mata kuliah dan satu mata kuliah hanya dapat diajar oleh seorang dosen saja. Relasi dengan kondisi seperti ini dinamakan relasi one-to-one (1 : 1).
•
Seorang dosen dapat mengajar lebih dari satu mata kuliah dan satu mata kuliah hanya dapat diajar oleh seorang dosen saja. Relasi dengan kondisi seperti ini dinamakan relasi one-to-many (1 : n).
•
Seorang dosen hanya dapat mengajar satu mata kuliah dan satu mata kuliah dapat diajar lebih dari satu orang dosen. Relasi dengan kondisi seperti ini dinamakan relasi many-to-one (n : 1).
51 2.5
Flowchart
Gambar 2.43 Contoh Flowchart Sederhana Sumber: Widharto, 2005, petra.ac.id
Flowchart adalah digunakan untuk menggambarkan alur dilaksanakannya suatu proses. Contoh dari flowchart sederhana dapat dilihat pada Gambar 2.43. Flowchart menggunakan beberapa simbol untuk menggambarkan operasi atau proses yang akan dilakukan. Simbol-simbol ini merupakan sebuah bahasa yang digunakan untuk memvisualisasikan masalah sehingga lebih mudah untuk dibaca dan dimengerti.
2.6.1 Terminator atau Terminal Simbol ini digunakan untuk menandai awal dan akhir dari suatu proses. Simbol terminator dapat dilihat pada Gambar 2.44.
Gambar 2.44. Simbol Terminator Sumber: Widharto, 2005, petra.ac.id
52 2.6.2 Inisialisasi Awal Simbol ini digunakan untuk melakukan inisialisasi terhadap variabel variabel yang digunakan dalam proses atau melakukan persiapan-persiapan sebelum suatu proses dijalankan. Simbol inisialisasi dapat dilihat pada Gambar 2.45
Gambar 2.45 Simbol Inisialisasi Awal Sumber: Widharto, 2005, petra.ac.id
2.6.3 Proses Simbol proses seperti yang terdapat pada Gambar 2.46. digunakan untuk menggambarkan sebuah aktifitas tunggal (contoh: “x _ x + 1”) ataupun untuk menggambarkan keseluruhan sub proses (contoh: “Hitung rata-rata nilai”) dalam sebuah proses yang lebih besar.
Gambar 2.46 Simbol Proses Sumber: Widharto, 2005, petra.ac.id
2.6.4 Input atau Output Simbol ini digunakan untuk menggambarkan data dimasukkan oleh user atau yang dikeluarkan dari sebuah proses. Gambar simbol input/output dapat dilihat pada Gambar 2.47.
53
Gambar 2.47 Simbol Input/Output Sumber: Widharto, 2005, petra.ac.id 2.6.5 Decision Simbol ini digunakan untuk menggambarkan sebuah kondisi yang ada. Apabila kondisi tersebut terpenuhi maka proses akan dilanjutkan pada jalur yang bernilai benar dan sebaliknya. Bentuk simbol decision dapat dilihat pada Gambar 2.48
Gambar 2.48 Simbol Decision Sumber: Widharto, 2005, petra.ac.id
2.6.6 Sub Routine (prosedur/fungsi) Simbol ini mengindikasikan adanya rentetan aktivitas yang spesifik pada sebuah proses. Proses lebih lanjut yang terjadi pada sub routine ini akan dijelaskan pada flowchart yang berbeda.
Gambar 2.49 Simbol Sub Routine Sumber: Widharto, 2005, petra.ac.id
