TEORI GRAPH

1.      Definisi Graph

      Suatu graph didefinisikan oleh himpunan verteks dan himpunan sisi (edge). Verteks menyatakan entitas-entitas data dan sisi menyatakan keterhubungan antara verteks. Biasanya untuk suatu graph G digunakan notasi matematis.

                                                  G = (V, E)

      Dimana :        G = Graph

                              V = Simpul atau Vertex, atau Node, atau Titik

                              E = Busur atau Edge, atau arc

V adalah himpunan verteks dan E himpunan sisi yang terdefinisi antara pasangan-pasangan verteks. Sebuah sisi antara verteks x dan y ditulis {x, y}. Suatu graph H = (V1, E1) disebut subgraph dari graph G jika V1 adalah himpunan bagian dari V dan E1 himpunan bagian dari E.

Cara pendefinisian lain untuk graph adalah dengan menggunakan himpunan keterhubungan langsung Vx. Pada setiap verteks x terdefinisi Vx sebagai himpunan dari verteks-verteks yang adjacent dari x. Secara formal:

Vx = {y | (x,y) -> E}

Dalam digraph didefinisikan juga terminologi-terminologi berikut ini. Predesesor dari suatu verteks x (ditulis Pred(x)) adalah himpunan semua verteks yang adjacent ke x. Suksesor dari verteks x (ditulis Succ(x)) adalah himpunan semua verteks yang adjacent dari x, yaitu adjacenct set di atas.

Struktur data yang berbentuk network/jaringan, hubungan antar elemen adalah many-to-many. Contoh dari graph adalah informasi topologi jaringan dan keterhubungan antar kota-kota. Keterhubungan dan jarak tidak langsung antara dua kota sama dengan data keterhubungan langsung dari kota-kota lainnya yang memperantarainya. Penerapan struktur data linear atau hirarkis pada masalah graph dapat dilakukan tetapi kurang efisien. Struktur data graph secara eksplisit menyatakan keterhubungan ini sehingga pencariannya langsung (straight forward) dilakukan pada strukturnya sendiri.

1.            Struktur Data Linear = keterhubungan sekuensial antara entitas data

2.            Struktur Data Tree = keterhubungan hirarkis

3.            Struktur Data Graph = keterhubungan tak terbatas antara entitas data.

Representasi Graph dalam Bentuk Matrik

a. Graph Tak Berarah

Graf tersebut dapat direpresentasikan dalam sebuah matrik 5x5 , dimana baris dan kolom di matriks tersebut menunjukan vertex yang ada.      

b. Graph Berarah

Dalam matrik diatas dapat kita lihat bahwa kotak yang berisi angka satu menunjukan bahwa dalam dua vertex tersebut terdapat edge yang menghubungkannya. Dan jika dalam kotak terdapat angka nol, maka hal tersebut menandakan tidak ada edge yang mengubungkan secara langsung dua vertex tersebut.

E. Metode Pencarian Vertex

Pencarian vertex adalah proses umum dalam graph. Terdapat 2 metoda pencarian, yakni Depth First Search (DFS) dan Breadth First Search (BFS).

a. Depth First Search (DFS)

Pencarian dengan metode ini dilakukan dari node awal secara mendalam   hingga yang paling akhir (dead-end) atau sampai ditemukan. Dengan kata lain, simpul cabang atau anak yang terlebih dahulu dikunjungi.

Proses pencarian dilakukan dengan mengunjungi cabang terlebih dahulu hingga tiba di simpul terakhir. Jika tujuan yang diinginkan belum tercapai maka   pencarian dilanjutkan  ke  cabang  sebelumnya,  turun  ke  bawah  jika  memang masih  ada  cabangnya.  Begitu seterusnya hingga diperoleh tujuan akhir (goal).  Depth First Search, memiliki kelebihan diantaranya adalah cepat mencapai kedalaman ruang pencarian. Jika diketahui bahwa lintasan solusi permasalahan akan  panjang  maka  Depth  First  Search  tidak  akan  memboroskan waktu  untuk  melakukan  sejumlah  besar  keadaan  dangkal  dalam permasalahan graf. Depth First Search jauh lebih efisien untuk ruang pencarian  dengan  banyak  cabang  karena  tidak  perlu  mengeksekusi semua simpul pada suatu level tertentu pada daftar open. Selain itu, Depth  First  Search  memerlukan  memori  yang  relatif  kecil  karena banyak node pada lintasan yang aktif saja yang Selain kelebihan, Depth First Search juga memiliki kelemahan di antaranya adalah memungkinkan tidak ditemukannya tujuan yang diharapkan  dan  hanya  akan  mendapatkan  satu  solusi  pada  setiap pencarian.

b. Breadth First Search (BFS)

Prosedur Breadth First Search (BFS) merupakan pencarian yang dilakukan dengan mengunjungi tiap-tiap node secara sistematis pada setiap  level  hingga  keadaan tujuan (goal  state) ditemukan. Atau dengan kata lain, penulusuran   yang   dilakukan   adalah   dengan mengunjungi tiap-tiap node pada level yang sama hingga ditemukan goal  state-nya. 

Implementasi algoritma BFS :

