Graph Problem ~ Kuliah Teknik Informatika

Grap adalah sekumpulan node (simpul) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis (sisi). Graph dapat digunakan untuk merepresentasikan objek – objek diskrit dan hubungan antara objek - objek tertentu dengan objek sebagai node (simpul) , bulatan atau titik (Vertex), sedangkan hubungan antara objek dinyatakan dengan garis (Edge).

Istilah-istilah dalam Graph antara lain:

1. Vertex yaitu himpunan node / titik pada sebuah graph.

2. Edge yaitu himpunan garis yang menghubungkan tiap node / vertex

3. Adjacent sesuai dengan kata Adjacent yang artinya “bersebelahan, berdekatan, berdampingan”. Jadi Adjacent adalah dua buah titik dikatakan berdekatan (adjacent) jika dua buah titik tersebut terhubung dengan sebuah sisi yang lain.

4. Weight yaitu menyatakan hubungan antara kedua buah vertex maka edge tersebut dikatakan memiliki bobot. Graph yang memiliki bobot dapat disebut sebagai graph berbobot atau weight graph

5. Path (lintasan) yaitu serangkaian vertex yang berbeda yang adjacent secara berturut – turut dari vertex satu ke vertex berikutnya.

6. Direct (arah) merupakan arah suatu graph . Pada graph berarah urutan vertex memiliki arti.

G = (V,E)

Dimana:

- V adalah Vertex, menyatakan entitas data.

- E adalah Edge, menyatakan garis penghubung antar node.

- Vertex (Vertices) disebut juga sebagai node atau point.

- Edge disebut juga sebagai arcs atau lines.

- Setiap edge menghubungkan dua vertices.

Contoh Graph

Contoh persoalan di dunia nyata yang dapat direpresentasikan dengan graph adalah: Jaringan pertemanan pada Facebook.

Graph dengan 6 node/vertex dan 7 lines/edge yang merepresentasikan jaringan pertemanan pada Facebook

Penjabaran:

- Node(vertex): para pemakai Facebook

- Lines(edge) : Garis penghubung antara pemakai satu dengan yang lain.

- Sehingga dari contoh graph diatas dapat dijabarkan sebagai berikut:

· V = {Nina, Toni, Ale, Riza, Joko, Firda}

E = {{Nina,Toni},{Toni,Riza},{Nina, Riza}, {Toni,Ale}, {Ale,Joko},{Riza,Joko},{Firda,Joko}}

Jenis-Jenis Graph

1. Directed Graph (Digraph)

· Graph yang memiliki orientasi/arah.

· Setiap lines/edge Digraph memiliki anak panah yang mengarah ke node tertentu.

· Secara notasi sisi digraph ditulis sebagai vektor (u, v).

u = origin (vertex asal)

v = terminus (vertex tujuan)

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)}.

Gambar Digraph:

1. 2. Undirected Graph

Graph yang tidak memiliki orientasi/arah.
Setiap sisi {u, v} berlaku pada kedua arah.
Misalnya : {x,y}. Arah bisa dari x ke y, atau y ke x.
Secara grafis sisi pada undigraph tidak memiliki mata panah dan secara notasional menggunakan kurung kurawal.

Contoh Undi-Graph:

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}}.

Gambar Undi-Graph: