GRAPH BERBOBOT DAN MEMPUNYAI ARAH, KETERHUBUNGAN,MATRIKS PENYAJIAN GRAPH

1. GRAPH BERBOBOT DAN MEMPUNYAI  ARAH

Simpul asal: 1

Simpul tujuan: 5

Ditanya :

1. Critical path?

2. Shortest path?

Jawab:

Diperoleh:

1. Critical path : 29

2. Shortest path: 20

2.  KETERHUBUNGAN

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.

 Dari gambar diatas bisa kita ambil contoh walk, trail, path, dan cycle :

Contoh 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

Contoh 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

Contoh path :

1. a, d, g, k
2. C, E, F
3. B, C, E

Contoh cycle :

1. B, D, C, B
2. A, B, C, A
3. A, B, D, E, F, C, A

3. 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 dari Graph

Matriks Adjaceny

\

Matriks Incidence

Kunjungan Pohon Biner

Pembahasan lanjutan dari postingan saya sabelumnya tentang Struktur Pohon Biner, kali ini saya akan membahas/memberikan contoh kunjunga pohon biner dari struktur pohon biner.
Untuk lebih jelasnya, sekidit saya berikan gambaran tentang Kunjungan pohon biner.

Kunjungan pada pohon biner merupakan salah satu operasi yang sering dilakukan pada suatu pohon biner tepat satu kali(Binary Tree Traversal).

Operasi ini terbagi menjadi 3 bentuk yaitu;

1.    Kunjungan secara Preorder (Depth First Order)
       Dengan Urutan Kunjungan Pohon Biner sebagai berikut:

a)      Cetak isi simpul yang di kunjungi (root)

b)      Kunjungi Cabang Kiri

c)        Kunjungi Cabang Kanan

2.     Kunjungan secara inorder(Sympatic Order), dengan urutan:

a)      Kunjungi Cabang Kiri

b)      Cetak isi simpul yang dikunjungi (Simpul Akar)

c)       Kunjungi Cabang Kanan

3.    Kunjungan secara Postorder, mempunyai urutan :

            a)      Kunjungi Cabang Kiri

            a)      Kunjungi Cabang Kanan

            b)      Cetak isi simpul yang dikunjungi (Simpul Akar)

      Dari barisan bilangan saya akan membuat pohon biner serta ketiga kunjungan terhadap pohon biner tersebut yaitu Preorder,Inorder dan Posorder.

         Sekian dan semoga bermanfaat

Penyajian Pohon Binar (Binary Tree)

Pada kesempatan ini saya akan mencoba membahas tentang penyajian Pohon Biner

•  Tree dapat dibuat dengan menggunakan linked list secara rekursif.

•  Linked list yang digunakan adalah double linked list non circular

•  Data yang pertama kali masuk akan menjadi node root.

•  Data yang lebih kecil dari data node root akan masuk dan menempati node kiri dari node root, sedangkan jika lebih besar dari data node root, akan masuk dan menempati node di sebelah kanan node root.

Sebagai contoh:

Buatlah pohon biner dari barisan bilangan berikut:

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

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

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

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

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

Maka hasil dari soal tersbut diatas yaitu:

Contoh Pemetaan RMO dan CMO Array Dimensi 3

Minggu yang lalu telah di bahas tentang Pemetaan Array dimensi 1 dan 2. Pada kesempatan ini kita akan lanjutkan membahas sekaligus menyelesaikan soal Pemataan RMO dan CMO Array dimensi 3.

Berikut Soal dan cara penyelesaiannya:

SOAL :

Buatlah Ilustrasi Tabel, Pemetaan RMO & CMO, Jalur Perpindahan Serta Hitunglah hasilnya dalam array-array dibawah ini:

1.       Array Long A[5][4][2] dengan nilai awal A[0][1][0] = 00AF(H). Berapa nilai A[4][2][1]..?

