Fithriyah, Inayatul (2013) Algoritma capacity scaling dalam menyelesaikan maximum flow problem dan implementasinya / Inayatul Fithriyah. Diploma thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
Fithriyah Inayatul. 2012. Algoritma Capacity Scaling Dalam Menyelesaikan Maximum Flow Problem Dan Implementasi Programnya. Skripsi Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang. Pembimbing (I) Dra. Sapti Wahyuningsih M. Si (II) Darmawan Satyananda S. T M. T . Kata Kunci maximum flow capacity scaling algoritma capacity scaling 12288 12288 12288 12288 Maximum flow problem dideskripsikan sebagai masalah pencarian untuk mencari arus maksimum yang dapat mengalir pada sebuah network yang hanya memiliki satu source (sumber) dan sink (tujuan). Terdapat beberapa algoritma yang dapat digunakan pada penyelesaian maximum flow salah satu algoritma yang masih belum umum digunakan adalah algoritma capacity scaling 12288 12288 12288 12288 Algoritma capacity scaling merupakan suatu variasi dari maximum capacity augmenting algorithm yang dalam setiap iterasinya tidak dibutuhkan suatu perhitungan yang lebih banyak. Ide dari algoritma capacity scaling ini secara konseptual sederhana yakni dengan menambahkan aliran sepanjang lintasan dengan suatu kapasitas residu yang relatif besar yang telah ditetapkan. 12288 12288 12288 12288 Algoritma capacity scaling ini dimulai dengan inisialisasi semua aliran dengan nol. Lalu dilanjutkan dengan pencarian dengan menggunakan data kapasitas terbesar . Adapun rumus mencari adalah . Jika dari perhitungan diperoleh maka dapat dilanjut pada langkah selanjutnya yakni pencarian lintasan penambah. Namun jika hasil perhitungan menunjukkan bahwa maka algoritma berhenti. Dalam pencarian lintasan penambah dalam algoritma ini tidak ada aturan khusus. 12288 12288 12288 12288 Dari ketiga contoh pada bab III dapat disimpulkan beberapa perbedaan dan persamaan antara algoritma capacity scaling dengan algoritma maximum capacity augmenting path. Dari ketiga contoh tersebut dapat dilihat bahwa jumlah banyaknya lintasan cara dalam menambahkan aliran ke dalam lintasan penambah serta hasil yang diperoleh sama. Namun cara pemilihan lintasan pada kedua algoritma tersebut berbeda. 12288 12288 12288 12288 Dari ketiga contoh pada bab III dapat disimpullkan bahwa algoritma capacity scaling lebih efisien. Hal ini karena pada algoritma capacity scaling hanya perlu memeriksa lintasan pada digraph bagian dari residual network yang ada Implementasi program dari algoritma capacity scaling yang telah dibuat oleh penulis juga sangat membantu dalam menyelesaikan permasalahan maximum flow khususnya dengan banyak titik.
| Item Type: | Thesis (Diploma) |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Fakultas Matematika dan IPA (FMIPA) > Departemen Matematika (MAT) > S1 Matematika |
| Depositing User: | Users 2 not found. |
| Date Deposited: | 26 Sep 2013 04:29 |
| Last Modified: | 09 Sep 2013 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/17196 |
Actions (login required)
 |
View Item |