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

Binary Tree Traversal Preorder, Inorder & Postorder

Binary tree traversal
Operasi ini terbagi menjadi 3 bentuk yaitu;

1.  Preorder (depth first order)
mempunayi urutan;
a.    Cetak isi simpul yang di kunjungi (root)
b.    Kunjungi Cabang Kiri
c.    Kunjungi Cabang Kanan

2.  Inorder(sympatic order), 

mempunyai urutan :
a.    Kunjungi Cabang Kiri
b.    Cetak isi simpul yang dikunjungi (Simpul Akar)
c.     Kunjungi Cabang Kanan

3.  Postorder, 
mempunyai urutan :
a.    Kunjungi Cabang Kiri
b.    Kunjungi Cabang Kanan
c.    Cetak isi simpul yang dikunjungi (Simpul Akar)

Pada ketiga cara kunjungan diatas, kunjungan ke Cabang Kiri dilakukan terlebih dahulu, baru kemudian kunjungan ke Cabang Kanan. Dengan orientasi semacam ini, Ketiga kunjungan diatas disebut dengan Left To Right Oriented (LRO).
Jika kunjungan ke Cabang Kanan dilakukan lebih dahulu baru kemudian kunjungan ke Cabang Kiri, maka Orientasi semacam ini disebut Right To Left Oriented (RLO).


Berikut contoh kunjungan pada pohon biner ;

1.    12, 22, 8, 19, 10, 9, 20, 4, 2, 6

Terdiri Dari : *.    Preorder    : 12, 8, 4, 2, 6, 10, 9, 22, 19, 20
                     *    Inorder      : 2, 6, 4, 8, 9, 10, 12, 19, 20, 22
                     *    Postorder   :6, 2, 4, 9, 10, 8, 20, 19, 22, 12

2.    2, 3, 4, 5, 50, 10, 15, 13, 20, 12, 10, 5, 7

Terdiri Dari  : *.    Preorder     : 2, 3, 4, 5, 50, 10, 15, 13, 12, 7, 20

                     *.    Inorder       : 7, 12, 13, 15, 12, 10, 50, 5, 4, 3, 2

                     *.    Postorder    : 7, 12, 13, 20, 15, 10, 50, 5, 4, 3, 2

 

3.    7, 13, 4, 6, 5, 9, 15, 20, 60, 14, 40, 70

Terdiri Dari : *.    Preorder     : 7, 4, 6, 5, 9, 13, 15, 14, 20, 60, 40, 70

                    *     Inorder       : 5, 6, 9, 4, 7, 40, 60, 70, 14, 15, 20, 13
                    *    Postorder    : 5, 9, 6, 4, 40, 70, 60, 14, 20, 15, 13, 7







4.    50, 45, 55, 50, 40, 40, 60, 70, 40, 35, 30, 20, 80, 75, 85

Terdiri Dari : *    Preorder     : 50, 45, 40, 35, 30, 20, 55, 60, 70, 80, 75, 85
                    *    Inorder       : 20, 30, 35, 40, 45, 50, 75, 80, 85, 70, 60, 55
                    *    Postorder    : 20, 30, 35, 40, 45, 75, 85, 80, 70, 60, 55, 50

 

5.    12, 13, 11, 17, 19, 21, 20, 22, 13, 14, 18, 16, 15

Terdiri Dari :*     Preorder      : 12, 11, 13, 17, 14, 16, 15, 19, 18, 21, 20, 22
                   *.    Inorder        : 11, 12, 15, 16, 14, 17, 20, 21, 22, 18, 19, 13
                   *.    Postorder    : 11, 15, 16, 14, 20, 22, 21, 18, 19, 17, 13, 12

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