Fathimatuzzahro (2013) Penyelesaian masalah aliran maksimum menggunakan Edmons Karp Algorithm / Fathimatuzzahro. Diploma thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
Fathimatuzzahro. 2013. Penyelesaian Masalah Aliran Maksimum Menggunakan Edmons Karp Algorithm. Skripsi. Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang. Pembimbing (I) Dra. Sapti Wahyuningsih M.Si (II) Darmawan Satyananda S.T M.T Kata Kunci aliran maksimum edmons karp edmons karp algorithm Maximum flow problem dideskripsikan sebagai masalah pencarian arus maksimum (flow maximum) yang dapat mengalir pada sebuah network yang hanya memiliki satu sumber (source) dan satu tujuan (sink). Terdapat beberapa algoritma yang dapat digunakan pada penyelesaian maximum flow problem salah satu algoritma yang masih jarang digunakan adalah algoritma Edmons Karp. Algoritma Edmons Karp merupakan penyempurnaan dari algoritma Ford Fulkerson yakni pembatasan dalam pencarian lintasan residualnya. Dalam algoritma Edmons Karp lintasan yang dipilih merupakan lintasan yang terpendek. Untuk memilih lintasan penambah terpendek yang dimaksud digunakan algoritma Breadth First Search (BFS). Algoritma Edmons Karp ini dimulai dengan inisialisasi semua aliran dengan nol. Dilanjutkan dengan pencarian lintasan penambah terpendek dari s ke t dengan menggunakan algoritma BFS. Jika diperoleh lintasan penambah terpendek dilanjutkan dengan pencarian kapasitas residu pada lintasan tersebut yang dinotasikan dengan 916 . Setelah didapatkan 916 tambahkan pada aliran sepanjang lintasan tersebut sebesar 916 . Jika tidak ditemukan lintasan penambah terpendek lagi maka algoritma berhenti. Dari 3 contoh yang dibahas dalam bab III dapat disimpulkan bahwa cara dalam menambahkan aliran ke dalam lintasan penambah dan solusi yang diperoleh hasilnya sama sedangkan perbedaan algoritma Ford Fulkerson dan algoritma Edmons Karp hanya terletak pada langkah ke-3 yaitu dalam pemilihan lintasan penambah. Pada algoritma Edmons Karp digunakan algoritma BFS untuk pemilihan lintasan penambah terpendek namun pada algoritma Ford Fulkerson tidak menggunakan standar khusus dalam pemilihan lintasan penambahnya. Implementasi program dari algoritma Edmons Karp ini adalah program Delphi dengan inputnya berupa input titik kapasitas titik sumber dan titik tujuan. Hasil yang diperoleh berupa residual network beserta flow maksimum dalam network tersebut. Berdasarkan uji coba yang telah dilakukan pada beberapa network dengan menggunakan 5 6 17 dan 41 titik program yang telah dibuat sangat membantu dalam menyelesaikan permasalahan maximum flow khususnya dengan banyak titik.
| Item Type: | Thesis (Diploma) |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Fakultas Matematika dan IPA (FMIPA) > Departemen Matematika (MAT) > S1 Matematika |
| Depositing User: | library UM |
| Date Deposited: | 26 Sep 2013 04:29 |
| Last Modified: | 09 Sep 2013 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/17201 |
Actions (login required)
 |
View Item |