Graph

GRAPH

A.     Pengertian Graph

Graph merupakan visualisasi abstrak dari himpunan objek yang saling terhubung. Objek atau simpul-simpul dalam graf biasa disebut dengan vertex, sedangkan garis yang menghubungkan simpul-simpul yang ada di dalam graf disebut dengan edge.

Secara sistematis dinyatakan sebagai

G = (V,E)

Keterangan :

G = Graph
V = Simpul/Vektor/Node/Titik
E = Busur/Edge/arc

B.     Macam – macam Graph

·         Graf tak berarah (undirected graph)

Merupakan graph yang sisinya tidak mempunyai orientasi arah. Pada graph tak berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Salah satu contoh graph tak berarah dimana sisi yang menghubungkan antar simpul dalam graph tersebut tidak memiliki arah

·         Graph Berarah (directed graph)

Graph yang setiap sisinya memiliki orientasi arah. Sisi berara dalam graf ini dinamakan sebagai busur. Lain halnya dengan graf tak berarah, urutan pasangan simpul di dalam graf berarah sangat diperhatikan karena dapat menyatakan hal yang berbeda. Pada graf berarah ( ac, ad) dan (ad,ac) menyatakan dua buah busur yang berbeda.

·         Graph Berbobot (Weighted Graph)

1.      Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut merupakan grap yang memiliki bobot

2.      Bobot sebuah busur dapat dinyatakan sebagai panjang sebuah jalan dari 2 buah titik.

C.     Istilah – istilah pada Graph

·         Incident

Jika e merupakan  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 dengan v dan w

·         Degree (derajat)

Merupakan jumlah busur yang incident dengan simpul tersebut.

Didalam Degree terdapat 2 istilah, yaitu Indegree dan Outdegree.

Indegree sebuah simpul pada graph berarah merupakan jumlah busur yang masuk atau menuju suatu simpul

Outdegree merupakan lawan dari indegree, indegree masuk kesuatu simpul lain halnya dengan outdegree, arah panah outdegree adalah keluar atau berasal dari simpul tersebut.

·         Adjacent

Pada graph tidak berarah, 2 simpul dikatakan adjacent jika terdapat busur yang menghubungkan kedua simpul tersebut.

Contoh simpul v dan w merupakan adjacent

Pada graph berarah, simpul v disebut adjacent dengan simpul w jika terdapat busur dari w menuju v.

·         Successor dan Predecessor

Pada graph berarah, bila simpul v adjacent dengan simpul w, maka simpul v merupakan successor simpul w, dan simpul w merupakan predecessor dari simpul v.

·         Path

Sebuah path merupakan serangkaian simpul-simpul yang berbeda, yang adjacent secara berturut-turut dari simpul satu kesimpul lainnya.

D.     Representasi Graph dalam Bentuk Matirix

·         Adjacency Matrix graph tak berarah

·         Adjacency Matrix graph Berarah

·         Adjacency Matrix graph berarah dan berbobot