Electronic Theses and Dissertation

Teori graf merupakan salah satu cabang ilmu matematika yang dalam perkembangannya memperkenalkan mengenai pengoptimalan yang dapat diatasi dengan menggunakan metode pohon merentang minimum (minimum spanning tree). Konsep minimum spanning tree memiliki lingkup penerapan yang sangat luas salah satunya untuk mencari pengoptimalan jaringan pipa distribusi air. Pada pembangunan jaringan pipa distribusi air masih banyak terdapat bentuk loop/cycle seperti pada jaringan pipa distribusi air di lingkup Universitas Syiah Kuala (USK). Bentuk loop/cycle tersebut menandakan bahwa jaringan pipa distribusi yang sudah terbentuk masih belum dapat dikatakan optimal. Untuk itu dibutuhkan rancangan yang tepat dalam membangun jalur pipa distribusi air sehingga biaya, waktu dan kualitas air yang didistribusikan semakin efisien. Sebagai solusi permasalahan terkait pengoptimalan, terdapat beberapa algoritma yang dapat digunakan dalam konsep minimum spanning tree seperti algoritma Kruskal, algoritma Prim. Dengan menerapkan algoritma Prim dan algoritma Kruskal pada jaringan pipa distribusi air di lingkup USK diperoleh hasil dari representasi perpotongan antar pipa sebagai simpul yaitu sebanyak 199 simpul dan hasil representasi dari panjang pipa sebagai sisi yaitu sebanyak 251 sisi. Hasil pada penelitian ini menunjukkan selisih yang cukup besar pada total panjang pipa dan total harga pipa yang terpasang sebelum dilakukan pengoptimalan dan sesudah dilakukan pengoptimalan. Pada total panjang pipa yang terpasang sebelum dilakukan pengoptimalan panjang yaitu sepanjang 26.156,1 m menjadi 15.302,3 m dan pada harga pipa yang terpasang sebelum dilakukan pengoptimalan yaitu Rp6.192.397.500,00 menjadi Rp6.047.667.500,00. Pada penelitian ini menunjukkan bahwa kedua algoritma memiliki kelebihan dan kekurangannya masing-masing tergantung pada bentuk graf dan cara
pengerjaannya meskipun hasil yang diperoleh dari kedua algoritma adalah sama.

Kata kunci : Algoritma Kruskal, algoritma Prim, jaringan pipa distribusi, minimum spanning tree, teori graf.

Graph theory is one of the branches of mathematics which in its development introduces optimization that can be solved using the minimum spanning tree method. The minimum spanning tree concept has a very broad scope of application, one of which is to find optimization of water distribution pipe networks. In the construction of water distribution pipelines, there are still many loop / cycle forms such as the water distribution pipeline network within the scope of Syiah Kuala University (USK). The loop / cycle form indicates that the distribution pipe network that has been formed still cannot be said to be optimal. For this reason, the right design is needed in building water distribution pipelines so that the cost, time and quality of water distributed are more efficient. As a solution to problems related to optimization, there are several algorithms that can be used in the concept of minimum spanning tree such as Kruskal algorithm, Prim algorithm. By applying Prim's algorithm and Kruskal's algorithm to the water distribution pipe network in the scope of USK, the results of the representation of the intersection between pipes as nodes are 199 nodes and the results of the representation of the length of the pipe as an edge are 251 edges. The results in this study show a considerable difference in the total length of pipes and the total price of pipes installed before optimization and after optimization. In the total length of pipe installed before optimization and after optimization. In the total length of the installed pipe before optimization, the length was 26,156.1 m to 15,302.3 m and the price of the installed pipe before optimization was Rp6,192,397,500.00 to Rp6,047,667,500.00. This research shows that both algorithms have their own advantages and disadvantages depending on the shape of the graph and the way of working even though the results obtained from both algorithms are the same. Keywords : Kruskal’s algorithm, Prim’s algorithm, distribution pipeline network, minimum spanning tree, Graph theory.