matdis-optimisasi

Pembuktian suatu teorema memegang peranan yang penting dalam matematika. Di dalam matematika, secara umum ada dua untuk membuktikan suatu teorema, yaitu secara induktif dan secara deduktif. Secara deduktif pembuktian didasarkan pada aksioma, definisi, ataupun dalil-dalil yang telah ada. Pembuktian secara induktif dapat dipergunakan untuk dalil-dalil yang berlaku dalam domai bilangan cacah. Pembuktian ini didasarkan pada prinsip induksi, yaitu dimulai dengan beberapa kasus, diasumsikan berlaku untuk kasus tertentu, n=k, dan dari asumsi ini dibuktikan juga berlaku untuk n=k+1.

10.1 Representasi Aritmetika Dengan TreeOperasi aritmetika dapat direpresentasikan dengan menggunakan binary tree.

Internal vertek untuk menyatakan operator, sedangkan leaf sebagai operand. Root pada setiap subtree akan sebagai operator. Oleh karena itu operator yang paling luar (paling akhir dilakukan) sebagai root. Sebagai ilustrasi perhatikan beberapa contoh berikut :

a. a + b dapat dinyatakan sebagai :

b. (a+b)*(d/c) dapat dinyatakan sebagai :

c.

Topik10 Penelusuran dan Optimisasi Pada Graph

10-1

+

a b

+

a b

/

d c

*

+

^ d

+

* d

/

b c b

- c

a

Di dalam operasi matematika yang biasa kita pelajari adalah operasiu infik, yaitu operator diletakkan di antara operand, seperti a+b, a-B, a*b, dan sebagainya. Sebenarnya ada tiga jenis operasi, yaitu : infiks, prefiks, dan postfiks. Untuk membandingkan ketiganya, perhatikan contoh berikut :

infiks prefiks postfiks

a+b +ab ab+

(a+b)-c -+abc ab+c-

