MATRIKS PENYAJIAN GRAPH

1. Keterhubungan

Dalam keterhubungan sebuah graf, akan dikenal beberapa istilah-istilah berikut :

1. Walk : barisan simpul dan ruas

2. Trail : Walk dengan ruas yang berbeda

3. Path / Jalur : Walk dengan simpul yang berbeda

4. Cycle / Sirkuit : Trail tertutup dengan derajat setiap simpul = 2

1. Contoh Walk :

• A,  B, C, D, E, F, C, A, B,  D, C

• A, B, D, C, B, D, E

• a, b, c, d, b, c, g, h

2. Contoh Trail :

• A, B, C, D, E, F, C, A

• A, B, C, D, E, C, F

• A, B, D, C, E, D

3. Contoh Path/Jalur :

• C, E, F

• a, d, g, k

• B, C, E

4. Contoh Cycle/Sirkuit :

• B, D, C, B

• A,  B, C, A

• A, B, D, E, F, C, A

2. Critical Path

Critical Path

Merupakan Graph yang berbobot dan mempunyai arah.

Lihat graph berikut :

Simpul asal  : A

Simpul tujuan  : E

Dari simpul A ke simpul E dapat menggunakan alternative berikut :

Diperoleh : Critical Path (Lintas Kritis) : 29

            Shortest Path(Lintasan Pendek) : 20

MINIMUM SPANNING TREE

Merupakan Spanning Tree yang mempunyai Bobot dan tidak mempunyai arah dengan hasil penjumlahan bobotnya adalah minimum.

Lihat gambar Graph  berikut :

Langkah yang dilakukan untuk membentuk minimum spanning tree adalah :

• Bentuk kembali semua simpul tetapi tanpa ruas. 

• Gambar dan telusuri ruas dengan bobot paling kecil, seterusnya (secara ascending) hingga semua simpul terhubung 

Total minimum spaining tree : 29

3. Matriks Adjacency dan Matriks Incidence 

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.

Berikut Graph :

 

• Matriks Adjaceny

Berikut Graph :

• Contoh dari Matriks Incidence