Skripsi

Analisis kinerja algoritma min cut tree dalam menyelesaikan permasalahan pada maximum flow / Aris Febrianto

Abstrak
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.

Informasi Detail

DDC

Rs 518.1 FEB a

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2016.

Deskripsi Fisik

vii, 73 lembar : il. , tab. ; 30 cm.

Bahasa

Indonesia

No Reg

02224/KI/16

Edisi

Skripsi (Sarjana). Universitas Negeri Malang, 2016

Subjek

1. ALGORITMA
2. ALGORITHMS

Pembimbing

1. Susy Kuspambudi Andaini

Lampiran Berkas