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 PreflowPush. 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 PreflowPush 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 PreflowPush menggunakan alat bantu yaitu software GIDEN. Dari contoh penggunaan aliran maksimum dalam penelitian ini diperoleh aliran maksimum = pemutus -(s,t) minimum = 600.