GRAPH

GRAPH

Apasih yang di maksud dengan graph?

Graph adalah kumpulan / hubungan antara simpul dan busur. Secara matematis dapat di nyatakan sebagai berikut G = (V,E).

Dimana:

G adalah graph;

V adalah  vertex atau simpul;

E adalah edges atau busur;

Graph di bagi menjadi 2 yaitu:

• Graph terhubung

Yaitu graph yang vertex (V) dan edges (E) nya saling terhubung.

•  Graph tidak terhubung

Yaitu graph yang vertex (V) dan edges (E) nya saling terpisah.

Graph juga dibagi menjadi:

• Graph tidak berlabel

• Graph berlabel

Graph berlabel  ini dibagi menjadi dua kategori yaitu:

a.    Graph berlabel ajaib

Graph berlabel ajaib adalah graph yang memiliki weight (W) atau berat yang sama.

Contoh:

              

          W1 = 1 + 3 + 5 = 9

          W2 = 3 + 4 + 2 = 9

Bobot W1 dan W2 adalah sama, yaitu sama-sama 9. Maka graph ini disebut graph ajaib.

b.    Graph berlabel anti ajaib

Graph anti ajaib adalah graph yang memiliki weigh (W) yang berbeda-beda, namun dengan selisih yang sama. Contohnya:

                            

               

W1 = 1 + 10 + 3 = 14

W2 = 3 + 8 + 5 = 16

W3 = 5 + 6 + 7 = 18

W4 = 7 + 4 + 9 = 20

W5 = 9 + 2 + 11 = 22

W6 = 11 + 12 + 1 = 24

W1, W2, W3, W4, W5, W6 memiliki selisih yang sama yaitu dua.

Sumber :

Arsip pribadi (catatan mata kuliah Graph dan Analisis Algoritma)