GRAPH BERBOBOT DAN MEMPUNYAI ARAH, KETERHUBUNGAN,MATRIKS PENYAJIAN GRAPH

1. GRAPH BERBOBOT DAN MEMPUNYAI  ARAH

Simpul asal: 1

Simpul tujuan: 5

Ditanya :

1. Critical path?

2. Shortest path?

Jawab:

Diperoleh:

1. Critical path : 29

2. Shortest path: 20

2.  KETERHUBUNGAN

Walk atau perjalanan dalam Graph G adalah barisan simpul dan ruas berganti-ganti

Banyaknya ruas disebut Panjang Walk. Walk dapat ditulis lebih singkat dengan hanya menulis deretan ruas.

Trail adalah walk dengan semua ruas dalam barisan adalah berbeda.

Path adalah jalur walk yang semua simpul dalam barisan adalah berbeda, jadi suatu path pastilah sebuah tail.

Cycle atau sirkuit adalah suatu trail tertutup dengan derajat setiap simpulnya = 2.

 Dari gambar diatas bisa kita ambil contoh walk, trail, path, dan cycle :

Contoh walk :

1. a,b,c,d,b,c,g,h
2. A, B, C, D, E, F, C, A, B, D, C
3. A, B, D, C, B, D, E

Contoh trail :

1. A, B, D, C, E, D
2. C, A, B, C, D, E, C, F, E
3. A, B, C, E, F, C, A

Contoh path :

1. a, d, g, k
2. C, E, F
3. B, C, E

Contoh cycle :

1. B, D, C, B
2. A, B, C, A
3. A, B, D, E, F, C, A

3. MATRIKS PENYAJIAN GRAPH

Misalnya disajikan Graph G dalam Matriks  ruas B ukuran (M x 2), maka setiap baris Matriks menyatakan ruas, misalnya baris (4  7) menyatakan ada ruas menghubungkan simpul 4 dan 7.

Matriks Adjacency dari Graph G, yaitu Matriks yang menghubungkan Vertex dengan Vertex,  tanpa ruas sejajar adalah Matriks A berukuran (N x N) yang bersifat :

aij=      1 , bila ada ruas (Vi, Vj)
0, bila dalam hal lain.

Matriks Incidence dari Graph G, yaitu Matriks yang  Matriks Incidence dari Graph G, yaitu Matriks yang menghubungkan Vertex dengan Edge, tanpa self-loop didefinisikan sebagai Matriks M berukuran (NXM) sebagai berikut :

mij =    1, bila ada ruas ej berujung di simpul Vi

0, dalam hal lain.

Contoh dari Graph

Matriks Adjaceny

\

Matriks Incidence