MEMBANDINGKAN KEMANGKUSAN ALGORITMA DINIC DAN ALGORITMA PELA BELAN FORD-FULKERSON UNTUK MASALAH ARUS MAKSIMUM
Total View This Week0

Institusion

Universitas Negeri Medan

Author

Katrin Jenny Sirait (STUDENT ID : 408211024)
Nerly Khairani (LECTURER ID : 196801141994122001)

Subject

QA Mathematics 

Datestamp

2016-08-15 07:38:00 

Abstract :
Teori graf merupakan salah satu cabang matematika yang paling banyak aplikasinya dalam kehidupan sehari-hari. Salah satu bentuk dari graf adalah jaringan (network), yaitu graf berarah berbobot sederhana yang memiliki simpul sumber (source), simpul tujuan (sink), dan tiap sisinya mempunyai kapasitas tertentu. Algoritma Dinic dan algoritma Pelabelan Ford-Fulkerson merupakan algoritma yang digunakan dalam pemecahan masalah arus maksimum. Algoritma Dinic memanfaatkan jaringan sisa. Pada jaringan sisa ini diidentifikasi f-augmenting path terpendek melalui layered network, kemudian dikonstruksi suatu blocking flow yang dapat digunakan untuk menentukan arus maksimum. Algoritma pelabelan Ford-Fulkerson berisi 2 fase. Fase pertama melakukan pelabelan untuk memeriksa apakah terdapat f-augmenting path. Jika terdapat f-augmenting path, maka menentukan dan menambahkan f-augmenting path pada arus f. Algoritma Dinic dan algoritma pelabelan Ford-Fulkerson memberikan solusi arus maksimum yang sama yaitu sebanyak 7. Algoritma pelabelan Ford-Fulkerson lebih mangkus dibandingkan dengan algoritma Dinic karena algoritma pelabelan Ford-Fulkerson membutuhkan waktu dan ruang memori yang lebih sedikit dalam mencari solusi dari masalah arus maksimum. 

File :
1 408211024 cover katrin.pdf
2 408211024 Lembar Pengesahan.pdf
13 RIWAYAT HIDUP katrin.pdf
3 408211024 KATA PENGANTAR katrin.pdf
4 408211024 ABSTRAK katrin.pdf
5 408211024 Daftar Isi katrin.pdf
7 408211024 Daftar Gambar katrin.pdf
9 408211024 Daftar lampiran katrin.pdf
10 408211024 BAB 1 katrin.pdf
11 408211024 BAB V katrin.pdf
12 408211024 DAFTAR PUSTAKA katrin.pdf