ABSTRAK
Teori graf merupakan cabang matematika sekaligus pokok bahasan yang memiliki banyak terapan saat ini. Graf adalah satu alat yang digunakan untuk untuk mencari solusi dari permasalahan diskret yang ditemui dalam dunia nyata. Pada skripsi ini menghadirkan graf dengan konsep pohon untuk memecahkan masalah yaitu mencari algoritma yang paling efektif dari algoritma Boruvka, algoritma Prim, algoritma Kruskal, dan algoritma Sollin. Sedangkan tujuan penulisan skripsi ini adalah menentukan algoritma manakah yang paling efektif digunakan dalam menentukan pohon merentang minimum. Algoritma Boruvka, algoritma Prim, algoritma Kruskal, dan algoritma Sollin adalah algoritma yang digunakan dalam membangun pohon merentang minimum. Bagaimanakah langkah-langkah keempat algoritma ini dalam menentukan pohon merentang minimum dari graf yang disajikan di dalam skripsi ini dan bagaimana perbandingan antara keempatnya. Data yang digunakan adalah graf berbobot yang pada skripsi ini disajikan 4 graf berbobot yang setiap graf berbobot memuat 8 titik dengan jumlah sisi yang berbeda. Maka dalam skripsi ini jenis penelitian yang digunakan adalah studi kepustakaan (Library Research). Hasil penelitian ini merupakan pendeskripsian langkah-langkah dalam menentuka pohon merentang minimum dengan menggunakan empat algoritma. Setelah itu dilanjutkan dengan analisis perbandingan dari empat algoritma tersebut. Hasil penelitian menunjukkan bahwa bentuk pohon merentang dan jumlah bobot merentangnya mempunyai kesamaan untuk setiap graf berbobot tersebut. Yang membedakan antara algoritma Boruvka, algoritma Prim, algoritma Kruskal, dan algoritma Sollin adalah algoritmanya berbeda-beda sehingga jumlah langkah yang digunakan keempat algoritma adalah berbeda-beda. Untuk graf G dengan jumlah sisi = 2(p - 1) algoritma Sollin paling efektif dan efisien dibandingkan algoritma Boruvka, algoritma Prim, dan algoritma Kuskal. Untuk graf G dengan jumlah sisi = 2(p - 1) namun terdapat sisi yang memiliki bobot yang sama algoritma Prim dan algoritma Sollin paling efektif dan efisien dibandingkan algoritma Boruvka, dan algoritma Kuskal. Untuk graf G dengan jumlah sisi < 2(p - 1) algoritma Sollin paling efektif dan efisien dibandingkan algoritma Boruvka, algoritma Prim, dan algoritma Kuskal. Untuk graf G dengan jumlah sisi > 2(p - 1) algoritma Kruskal paling efektif dan efisien dibandingkan algoritma Boruvka, algoritma Prim, dan algoritma Sollin. Pembahasan mengenai pohon merentang minimum ini masih dapat dilanjutkan untuk penelitian pohon merentang minimum pada jenis graf yang lain.
