Graph

Struktur Data Graph :
Pendahuluan :
1. Graph : struktur data yang berbentuk network/jaringan, hubungan
antar elemen adalah many-to-many
2. Struktur Data Linear = keterhubungan sekuensial antara entitas data
3. Struktur Data Tree = keterhubungan hirarkis
4. Struktur Data Graph = keterhubungan tak terbatas antara entitas data.
Contoh graph : Informasi topologi jaringan dan keterhubungan antar
kota-kota
5. Keterhubungan dan jarak tidak langsung antara dua kota = data
keterhubungan langsung dari kota-kota lainnya yang
memperantarainya.
6. 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
(straightforward) dilakukan pada strukturnya sendiri

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

Graph terdiri dari himpunan verteks (node) dan himpunan sisi (edge, arc).
Verteks menyatakan entitas-entitas data dan sisi menyatakan
keterhubungan antara verteks.
Notasi matematis graph G adalah :
G = (V, E)
Sebuah sisi antara verteks x dan y ditulis {x, y}.
Subgraph : graph yang merupakan suatu subset (bagian) graph yang
connected
Graph H = (V1, E1) disebut subgraph dari graph G jika V1 adalah himpunan
bagian dari V dan E1 himpunan bagian dari E.
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, 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)}.

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}}.
Khusus graph, undigraph bisa sebagai digraph (panah di kedua ujung edge
berlawanan)
Struktur data linear maupun hirarkis adalah juga graph. Node-node pada
struktur linear ataupun hirarkis adalah verteks-verteks dalam
pengertian graph dengan sisi-sisinya menyusun node-node tersebut
secara linear atau hirarkis.
Struktur data linear adalah juga tree dengan pencabangan pada setiap node
hanya satu atau tidak ada.
Linear 1-way linked list (digraph), linear 2-way linked list (undigraph).

Konektivitas pada Undigraph
• Adjacency: Dua verteks x dan y yang berlainan disebut
terhubung langsung (adjacent) jika ada sisi {x, y} dalam E.
• Path : Urutan dari kumpulan node-node, dimana tiap node
dengan node berikutnya dihubungkan dengan Edge
• Simple Path : Jika node dalam path tsb hanya muncul 1 kali
• Panjang dari path: jumlah sisi yang dilalui path.
• Siklus (cycle) : suatu path dengan panjang lebih dari satu,
dimana vertex awal dan akhir sama.
• Siklus sederhana: dalam undigraph, siklus yang terbentuk dari
tiga atau lebih verteks yang berlainan, dimana tidak ada vertex
muncul lebih satu kali kecuali verteks awal/akhir.
• Dua verteks x dan y yang berbeda dalam suatu undigraph
disebut berkoneksi (connected) apabila ada path penghubung.
• Suatu komponen terkoneksi (connected components) adalah
subgraph (bagian dari graph) yang berisikan satu himpunan
bagian verteks yang berkoneksi

Konektivitas pada Digraph
Terminologi pada Undigrap berlaku, kecuali dalam digraph harus dikaitkan
dengan arah tertentu karena pada arah yang sebaliknya belum tentu
terdefinisi.
Adjacency ke/dari : Jika ada sisi (x,y) maka pada digraph dikatakan bahwa
x "adjacent ke" y atau y "adjacent dari" x. Demikian pula jika terdapat
path dari x ke y maka belum tentu ada path dari y ke x. Jadi dalam
digraph keterkoneksian didefinisikan lebih lanjut lagi sebagai berikut.
- Terkoneksi Kuat : Bila setiap pasangan verteks berbeda x dan y
dalam S, x berkoneksi dengan y dan y berkoneksi dengan x
- Terkoneksi Lemah : Bila setiap pasangan verteks berbeda x dan y

Konektivitas pada Digraph
Terminologi pada Undigrap berlaku, kecuali dalam digraph harus dikaitkan
dengan arah tertentu karena pada arah yang sebaliknya belum tentu
terdefinisi.
Adjacency ke/dari : Jika ada sisi (x,y) maka pada digraph dikatakan bahwa
x "adjacent ke" y atau y "adjacent dari" x. Demikian pula jika terdapat
path dari x ke y maka belum tentu ada path dari y ke x. Jadi dalam
digraph keterkoneksian didefinisikan lebih lanjut lagi sebagai berikut.
- Terkoneksi Kuat : Bila setiap pasangan verteks berbeda x dan y
dalam S, x berkoneksi dengan y dan y berkoneksi dengan x
- Terkoneksi Lemah : Bila setiap pasangan verteks berbeda x dan y
dalam S, salah satu: x berkoneksi dengan y (atau y berkoneksi
dengan x) dan tidak kebalikan arahnya (hanya terdefinisi satu path:
dari x ke y atau sebaliknya dari y ke x).

Sumber : http://alpz.files.wordpress.com/2007/12/tree-btree-graph.pdf
dalam S, salah satu: x berkoneksi dengan y (atau y berkoneksi
dengan x) dan tidak kebalikan arahnya (hanya terdefinisi satu path:
dari x ke y atau sebaliknya dari y ke x).