MENENTUKAN ALIRAN MAKSIMUM DENGAN ALGORITMA FORDFULKERSON DAN PREFLOW-PUSH - Ulya, Rif’ah; Mulyono, Mulyono; Suyitno, Amin (Universitas Negeri Semarang, 2013)
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 aliranmaksimum 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 berhentiketika 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.