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.
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.
No comments:
Post a Comment