[a*(c-b)]/d /*a-cbd acb-*d/

10.2 Penelusuran VertekBagi komputer operasi prefiks maupun postfiks lebih mudah disbanding infiks.

Hal ini berlaku sebaliknya untuk manusia. Pada bagian ini akan diuraikan bagaimana menelusuri tree sehingga terjadi pembacaan infiks, prefiks, maupun postfiks.

a. Penelusuran Infiks (Inorder Traversal).

1. Lakukan inorder traversal pada subtree kiri

2. Baca root

3. Lakukan inorder traversal pada subtree kanan

b. Penelusuran Prefiks (Preorder Traversal)

1. Baca root



c. Penelusuran Postfiks (Postorder Traversal)



3. Baca root

Sebagai ilustrasi perhatikan tree berikut :

Inorder : a-b^c+d/b*c+d

Preorder : /+^-abcd+*bcd

Postorder : ab-c^d+bc*d+/

5.3. DFS DAN BFS


10-2

+

^ d

+

* d

/

b c b

- c

a

DFS (Depth-First Search Algorithm) merupakan algoritma untuk menelusuri vertek-vertek suatu graph, sehingga akan terbentuk suatu spanning tree dari graph tersebut. Algoritma DFS ini adalah :

1. Pilih satu vertek (r) sebagai root, dan masukkan vertek r ke dalam T. Beri v sebagai r.

2. Pilih nilai i terkecil, 2in, sedemikian sehingga {v,vi}V dan vi belum pernah dikunjungi.

Jika tidak ada i, maka langsung ke langkah 3. Untuk hal lainnya, lakukan :

a. ambil edge {v,vi}ke dalam T,

b. beri v sebagai vi,

c. kembali ke langkah 2.

3. Jika v=r, maka T adalah spanning tree dari graph G, dan selesai.

4. Untuk vr, lakukan backtrack dari v. Jika u adalah parent dari vertek v, maka beri nilai v sebagai u, dan kembali ke langkah 2.

Sebagai ilustrasi dari algoritma di atas, maka akan diterapkan untuk graph berikut :

Misalkan vertek-vertek diurut sesuai dengan : a, b, c, d, …..,h, i, j, maka hasilnya adalah :

1. Pertama ambil vertek a sebagai root, dan T={a}, serta v=a.

2. Vertek yang adjacent dengan a adalah : b, c, d. Ambil b, masukkan edge {a,b} ke dalam T. v=b, dan looping

Vertek yang adjacent dengan b adalah a, d dan e. (a tidak diambil, sebab sudah dikunjungi) Ambil d, masukkan edge {b,d} ke dalam T. v=d, dan looping

Vertek yang adjacent dengan d adalah a dan b (keduanya telah dikunjungi, maka ke langkah 3.

3. v=da, maka ke langkah 4

4. backtrack dari d dan v=b, dan kembali ke langkah 2.

2. Vertek yang adjacent dengan b adalah a, d, dan e. (a dan d sudah dikunjungi) Ambil e, v=e dan masukkan edge {b,e} ke dalam T, lalu looping.

Vertek yang adjacent dengan e adalah b, f, h. Ambil f, v=f dan masukkan edge {e,f} ke dalam T, looping

Vertek yang adjacent dengan f adalah e (sudah dikunjungi), maka ke langkah 3.

3. v=fa, maka ke langkah 4

4. backtrack dari f dan v=e, dan kembali ke langkah 2.


10-3

g a b

d

e

f

h

c

i j

2. Vertek yang adjacent dengan e adalah b, f, dan h. Ambil h, v=h dan masukkan edge {e,h} ke dalam T, lalu looping

Vertek yang adjacent dengan h adalah e (sudah dikunjungi), maka ke langkah 3.

3. v=ha, maka ke langkah 4

4. backtrack dari h dan v=e, dan kembali ke langkah 2.

2. Vertek yang adjacent dengan vertek e adalah b, f, h (sudah dikunjungi semua), maka ke langkah 3.

3. v=ha, maka ke langkah 4

4. backtrack dari h dan v=e, dan kembali ke langkah 2.

2. Vertek yang adjacent dengan vertek e adalah b, h, dan f (semua suadh dikunjungi), maka ke langkah 3.

3. v=ea, maka ke langkah 4

4. backtrack dari e dan v=b, dan kembali ke langkah 2.

2. Vertek yang adjacent dengan vertek b adalah a, d, dan e (semua suadh dikunjungi), maka ke langkah 3.

3. v=ba, maka ke langkah 4

4. backtrack dari b dan v=a, dan kembali ke langkah 2.

2. Vertek yang adjacent dengan vertek a adalah b, c dan d. Ambil c, dan v=c, ambil edge {a,e} ke dalam T, lalu looping.

Vertek yang adjacent dengan c adalah a dan g. Ambil g, v=g dan ambil edge {e,g} ke dalam T, lalu looping

Vertek yang adjacent dengan g adalah c, i dan j. Ambil i, v=i dan ambil edge {g,i} ke dalam T, lalu looping.

Vertek yang adjacent dengan i adalah g (sudah dikunjungi), maka ke langkah 3.

3. v=ia, maka ke langkah 4

4. backtrack dari i dan v=g, dan kembali ke langkah 2.

2. Vertek yang adjacent dengan vertek g adalah c, i, j. Ambil j, v=j dan ambil edge {g,j} ke dalam T, lalu looping.

Vertek yang adjacent dengan vertek j adalah g (sudah dikunjungi), maka ke langkah 3.

3. v=ja, maka ke langkah 4

4. backtrack dari j dan v=g, dan kembali ke langkah 2.

2. Vertek yang adjacent dengan vertek g adalah c, i, j (sudah dikunjungi), maka ke langkah 3.

3. v=ca, maka ke langkah 4

4. backtrack dari c dan v=c, dan kembali ke langkah 2.

2. Vertek yang adjacent dengan vertek c adalah a dan g (sudah dikunjungi), maka ke langkah 3.

3. v=ca, maka ke langkah 4


10-4

4. backtrack dari c dan v=a, dan kembali ke langkah 2.

2. Vertek yang adjacent dengan vertek a adalah b, c, dan d (sudah dikunjungi), maka ke langkah 3.

3. v=a, maka selesai.

Hasilnya adalah :

BFS (Breadth-First Search Algorithm) merupakan algoritma untuk menelusuri vertek-vertek suatu graph, sehingga akan terbentuk suatu spanning tree dari graph tersebut. Perbedaan dengan DFS adalah bahwa pada BFS, pembacaan dilakukan pada seluruh level.yang sama. Oleh karena itu tree yang akan terbentuk cenderung melebar. Algoritma DFS ini adalah :

1. Pilih satu vertek (r) sebagai root, dan masukkan vertek r ke dalam antraian Q. Serta insialisasi tree T dengan T={r}.

2. Hapuskan vertek terdepan dari Q. Untuk setiap i terkecil, 2in, sedemikian sehingga {v,vi}E dan vi belum pernah dikunjungi, masukkan edge {v,vi}ke dalam T.

3. Masukkan vertek yang adjacent dengan vertek v yang dihapus pada langkah (2) tersebut ke dalam Q dengan urutan yang disesuaikan, dan kembali ke langkah 2.

Sebagai ilustrasi dari algoritma di atas, maka akan diterapkan untuk graph berikut :

Misalkan vertek-vertek diurut sesuai dengan : a, b, c, d, …..,h, i, j, maka hasilnya adalah :

LATIHAN 5

1. Untuk graph berikut lakukan :


10-5

a

b c

f g

ja

ed

i

q

h

k ol p

s t

r

u v

w

g a b

d

e

f

h

c

i j

g a b

d

e

f

h

c

i j

g a b

d

e

f

h

c

i j

a. Penelusuran secara inorder

b. Penelusuran secara preorder

c. Penelusuran secara postorder

2. Perhatikan operasi aritmetika berikut :

a. Buatlah binary tree untuk operasi aritmetika tersebut !

b. Tentukan notasi infiksnya

c. Tentukan notasi prefiksnya

d. Tentukan notasi postfiksnya

3. Suatu complete binary T=(V,E) dengan V={a, b, c, …, i, j, k} dan a sebagai root. Jika hasil penelusuran postorder adalah : d, e, b, h, i, f, j, k, g, c, a. Gambarkan tree ini.

a. Jika tinggi tree ini adalah 3.

b. Jika tinggi subtree kiri dari tree ini adalah 3.

4. Perhatikan graph berikut :

Jika vertek diurut dari a, b, …, j, k, tentukan spanning tree dari graph tersebut dengan menggunakan :

a. Depth-first search algorithm (DFS)


10-6

a

j

de

b

i

h

c

fg

k

b. Bread-first search algorithm (BFS)

5. Soal seperti nomor (4) untuk graph :

6. Soal seperti nomor (4) untuk graph :

BAB 6. OPTIMISASI

6.1. PENDAHULUAN

Optimisasi berkaitan dengan beberapa operasi yang diterapkan pada graph yang terboboti, yaitu graph dengan setiap edge mempunyai bobot yang tidak harus sama. Ada beberapa optimisasi di dalam graph terboboti, yaitu :

1. Algoritma Dijkstra : untuk mencari path terpendek dari satu vertek ke vertek lainnya di dalam graph tersebut.

2. Algoritma Kruskal : Algoritma ini untuk mencari spanning tree dari suatu graph dengan panjang path antar vertek minimum. Hasil dari algoritma ini adalah minimum spanning tree.

3. Algoritma Prim : algortima ini bertujuan sama dengan algoritma Kruskal.

4. Algoritma Max-Flow Min-Cut : untuk mencari aliran terbesar dari satu vertek ke satu vertek lainnya.

Di dalam bagian ini hanya akan dibahas algoritma Dijkstra saja.

6.2. ALGORITMA DIJKSTRA

Algoritma Dikstra (Dikstra’s shortest path algorithm) merupakan algoritma untuk mencari lintasan (path) terpendek dari suatu vertek ke vertek-vertek lainnya dalam suatu graph G=(V,E). Di dalam hal ini edge-edge dalam graph G tersebut mempunyai bobot yang berbeda (disebut weighted graph).

Algoritma Dikstra ini adalah sebagai berikut :


10-7

a

d

c b

gi

fe

h

k

j

a

b

fe g

dc

1. Inisialisasi : i=0, S0={v0}. Beri label vertek v0 dengan (0,-) dan setiap vertek vv0 diberi label (,-).

Jika n=1, V={v0} dan selesai.

Jika n>1, lanjutkan ke langkah 2.

2. Untuk setiap v , gantikan (jika mungkin) label pada v dengan (L(v), y), dengan :

y adalah vertek di dalam Si dengan L(v) minimum.

3. Jika setiap vertek di (0in-2) berlabel (,-) maka selesai. Jika tidak, maka lakukan :

a. Pilih vertek vi+1 dengan label L( vi+1) minimum, lalu :

b. Si+1=Si{ vi+1}

c. i=i+1, jika i=n-1, maka selesai. Jika tidak, maka kembali ke langkah 2.

Sebagai ilustrasi algortima di atas, maka perhatikan contoh dengan graph berikut :

Hasil dari graph tersebut adalah :


10-8

L(v) = min {L(v), L(u)+wt(u,v)}uSi

(22,a)

c

a

g

h

f

b

11 7

6

6

11 9

4

7

11

3

5

49

4

5

1117

(6,c)(0,-)

(14,h)

(17,f)(10,f)

c

a

g

h

f

b

11 7

6

6

11 9

4

7

11

3

5

49

4

5

1117

LATIHAN 6

1. Perhatikan graph berikut :

a. Lakukan operasi dengan algoritma Dijkstra untuk memperoleh jarak terpendek dari vertek a ke setiap vertek lainnya.

2. Soal sama seperti nomor (1) untuk graph berikut :

Diketahui bobot edge :

{a,c}=10 {a,d}=20

{a,e}=15 {a,g}=5

{b,c}=3 {b,d}=2

{b,f}=1 {c,d}=1

{c,g}=1 {d,e}=2

{e,f}=3 {f,g}=2


10-9

5

5a

d

c b

gi

fe

h

k

j

10

20

304

10

2

615

20

8

4

5

6

10

3

a

b

fe g

dc

matdis-optimisasi

Documents