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

Graph & Matriks Penyajian Grap(Walk,Trail,Path,Cycle)

• 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.

Contoh walk, trail, path, dan cycle pada gambar di atas: 
1. 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

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

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

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 :

	PATH	BOBOT
Alternatif:	A→C→E	20
	A→D→E	28
	A→C→B→E	25
	A→D→B→E	20
	A→D→B→C→E	29

Diperoleh :      Critical Path (Lintas Kritis) : 29

                        Shortest Path(Lintasan Pendek) : 20

Minimum Spainning Tree

merupakan Spainning Tree yang mempunyai Bobot dan tidak mempunyai arah dengan hasil penjumlahan bobotnya adalah minimum.

Lihat gambar Graph  berikut :

Langkah yang dilakukan untuk membentuk minimum spainning tree adalah :

• Bentuk kembali semua simpul tetapi tanpa ruas. 
• Gambar dan telusuri ruas dengan bobot paling kecil, seterusnya (secara ascending) hingga semua simpul terhubung.

dari graph di atas, didapatkan minimum spainning treenya yaitu :

Total minimum spaining 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.

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 graph :

Matriks Adjacency :

contoh graph :  

Matriks Incidence :   

Nama : Yasinta Octalia
Kelas : 12.2C.06
NIM : 12130426