Model Jaringan
1
Topik Yang dibahas 1. Minimal spanning tree 2. Shortest-route algorithm 3. Maximum flow algorithm
2
Definisi Jaringan • • • • • • • •
Jaringan (network) = (N, A); N=node, A=arc = sisi=busur. Arc (sisi) terarah mempunyai arah. Jaringan terarah mempunyai semua sisi yang terarah. Path (lintasan) = sekumpulan arc yang berbeda yang menghubungkan dua node melalui node yang lain tanpa memperhatikan arah aliran sisi (arc). Path yang menghubungan node dengan dirinya = cycle (siklus) Network terhubung = setiap dua node berbeda dihubungkan oleh paling sedikit satu path. Tree=jaringan terhubung yg merupakan subset dari jaringan tanpa cycle (sikluc) Spanning tree= tree yg menghubungkan semua node dari jaringan tanpa cycle. 3
1
3
2 Tree
4
Latihan • Untuk setiap jaringan berikut tentukan sebuah (a) path, (b) cycle, (c) cycle terarah, (d) tree, (e) spanning tree, (f) N dan A. 3
2
1
5
3
4
(i)
1
4
2 (ii)
• Gambarkan jaringan yang didefinisikan dengan N={1,2,3,4,5,6} A={(1,2),(1,5),(2,3),(2,4),(3,5),(3,4),(4,3),(4,6),(5,2),(5,6)}
5
1. Minimal Spanning Tree Algorithm • Minimal spanning tree algorithm dilakukan dengan menghubungkan node-node dari sebuah jaringan, secara langsung maupun tak langsung, menggunakan panjang terpendek dari cabang-cabang yang terhubung. • Contoh: – Pembangunan jalan yang menghubungkan beberapa kota – Pembangunan jaringan pipa gas alam cair yang menghubungkan beberapa tempat – dll 6
The Algorithm • N={1,2,…,n} = node-node dari jaringan • Ck = Himpunan node yang telah dihubungkan secara permanen pada iterasi k; Ck = Himpunan node yang belum dihubungkan secara permanen. • Langkah 0 : C0=φ dan C0 = N. • Langkah 1 : Mulai dari sebarang node, i, C1 = {i} dan C1=N-{i}. Lanjutkan ke Langkah k = 2. • Langkah k : Pilih node j* di Ck-1 yang sisinya terpendek ke sebuah node di Ck-1 . Jadi Ck = Ck-1+{j*} dan Ck=Ck-1-{j*}. Jika Ck= φ, stop. Jika tidak lanjutkan ke langkah k=k+1. 7
Contoh Midwest TV Company dalam proses menyediakan jaringan kabel ke lima wilayah pengembangan perumahan baru. Gambar di bawah adalah jaringan TV yang mungkin yang menghubungkan ke lima wilayah tersebut. Kabel diukur dalam mil yang ditunjukkan oleh setiap arc (sisi).
8
Jawaban • N={1,2,3,4,5,6} • C1={1} (sebarang node juga dapat digunakan untuk memulai); C1={2,3,4,5,6}. • C2={1,2} dan C2={3,4,5,6}. Jaraknya = 1 • C3={1,2,5} dan C3={3,4,6}. Jaraknya = 3 • C4={1,2,5,4} dan C4={3,6}. Jaraknya = 4 • C5={1,2,5,4,6} dan C5={3}. Jaraknya = 3 • C6={1,2,5,4,6,3} dan C6={ }=φ. Jaraknya = 5 • Jadi kabel minimum (terpendek) yang diperlukan adalah 1+3+4+3+5=16 mil
2 3 mil 1 4
5 Alternate links
1 5 3
6 5 3 4 Minimal spanning tree
9
Latihan Tentukan minimal spanning tree dari jaringan berikut: SE 2000 1100
1300 1000
DE
CH
800
NY
2000 LA
200 2600 1400
780
DC
900 1300 DA
10
2. ShortestShortest-Route Problem • Menentukan rute terpendek antara sebuah sumber (daerah asal) dan daerah tujuan dalam suatu jaringan transportasi. • Algoritma ini digunakan untuk menyelesaikan jaringan siklis maupun bukan siklis adalah: – Dijkstra’s algorithm – Floyd’s algorithm.
• Aplikasi: – Equipment replacement – Most reliable route – Three-Jug Puzzle.
11
Dijkstra’s Algorithm • Digunakan untuk menentukan rute terpendek diantara node tertentu ke setiap node yang lainnya di dalam jaringan. • Contoh: Cari rute terpendek dari node 1 dan setiap node lainnya (node 2 ,3,4,5) dari jaringan di sebelah ini.
12
• Cara mementukan rute terpendek antara node 1 dan sebarang nodee lainnya dalam jaringan adalah ditentukan dengan mulai pada tujuan (node) yang dituju dan arah mundur melalui node-node menggunakan informasi yang diberikan oleh label permanen. Contoh: Rute terpendek dari node 1 ke node 2: (2) [55,4] (4) [40,3] 3 [30,1] 1 • Jadi rute terpendek adalah: Node
Jarak
Rute
1 2 3 4 5
0 55 30 40 90
1-3-4-2 1-3 1-3-4 1-3-4-5 atau 1-3-5 13
Latihan Gunakan Dijkstra’s algorithm untuk mencari rute terpendek antara node 1 dan setiap node lainnya dalam jaringan berikut:
14
3. Maximal Flow Model • Digunakan untuk kapasitas maksimum suatu jaringan di antara dua node. • Contoh: Perhatikan jaringan berikut. Kapasitas dua arah ditunjukkan oleh busur (sisi/arc) masing-masing. Sebagai contoh, untuk busur (3,4); limit aliran adalah 10 unit dari 3 ke 4, dan 5 unit dari 4 ke 3.
15
Solusi
16
17
• Kesimpulan: Aliran maksimum adalah F = f1+f2+f3+f4+f5 = 20+10+10+10+10 = 60. • Aliran dalam busur berbeda adalah kapasitas awal – residu terakhir
18
Arc
Kapasitas awal kapasitas akhir
Flow amount
(1, 2) (1, 3) (1, 4) (2, 3) (2, 5) (3, 4) (3, 5) (4, 5)
(20,0)-(0,20) = (20,-20) (30,0)-(0,30) = (30,-30) (10,0)-(0,10) = (10,-10) (40,0)-(40,0) = (0,0) (30,0)-(10,20) = (20,-20) (10,5)-(0,15) = (10,-10) (20,0)-(0,20) = (10,-20) (20,0)-(0,20) = (20,-20)
20 30 10 0 20 10 20 20
Arah 1 1 1
2 3 4 ----
2 3 3 4
5 4 5 5
19
Latihan 1.Tentukan maximal flow dari jaringan berikut dan tentukan pula optimal flow di setiap ruas (arc):
20
2.Perhatikan jaringan pipa beikut. Tentukan (a) Produksi per hari di setiap refinery yang membuat kapasitas jaringan maksimum. (b) Permintaan per hari di setiap terminal yang membuat kapasitas jaringan maksimum. (c) Kapasitas per hari dari setiap pump yang membuat kapasitas jaringan maksimum.
21
