2.1.1 Definisi Graf
Secara matematis, graf didefiniskan sebagai berikut :
Definisi. Graf G didefinisikan sebagai pasangan himpunan (V, E) ditulis dengan notasi G = (V, E), yang dalam hal ini V adalah himpunan tidak-kosong dari simpul-simpul (vertices atau node) dan E adalah himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul (vertices).
Definisi di atas menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi, sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada, minimal satu.
2.1.2 Jenis-Jenis Graf
Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis :
1. Graf sederhana ( simple graph ).
Graf yang tidak memiliki gelang maupun sisi-ganda.
2. Graf tak-sederhana ( unsimple-graph ).
Graf yang memiliki gelang maupun sisi-ganda. Ada dua macam graf tak-sederhana, yaitu graf ganda (multigraph) dan graf semu (pseudograph). Graf ganda adalah graf yang memiliki sisi ganda, sedangkan graf semu adalah graf yang memiliki gelang.
Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:
1. Graf berhingga ( limited graph ).
2. Graf tak-berhingga ( unlimited graph ).
Berdasarkan orientasi arah pada sisi maka secara umum graf dapat digolongkan menjadi dua jenis:
1. Graf berarah ( directed graph ).
Graf yang setiap sisinya diberikan orientasi arah. Pada graf berarah, ( vj, vk ) dan ( vk , vj ) menyatakan dua busur yang berbeda, dengan kata lain
( vj ,vk ) ≠ ( vk ,vj )
Untuk busur ( vj ,vk ), simpul vj disebut simpul asal ( initial vertex ) dan untuk simpul vk disebut simpul terminal
( terminal vertex ).
2. Graf tak-berarah ( undirected graph ).
Graf yang sisinya tidak memiliki orientasi arah. Pada graf tek-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan, dengan kata lain:
( vj ,vk ) = ( vk ,vj ).
2.1.3 Terminologi Dasar
Terdapat beberapa istilah penting yang berkaitan dengan graf. Berikut ini didefinisikan beberapa terminologi yang sering digunakan:
1. Bertetangga ( Adjacent )
Dua bua simpul pada graf tak-berarah G dikatakan bertetangga bila keduanya terhubung langsung dengan sebuah sisi. Dengan kata lain, vj bertetangga dengan vk jika (vj , vk ) adalah sebuah sisi pada graf G.
2. Bersisian ( Incident )
Untuk sembarang sisi e = (vj , vk ), sisi e dikatakan bersisian dengan simpul vj dan simpul vk .
3. Simpul Terpencil ( Isolated Vertex )
Simpul yang tidak mempunyai sisi yang bersisian dengannya. Atau, dapat juga dinyatakan bahwa simpul terpencil adalah simpul yang tidak satupun bertetangga dengan simpul-simpul lainnya.
4. Graf Kosong ( Null atau Empty Graph )
Graf yang himpunan sisinya merupakan himpunan kosong, ditulis sebagai Nn, yang dalam hal ini n adalah jumlah simpul.
5. Derajat ( Degree )
Derajat suatu simpul pada graf tak berarah adalah jumlah sisi yang bersisian dengan simpul tersebut.
Pada graf berarah, derajat simpul v dinyatakan dengan din(v) dan dout(v), yang dalam hal ini:
din(v) = derajat masuk (in-degree)
= jumlah simpul yang masuk ke simpul v
dout(v) = derajat masuk (in-degree)
= jumlah simpul yang keluar dari simpul v
dan
d(v) = din(v) + dout(v).
Notasi: d(v) menyatakan derajat simpul.
6. 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 v0 , e1 , v1 , e2 , v2 ,…,vn-1 ,en ,vn sedemikian sehingga e1 = ( v0 , v1 ) ,
e2 = ( v1 , v2 ) , … , en = ( vn-1 , vn ) adalah sisi-sisi dari graf G.
7. Siklus ( Cycle ) atau Sirkuit ( Circuit )
Lintasan yang berawal dan berakhir pada simpul yang sama.
8. Terhubung (connected)
Graf tak-berarah G disebut graf terhubung ( connected graph ) jika untuk setiap pasang simpul vi dan vj di dalam himpunan V terdapat lintasan dari vi ke vj ( yang juga harus berarti ada lintasan dari vi ke vj ). Jika tidak, maka G disebut graf tak-terhubung (disconnected graph ). Sedangkan graf berarah G dikatakan terhubung jika graf tak-berarahnya terhubung (graf tak-berarah dari G diperoleh dengan menghilangkan arahnya).
9. Upagraf ( Subgraph )
Misalkan G = (V,E) adalah sebuah graf. G1 = (V1 , E1) adalah upagraf dari G jika V1 C V dan E1 C E
10. Komplemen Upagraf
Komplemen dari upagaraf G1 terhadap graf G adalah graf G2 = (V2 , E2) sedemikian sehingga E2 = E – E1 dan V2 adalah himpunan simpul yang anggota – anggota E2 bersisian dengannya.
11. Upagraf Merentang (Spanning Subgraph )
Upagraf G1 = (V1 , E1) dari G = (V, E) dikatakan upagraf merentang jika V1 = V ( yaitu G1 mengandung semua simpul dari G ).
12. Cut-set
Cut-set dari graf terhubung G adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen terhubung.
13. Graf Berbobot ( Weighted Graph )
Graf yang setiap sisinya diberi harga (bobot).
2.1.4 Beberapa Graf Sederhana Khusus
Ada beberapa graf sederhana khusus yang dijumpai pada banyak aplikasi. Beberapa di antaranya adalah seperti yang didefinisikan di bawah ini :
1. Graf Lengkap ( Complete Graph )
Graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya. Graf lengkap dengan n buah simpil dilambangkan dengan Kn. Setiap simpul pada Kn berderajat n-1. Jumlah sisi pada graf lengkap yang terdiri dari n buah simpul adalah n(n - 1)/2.
2. Graf Lingkaran
Graf sederhana yang setiap simpulnya berderajat dua. Graf lingkaran dengan n simpul dilambangkan dengan Cn.
3. Graf Teratur ( Regular Graphs )
Graf yang setiap simpulnya mempunyai derajat yang sama. Apabila derajat setiap simpunya adalah r, maka graf tersebut disebut juga graf teratur derajat r.
4. Graf Bipartit ( Bipartite Graph )
Graf G yang himpunan simpulnya dapat dipisah menjadi dua himpunan bagian V1 dan V2, sedemikian sehingga setiap sisi pada G menghubungkan sebuah simpul di V1 ke sebuah simpul di V2. Dapat juga dinyatakan sebagai G(V1,V2).
5. Graf Isomorfik ( Isomorphic Graph )
Dua bua graf, G1 dan G2 dikatakan isomorfik jika terdapat korespondensi satu-satu antara simpul-simpul keduanya dan antara sisi-sisi keduanya sedemikian sehingga jika sisi e bersisian dengan simpul u dan v di G1 , maka sisi e’ yang berkorespon di G2 juga harus bersisian dengan simpul u’ dan v’ di G2.
Syarat-syarat dua buah graf dapat dikatakan isomorfik :
-
Mempunyai jumlah simpul yang sama
-
Mempunyai jumlah sisi yang sama
-
Mempunyai jumlah simpul yang sama berderajat tertentu
6. Graf Planar (Planar Graph)
Graf G yang dapat digambarkan pada bidang datar dengan sisi-sisi yang tidak saling memotong (bersilangan). Graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan dinamakan graf bidang (plane graph).
7. Pohon (tree)
Graf tak-berarah terhubung yang tidak mengandung sirkuit.
2.2 LINTASAN TERPENDEK (SHORTEST PATH)
Menurut teori Graf, persoalan lintasan terpendek (The Shortest Path Problem) adalah merupakan suatu persoalan untuk mencari lintasan antara dua buah simpul pada graf berbobot yang memiliki gabungan nilai jumlah bobot pada sisi graf yang dilalui dengan jumlah yang paling minimum atau dapat dinyatakan juga sebagai berikut :
-
Diberikan sebuah graf berbobot (dengan himpunan simpul V, himpunan sisi E, dan fungsi bobot bernilai bilangan riil yang dapat ditulis dengan f : E → R ), dan diberikan elamen v dari V , sehingga dapat dicari sebuah lintasan P dari v ke setiap v‘ dari V, sehingga
Adalah nilai minimal dari semua lintasan yang menghubungkan v ke v’.
Persoalan lintasan terpendek merupakan salah satu persoalan optimasi yang menggunakan graf berbobot, dimana bobot pada setiap sisi graf tersebut dapat kita gunakan untuk menyatakan jarak antar kota, waktu pengiriman pesan, ongkos pembangunan, dan sebagainya.
Lintasan terpendek adalah jalur yang dilalui dari suatu node ke node lain dengan besar atau nilai pada sisi yang jumlah akhirnya dari node awal ke node akhir paling kecil.
Lintasan terpendek adalah lintasan minimum yang diperlukan untuk mencapai suatu tempat dari tempat lain. Lintasan minimum yang dimaksud dapat dicari dengan menggunakan graf. Graf yang digunakan adalah graf yang berbobot, yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot.
2.2.1 Jenis Persoalan Rute Terpendek (Shortest Path Problem)
Ada beberapa macam persoalan lintasan terpendek, antara lain:
a. Lintasan terpendek antara dua buah simpul tertentu (a pair shortets path).
b. Lintasan terpendek antara semua pasangan simpul (all pairs shortest path).
c. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain (single-source shoertest path).
d. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu (intermediate shortest path)
2.3 ALGORITMA DJIKSTRA
2.3.1 Definisi Algoritma Djikstra
Edsger Wybe Dijkstra, menemukan suatu algoritma untuk mencari lintasan terpendek pada suatu graf. Algoritma Dijkstra pada awalnya diterapkan pada graf berarah, tetapi ternyata algoritma ini juga benar untuk algoritma graf tak-berarah. Algoritma ini menggunakan prinsip greedy yang digunakan untuk menyatakan bahwa pada setiap langkah kita memilih sisi yang berbobot minimum dan memasukannya ke dalam himpunan solusi. Akan tetapi bobot dari graf tersebut harus bernilai bilangan positif (bobot >=0).
Pada dasarnya, algoritma ini merupakan salah satu bentuk algoritma greedy. Algoritma ini termasuk algoritma pencarian graf yang digunakan untuk menyelesaikan masalah lintasan terpendek dengan satu sumber pada sebuah graf yang tidak memiliki cost sisi negatif, dan menghasilkan sebuah pohon lintasan terpendek. Algoritma ini sering digunakan pada routing
2.3.2 Mekanisme Algoritma Djikstra
Algoritma dijkstra mencari lintasan terpendek dalam sejumlah langkah. Algoritma ini menggunakan strategi greedy sebagai berikut :
Untuk setiap simpul sumber (source) dalam graf, algoritma ini akan mencari jalur dengna cost minimum antara simpul tersebut dengan simpul lainnya. Algoritma ini juga dapat digunakan untuk mencari total biaya (cost) dari lintasan terpendek yang dibentuk dari sebuah simpul ke sebuah simpul tujuan. Sebagai contoh, bila simpul pada graf merepresentasikan kota dan bobot sisi merepresentasikan jarak antara 2 kota yang mengapitnya, maka algoritma dijkstra dapat digunakan untuk mencari rute terpendek antara sebuah kota dengan kota lainnya.
Input algoritma ini adalah sebuah graf berarah yang berbobot (weighted directed graph) G dan sebuah sumber vertex s dalam G dan V adalah himpunan semua vertices dalam graph G.
Algoritma dijkstra dimulai dari sebuah simpul asal dan dalam setiap iterasinya menambahkan sebuah verteks lain ke lintasan terpendek pohon merentang. Verteks ini merupakan titik terdekat ke akar namun masih diluar bagian pohon.
Properti Algoritma Djikstra :
1. Matriks Ketetanggan M[mij]
mij = bobot sisi (i,j) ; pada graf tak berarah mij = mji
mii = 0
mij = ∞ , jika tidak ada sisi dari simpul i ke simpul j
2. Larik S = [si] yang dalam hal ini,
si = 1, jika simpul i termasuk ke dalam lintasan terpendek
si = 0, jika simpul i tidak termasuk ke dalam lintasan terpendek
3. Larik/tabel D = [di] yang dalam hal ini,
di = panjang lintasan dari simpul awal s ke simpul i
Algoritma Lintasan Terpendek Dijkstra :
(Mencari lintasan terpendek dari simpul a ke semua simpul lain}
Langkah 0 (inisialisasi):
- inisialisasi si = 0 dan di = mai untuk i = 1, 2, …, n
Langkah 1:
- isi sa dengan 1 (karena simpul a adalah simpul asal lintasan terpendek, jadi sudah pasti terpilih)
- isi da dengan ∞ (tidak ada lintasan terpendek dari simpul a ke a)
Langkah 2, 3, … , n-1:
- cari j sedemikian sehingga sj = 0 dan dj = min{d1, d2, …, dn}
- isi sj dengan 1
- perbarui di, untuk i = 1, 2, 3, …, n dengan:
di (baru) = min{di (lama), dj + mji }.
Algoritma Djikstra dalam psedo-code :
procedure Dijkstra (input m: matriks, a:simpul awal)
{mencari lintasan terpendek dari simpul awal a ke semua simpul lainya
Masukan : matriks ketetanggaa (m) dari graf berbobot G dan simpul awal a
Keluaran: lintasan terpendek dari a ke semua simpul lainnya}
Deklarasi
s1,s2,…,sn : interger {larik interger}
d1,d2,…,dn : interger {larik interger}
i : interger
Algoritma
{Langkah 0 (inisialisasi) : }
for i ← 1 to n do
si ← 0
di ← mai
endfor
{Langkah 1: }
sa ← 1 {karena simpul a adalah simpul asal lintasan terpendek, jadi terpilih dalam lintasan terpendek}
da ← ∞{tidak ada lintasan terpendek dari simpul a ke a}
{Langkah 2,3,…,n1:}
for i ← 2 to n-1 do
Cari j sedemikian sehingga sj = 0 dan dj = min {d1,d2,…,dn}
Sj ← 1 {simpul j sudah terpilih ke dalam lintasan terpendek}
perbarui di, untuk i = 1,2,3,…,n
dengan : di (baru) = min {di(lama),dj + mji}
endfor.
a. Apakah Ada Lintasan Euler ?
a. Apakah ada lintasan Euler ?
