Electronic Theses and Dissertation

Jaringan distribusi pipa air bersih merupakan komponen penting dalam sistem
penyediaan air bersih yang memerlukan perencanaan secara efisien untuk
meminimalkan panjang jaringan dan biaya material pipa. Salah satu pendekatan
optimasi yang dapat digunakan adalah Minimum Spanning Tree (MST), yaitu subgraf
yang menghubungkan seluruh simpul tanpa membentuk sirkuit dengan total bobot
minimum. Penelitian ini bertujuan untuk merepresentasikan jaringan distribusi pipa air
bersih PDAM Tirta Daroy pada sebagian Kecamatan Banda Raya ke dalam bentuk
graf, menerapkan algoritma Prim, Reverse Delete, dan Boruvka dalam pembentukan
MST, serta membandingkan hasil ketiga algoritma berdasarkan total panjang pipa,
estimasi biaya material pipa, dan waktu eksekusi. Data yang digunakan berupa
jaringan distribusi pipa air bersih tahun 2026 yang mencakup area seluas 306,15 ha.
Hasil penelitian menunjukkan bahwa jaringan berhasil direpresentasikan menjadi graf
terhubung berbobot dan tidak berarah yang terdiri atas 288 simpul dan 339 sisi dengan
total panjang awal 35.572,29 meter. Ketiga algoritma menghasilkan MST yang sama,
yaitu terdiri atas 287 sisi dengan total panjang 25.472,29 meter, sehingga panjang
jaringan berkurang sebesar 10.100 meter atau 28,39%. Estimasi biaya material pipa
juga menurun dari Rp4.730.342.246 menjadi Rp3.393.791.876, sehingga diperoleh
penghematan sebesar Rp1.336.550.370 atau 28,25%. Dari sisi efisiensi komputasi,
algoritma Boruvka memiliki waktu eksekusi tercepat sebesar 0,0006926 detik, diikuti
algoritma Prim sebesar 0,0045739 detik, sedangkan algoritma Reverse Delete
memerlukan waktu eksekusi paling lama sebesar 0,16795 detik. Dengan demikian,
algoritma Boruvka merupakan algoritma yang paling efisien pada data penelitian ini.

Kata kunci: teori graf, minimum spanning tree, algoritma Prim, algoritma Reverse
Delete, algoritma Boruvka, jaringan distribusi pipa air bersih.

The clean water distribution pipeline network is an essential component of a water supply system that requires efficient planning to minimize pipeline length and pipeline material costs. One optimization approach that can be applied is the Minimum Spanning Tree (MST), which is a subgraph that connects all vertices without forming cycles while having the minimum total edge weight. This study aims to represent the clean water distribution pipeline network of PDAM Tirta Daroy in Banda Raya District as a graph, apply the Prim, Reverse Delete, and Boruvka algorithms to construct the MST, and compare the results of the three algorithms based on total pipeline length, estimated pipeline material cost, and execution time. The data used consist of the 2026 clean water distribution pipeline network covering an area of 306.15 hectares. The results show that the network was successfully represented as a connected, weighted, undirected graph consisting of 288 vertices and 339 edges with an initial total pipeline length of 35,572.29 meters. All three algorithms produced the same MST, consisting of 287 edges with a total length of 25,472.29 meters, resulting in a reduction of 10,100 meters or 28.39% in the pipeline network length. The estimated pipeline material cost also decreased from IDR 4,730,342,246 to IDR 3,393,791,876, yielding a cost saving of IDR 1,336,550,370 or 28.25%. In terms of computational efficiency, the Boruvka algorithm achieved the fastest execution time of 0.0006926 seconds, followed by the Prim algorithm at 0.0045739 seconds, while the Reverse Delete algorithm required the longest execution time of 0.16795 seconds. Therefore, the Boruvka algorithm was the most computationally efficient algorithm for the dataset used in this study. Keywords: graph theory, minimum spanning tree, Prim algorithm, Reverse Delete algorithm, Boruvka algorithm, clean water distribution pipeline network.