Graph & Matriks Penyajian Graph (Walk, Trial, Path, Cycle)

Contoh Walk, Trail, Path dan Cycle pada gambar di atas :

1. Walk
    1. a, b, c, d, c, g, h
    2. a, b, c, d, e, f, c, a, b, d, c
    3. a, b, d, c, b, d, e

2. Trial
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

3. Path
    1. a, d, g, k
    2. c, e, f
    3. b, c, e

4. Cycle
    1. b, d, c, b
    2. a, b, c, a
    3. a, b, d, e, f, c, a

Cartical Path
Cartical Path merupakan Graph yang berbobot dan mempunyai arah
Lihat Graph Berikut :

Dari simpul A ke simpul E

Dari simpul A kesimpul E menggunakan alternatif berikut :

Diperoleh :
Critical Path (Lintas Kritis ) : 29 Shotest Path ( Lintas Pendek ) : 20

Minimum Spainning Tree
Merupakan Spainning Tree yang mempunyai bobot dan tidak mempunyai arah dalam hasil penjumlahan bobotnya adalah minimum.

Lihat gambar graph berikut :

Langkah yang dilakukan untuk membentuk minimum spainning tree adalah :
1. Bentuk kembali semua simpul tetapi tanpa ruas
2. Gambar dan telusuri ruas dan bobot paling kecil ( secara ascending) hingga semua simpul terhubung

Dari graph di atas, didapat minimum spainning treenya yaitu :

                                                     Total minimum spainning tree : 29

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.

Martiks 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 arus (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 Graph :