Keefektifan penggunaan algoritma boruvka, algoritma prim, algoritma kruskal, dan algoritma sollin dalam menentukan pohon merentang minimum

INDONESIA:

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.

ENGLISH:

Graph theory is a branch of mathematics and a main topic which has many applications at the moments. Graph is one equipment applied for finding for solution from problems of discrete met in the real world. At this thesis presents graph with tree concept to solve problem that is looking for the most effective algorithm between Boruvka algorithm, Prim algorithm, Kruskal algorithm, and Sollin algorithm. While purpose of this thesis is determining which algorithm of is the most effective applied in determining.

Boruvka Algorithm, Prim algorithm, Kruskal algorithm, and Sollin algorithm are algorithms applied in building minimum spanning tree. How the steps of the four algorithms in determining minimum spanning tree from graph presented in this thesis and how comparison between them. Data applied is weighted graph which at this thesis presented 4 weighted graphs which every weighted graph loads 8 points with different sides number. Hence the research type of this thesis applied is bibliography study ( Library Research).

The result of this research is description of steps in determining minimum spanning tree by using four algorithms. Then is continued with comparative analysis out of the four algorithms. The result of this research indicates that the form of spanning tree and the number of weight spanning it is having equality for every weighted graph. What differentiates between Boruvka algorithm, Prim algorithm, Kruskal algorithm, and Sollin algorithm are different so algorithm the that number of steps applied by fourth of algorithms are different. For graph G with number of sides = 2(p-1), algoritma Sollin is the most efficient and effectively compared to Boruvka algoritma, Prim algorithm, and Kruskal algoritma. For graph G with number of sides = 2(p - 1) but there is side having the same weight, Prim algoritma and Sollin algoritma are the most efficient and effectively compared to Boruvka algoritma, and Kruskal algoritma. For graph G with number of sides < 2(p-1), Sollin algoritma is more efficient and effectively compared to Boruvka algorithm, Prim algorithm, and Kruskal algorithm. For graph G with number of sides > 2(p-1), algorithm Kruskal is the most efficient and effectively compared to Boruvka algorithm, Prim algorithm, and Sollin algorithm. Discussion about the minimum spanning tree admits of continued for research of minimum spanning tree other graphs type.