MEMBANDINGKAN KEMANGKUSAN ALGORITMA DINIC DAN ALGORITMA PELABELAN FORD-FULKERSON UNTUK MASALAH ARUS MAKSIMUM

Khairani, Nerli and Sirait, Jenny (2015) MEMBANDINGKAN KEMANGKUSAN ALGORITMA DINIC DAN ALGORITMA PELABELAN FORD-FULKERSON UNTUK MASALAH ARUS MAKSIMUM. Jurnal Generasi Kampus, 08 (01). pp. 176-190. ISSN ISSN 1978-869X

[thumbnail of Reviewer.pdf]
Preview
Text
Reviewer.pdf - Published Version

Download (393kB) | Preview

Abstract

Teori graf merupakan salah satu cabang matematika yang paling banyak aplikasinya dalam kehidupan sehari-hari. Salah satu bentuk dari graf adalah jaringan (network), yaitu graf berarah berbobot sederhana yang memiliki simpul sumber (source), simpul tujuan (sink), dan tiap sisinya mempunyai kapasitas tertentu. Algoritma Dinic dan algoritma Pelabelan Ford-Fulkerson merupakan algoritma yang digunakan dalam pemecahan masalah arus maksimum. Algoritma Dinic memanfaatkan jaringan sisa. Pada jaringan sisa ini diidentifikasi f-augmenting path terpendek melalui layered network, kemudian dikonstruksi suatu blocking flow yang dapat digunakan untuk menentukan arus maksimum. Algoritma pelabelan Ford-Fulkerson berisi 2 fase. Fase pertama melakukan pelabelan untuk memeriksa apakah terdapat f-augmenting path. Jika terdapat f-augmenting path, maka menentukan dan menambahkan f-augmenting path pada arus f. Algoritma Dinic dan algoritma pelabelan Ford-Fulkerson memberikan solusi arus maksimum yang sama yaitu sebanyak 7. Algoritma pelabelan Ford-Fulkerson lebih mangkus dibandingkan dengan algoritma Dinic karena algoritma pelabelan Ford-Fulkerson membutuhkan waktu dan ruang memori yang lebih sedikit dalam mencari solusi dari masalah arus maksimum.

Item Type: Article
Keywords: Algoritma dinic; Masalah arus maksimum; Jaringan; Algoritma pelabelan
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA150 Algebra
Q Science > QA Mathematics > QA75.5 Electronic computers. Computer science
Divisions: Fakultas Matematika dan Ilmu Pengetahuan Alam > Matematika
Depositing User: Mrs Harly Christy Siagian
Date Deposited: 16 Jul 2018 09:43
Last Modified: 16 Jul 2018 09:47
URI: https://digilib.unimed.ac.id/id/eprint/30720

Actions (login required)

View Item
View Item