Model JaringanModel Jaringan

11

Topik Yang dibahasTopik Yang dibahas

1. Minimal spanning tree2. Shortest-route algorithm3. Maximum flow algorithm

22

3. Maximum flow algorithm

Definisi JaringanDefinisi 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

33

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

44

1

2

3

Tree

Latihan Latihan • Untuk setiap jaringan berikut tentukan sebuah (a) path,

(b) cycle, (c) cycle terarah, (d) tree, (e) spanning tree, (f) N dan A.

1

2

5 1

3

4

55

• 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)}

1 5 1

2

4

(ii)

3 4

(i)

1. Minimal Spanning Tree Algorithm1. 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.

66

cabang-cabang yang terhubung.• Contoh:

– Pembangunan jalan yang menghubungkan beberapa kota

– Pembangunan jaringan pipa gas alam cair yang menghubungkan beberapa tempat

– dll

The AlgorithmThe Algorithm

• N={1,2,…,n} = node-node dari jaringan• Ck = Himpunan node yang telah dihubungkan secara

permanen pada iterasi k; Ck = Himpunan node yangbelum dihubungkan secara permanen.

• Langkah 0 : C0=φ dan C0 = N.

77

• 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 . JadiCk = Ck-1+{j*} dan Ck=Ck-1-{j*}.Jika Ck= φ, stop. Jika tidak lanjutkan ke langkah k=k+1.

Contoh Contoh

Midwest TV Company dalamproses menyediakan jaringankabel ke lima wilayahpengembangan perumahanbaru. Gambar di bawah adalahjaringan TV yang mungkin

88

jaringan TV yang mungkinyang menghubungkan ke limawilayah tersebut. Kabel diukurdalam mil yang ditunjukkanoleh setiap arc (sisi).

JawabanJawaban

• 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

1

2

3

5

6

3 mil

14

5

Alternate links

99

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

4

3

5

Minimal spanning tree

Latihan Latihan

Tentukan minimal spanning tree dari jaringan berikut:

SE

1300

2000

1010

LA

DE

DA

CH NY

DC

11001300

1000

2000

2600

1400780 900

1300

800

200

2. Shortest2. Shortest--Route ProblemRoute Problem

• Menentukan rute terpendek antara sebuahsumber (daerah asal) dan daerah tujuan dalamsuatu jaringan transportasi.

• Algoritma ini digunakan untuk menyelesaikanjaringan siklis maupun bukan siklis adalah:

1111

jaringan siklis maupun bukan siklis adalah:– Dijkstra’s algorithm– Floyd’s algorithm.

• Aplikasi:– Equipment replacement– Most reliable route– Three-Jug Puzzle.

Dijkstra’s AlgorithmDijkstra’s Algorithm

• Digunakan untukmenentukan ruteterpendek diantara nodetertentu ke setiap nodeyang lainnya di dalam

1212

yang lainnya di dalamjaringan.

• Contoh: Cari ruteterpendek dari node 1dan setiap node lainnya(node 2 ,3,4,5) darijaringan di sebelah ini.

• Cara mementukan rute terpendek antara node 1 dansebarang nodee lainnya dalam jaringan adalahditentukan dengan mulai pada tujuan (node) yang ditujudan arah mundur melalui node-node menggunakaninformasi 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:

1313

Node Jarak Rute

12345

055304090

-1-3-4-21-31-3-41-3-4-5 atau 1-3-5

Latihan Latihan

Gunakan Dijkstra’s algorithm untuk mencari rute terpendek antara node 1 dan setiap node lainnya dalam jaringan berikut:

1414

3. Maximal Flow Model3. Maximal Flow Model

• Digunakan untuk kapasitasmaksimum suatu jaringan diantara dua node.

• Contoh: Perhatikan jaringanberikut. Kapasitas dua arahditunjukkan oleh busur

1515

ditunjukkan oleh busur(sisi/arc) masing-masing.Sebagai contoh, untukbusur (3,4); limit aliranadalah 10 unit dari 3 ke 4,dan 5 unit dari 4 ke 3.

Solusi Solusi

1616

1717

• Kesimpulan: Aliran maksimum adalahF = f1+f2+f3+f4+f5 = 20+10+10+10+10 = 60.

• Aliran dalam busur berbeda adalah kapasitas awal – residu terakhir

1818

kapasitas awal – residu terakhir

Arc Kapasitas awal -kapasitas akhir

Flow amount

Arah

(1, 2)(1, 3)(1, 4)(2, 3)

(20,0)-(0,20) = (20,-20)(30,0)-(0,30) = (30,-30)(10,0)-(0,10) = (10,-10)

(40,0)-(40,0) = (0,0)

2030100

1 21 31 4

----

1919

(2, 3)(2, 5)(3, 4)(3, 5)(4, 5)

(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)

020102020

----2 53 43 54 5

LatihanLatihan

1.Tentukan maximalflow dari jaringanberikut dan tentukanpula optimal flow disetiap ruas (arc):

2020

setiap ruas (arc):

2.Perhatikan jaringan pipabeikut. Tentukan(a) Produksi per hari disetiap refinery yangmembuat kapasitasjaringan maksimum.(b) Permintaan per hari disetiap terminal yangmembuat kapasitas

2121

membuat kapasitasjaringan maksimum.(c) Kapasitas per hari darisetiap pump yangmembuat kapasitasjaringan maksimum.