Penerapan Metode Heuristik Dalam Mencari Himpunan Dominasi Pada Graf Menggunakan Python

Abstract

Himpunan dominasi merupakan konsep dalam teori graf yang digunakan untuk memodelkan masalah optimasi. Dalam graf G=(V(G),E(G)), suatu himpunan S⊆V(G)  disebut sebagai himpunan dominasi jika setiap simpul yang tidak berada S dalam  bertetangga dengan setidaknya satu simpul di  S , sehingga memenuhi N[S]=V[G], dengan N[S]  merupakan gabungan dari himpunan simpul-simpul yang bertetangga dengan v∈S    dan memuat v. Pada penelitian ini yaitu mencari himpunan dominasi pada graf berbantuan Python, khususnya dalam penempatan perangkat penguat sinyal jaringan internet di Universitas Tanjungpura. Dalam penelitian ini metode yang digunakan adalah metode heuristik untuk mencari himpunan dominasi dalam graf, di mana langkah-langkahnya meliputi pencarian himpunan bagian tak kosong S_j    dari  V(G), dan pemeriksaan setiap simpul v_i∈V(G)    apakah merupakan elemen dari S_j  atau bertetangga dengan elemen S_j  hingga didapat S_j  sebagai himpunan dominasi. Algoritma ini diimplementasikan menggunakan pemrograman Python. Penelitian ini memanfaatkan konsep himpunan dominasi untuk menentukan alternatif penempatan perangkat penguat sinyal pada jaringan internet yang melintasi 26 unit menggunakan program Python. Hasil penelitian menunjukkan terdapat 14 alternatif penempatan optimal untuk perangkat penguat sinyal yang ada di Universitas Tanjungpura, di mana masimg-masing alternatif mencakup 18 unit tempat pemasangan.