Graph

Definisi Graph

Graph adalah kumpulan busur dan simpul, secara matematis dapat kita tuliskan SBB.

G = (V,E)

G = Graph
V = Vertex/Simpul, Node/Titik
E = Edge/Busur

Jenis Graph
a. Directed Graph (Digraph)
Jika sisi-sisi graph hanya berlaku satu arah.
Misalnya :
{x,y} yaitu arah x ke y, bukan dari y ke x;
x disebut origin dan y disebut terminus. Secara notasi sisi digraph ditulis sebagai vektor (x, y).

Contoh Digraph G = {V, E} : V = {A, B, C, D, E, F, G, H, I,J, K, L,

E = {(A,B),(A,C), (A,D), (A,F), (B,C), (B,H), (C,E), (C,G), (C,H), (C,I), (D,E), (D,F), (D,G), (D,K), (D,L), (E,F), (G,I), (G,K), (H,I), (I,J), (I,M), (J,K), (J,M), (L,K), (L,M)}.

b. Graph Tak Berarah (Undirected Graph atau Undigraph) 
Setiap sisi {x, y} berlaku pada kedua arah: baik x ke y maupun y ke x. Secara grafis sisi pada undigraph tidak memiliki mata panah dan secara notasional menggunakan kurung kurawal.

Contoh Undigraph G = {V, E} :

 V = {A, B, C, D, E, F, G, H, I,J, K, L, M}

 E = { {A,B},{A,C}, {A,D}, {A,F}, {B,C}, {B,H}, {C,E}, {C,G}, {C,H}, {C,I}, {D,E}, {D,F}, {D,G}, {D,K}, {D,L}, {E,F}, {G,I}, {G,K}, {H,I}, {I,J}, {I,M}, {J,K}, {J,M}, {L,K}, {L,M}}

Masalah-Masalah Graph 

1. Masalah path minimum (Shortest path problem)Mencari route dengan jarak terpendek dalam suatu jaringan transportasi
2. Masalah aliran maksimum (maximum flow problem)
   Menghitung volume aliran BBM dari suatu reservoir ke suatu titik tujuan melalui jaringan pipa
3. Masalah pencarian dalam graph (graph searching problem) Mencari langkah-langkah terbaik dalam program permainan catur komputer. 
4. Masalah pengurutan topologis (topological ordering problem)
   Menentukan urutan pengambilan mata-mata kuliah yang saling berkaitan dalam hubungan prasyarat (prerequisite). 
5. Masalah jaringan tugas (Task Network Problem)
   Membuat penjadwalan pengerjaan suatu proyek yang memungkinkan waktu penyelesaian tersingkat. 
6. Masalah pencarian pohon rentang minimum (Minimum Spanning Tree Problem) Mencari rentangan kabel listrik yang totalnya adalah minimal untuk menghubungkan sejumlah kota. 
7. Travelling Salesperson ProblemTukang pos mencari lintasan terpendek melalui semua alamat penerima pos tanpa harus mendatangi suatu tempat lebih dari satu kali.
8. Four-color problem
   Dalam menggambar peta, memberikan warna yang berbeda pada setiap propinsi yang saling bersebelahan.

Rangkuman Struktur Data Graph
Mengenal Graph ƒ

• Terdiri dari node 
• Terdiri dari link

Node disebut vertex ƒ

• Link disebut edge ƒ
• Informasi penting dalam graph adalah koneksi antar vertex

• Pada undirected graph, tidak terdapat directions (arah) ƒ
• Edge dari v0 ke v1 adalah sama dengan edge dari v1 ke v0 ƒJika sebuah masalah dapat direpresentasikan ke dalam bentuk graph maka solusi dari masalah tersebut bisa dicari dengan bantuan graph
• ƒSetiap vertex mewakili sebuah kondisi (state) dan edge mewakili transisi antar state

Analogi Graph dalam Kehidupan Sehari-Hari

      Graph dalam kehidupan sehari-hari dapat dianalogikan sebagai suatu jaringan satu dengan jaringan lainnya yang saling terhubung. Misal seperti negara Indonesia yang memiliki banyak kota seperti: Jakarta, Bandung, Srabaya, Yogyakarta. Kota-kota itulah yang tergabung dalam negara Indonesia dan kota-kota itulah yang saling berhubungan.

Referensi
http://www.slideshare.net/zaldyputra/makalah-graph-i
http://eprints.undip.ac.id/5202/2/BAB_I_dan_II.pdf
https://www.google.co.id/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&cad=rja&uact=8&ved=0ahUKEwi5s8eA-cDPAhVBKY8KHWBkBSgQFggpMAI&url=http%3A%2F%2Fwww.informatika.unsyiah.ac.id%2Ftfa%2Fds%2Fgraph.pdf&usg=AFQjCNHWZIOpY-xapCzT6cP4dcD84vR9_g&sig2=C2LbiffCPD_cQdxyLJSbRA&bvm=bv.134495766,d.c2I