Pengimplementasian BFS dapat ditelusuri dengan  menggunakan daftar (list),   open, dan closed, untuk menelusuri gerakan pencarian di dalam  ruang  keadaan.  Prosedur untuk Breadth First Search dapat dituliskan sebagai berikut:

Pada diatas, state 21 merupakan tujuannya (goal) sehingga bila ditelusuri   menggunakan prosedur  Breadth First Search, diperoleh:

1)     Open = [1]; closed = [ ].

2)     Open = [2, 3, 4]; closed = [1].

3)     Open = [3, 4, 5, 6]; closd = [2, 1].

4)     Open = [4, 5, 6, 7, 8]; closed = [3, 2, 1].

5)     Open = [5, 6, 7, 8, 9, 10]; closed = [4, 3, 2, 1].

6)     Open = [6, 7, 8, 9, 10, 11, 12]; closed = [5, 4, 3, 2, 1].

7)     Open  =  [7,  8,  9,  10,  11,  12,  13]  (karena  12  telah  di-open);

         closed = [6, 5, 4, 3, 2, 1].

8)     Open = [8, 9, 10, 11, 12, 13, 14]; closed = [7, 6, 5, 4, 3, 2, 1].

9)     Dan seterusnya sampai state 21 diperoleh atau open = [ ].

Ada  beberapa  keuntungan  menggunakan  algoritma  Breadth First Search ini, diantaranya adalah tidak akan menemui jalan buntu dan jika ada   satu solusi maka Breadth First Search akan menemukannya, dan jika ada lebih  dari  satu  solusi  maka solusi minimum akan ditemukan.

Namun  ada  tiga  persoalan  utama  berkenaan  dengan  Breadth First Search ini yaitu :

1) Membutuhkan  memori  yang  lebih  besar,  karena menyimpan semua node dalam satu pohon. 

2) Membutuhkan   sejumlah   besar   pekerjaan,   khususnya   jika lintasan  solusi  terpendek  cukup  panjang,  karena  jumlah  node yang  perlu  diperiksa  bertambah  secara  eksponensial  terhadap panjang lintasan.

3) Tidak relevannya operator akan menambah jumlah node yang harus diperiksa.

Oleh  karena  proses  Breadth  First  Search  mengamati  node  di setiap  level  graf  sebelum  bergerak  menuju  ruang  yang  lebih  dalam maka  mula-mula  semua  keadaan  akan  dicapai  lewat  lintasan  yang terpendek  dari  keadaan  awal.  Oleh  sebab  itu,  proses  ini  menjamin ditemukannya  lintasan  terpendek  dari  keadaan  awal  ke  keadaan tujuan   (akhir).   Lebih   jauh   karena   mula-mula   semua   keadaan ditemukan melalui lintasan terpendek sehingga setiap keadaan  yang ditemui  pada  kali  kedua  didapati  pada  sepanjang  sebuah  lintasan yang sama atau lebih panjang. Kemudian, jika tidak ada kesempatan ditemukannya  keadaan  yang  identik  pada  sepanjang  lintasan  yang lebih baik maka algoritma akan menghapusnya

F. Shortest Path

Pencarian shortest path (lintasan terpendek) adalah masalah umum dalam suatu weighted, connected graph. Misal : Pencarian jaringan jalan raya yang menghubungkan kota-kota disuatu wilayah.

1.            Lintasan terpendek yag menghubungkan antara dua kota berlainan tertentu (Single-source Single-destination Shortest Path Problems)

2.            Semua lintasan terpendek masing-masing dari suatu kota ke setiap kota lainnya (Single-source Shortest Path problems)

3.            Semua lintasan terpendek masing-masing antara tiap kemungkinan pasang kota yang berbeda (All-pairs Shortest Path Problems)

Untuk memecahkan masing-masing dari masalah-masalah tersebut terdapat sejumlah solusi.

Dalam beberapa masalah graph lain, suatu graph dapat memiliki bobot negatif dan kasus ini dipecahkan oleh algoritma Bellman-Ford. Yang akan dibahas di sini adalah algoritma Dijkstra yaitu mencari lintasan terpendek dari suatu verteks asal tertentu vs ke setiap verteks lainnya.

a. Graph berbobot (weighted graph)

Apabila sisi-sisi pada graph disertai juga dengan suatu (atau beberapa) harga yang menyatakan secara unik kondisi keterhubungan tersebut maka graph tersebut disebut graph berbobot. Biasanya dalam masalah-masalah graph bobot tersebut merupakan "harga" dari keterhubungan antar vertex. Pengertian "harga" ini menggeneralisasikan banyak aspek, biaya ekonomis dari proses/aktifitas, jarak geografis/tempuh, waktu tempuh, tingkat kesulitan, dan lain sebagainya.

 Dalam beberapa masalah lain bisa juga bobot tersebut memiliki pengertian "laba" yang berarti kebalikan dari "biaya" di atas. Dalam pembahasan algoritma-algoritma graph nanti pengertian bobot akan menggunakan pengertian biaya sehingga apabila diaplikasikan pada masalah yang berpengertian laba maka kuantitas-kuantitas terkait adalah kebalikannnya. Misalnya mencari jarak tempuh minimum digantikan dengan mencari laba maksimum.