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

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 :

 

Matriks Adjacency :

Contoh Graph :

Matriks Incidence : 

 

Nama   : MARDIYAH
Kelas   : 12.2C.06
Nim     : 12130506

Binary Tree Traversal Preorder, Inorder, & Postorder

Binary Tree Traversal
Operasi ini terbagi menjadi 3 bentuk, yaitu :

1. Preorder ( Depth First Order )
    Mempunyai 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 di kunjungi ( Simpul Akar )
    c. Kunjungi Cabang Kanan


3. Postorder 
    Mempunyi urutan :
    a. Kunjungi Cabang Kiri
    b. Kunjungi Cabang Kanan
    c. Cetak isi simpul yang di kunjungi ( Simpul Akar )

Pada ketingan kunjungan di atas, kunjungan ke cabang kiri di lakukan terlebih dahulu , baru kemudian kunjungan kecabang kakan. Dengan orientasi semacam ini , ketiga kunjungan di atas di sebut dengan Left To Right Oriented (LRO) .
Jika kunjungan kecabang kanan dilakukan lebih dahulu baru kemudian kunjungan ke cabang kiri . maka orientasi semacam ini disebut Right To Left Oriented (RLO).



Berikut 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, 12, 7, 20
 
    Terdiri Dari :    > Preorder      : 2, 3, 4, 5, 50, 10, 15, 13, 12, 7, 20
                           > Inorder        : 7, 13, 12, 15, 12, 10, 50, 5, 4, 3, 2
                           > Postorder    : 7, 13, 12, 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 :       > Perorder    : 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     : MARDIYAH
Kelas     : 12.2C.06
Nim       : 12130506

Tugas Struktur Data

Buatlah Pohon Biner Dari Barisan Bilangan Berikut :


1. Soal : 12, 22, 8,19,10, 9, 20, 4, 2, 6
    Root (Akar): 12
    1. 22 > 12 maka 22 di kanan 12
    2. 8 < 12 maka 8 di kiri 12
    3. 19 > 12, 19 < 22 maka 19 di kiri 19
    4. 10 < 22, 10 < 19 maka 10 di kiri 19
    5. 9 < 10 maka 9 di kiri 10
    6. 20 > 10 maka 20 di kanan 10
    7. 4 < 10, 4 < 9 maka 4 di kiri 9
    8. 2 < 4 maka 2 di kiri 4
    9. 6 > 4 maka 6 di kanan 4

2. Soal : 2, 3, 4, 5, 50, 10, 15, 13, 20, 12, 10, 5, 7
    Root (Akar) :
    1. 3 > 2 maka 3 di kanan 2
    2. 4 > 2, 4 > 3 maka 4 di kanan 3
    3. 5 > 3, 5 > 4 maka 5 di kanan 4
    4. 50 > 5 maka 50 di kanan 5
    5. 10 > 5, 10 < 50 maka 10 di kiri 50
    6. 15 < 50, 15 > 10 maka 15 di kanan 10
    7. 13 > 10, 13 < 15 maka 13 di kiri 15
    8. 20 > 15 maka 20 di kanan 15
    9. 12 < 13 maka 12 di kanan 13
    10. 10 < 13, 10 < 12 maka 10 di kiri 12
    11. 5 < 10 maka 5 di kiri 10
    12. 7 < 10, 7 > 5 maka 7 di kanan 5

3. Soal : 7, 13, 4, 6, 5, 9, 15, 20, 60, 14, 40, 70
    Root (Akar) : 7
    1. 13 > 7 maka 13 di kanan 7
    2. 4 < 7 maka 4 di kiri 7
    3. 6 < 7, 6 > 4 maka 6 di kanan 4
    4. 5 < 7, 5 > 4, 5 < 6 maka 5 di kiri 6
    5. 9 > 7, 9 < 13 maka 9 di kiri 13
    6. 15 > 13 maka 15 di kanan 13
    7. 20 > 15 maka 20 di kanan 15
    8. 60 > 20 maka 60 di kanan 20
    9. 14 < 60 maka 14 di kiri 60
    10. 40 < 60, 40 > 14 maka 40 di kanan 14
    11. 70 > 14, 70 > 40 maka 70 di kanan 40

4.Soal  : 50, 45, 55, 50, 40, 50, 60, 70, 40, 35, 30, 20, 80, 75, 85
   Root (Akar) : 50
   1. 45 < 50 maka 45 di kiri 50
   2. 55 > 50 maka 55 di kanan 50
   3. 40 < 50, 40 < 45 maka 40 di kiri 45
   4. 50 = 50,  50 < 55 maka 50 di kiri 55
   5. 60 > 50, 60 > 55 maka 60 di kanan 55
   6. 70 > 50, 70 > 55, 70 > 60 maka 70 di kanan 60
   7. 40 < 60 maka 40 di kiri 60
   8. 35 < 40, 35 < 70 maka 35 di kiri 40
   9. 30 < 35 maka 30 di kiri 35
  10. 20 < 30 maka 20 di kiri 30
  11. 80 > 30 maka 80 di kanan 30
  12. 75 > 3, 75 < 80 maka 75 di kiri 80
  13. 85 > 80 maka 85 di kanan 80

5. Soal : 12, 13, 11, 17, 19, 21, 20, 22, 13, 14, 18, 16, 15
    Root (Akar) : 12
   1. 13 > 12 maka 13 di kanan 12
   2. 11 < 12 maka 11 di kiri 12
   3. 17 > 12, 17 > 13 maka 17 di kanan 13
   4. 19 > 13, 19 > 17 maka 19 di kanan 17
   5. 21 > 17, 21 > 19 maka 21 di kanan 19
   6. 20 > 19, 20 < 21 maka 20 di kiri 19
   7. 22 > 21 maka 22 di kanan 21
   8. 13 < 21, 13 < 20 maka 13 d kiri 20
   9. 14 < 20, 14 > 13 maka 14 di kanan 13
   10. 16 > 14, 16 < 18 maka 16 di kiri 18
   11. 15 < 18, 15 < 16 maka 15 di kiri 16

Nama   : MARDIYAH
Kelas    : 12.2C.06
Nim      : 12130506