Raph dapat
digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek
- objek tersebut.
Representasi
visual dari graph adalah
dengan menyatakan objek sebagai noktah, bulatan atau titik (Vertex), sedangkan
hubungan antara objek dinyatakan dengan garis (Edge).
Ada
beberapa cara untuk menyimpan graph di dalam sitem komputer. Struktur data
bergantung pada struktur graph dan algoritma yang digunakan untuk memmanipulasi
graph. Secara teori salah satu dari keduanya dapat dibedakan antara struktur
list dan matriks, tetapi dalam penggunaannya struktur terbaik yang sering
digunakan adalah kombinasi keduanya.
A. Graph
tak berarah (undirected graph atau non-directed graph) :
Urutan simpul dalam sebuah busur
tidak dipentingkan.
B. Graph
berarah (directed graph) :
Urutan simpul mempunyai arti. Misal
busur AB adalah e1 sedangkan busur BA adalah e8.
C. Graph
Berbobot (Weighted Graph)
Jika setiap busur mempunyai nilai
yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan
memiliki bobot.
Kemudian
terdapat istilah-istilah yang berkaitan dengan graph yaitu:
A. Vertex
himpunan
node / titik pada sebuah graph.
B. Edge
himpunan
garis yang menghubungkan tiap node / vertex.
C. Adjacent
dua
buah titik dikatakan berdekatan (adjacent) jika dua buah titik tersebut
terhubung dengan sebuah sisi.
D. Weight
Dikatakan
sebuah graf berbobot(weight graph), apabila terdapat sebuah fungsi bobot bernilai
real W pada himpunan E
Beberapa masalah
sangat sulit diselesaikan dengan cara komputasi hanya beberapa contoh yang
dapat diselesaikan dalam waktu yang dapat diterima. Contoh :
·
TSP (Traveling Salesman
Problem)
suatu permasalahan
dimana seorang salesman harus mengunjungi semua kota dimana tiap kota hanya
dikunjunjungi sekali, dan dia harus mulai dari dan kembali ke kota asal.
Tujuannya adalah menentukan rute dengan jarak total atau biaya paling minimum.
Salah satu algoritma
yang dapat dipakai yaitu algoritma Heuristik.
·
GCP(Graph Coloring
Problem) Pewarnaan Graph
pemberian warna
terhadap vertex-vertex graf dimana dua buah vertex yang berdampingan tidak
boleh mempunyai warna yang sama.
Algoritma yang dapat
digunakan untuk menyelesaikan permasalahan pewarnaan graf salah satunya adalah
algoritma Greedy
·
Chinese Postman Problem
(CPP)
Dalam istilah graf
definisi CPP adalah mencari lintasan pada suatu graf berbobot yang terhubung
yang melewati semua sisi (minimal sekali) dengan jumlah bobot minimum dari
suatu simpul kembali ke simpul awal.
Masalah ini dapat
terjadi pada :
o Graf
berarah
o Graf
tidak berarah dan
o Graf
campuran
Dasar untuk
menyelesaikan masalah CPP adalah keberadaan sirkuit dan lintasan Euler.
·
Minimum Spanning Tree
(MST)
Cara menemukan jalan
terpendek dimana semua vertex telah terlewati sekali tanpa terjadi
looping. Salah satu algoritma yang dapat digunakan untuk menyelesaikannya
yaitu algoritma Prim.
Shorhest Path
Problem dalam Graf
merupakan salah
satu dari masalah yang dapat diselesaikan dengan graf. Jika diberikan sebuah
graf berbobot, masalah lintasan terpendek adalah bagaimana kita mencari sebuah
jalur pada graf yang meminimalkan jumlah bobot sisi pembentuk jalur
tersebut.
Beberapa macam persoalan lintasan
terpendek antara lain:
·
Lintasan terpendek
antara dua buah simpul tertentu (a pair shortets path).
·
Lintasan terpendek
antara semua pasangan simpul (all pairs shortest path).
·
Lintasan terpendek dari
simpul tertentu ke semua simpul yang lain (single-source shoertest path).
·
Lintasan terpendek
antara dua buah simpul yang melalui beberapa simpul tertentu (intermediate
shortest path).
Algoritma
yang digunakan untuk menyelesaikan persoalan lintasan terpendek diantaranya
Pathing Algoritma (pathing
algorithm), Algoritma Djikstra ( Djikstra Algorithm ) dan
Algoritma Bellman-Ford ( Bellman-Ford Algorithm ).
Sumber :
Tidak ada komentar:
Posting Komentar