Mulyono, - MENENTUKAN ALIRAN MAKSIMUM DENGAN ALGORITMA FORD- FULKERSON DAN PREFLOW-PUSH. Unnes Journal of Mathematics.

PDF Download (6MB)

Abstract

Penelitian ini bertujuan untuk mengetahui konsep aliran maksimum berdasarkan teorema Maximal Flow–Minimal Cut serta mengetahui cara menentukan aliran maksimum dengan algoritma Ford-Fulkerson dan Preflow­Push. Metode penelitian yang digunakan adalah metode studi pustaka. Pada penelitian ini dapat disimpulkan: (1) konsep aliran maksimum berdasarkan teorema Maximal Flow–Minimal Cut menjelaskan bahwa nilai aliran f *=c(X,X1 ) dengan B(X,X1 ) merupakan sebuah pemutus-(s,t) minimum di N, maka f * adalah aliran maksimum di N yang nilainya selalu sama dengan kapasitas pemutus -(s,t) minimum di N; (2) algoritma Ford-Fulkerson bekerja dengan mengkonstruksi aliran baru dengan nilai yang lebih besar dari aliran yang lama, dan menggunakan teknik pelabelan Routin, pencarian aliran baru akan berhenti ketika semua titik N yang terlabel telah teramati dan titik t tidak terlabel; (3) algoritma Preflow­Push bekerja dengan operasi dasar push dan relabel, algoritma ini berhenti ketika tidak ada lagi titik yang aktif. Dalam penelitian ini algoritma Ford-Fulkerson dihitung secara manual, sedangkan algoritma Preflow­Push menggunakan alat bantu yaitu software GIDEN. Dari contoh penggunaan aliran maksimum dalam penelitian ini diperoleh aliran maksimum = pemutus -(s,t) minimum = 600.

Actions (login required)

View Item