Skripsi

Penyelesaian masalah aliran maksimum menggunakan Edmons Karp Algorithm / Fathimatuzzahro

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

Informasi Detail

DDC

Rs 511.8 FAT p

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2013.

Deskripsi Fisik

xv, 96 lembar : il., tab. ; 30 cm

Bahasa

Indonesia

No Reg

04356/KI/13

Edisi

Skripsi (Sarjana)-- Universitas Negeri Malang, 2013

Subjek

1. ALGORITMA

Pembimbing

1. Sapti Wahyuningsih ; 2. Darmawan Satyananda

Lampiran Berkas