Implementasi Algoritma Greedy Pada Penentuan Dominating set (Studi Kasus: Penentuan Sumur Resapan Di Universitas Jember)

Abstract

Perkembangan zaman tidak terlepas dari perkembangan sains dan teknologi. Salah satu bidang yang berkaitan dengan sains dan teknologi adalah matematika. Saat ini banyak permasalahan yang dapat diselesaikan menggunakan teori matematika. Salah satu teori matematika yang digunakan untuk memecahkan masalah sehari-hari adalah teori graf. Dalam Penelitian ini teori graf digunakan untuk mengetahui titik pendominasi pada graf sumur resapan di Universitas Jember. Pada graf sumur resapan, node yang dimiliki ada representasi dari letak sumur resapan di Universitas Jember dan jarak antar sumur resapan di representasikan sebagai vertex yang menghubungkan antar sumur. Peletakan node dan vertex pada graf sumur resapan berdasarkan graf grid, dimana tiap node dihubungan dengan node lain berdasarkan sisi lahan yang berhimpitan. Penentuan titik pendominasi menggunakan algoritma greedy. Algoritma greedy akan mencari penyelesaian pertahap sampai menghasilkan solusi optimum. Hasil yang diperoleh dari algoritma greedy digunakan sebagai inputan dominating set dan kemudian dihitung nilai keoptimalannya berdasarkan perhitungan dominating set. Hasil dari penelitian ini adalah jumlah himpunan pendominasi dari graf sumur resapan dan lokasi sumur resapan yang ditampilkan pada peta.