MATRIKS PENYAJIAN GRAPH

1. Keterhubungan

Dalam keterhubungan sebuah graf, akan dikenal beberapa istilah-istilah berikut :

1. Walk : barisan simpul dan ruas

2. Trail : Walk dengan ruas yang berbeda

3. Path / Jalur : Walk dengan simpul yang berbeda

4. Cycle / Sirkuit : Trail tertutup dengan derajat setiap simpul = 2

1. Contoh Walk :

• A,  B, C, D, E, F, C, A, B,  D, C

• A, B, D, C, B, D, E

• a, b, c, d, b, c, g, h

2. Contoh Trail :

• A, B, C, D, E, F, C, A

• A, B, C, D, E, C, F

• A, B, D, C, E, D

3. Contoh Path/Jalur :

• C, E, F

• a, d, g, k

• B, C, E

4. Contoh Cycle/Sirkuit :

• B, D, C, B

• A,  B, C, A

• A, B, D, E, F, C, A

2. Critical Path

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 :

Diperoleh : Critical Path (Lintas Kritis) : 29

            Shortest Path(Lintasan Pendek) : 20

MINIMUM SPANNING TREE

Merupakan Spanning Tree yang mempunyai Bobot dan tidak mempunyai arah dengan hasil penjumlahan bobotnya adalah minimum.

Lihat gambar Graph  berikut :

Langkah yang dilakukan untuk membentuk minimum spanning tree adalah :

• Bentuk kembali semua simpul tetapi tanpa ruas. 

• Gambar dan telusuri ruas dengan bobot paling kecil, seterusnya (secara ascending) hingga semua simpul terhubung 

Total minimum spaining tree : 29

3. Matriks Adjacency dan Matriks Incidence 

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.

Berikut Graph :

 

• Matriks Adjaceny

Berikut Graph :

• Contoh dari Matriks Incidence

Kunjungan pada 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;
1. Kunjungan secara preorder (depth first order) yang mempunyai urutan;
• Cetak isi simpul yang di kunjungi (root)
• Kunjungi Cabang Kiri
• Kunjungi Cabang Kanan
2. Kunjungan secara inorder(sympatic order), yang mempunyai urutan :
• Kunjungi Cabang Kiri
• Cetak isi simpul yang dikunjungi (Simpul Akar)
• Kunjungi Cabang Kanan

3. Kunjungan secara Postorder, yang mempunyai urutan :
• Kunjungi Cabang Kiri
• Kunjungi Cabang Kanan
• 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
a. Preorder : 12, 8, 4, 2, 6, 10, 9, 22, 19, 20
b. Inorder : 2, 6, 4, 8, 9, 10, 12, 19, 20, 22
c. 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
a. Preorder : 2, 3, 4, 5, 50, 10, 15, 13, 12, 7, 20
b. Inorder : 7, 12, 13, 15, 12, 10, 50, 5, 4, 3, 2
c. 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
a. Preorder : 7, 4, 6, 5, 9, 13, 15, 14, 20, 60, 40, 70
b. Inorder : 5, 6, 9, 4, 7, 40, 60, 70, 14, 15, 20, 13
c. 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
a. Preorder : 50, 45, 40, 35, 30, 20, 55, 60, 70, 80, 75, 85
b. Inorder : 20, 30, 35, 40, 45, 50, 75, 80, 85, 70, 60, 55
c. 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
a. Preorer : 12, 11, 13, 17, 14, 16, 15, 19, 18, 21, 20, 22
b. Inorder : 11, 12, 15, 16, 14, 17, 20, 21, 22, 18, 19, 13
c. Postorder : 11, 15, 16, 14, 20, 22, 21, 18, 19, 17, 13, 12

Penyajian Pohon Binar (Binary Tree)

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

Berikut Contoh Penyajian Pohon Binar :

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

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

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

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

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

selamat mencoba,,, :)

PEMETAAN DIMENSI TIGA :)

Pemetaan RMO dan CMO Array Dimensi 3

Berikut cara menyelesaikan soal pemetaan array dimensi 3 tanpa menggunakan rumus ;
Contoh soal;
1. Terdapat array tiga dimensi dengan Long A[5][5][2] .
Diketahui nilai awal &A[1][1][0] = 5F(H), Ditanya & A[4][2][1] =....?

Ilustrasi Tabel A[5][5][2]

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			Ditanya?

