BAB PENDAHULUAN 1.1 Latar belakang Perkembangan ilmu pengetahuan dan teknologi yang sangat pesat, tidak lepas dari peran ilmu matematika, yaitu ilmu yang menjadi solusi secara konseptual dalam menyelesaikan berbagai permasalahan yang terjadi dalam kehidupan di dunia. Dewasa ini semakin banyak muncul penggunaan model matematika maupun penalaran matematika sebagai alat bantu dalam meyelesaikan permasalahan yang dihadapi dalam berbagai disiplin ilmu. Teori graf merupakan salah satu cabang ilmu matematika yang bermanfaat dengan teori-teorinya dapat diterapkan untuk memecahkan masalah dalam kehidupan sehari-hari. Dengan mengkaji dan menganalisis model atau rumusan teori graf, dapat diperlihatkan peranan dan kegunaannya dalam memecahkan permasalahan. Permasalahan yang dirumuskan dengan teori graf dibuat sederhana, yaitu diambil aspek-aspek yang diperlukan dan dibuang aspek-aspek lainnya (Purwanto, 1998). Dalam kehidupan sehari-hari terdapat permasalahan mengenai optimasi yang dapat diselesaikan menggunakan pohon merentang minimum, atau dikenal dengan istilah Minimum Spanning Tree(MST). Misalnya masalah mencari jarak terpendek, biaya termurah, dan tenaga seminimal mungkin dalam pembangunan jalan, jaringan telepon seluler, maupun jaringan listrik. Problema kita dapat pula berupa penentuan pohon rentang dari G dengan bobot maksimal. Sebagai contoh, simpul dan ruas dari G menyajikan berturut-turut kota dan jalan raya yang menghubungkan dua kota. Kita akan membangun system transportasi antar semua kota tersebut. Kita akan mengambil sejumlah jalan raya yang paling cocok dilalui sistem tersebut. Untuk itu mula-mula kita harus memberi bobot kepada masing-masing jalan raya. Di sini kita menggolongkan setiap jalan raya itu, misalkan berdasarkan kualitas jalan, potensi ekonomi, keadaan social, potensi pariwisata sepanjang jalan, dan lain sebagainya dengan memberi suatu bobot tertentu. Semakin baik kondisi jalan raya tersebut, maka semakin tinggi bobotnya. Pemecahan bobot ini pada hakekatnya sama dengan problema mencari pohon rentang maksimal dari G, atau dikenal dengan istilah Maximum Spanning Tree. Metode untuk menentukan minimum spanning treedapat juga digunakan saat kita membutuhkan sebuah maximum spanning tree. Terkait dengan pernyataan di atas, maka perlu adanya pemecahan untuk masalah-masalah tersebut. Salah satu teori yang dapat diaplikasikan dalam menyelesaikan permasalahan-permasalahan tersebut adalah dengan penerapan teori graf. Penyelesaiaan masalah-masalah tersebut di atas, pada dasarnya menentukan terjadinya semua maximum spanning treeyang mungkin dan memperhitungkan maximum spanning tree. Di dalam sebuah graf mungkin saja terdapat lebih dari satu spanning tree. Maka harus dicari spanning tree yang mempunyai jumlah jarak terpanjang, dengan kata lain harus dicari maximum spanning tree. Mencari maksimum dari suatu spanning treemerupakan suatu masalah yang sudah cukup dikenal dalam pokok bahasan graf dan mempunyai terapan yang luas dalam praktek. Terkait dengan pernyataan di atas, dalam menentukan algoritma yang paling efektif dalam menentukan maximum spanning tree. Pentingnya aplikasi graf dalam menentukan maximum spanning tree, untuk itu diperlukan suatu algoritma yang tepat untuk menentukan maximum spanning treedalam suatu graf terhubung, berbobot, dan tidak berarah. Dalam bahasan ini akan dikaji tentang algoritma-algoritma dalam menentukan maximum spanning tree. Peneliti merasa bahwa penelitian ini merupakan salah satu penelitian yang menarik untuk dikaji, karena terdapat beberapa macam algoritma yang dapat digunakan dalam menentukan maximum spanning tree. Di sini, peneliti meneliti 3 macam algoritma yang dapat digunakan dalam menentukan maximum spanning tree yaitu algoritma Prim, algoritma Kruskal, dan algoritma Sollin, yang masing-masing algoritma memiliki aturan yang berbeda-beda dalam menentukan maximum spanning tree, sehingga peneliti merasa perlu mengkaji algoritma manakah yang paling efektif dalam menentukan maximum spanning treeagar mendapatkan perbedaan dari ketiga algoritma tersebut.
Kamis, 18 Desember 2014
Download Skripsi Mathematics:Studi Perbandingan Algoritma Prim, Algoritma Kruskal, Dan Algoritma Sollin Dalam Menentukan Pohon Merentang Maksimum
Langganan:
Posting Komentar (Atom)
0 komentar:
Posting Komentar