Medi, Nurfadilah (2023) Perbandingan Algoritma Ford-Fulkerson, Edmonds-Karp dan Push-Relabel dalam Menentukan Aliran Maksimum. Skripsi thesis, Universitas Hasanuddin.
![[thumbnail of Bab 1-2]](/style/images/fileicons/text.png)
H011191011_skripsi_07-06-2023 1-2.pdf
Download (1MB)
![[thumbnail of Cover]](/32511/2.hassmallThumbnailVersion/H011191011_skripsi_07-06-2023%20cover1.png)
![](/32511/2.haspreviewThumbnailVersion/H011191011_skripsi_07-06-2023%20cover1.png)
H011191011_skripsi_07-06-2023 cover1.png
Download (242kB) | Preview
![[thumbnail of Daftar Pustaka]](/style/images/fileicons/text.png)
H011191011_skripsi_07-06-2023 dp.pdf
Download (10MB)
![[thumbnail of Full text]](/style/images/fileicons/text.png)
H011191011_skripsi_07-06-2023.pdf
Restricted to Repository staff only
Download (12MB)
Abstract (Abstrak)
Masalah aliran maksimum adalah permasalahan optimasi dengan tujuan mengetahui nilai aliran di dalam sebuah jaringan aliran (network flow). Jaringan aliran merupakan sebuah graf yang memiliki aliran (flow) pada setiap sisinya yang memenuhi syarat 0≤f(u,v)≤c(u,v). Masalah aliran maksimum dapat diselesaikan menggunakan beberapa algoritma diantaranya algortima Ford-Fulkerson, Edmonds-Karp dan Push-Relabel. Dalam skripsi ini ketiga metode tersebut akan dibandingkan dalam tiga aspek yang berbeda yaitu kompleksitas waktu, kesederhanaan, dan jumlah iterasi yang diperlukan untuk menentukan aliran maksimum baik secara manual maupun dengan menggunakan program python. Dengan adanya program python tersebut, masalah aliran maksimum dalam sebuah jaringan dapat ditentukan dengan cepat. Hasil dari program python telah dibandingkan dengan hasil yang diperoleh secara manual yang menunjukkan bahwa program python tidak salah. Ketiga algortima memberikan hasil yang sama dalam mencari aliran maksimum akan tetapi Ford-Fulkerson lebih sederhana dalam pencarian lintasan dibandingkan dengan Edmonds-Karp meskipun jumlah iterasi yang dibutuhkan Edmonds-Karp lebih sedikit. Berbeda dengan algortima Ford-Fulkerson dan Edmonds-Karp, pada algoritma Push-Relabel tidak menggunakan lintasan yang mana aliran tidak langsung dikirimkan dari titik sumber ke titik tujuan tetapi di alirkan ke titik yang bertetangga sehingga algoritma ini lebih mudah di terapkan untuk network yang besar walaupun membutuhkan lebih banyak iterasi.
Item Type: | Thesis (Skripsi) |
---|---|
Uncontrolled Keywords: | Aliran maksimum, Jaringan aliran, Ford-Fulkerson, Edmonds-Karp, Push-Relabel, Python. |
Subjects: | Q Science > QA Mathematics |
Divisions (Program Studi): | Fakultas Matematika dan Ilmu Peng. Alam > Matematika |
Depositing User: | Andi Milu |
Date Deposited: | 30 Jan 2024 07:29 |
Last Modified: | 30 Jan 2024 07:29 |
URI: | http://repository.unhas.ac.id:443/id/eprint/32511 |