Febrianto, Aris (2016) Analisis kinerja algoritma min cut tree dalam menyelesaikan permasalahan pada maximum flow / Aris Febrianto. Diploma thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
ABSTRAK Febrianto Aris. 2016. Analisis Kinerja Algoritma Min Cut Tree dalam Menyelesaikan Permasalahan pada Maximum Flow. Skripsi Jurusan Matematika Fakultas MIPA Universitas Negeri Malang. Pembimbing Dra. Susy Kuspambudi M.Kom. Kata Kunci maximum flow algoritma min cut tree kompleksitas waktu. Maximum flowmerupakan salah satu permasalahan dalam teori graph yang sering dihadapi dalam kehidupan sehari-hari.Maximum flow bekerja dengan cara menentukan besarnya arus maksimum yang mengalir dari titik sumber s menuju titik tujuan t dalam suatu jaringan yang direpresentasikan sebagai suatu graph G(V E).Untuk menentukan maximum flow yaitu dengan cara menentukan potongan minimum G(V E)pada lintasan s-t. Kompleksitas waktu yang dinyatakan oleh T(n) adalah jumlah operasi yang dilakukan untuk melaksanakan algoritma sebagai fungsi dari masukan n dimana ukuran masukan (n) merupakan jumlah data yang diproses oleh suatu algoritma. T(n) O(f(n))merupakan kompleksitas waktu untuk kasus terburuk yaitu kebutuhan waktu maksimum yang diperlukan suatu algoritma sebagai fungsi dari n. Salah satu algoritma yang dapat digunakan dalam menentukan maximum flow yaitu algoritma min cut tree. Prosedur algoritma min cut tree dimulai dengan penghitungan nilai batas atas N(i) 8704 i 1 nsebanyak n kali sehingga kompleksitasnyaO(n). Selanjutnya proses penggabungan dua titik (i j) dengan memotong sisi yang terkait antara dua titik tersebut dimana i 1 n-1 serta j i 1 n.Proses penggabungan pada pengulangan terdalam dilakukan sebanyak log 8289 12310 n 12311 kali 8704 j i 1 n. Pengulangan terluar dikerjakan sebanyak n kali 8704 i 1 n-1. Sehinggakompleksitasnya O(n log 8289 n).Setelah langkah penggabungan selesai dilanjutkan pada langkah pengkonstruksian tree. Langkah ini disesuaikan dengan langkah penggabungan dua titik sebelumnya yang dimulai dari iterasi akhir menuju iterasi awal sebanyak n-1 kali sehingga kompleksitasnyaO(n).Hasil akhir pengkonstruksian tree tersebut digunakan untuk menentukan maximum flow dari titik sumber s menuju titik tujuan t yang dilakukan sebanyak n kali sehingga kompleksitasnyaO(n).Kompleksitas waktu keseluruhan dari algoritma min cut tree yaitu O(n) O(n log 8289 12310 n) O(n 12311 ) O(n) O(n log 8289 12310 n) 12311 dimana O(n log 8289 12310 n) 12311 merupakan kompleksitas waktu untuk kasus terburuk dengan waktu maksimum yang diperlukan sebanyak n log 8289 n.
| Item Type: | Thesis (Diploma) |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Fakultas Matematika dan IPA (FMIPA) > Departemen Matematika (MAT) > S1 Matematika |
| Depositing User: | library UM |
| Date Deposited: | 10 Jun 2016 04:29 |
| Last Modified: | 09 Sep 2016 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/17450 |
Actions (login required)
 |
View Item |