Pemetaan RMO
1. Hitung besarnya perpindahan group : 1 dikurang 0 = 1
2. Total perpindahan 1 group : banyak baris dikali banyak kolom = 5 x 5 = 25.
3. Hitung bersarnya perpindahan baris : 4 dikurang 1 = 3.
4. Dalam 1 baris terdapat 5 kolom sehingga total perpindahan baris = 3 dikali 5 = 15.
5. Total perpindahan kolom adalah 2 dikurang 1 = 1.
6. Total dari seluruh perpindahan (Group + Baris + Kolom) = 25 + 15 +1 = 41
Jalur perpindahan
x[1][2][0] → x[1][3][0] → x[1][4][0] → x[2][0][0] → x[2][1][0] →
x[2][2][0] → x[2][3][0] → x[2][4][0] → x[3][0][0] → x[3][1][0] →
x[3][2][0] → x[3][3][0] → x[3][4][0] → x[4][0][0] → x[4][1][0] →
x[4][2][0] → x[4][3][0] → x[4][4][0] → x[0][0][1] → x[0][1][1] →
x[0][2][1] → x[0][3][1] → x[0][4][1] → x[1][0][1] → x[1][1][1] →
x[1][2][1] → x[1][3][1]  → x[1][4][1] →  x[2][0][1] → x[2][1[1] →
x[2][2][1] → x[2][3][1] → x[2][4][1] → x[3][0][1] → x[3][1][1] →
x[3][2][1] → x[3][3][1] → x[3][4][1] → x[4][0][1] → x[4][1[1] →
x[4][2][1]


Hasil:

= 5F(H)  + (41(D)  * 4)
Konversi nilai 5F(H)  ke desimal;
 F(H) = 15(D)
5F(H)  = (5 * 161) + (15 * 160)
= 80 + 15
= 95(D)
= 95(D)  + 164(D)
= 259(D)

konversi nilai  259(D) ke hexa    ;
259/16 = 16, sisa 3
16/16 = 1, sisa 0
1/16 = 0, sisa 1
 = 103(H) (di baca dari bawah)

Hasilnya yaitu  103(H)


Pemetaan CMO
1. Hitung besarnya perpindahan group : 1 dikurang 0 = 1
2. Total perpindahan 1 group : banyak baris dikali banyak kolom = 5 x 5 = 25.
3. Hitung bersarnya perpindahan kolom : 2 dikurang 1 = 1.
4. Dalam 1 kolom terdapat 5 baris sehingga total perpindahan kolom = 1 dikali 5 = 5.
5. Total perpindahan baris adalah 4 dikurang 1 = 3.
6. Total dari seluruh perpindahan (Group + Baris + Kolom) = 25 + 5 +3 = 33
Jalur perpindahan
x[2][1][0] → x[3][1][0] → x[4][1][0] → x[0][2][0] → x[1][2][0] →
x[2][2][0] → x[3][2][0] → x[4][2][0] → x[0][3][0] → x[1][3][0] →
x[2][3][0] → x[3][3][0] → x[4][3][0] → x[0][4][0] → x[1][4][0] →
x[2][4][0] → x[3][4][0] → x[4][4][0] → x[0][0][1] → x[1][0][1] →
x[2][0][1] → x[3][0][1] → x[4][0][1] → x[0][1][1] → x[1][1][1] →
x[2][1][1] →x[3][1][1] → x[4][1][1] → x[0][2][1] → x[1][2][1] →
x[2][2][1] →x[3][2][1] → x[4][2][1]


Hasil
= 5F(H ) + (33(D) * 4)
Konversi nilai 5F(H)  ke desimal;
 F(H) = 15(D)
5F(H)  = (5 * 161) + (15 * 160)
= 80 + 15
= 95(D)
= 95(D)  + 132(D)
= 227(D)

konversi nilai  227(D) ke hexa ;
227/16 = 14, sisa 3
14/16 = 0, sisa 14 (di tulis E)
 = E3(H) (di baca dari bawah)

Hasilnya yaitu  E3(H)



2. Terdapat array tiga dimensi dengan Long A[5][5][2] .
Diketahui nilai awal &A[1][1][0] =00CB(H), Ditanya & A[4][3][1] =..?

Ilustrasi Tabel A[5][5][2]

Group 0	0	1	2	3	4
0
1		CB(H)
2
3
4

Group 1	0	1	2	3	4
0
1
2
3
4				Ditanya?

Pemetaan RMO
1. Hitung besarnya perpindahan group : 1 dikurang 0 = 1
2. Total perpindahan 1 group : banyak baris dikali banyak kolom = 5 x 5 = 25.
3. Hitung bersarnya perpindahan baris : 4 dikurang 1 = 3.
4. Dalam 1 baris terdapat 5 kolom sehingga total perpindahan baris = 3 dikali 5 = 15.
5. Total perpindahan kolom adalah 3 dikurang 1 = 2.
6. Total dari seluruh perpindahan (Group + Baris + Kolom) = 25 + 15 +2 = 42
Jalur perpindahan
x[1][2][0] → x[1][3][0] → x[1][4][0] → x[2][0][0] → x[2][1][0] →
x[2][2][0] → x[2][3][0] → x[2][4][0] → x[3][0][0] → x[3][1][0] →
x[3][2][0] → x[3][3][0] → x[3][4][0] → x[4][0][0] → x[4][1][0] →
x[4][2][0] → x[4][3][0] → x[4][4][0] → x[0][0][1] → x[0][1][1] →
x[0][2][1] → x[0][3][1] → x[0][4][1] → x[1][0][1] → x[1][1][1] →
x[1][2][1] → x[1][3][1]  → x[1][4][1] →  x[2][0][1] → x[2][1[1] →
x[2][2][1] → x[2][3][1] → x[2][4][1] → x[3][0][1] → x[3][1][1] →
x[3][2][1] → x[3][3][1] → x[3][4][1] → x[4][0][1] → x[4][1[1] →
x[4][2][1] → x[4][3][1]

  Hasil:

= CB(H)  + (41(D)  * 4)
Konversi nilai CB(H)  ke desimal;
 C(H) = 12(D)
B(H) = 11(D)
CB(H)  = (12 * 161) + (11 * 160)
= 192 + 15
= 207(D)
= 207(D)  + 164(D)
= 371(D)

konversi nilai  371(D) ke hexa    ;
371/16 = 23, sisa 3
23/16 = 1, sisa 7
7/16 = 1, sisa 1
 = 173(H) (di baca dari bawah)

Hasilnya yaitu  173(H)





Pemetaan CMO
1. Hitung besarnya perpindahan group : 1 dikurang 0 = 1
2. Total perpindahan 1 group : banyak baris dikali banyak kolom = 5 x 5 = 25.
3. Hitung bersarnya perpindahan kolom : 3 dikurang 1 = 2.
4. Dalam 1 kolom terdapat 5 baris sehingga total perpindahan kolom = 2 dikali 5 = 10.
5. Total perpindahan baris adalah 4 dikurang 1 = 3.
6. Total dari seluruh perpindahan (Group + Baris + Kolom) = 25 + 10 +3 = 38
Jalur perpindahan
x[2][1][0] → x[3][1][0] → x[4][1][0] → x[0][2][0] → x[1][2][0] →
x[2][2][0] → x[3][2][0] → x[4][2][0] → x[0][3][0] → x[1][3][0] →
x[2][3][0] → x[3][3][0] → x[4][3][0] → x[0][4][0] → x[1][4][0] →
x[2][4][0] → x[3][4][0] → x[4][4][0] → x[0][0][1] → x[1][0][1] →
x[2][0][1] → x[3][0][1] → x[4][0][1] → x[0][1][1] → x[1][1][1] →
x[2][1][1] →x[3][1][1] → x[4][1][1] → x[0][2][1] → x[1][2][1] →
x[2][2][1] → x[3][2][1] → x[4][2][1] → x[0][3][1] → x[1][3][1] →
x[2][3][1] → x[3][3][1] → x[4][3][1]

  Hasil:

= CB(H)  + (38(D)  * 4)
Konversi nilai CB(H)  ke desimal;
 C(H) = 12(D)
B(H) = 11(D)
CB(H)  = (12 * 161) + (11 * 160)
= 192 + 15
= 207(D)
= 207(D)  + 152(D)
= 359(D)

konversi nilai  359(D) ke hexa    ;
359/16 = 22, sisa 7
22/16 = 1, sisa 6
1/16 = 0, sisa 1
 = 167(H) (di baca dari bawah)

Hasilnya yaitu  167(H)


3. Terdapat array tiga dimensi dengan Long A[5][5][2] .
Diketahui nilai awal &A[1][1][0] = 00AF(H), Ditanya & A[4][4][1] =..?

Ilustrasi Tabel A[5][5][2]

Group 0	0	1	2	3	4
0
1		AF(H)
2
3
4

Group 1	0	1	2	3	4
0
1
2
3
4					Ditanya?

Pemetaan RMO
1. Hitung besarnya perpindahan group : 1 dikurang 0 = 1
2. Total perpindahan 1 group : banyak baris dikali banyak kolom = 5 x 5 = 25.
3. Hitung bersarnya perpindahan baris : 4 dikurang 1 = 3.
4. Dalam 1 baris terdapat 5 kolom sehingga total perpindahan baris = 3 dikali 5 = 15.
5. Total perpindahan kolom adalah 4 dikurang 1 = 3.
6. Total dari seluruh perpindahan (Group + Baris + Kolom) = 25 + 15 +3 = 43
Jalur perpindahan
x[1][2][0] → x[1][3][0] → x[1][4][0] → x[2][0][0] → x[2][1][0] →
x[2][2][0] → x[2][3][0] → x[2][4][0] → x[3][0][0] → x[3][1][0] →
x[3][2][0] → x[3][3][0] → x[3][4][0] → x[4][0][0] → x[4][1][0] →
x[4][2][0] → x[4][3][0] → x[4][4][0] → x[0][0][1] → x[0][1][1] →
x[0][2][1] → x[0][3][1] → x[0][4][1] → x[1][0][1] → x[1][1][1] →
x[1][2][1] → x[1][3][1]  → x[1][4][1] →  x[2][0][1] → x[2][1[1] →
x[2][2][1] → x[2][3][1] → x[2][4][1] → x[3][0][1] → x[3][1][1] →
x[3][2][1] → x[3][3][1] → x[3][4][1] → x[4][0][1] → x[4][1[1] →
x[4][2][1] → x[4][3][1] → x[4][4][1]



Hasil:

= AF(H)  + (43(D)  * 4)
Konversi nilai AF(H)  ke desimal;
A(H) = 10(D)
 F(H) = 15(D)
AF(H)  = (10 * 161) + (15 * 160)
= 160 + 15
= 175(D)
= 175(D)  + 172(D)
= 347(D)

konversi nilai  347(D) ke hexa    ;
347/16 = 21, sisa 11 (di tulis B)
21/16 = 1, sisa 5
1/16 = 0, sisa 1
 = 15B(H) (di baca dari bawah)

Hasilnya yaitu  15B(H)


Pemetaan CMO
1. Hitung besarnya perpindahan group : 1 dikurang 0 = 1
2. Total perpindahan 1 group : banyak baris dikali banyak kolom = 5 x 5 = 25.
3. Hitung bersarnya perpindahan kolom : 4 dikurang 1 = 3.
4. Dalam 1 kolom terdapat 5 baris sehingga total perpindahan kolom = 3 dikali 5 = 15.
5. Total perpindahan baris adalah 4 dikurang 1 = 3.
6. Total dari seluruh perpindahan (Group + Baris + Kolom) = 25 + 15 +3 = 43
Jalur perpindahan
x[2][1][0] → x[3][1][0] → x[4][1][0] → x[0][2][0] → x[1][2][0] →
x[2][2][0] → x[3][2][0] → x[4][2][0] → x[0][3][0] → x[1][3][0] →
x[2][3][0] → x[3][3][0] → x[4][3][0] → x[0][4][0] → x[1][4][0] →
x[2][4][0] → x[3][4][0] → x[4][4][0] → x[0][0][1] → x[1][0][1] →
x[2][0][1] → x[3][0][1] → x[4][0][1] → x[0][1][1] → x[1][1][1] →
x[2][1][1] →x[3][1][1] → x[4][1][1] → x[0][2][1] → x[1][2][1] →
x[2][2][1] → x[3][2][1] → x[4][2][1] → x[0][3][1] → x[1][3][1] →
x[2][3][1] → x[3][3][1] → x[4][3][1] → x[0][4][1] → x[1][4][1] →
x[2][4][1] → x[3][4][1] → x[4][4][1]

Hasil:

= AF(H)  + (43(D)  * 4)
Konversi nilai AF(H)  ke desimal;
A(H) = 10(D)
 F(H) = 15(D)
AF(H)  = (10 * 161) + (15 * 160)
= 160 + 15
= 175(D)
= 175(D)  + 172(D)
= 347(D)

konversi nilai  347(D) ke hexa    ;
347/16 = 21, sisa 11 (di tulis B)
21/16 = 1, sisa 5
1/16 = 0, sisa 1
 = 15B(H) (di baca dari bawah)

Hasilnya yaitu  15B(H)