MODEL ARUS JARINGAN

MATERI 8

Jaringan

• Jaringan adalah suatu susunan garis edar (path)

yang menghubungkan berbagai titik

• Komponen jaringan :

simpul ( nodes) dan cabang ( branches)

Simpul melambangkan titik persimpangan,

sedang cabang menghubungkan antar simpul

RO/ X / 2

MASALAH RUTE TERPENDEK

• Berguna untuk menentukan jarak tersingkat antara titik awal ke beberapa titik tujuan.

• Metode: Solusi Terpendek (Shortest Path)

• Langkah : 1. Pilih simpul dengan rute langsung tersingkat dari titik awal 2. Buatlah suatu setelan permanen dengan titik awal dan simpul terpilih pd langkah 1

3. Tentukan seluruh simpul yang berhubungan

langsung dengan simpul simpul setelan

permanen

4. Pilihlah rute terpendek dari seluruh simpul

yg berhubungan langsung dg simpul simpul

setelan permanen.

5. Ulangi langkah 3 dan 4 sampai seluruh

simpul bergabung dengan setelan permanen

Contoh soal :

The Stagecoach Shipping Company mengangkut

jeruk dengan 6 truk dari LA ke enam kota di

bagian Barat dan Barat Tengah. Enam rute yang

berbeda antara LA, kota kota tujuan serta

lamanya waktu dalam jam yg dibutuhkan oleh

sebuah truk adalah :

1

3 6

74

52

16

35

915

22

25

19

14

17 14

812

1

3

4

2

16

35

9

9 *

1

3

4

2

16

35

915

622

9

16 *

1

3 6

4

52

16

35

915

22

25

9

24

16

*

1

3 6

74

52

16

915

22

25

19

14

17

9 31

24

16

*

1

3 6

74

52

16

915

22

25

19

14

14

9 31

38

24

16 *

1

3 6

74

52

16

915

22

19

14

0

9

24

16 38

31

43 *

MASALAH POHON RENTANG MINIMAL (SPANNING TREE)

• Hampir sama dengan Masalah Rute Terpendek, hanya

tujuannya adalah untuk menghubungkan seluruh simpul

dalam jaringan sehingga total panjangnya diminimumkan

• Jaringan yang dihasilkan merentangkan

( menghubungkan ) semua titik dalam jaringan tersebut

pada total jarak ( panjang) minimum

The Metro Cable Television Company akan

memasang suatu sistem kabel televisi dalam suatu

komunitas yang terdiri dari tujuh kota. Masing masing

kota harus dihubungkan ke sistem kabel utama.

Perusahaan kabel televisi tsb ingin merancang jaringan

kabel utama dg cara yang dpt meminimasi total panjang

kabel yg hrs dipasang.Jalur yg mungkin tersedia untuk

perush. tv kabel tsb dan panjangnya kabel yg dibutuhkan

digambarkan sbb :

Langkah

• Pilihlah simpul awal manapun ( biasanya simpul 1 yang terpilih )

• Pilihlah simpul yg terdekat dg simpul awal untuk bergabung dg pohon rentang

• Pilihlah simpul terdekat yg belum termasuk dlm pohon rentang

• Ulangi langkah 3 sampai seluruh simpul telah tergabung dlm pohon rentang

RO/ X / 17

1

2

3

4

5

6

716

35

915

22

12

25

14

19

1714

8

RO/ X / 18

1

2

3

4

5

6

716

35

915

22

12

25

14

19

1714

8

RO/ X / 19

1

2

3

4

5

6

716

35

915

22

12

25

14

19

1714

8

RO/ X / 20

1

2

3

4

5

6

716

35

915

22

12

25

14

19

1714

8

RO/ X / 21

1

2

3

4

5

6

716

35

915

22

12

25

14

19

1714

8

RO/ X / 22

1

2

3

4

5

6

716

35

915

22

12

25

14

19

1714

8

RO/ X / 23

1

2

3

4

5

6

716

35

915

22

12

25

14

19

1714

8

RO/ X / 24

MASALAH ARUS MAKSIMAL

• Dalam masalah ini, masalah jaringan memiliki kapasitas

arus yang terbatas.

• Permasalahannya : menentukan arus maksimum yang

dapat diperoleh melalui sistem tersebut

RO/ X / 25

LANGKAH

1. Pilih secara sembarang garis edar dalam

jaringan tersebut dari titik awal ke titik tujuan

2. Sesuaikan kapasitas pada setiap simpul dg

mengurangkan arus maksimal untuk garis

edar yg dipilih dlm langkah 1

3. Tambahkan arus maksimal sepanjang grs edar

ke arus berlawanan arah pd setiap simpul

4. Ulangi langkah 1,2 dan 3 sampai tidak ada lagi garis

edar dengan kapasitas arus yang tersedia

Contoh :

The Scott Tractor Company mengirim bagian bagian

traktor dari Omaha ke St Louis dengan jaringan sistem

rel kereta api seperti yang ditunjukkan pada gambar di

bawah ini. Namun kontrak membatasi jumlah gerbong

kereta api yg dpt dipastikan oleh perusahaan pada setiap

cabang selama 1 minggu

Berdasarkan kondisi yang terbatas ini, perusahaan

ingin mengetahui jml maksimum gerbong kereta api

yg berisi bagian traktor yg dapat dikirim dari Omaha

ke St Louis selama satu minggu. Jml gerbong

kereta api yg tersedia bagi perusahaan traktor tsb

untuk setiap cabang rel ditandai oleh angka pd

cabang di sisi kanan setiap sampul yang

melambangkan persimpangan rel,

1

2

3

4 6

5

Masuk Keluar

Omaha St. Louis

6

4

7

0 3

8

2

0 3

5

04

0 0

0

0 2

6

RO/ X / 29

1

2

3

4 6

5

Masuk Keluar

Omaha St. Louis

64

7

0 3

8

2

0 3

5

04

0 0

0

0 2

6

Arus maksimum untuk garis edar 1-2-5-6

4

4

4

4 4

2

40

RO/ X / 30

1

2

3

4 6

5

Masuk Keluar

Omaha St. Louis

24

7

0 3

4

2

0 3

5

00

0 0

0

0 2

6

Arus maksimum untuk garis edar 1-4-6

4

4

4

8 84 40

1

RO/ X / 31

1

2

3

4 6

5

Masuk Keluar

Omaha St. Louis

20

7

0 3

4

2

0 3

1

00

0 0

0

0 2

6

Arus maksimum untuk garis edar 1-3-6

4

4

4

14 144 4

6 61

0

RO/ X / 32

1

2

3

4 6

5

Masuk Keluar

Omaha St. Louis

20

0 3

4

2

0 3

1

00

0 0

0

0 2

Arus maksimum untuk garis edar 1-3-6

4

4

4

15 154 4

1 61

0

61

10

1

0

RO/ X / 33

1

2

3

4 6

5

Masuk Keluar

Omaha St. Louis

20

0 3

4

2

0 3

0

00

0 0

0

0 1

Arus maksimum untuk garis edar 1-3-6

4

4

4

15 154

60

0

7 1

5

RO/ X / 34