Graph

Assalamualaikum.Wr.Wb.

Hai kawan! Kembali lagi kita dalam pelajaran struktur data yang akan membahas mengenai "GRAPH".

Tahukah kamu apa itu graph ?

Graph adalah kumpulan dari simpul dan busur yang secara matematis dinyatakan sebagai :
G = (V,E)
Yaitu
G = Graph
V = Simpul atau Vertex, atau Node, atau Titik
E = Busur atau Edge, atau arc


Pengertian dalam graph
1. Sebuah graph mungkin hanya terdiri dari satu simpul.
2. Sebuah graph belum tentu semua simpulnya terhubung dengan busur.
3. Semua graph mungkin mempunyai simpul yang tak terhubung dengan simpul yang lain.
4. Debuah graph mungkin semua simpulnya saling berhubungan.



Macam-macam graph


1. Graph tak berarah (undirected graph atau non-directed graph) yaitu urutan simpul dalam sebuah     busur tidak dipentingkan. Misalnya busur e1 dapat disebut busur AB atau BA.

Contoh graph tak berarah:

V terdiri dari v1,v2.v3.v4.v3
E terdiri dari e1,e2,e3,e4,e5,e6,e7
Dari contoh diatas merupakan graph tak berarah yaitu tidak ada arah (tanda panah) yang dapat diartikan busur e7 dapat disebut CD atau DC.


Contoh lainnya:
Sebuah graph tak berarah mempunyai 5 buah vertex yaitu P,Q,R,S,T. Vertex tersebut dihubungkan oleh 6 buah edge yang menghubungkan antara P-Q,P-S,Q-T,Q-R,R-S dan R-T.

2. Graph berarah (directed graph) yaitu urutan simpul mempunyai arti. Misalkan busur AB adalai e1 

    sedangkan busur BA adalah e2

Contoh graph berarah :

V terdiri dari v1,v2.v3.v4.v3
E terdiri dari e1,e2,e3,e4,e5,e6,e7
Dari contoh diatas merupakan graph berarah yaitu ada arah (tanda panah) yang dapat diartikan busur e4 dapat disebut AE sedangkan busur e2 dapat disebut EA.


3. Graph Berbobot (Weighted Graph) yaitu jika setiap busur mempunyai nilai yang menyatakan
    hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki bobot.

    Catatan: Bobot yang lebih besar belum berarti lebih panjang.

Contoh :

Sebuah graph berarah mempunyai 5 buah vertex yaitu P,Q,R,S,T. Jika graph tersebut adalah graph terarah dan berbobot, dengan nilai bobot dan arah sebagai daftar dibawah

Grambarkan bentuk graph tersebut.

PQ = 8

SR = 9

SQ = 5

QP = 6

RT = 8

TS = 4

RS = 9

QS = 2

Istilah pada graph

1. Incident

Jika e menupakan busur dengan simpul-simpulnya adalah v dan w yang ditulis e=(v,w) maka v dan w disebut "terletak" pada e, dan e disebut incident denagn v,w

2. Degree (derajat), indegree dan outdegree

Degree sebuah simpul adalah jumlah busur yang incident dengan simpul tersebut.

Indegree sebuah simpul pada graph berarah adalah jumlah busur yang kepalanya incident dengan simpul tersebut, atau jumlah busur yang "masuk" atau menuju simpul tersebut.

Outdegree sebuah simpul pada graph berarah adalah jumlah busur yang ekornya incident dengan simpul tersebut, atau jumlah busur yang "keluar" atau berasal dari simpul tersebut.

3. Adjacent

Pada graph tak berarah, 2 buah simpul disebut adjacent bila ada busur yang menghubungkan kedua simpul tersebut. simpul a dan b disebut adjacent.

Dari contoh diatas dapat disimpulkan

a adjacent b

b adjacent a

Pada graph berarah, simpul a disebut adjecent.

Dari contoh diatas dapat disimpulkan

a adjacent b

b tidak adjacent a

4. Successor dan Predecessor

Hanya terdapat pada graph berarah, bila simpul a adjacent dengan simpul b, makan simpul a adalah successor simpul b, dan simpul b adalah predecessor dari simpul a.

5. Path

Path atau disebut jalur adalah serangkaian simpul-simpul yang berbeda, yang adjacent secara berturut-turut dari simpul satu ke simpul berikutnya.

Contoh 1 :

Contoh 2 :

Contoh 3 :

Contoh 4 :

Representasi graph dalam bentuk matrik

1. Graph tak berarah

Maka :

Dapat disimpulkan bahwa
A - B dengan B - A sama dengan nilai 1
A - D dengan D - A sama dengan nilai 1
D - E dengan E - D sama dengan nilai 1
E - C dengan C - E sama dengan nilai 1
C - B dengan B - C sama dengan nilai 1
C - D dengan D - C sama dengan nilai 1
B - E dengan E - B sama dengan nilai 1



2. Graph berarah

Maka :

Dapat disimpulkan bahwa
B - C  dengan nilai 1
B - E  dengan nilai 1
C - B  dengan nilai 1
C - D dengan nilai 1
C - E dengan nilai 1
D - C dengan nilai 1
D - E  dengan nilai 1


3, Graph Berbobot

Jika ada bobot maka nilainya bobot tersebut  dan jika tidak ada bobot maka nilainya 0.

Maka :

Dapat disimpulkan bahwa
A - C  dengan nilai 22
A - E  dengan nilai 12
B - A  dengan nilai 50
C - D dengan nilai 15
C - F dengan nilai 30
D - B dengan nilai 25
D - E dengan nilai 22
E - D  dengan nilai 55


Dari materi diatas, Semoga Bermanfaat

Wassalamualaikum.Wr.Wb