2.       Array Long A[5][5][2] dengan nilai awal A[1][1][0] = 5F(H). Berapa nilai A[4][2][1]..?

3.       Array Long A[5][5][2] dengan nilai awal A[1][1][0] = 00AF(H). Berapa nilai A[4][4][1]..?

Pemetaan RMO dan CMO Array Dimensi 3

No 1.

Terdapat array tiga dimensi dengan long A[5][4][2].

Diketahui &A[0][1][0]=00AF(H),

Ditanya &A[4][2][1] =....?

Tabel array  [BARIS][KOLOM][GROUP] 

Group 0	0	1	2	3
0		00AF(h)
1
2
3
4

Group 1	0	1	2	3
0
1
2
3
4			&A[4][2][1]..?

Pemetaan RMO

1. Hitung besarnya perpindahan group: 1-0=1
2. Total perpindahan 1 group = banyak baris dikali banyak kolom =5*4=20
3. Hitung bersarnya perpindahan baris: 4-0=4
4. Dalam 1 baris terdapat 4 kolom sehingga total perpindahan baris =4*4=16
5. Total perpindahan kolom adalah :2-1=1
6. Total dari seluruh perpindahan (Group + Baris + Kolom) =20+16+1=37

Jalur perpindahan:               A[0][2][0] → A[0][3][0] → A[1][0][0] → A[1][1][0] →A[1][2][0] →

                                                A[1][3][0] → A[2][0][0] → A[2][1][0] →A[2][2][0] → A[2][3][0] →

                                                A[3][0][0]→A[3][1][0] → A[3][2][0] → A[3][3][0] → A[4][0][0] →

                                                A[4][1][0] →A[4][1][0] → A[4][3][0] → A[0][0][1] → A[0][1][1] →

                                                A[0][2][1] →A[0][3][1] → A[1][0][1] → A[1][1][1] → A[1][2][1] →

                                                A[1][3][1] →A[2][0[1] → A[2][1][1] → A[2][2][1] → A[2][3][1] →

                                                A[3][0][1] →A[3][1[1] → A[3][2][1] → A[3][3][1] → A[4][0][1] →

                                                A[4][1][1] →A[4][2[1]

Hasil: 00AF(H) + (37(D)*2)                     = (0*16³)+(0*16²)+(10 * 16¹)+(15 * 16⁰)(D) + 74(D)

                                                                = 175(D) + 74(D)

                                                                = 267(D)

                                                                = F9(H)

Pemetaan CMO

1. Hitung besarnya perpindahan group:1-0=1
2. Total perpindahan 1 group = banyak baris dikali banyak kolom =5*4=20
3. Hitung bersarnya perpindahan kolom: 2-1=1
4. Dalam 1 kolom terdapat 5 baris sehingga total perpindahan kolom =1*5=5
5. Total perpindahan baris adalah :4-0=4
6.  Total dari seluruh perpindahan (Group + Baris + Kolom) =20+4+5=29

Jalur perpindahannya :        A[1][1][0] → A[2][1][0] → A[3][1][0] → A[4][1][0] →A[0][2][0] →

                                                A[1][2][0] → A[2][2][0] → A[3][2][0] →A[4][2][0] → A[0][3][0] →

                                                A[1][3][0]→A[2][3][0] → A[3][3][0] → A[4][3][0] → A[0][0][1] →

                                                A[1][0][1] →A[2][0][1] → A[3][0][1] → A[4][0][1] → A[0][1][1] →

                                                A[1][1][1] →A[2][1][1] → A[3][1][1] → A[4][1][1] → A[0][2][1] →

                                                A[1][2][1] →A[2][2[1] → A[3][2][1] → A[4][2][1] →

Hasil: 00AF(H) + (29(D)*2)                     = (0*16³)+(0*16²)+(10 * 16¹)+(15 * 16⁰)(D) + 58(D)

                                                                = 175(D) + 58(D)

                                                                = 233(D)

                                                                = E9(H)

No 2.

Terdapat array tiga dimensi dengan long A[5][5][2].

Diketahui &A[1][1][0]=5F(H),

Ditanya &A[4][2][1] =....?

Tabel array  [BARIS][KOLOM][GROUP]

Group 0	0	1	2	3	4
0
1		5F(H)
2
3
4

Group 1	0	1	2	3	4
0
1
2
3
4			&A[4][2][1]..?

Pemetaan RMO

7. Hitung besarnya perpindahan group: 1-0=1
8. Total perpindahan 1 group = banyak baris dikali banyak kolom =5*5=25
9. Hitung bersarnya perpindahan baris: 4-1=3
10. Dalam 1 baris terdapat 5 kolom sehingga total perpindahan baris =3*5=15
11. Total perpindahan kolom adalah :2-1=1
12. Total dari seluruh perpindahan (Group + Baris + Kolom) =25+15+1=41

Jalur perpindahan :              A[1][2][0] → A[1][3][0] → A[1][4][0] → A[2][0][0] →A[2][1][0] →

                                                A[2][2][0] → A[2][3][0] → A[2][4][0] →A[3][0][0] → A[3][1][0] →

                                                A[3][2][0]→A[3][3][0] → A[3][4][0] → A[4][0][0] → A[4][1][0] →

                                                A[4][2][0] →A[4][3][0] → A[4][4][0] → A[0][0][1] → A[0][1][1] →

                                                A[0][2][1] → A[0][3][1] → A[0][4][1] → A[1][0][1] →A[1][1][1] →

                                                A[1][2][1] →A[1][3[1] → A[1][4][1] →A[2][0][1] → A[2][1][1] →

                                                A[2][2][1] →A[2][3][1] →A[2][4][1] → A[3][0[1] → A[3][1][1] →

                                                A[3][2][1] → A[3][3][1] →A[3][4][1] →A[4][0[1] → A[4][1][1] →

                                                A[4][2][1]

Hasil: 5F(H) + (41(D)*2)          = (5 * 16¹)+(15 * 16⁰)(D) + 82(D)

                                                = 95(D) + 82(D)

                                                = 177(D)

                                                = B1(H)

Pemetaan CMO

7. Hitung besarnya perpindahan group:1-0=1
8. Total perpindahan 1 group = banyak baris dikali banyak kolom =5*5=25
9. Hitung bersarnya perpindahan kolom: 2-1=1
10. Dalam 1 kolom terdapat 5  baris sehingga total perpindahan kolom =1*5=5
11. Total perpindahan baris adalah :4-1=3
12.  Total dari seluruh perpindahan (Group + Baris + Kolom) =25+3+5=33

Jalur pemindahan :              A[2][1][0] → A[3][1][0] → A[4][1][0] → A[0][2][0] →A[1][2][0] →

                                                A[2][2][0] → A[3][2][0] → A[4][2][0] →A[0][3][0] → A[1][3][0] →

                                                A[2][3][0]→A[3][3][0] → A[4][3][0] → A[0][4][0] → A[1][4][0] →

                                                A[2][4][0] →A[3][4][0] → A[4][4][0] → A[0][0][1] → A[1][0][1] →

                                                A[2][0][1] → A[3][0][1] → A[4][0][1] → A[0][1][1] →A[1][1][1] →

                                                A[2][1][1] →A[3][1[1] → A[4][1][1] →A[0][2][1] → A[1][2][1] →

                                                A[2][2][1] →A[3][2][1] →A[4][2][1]

Hasil: 5F(H) + (33(D)*2)         = (5 * 16¹)+(15 * 16⁰)(D) + 66(D)

                                                = 95(D) + 66(D)

                                                = 161(D)

                                                = A1(H)               

No 3.

 Terdapat array tiga dimensi dengan long A[5][5][2].

Diketahui &A[1][1][0]=00AF(H),

Ditanya &A[4][4][1] =....?

Tabel array  [BARIS][KOLOM][GROUP]

Group 0	0	1	2	3	4
0
1		00AF(h)
2
3
4

Group 1	0	1	2	3	4
0
1
2
3
4					&A[4][4][1]..?

Pemetaan RMO

13. Hitung besarnya perpindahan group: 1-0=1
14. Total perpindahan 1 group = banyak baris dikali banyak kolom =5*5=25
15. Hitung bersarnya perpindahan baris: 4-1=3
16. Dalam 1 baris terdapat 5 kolom sehingga total perpindahan baris =3*5=15
17. Total perpindahan kolom adalah :4-1=3
18. Total dari seluruh perpindahan (Group + Baris + Kolom) =25+15+3=43

Jalur pemindahan :              A[1][2][0] → A[1][3][0] → A[1][4][0] → A[2][0][0] →A[2][1][0] →

                                                A[2][2][0] → A[2][3][0] → A[2][4][0] →A[3][0][0] → A[3][1][0] →

                                                A[3][2][0]→A[3][3][0] → A[3][4][0] → A[4][0][0] → A[4][1][0] →

                                                A[4][2][0] →A[4][3][0] → A[4][4][0] → A[0][0][1] → A[0][1][1] →

                                                A[0][2][1] → A[0][3][1] → A[0][4][1] → A[1][0][1] →A[1][1][1] →

                                                A[1][2][1] →A[1][3[1] → A[1][4][1] →A[2][0][1] → A[2][1][1] →

                                                A[2][2][1] →A[2][3][1] →A[2][4][1] → A[3][0[1] → A[3][1][1] →

                                                A[3][2][1] → A[3][3][1] →A[3][4][1] →A[4][0[1] → A[4][1][1] →

                                                A[4][2][1] → A[4][3][1] →A[4][4][1]

Hasil: 00AF(H) + (43(D)*2)                     = (0*16³)+(0*16²)+(10 * 16¹)+(15 * 16⁰)(D) + 86(D)

                                                                = 175(D) + 86(D)

                                                                = 261(D)

                                                                = 105(H)

Pemetaan CMO

13. Hitung besarnya perpindahan group:1-0=1
14. Total perpindahan 1 group = banyak baris dikali banyak kolom =5*5=25
15. Hitung bersarnya perpindahan kolom: 4-1=3
16. Dalam 1 kolom terdapat 5 baris sehingga total perpindahan kolom =3*5=15
17. Total perpindahan baris adalah :4-1=3
18.  Total dari seluruh perpindahan (Group + Baris + Kolom) =25+3+15=43

Jalur pemindahan :                

                                                A[2][1][0] → A[3][1][0] → A[4][1][0] → A[0][2][0] →A[1][2][0] →

                                                A[2][2][0] → A[3][2][0] → A[4][2][0] →A[0][3][0] → A[1][3][0] →

                                                A[2][3][0]→A[3][3][0] → A[4][3][0] → A[0][4][0] → A[1][4][0] →

                                                A[2][4][0] →A[3][4][0] → A[4][4][0] → A[0][0][1] → A[1][0][1] →

                                                A[2][0][1] → A[3][0][1] → A[4][0][1] → A[0][1][1] →A[1][1][1] →

                                                A[2][1][1] →A[3][1[1] → A[4][1][1] →A[0][2][1] → A[1][2][1] →

                                                A[2][2][1] →A[3][2][1] →A[4][2][1] →A[0][3][1] → A[1][3][1] →

                                                A[2][3][1] →A[3][3[1] → A[4][3][1] →A[0][4][1] → A[1][4][1] →

                                                A[2][4][1] →A[3][4][1] →A[4][4][1]

Hasil: 00AF(H) + (43(D)*2)                     = (0*16³)+(0*16²)+(10 * 16¹)+(15 * 16⁰)(D) + 86(D)

                                                                = 175(D) + 86(D)

                                                                = 261(D)

                                                                = 105(H)