Skripsi

Penyelesaian masalah maksimum flow dengan menggunakan algoritma preflow push / Amalia Ika Prativi

Abstrak
Teori graph merupakan salah satu cabang matematika yang penting dan banyak model teori graph yang dapat diterapkan adalah masalah maksimum flow yaitu masalah bagaimana cara menentukan besarnya penugasan flow pada suatu jaringan kerja sehingga flow yang sampai ke tujuan maksimal. Penyelesaian masalah maksimum flow dapat lebih mudah dan efisien jika menggunakan algoritma. Dua algoritma yang sudah ada dan sering digunakan yaitu algoritma Lintasan Penambah dan algoritma Pelabelan Aka. Operasi dasar kedua algoritma tersebut adalah sama yaitu berulang-ulang mencari suatu lintasan dari titik sumber ke titik tujuan dan menghitung nilai kapasitas sisaannya yang digunakan untuk mengembangkan flow pada lintasan yang terpilih tersebut. Perulangan berhenti jika tidak ada lagi lintasan dari titik sumber ke titik tujuan. Pada skripsi ini disampaikan suatu alternatif algoritma yaitu algoritma yang operasi dasarnya berbeda dengan dua algoritma tersebut yaitu algoritma Preflow Push. Operasi dasarnya yaitu selalu memeriksa setiap titik dengan excess positif dan titik dengan label jarak terbesar tanpa menentukan lintasan dari titik sumber ke titik tujuan. Prosesnya diawali dengan pelabelan jarak semua titik penyerapan sisi sj oleh titik sumber dengan memindahkan kapasitas sisi sj ke excess titik yang dekat dengan titik sumber dan pelabelan jarak baru untuk titik sumber. Kemudian berulang-ulang memilih titik aktif i dan menentukan sisi admissible ij. Jika sisi admissible ij tidak ada maka dilakukan pelabelan jarak baru titik i. Lalu mencari nilai kapasitas sisaan Preflow Push untuk mengembangkan flow disepanjang sisi admissible ij excess titik i dan titik j pada jaringan kerja. Perulangan berhenti jika tidak ada lagi titik aktif pada jaringan kerja tersebut. Untuk mempermudah penyelesaian masalah maksimum flow dengan algoritma Preflow Push Lintasan Penambah dan algoritma Pelabelan Aka digunakan komputer dengan program GIDEN yang hasilnya disertakan pada Lampiran. Dalam menyelesaikan masalah maksimum flow algoritma Preflow Push memerlukan proses yang lebih lama dibandingkan algoritma Lintasan Penambah dan algoritma Pelabelan Aka. Tapi algoritma Preflow Push dapat lebih spesifik dan teliti karena selalu memeriksa titik pada jaringan kerja yang mempunyai excess positif dan titik yang mempunyai label jarak terbesar.

Informasi Detail

DDC

Rs 518.1 AMA p

Prodi

Skripsi (Sarjana)--Universitas Negeri Malang. Program Studi Matematika, 2007.

Deskripsi Fisik

vii, 118 hlm : il. ; 29 cm

Bahasa

Indonesia

No Reg

01297/KI/07

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang, 2007

Subjek

1. ALGORITMA
2. MAKSIMUM FLOW

Pembimbing

1. PURWANTO ; 2. SAPTI WAHYUNINGSIH

Lampiran Berkas