Graph dan Contoh penerapan Graph pada Struktur Data.

GRAPH

* GRAPH merupakan suatu koleksi dari himpunan VG dan EG.
Notasi : G = { VG, EG }
G = Graph
VG = Himpunan titik
EG = HImpunan garis

Titik : Node / Vertex
Garis : Arc / Edge
Contoh : Graph G terdiri dari : G = { VG, EG }
VG = { a,b,c,d }
EG = { 1,2,3,4,5,6,7,8 }

Gambar 1. Graph

Pada Gambar 1, edge 1 menghubungkan vertex a & b * Edge 1 = (a,b)
edge 2 menghubungkan vertex b & c * Edge 2 = (b,c)
edge 3 menghubungkan vertex b & c * Edge 3 = (b,c), dst ...

* Jumlah vertex dalam suatu graph disebut ORDER dari graph tersebut.
Contoh : Graph G dengan order = 4 (jumlah vertex = 4 ; a,b,c,d)

* Suatu graph hanya ditentukan oleh vertex-vertex dan edge-edgenya. Posisi dari vertex-vertex dan edge-edge dalam penggambaran tidaklah penting.
GRAPH EQUIVALEN : penggambaran graph yang sama.

Gambar 2

GRAPH EQUIVALEN

* Suatu graph G disebut SIMPLE GRAPH, jika :
1. tidak mempunyai edge yang SELF LOOP (tidak ada (V,V) dalam G)
2. tidak mempunyai MULTIPLE EDGE (hanya ada (Vi, Vj) dalam G)
(V1, V2, V3, ...... * VG)

Gambar 3

SIMPLE GRAPH


* MULTIPLE EDGE adalah 1 vertex dihubungkan oleh beberapa edge.
Contoh : Pada Gambar 2 ; vertex b dihubungkan oleh edge-edge 1,2,3,5,6,7
vertex c dihubungkan oleh edge-edge 2,3,4

* SELF LOOP adalah vertex yang dihubungkan oleh edge-edge menuju edge itu sendiri.
Contoh : Vertex a dihubungkan oleh edge 8 menuju a kembali (Gambar 2)

* Suatu Graph G disebut CONNECTED (terhubung) jika Graph G dapat dipartisi (dibagi) menjadi 2 graph dengan menghapus paling sedikit 1 edge.

* Contoh yang tidak connected :
Suatu graph G terdiri dari : G = { VG, EG }
VG = { e,f,g,h }
EG = { 1,2,3 }

Gambar 4

UNCONNECTED GRAPH

* PATH dalam Graph adalah barisan dari 1 buah edge-edge yang menghubungkan 2 vertex.
Notasi : P(Vi, Vj) = (Vi, X1) (X1, X2) (X2, Xn-1) (Xn-1, Xn) (Xn, Vj)
Dari Gambar 3: P(b,d) = (b,c) (c,d)
P(b,d) = (b,c) (c,b) (b,c) (c,d)
P(b,d) = (b,d)
P(b,d) = (b,c) (c,b) (b,d)

* LENGTH dari suatu path adalah jumlah edge-edge pada path tersebut.
Contoh : Perhatikan Gambar 3 : P(b,d) = (b,d) * length = 1
= (b,c) (c,d) * length = 2
= (b,c) (c,b) (b,d) * length = 3

* CYCLE adalah path yang memenuhi syarat sebagai berikut :
1. tidak ada edge yang tampil lebih dari satu kali dalam barisan edge dari path tersebut
contoh : Gambar 3 ; P(b,d) = (b,c) (c,b) (b,d)
 tidak boleh
2. path harus berbentuk P(V,V)
3. tidak ada vertex yang dikunjungi lebih dari satu kali
contoh : P(a,a) = (a,b) (b,c) (c,d) (d,b) (b,a)
b dikunjungi lebih dari 1x
P(b,b) = (b,c) (c,b) (b,a) (a,c) (c,b)
c & b dikunjungi 3x

Contoh CYCLE : P(b,b) = (b,d) (d,c) (c,b)

* ACYCLIC adalah graph yang tidak mempunyai cycle.
Contoh : Graph G terdiri dari : G = { VG, EG }
VG = { e,f,g,h }
EG = { 1,2,3 }

Gambar 5

ACYCLIC GRAPH


Graph yang Simple belum tentu graph yang Acyclic.
Graph yang Acyclic adalah graph yang Simple.

* Graph yang berarah disebut DI-GRAPH / DIRECTED GRAPH, adalah merupakan graph dimana edge-edgenya mempunyai suatu arah.

Gambar 6

Pada Gambar 6 ; (a,b) * 1 arah
(b,a) * 0 arah

* Graph yang tidak mempunyai arah boleh bolak-balik.

Gambar 7

Pada Gambar 7 ; (a,b) * 1 arah
(b,a) * 1 arah

Sumber: Graph dan Contoh penerapan Graph pada Struktur Data.