Seminar Tugas Akhir

Nina Herniawaty
G05400022

Penyelesaian Masalah Arus Maksimum dengan Algoritma Incremental

Suatu graf berarah dapat digunakan sebagai model jaringan arus (flow network). Misalkan sumber (source) memproduksi suatu meterial, kemudian mengirimkannya ke suatu tempat untuk dikonsumsi, sebut saja tempat tersebut sebagai ujung (sink). Sisi berarah pada jaringan arus merupakan tempat untuk meterial bergerak, setiap sisi berarah mempunyai kapasitas sisi tertentu. Jaringan arus dapat digunakan dalam berbagai bidang, yaitu jaringan komunikasi, jaringan transportasi, jariangn listrik, dll. Tujuan dari masalah arus maksimum adalah mencari angka terbesar dari material yang dikirimkan dari sumber ke ujung dengan memperhatikan kendala kapasitas. Algoritma Incremental adalah algoritma yang dapat bekerja dengan efisien ketika terjadi penyisipan sisi pada jaringan, algoritma tersebut dapat memperbaharui solusi dikarenakan perubahan input pada jaringan. pada awalnya algoritma Incremental mencari simpul affected dengan menggunakan bantuan Algoritma Backward Breadth First Search (BBFS) dan Algoritma Forward Breadth First Search (FBFS), kemudian memanggil algoritma Mod_Preprocess. Setelah itu algoritma Incremental melakukan pendekatan algoritma generic Preflow Push, operasi-operasi tersebut hanya dapat diterapkan pada simpul-simpul affected. Algoritma Incremental akan berakhir ketika tidak ada lagi simpul aktif pada jaringan. Pada saat itulah arus tambahan, jika ada, ditambahkan ke perhitungan arus maksimum sebelumnya.