1
BAB 1
PENDAHULUAN
1.1 Latar Belakang
Hubungan antara titik-titik dalam graf kadang-kadang perlu diperjelas. Hubungannya tidak cukup hanya menunjukkan titik-titik mana yang berhubungan langsung, tetapi juga seberapa kuatkah hubungan itu. Sebagai contoh, andaikata suatu graf menyatakan “peta” suatu daerah. Titik-titik graf menyatakan kota-kota di daerah tersebut. Garis-garis dalam graf menyatakan jalan yang menghubungkan kota-kota tersebut. Jadi, setiap garis dalam graf berhubungan dengan menyatakan bobot garis tersebut.
Algoritma Kruskal adalah algoritma untuk mencari pohon merentang minimum secara langsung didasarkan pada algoritma MST (Minimum Spanning Tree) umum. Pada algoritma Kruskal sisi-sisi di dalam graf diurut terlebih dahulu berdasarkan bobotnya dari kecil ke besar. Sisi yang dimasukkan ke dalam himpunan T adalah sisi graf G sedemikian sehingga T adalah pohon. Sisi dari graf G ditambahkan ke T jika tidak membentuk sirkuit di T. (Aceng Hasiri, 2012)
Universitas Sumatera Utara
2
Aplikasi yang sering dipakai dalam graf berlabel adalah mencari pohon rentang dengan total bobot seminimum mungkin atau disebut pohon merentang minimum. Jika semua jaringan listrik dibuat terlalu banyak maka biaya akan boros. Beberapa jalur yang menghubungkan 2 kota secara langsung tidak perlu dibuat karena kota-kota tersebut tetap dapat teraliri listrik secara tidak langsung, yaitu dengan melalui kota lain sedemikian hingga total biaya pemasangan jaringan listrik seminimum mungkin. Atau dengan kata lain, mencari pohon rentang dengan total bobot seminimum mungkin. Cara yang paling sederhana adalah dengan mendaftarkan semua pohon rentang yang mungkin dibuat dan menghitung total bobot tiap-tiap pohon rentang. Selanjutnya dipilih pohon rentang dengan total bobot yang paling kecil. Metode itu tidak efisien, terutama pada graf yang cukup besar karena terdapat banyak sekali pohon rentang yang dapat dibuat.
Melihat hal itu penulis ingin membantu menemukan pohon rentang minimum dengan total bobot yang paling kecil secara sederhana. Sehingga untuk mengatasi permasalahan di atas penulis mengajukan proposal dengan judul : “MENENTUKAN
MINIMUM
SPANNING
TREE
MENGGUNAKAN
ALGORITMA KRUSKAL DENGAN BAHASA PEMROGRAMAN C ”.
1.2 Rumusan Masalah
Berdasarkan latar belakang di atas, rumusan masalah dalam penelitian ini adalah sebagai berikut Apakah dapat dibuat program menggunakan konsep bahasa pemrograman C untuk menentukan minimum spanning tree menggunakan algoritma kruskal?
Universitas Sumatera Utara
3
1.3 Batasan Masalah
Dalam perancangan program ini dilakukan beberapa batasan sebagai berikut : 1. Bahasa pemrograman yang digunakan dalam membuat program ini adalah bahasa C. 2. Aplikasi ini terfokus hanya mencari minimum spanning tree pada suatu graph tertentu. 3. Penulisan dan Penghitungan hanya dilakukan pada satu jenis metode, yaitu dengan menggunakan Algoritma Kruskal 4. Menggunakan Graf Berlabel dan Graf terhubung.
1.4 Tujuan
Penelitian ini bertujuan untuk mengaplikasikan algoritma kruskal dan menentukan Minimum Spanning Tree suatu Graph dengan bahasa Pemrograman C
1.5 Manfaat
Manfaat yang diperoleh dari program Minimum Spanning Tree ini : 1. Untuk mencari jalan penghubung yang dapat menghubungkan semua titik dalam jaringan secara bersamaan sampai diperoleh jarak minimum. 2. Memberi kemudahan pengguna untuk mengetahui yang harus dilalui untuk mencapai suatu daerah.
Universitas Sumatera Utara
4
1.6 Metodologi Penelitian
Metodologi penelitian yang digunakan penulis untuk menyelesaikan permasalahan yang terjadi di atas adalah :
1. Penelitian Kepustakaan(Library Research) Pengumpulan data yang erat kaitannya dengan permasalahan dengan cara membaca buku-buku, makalah, dan membaca bahan-bahan sumber lainnya diperpustakaan USU, LIDA dan perpustakaan lainnya..
2. Analisis Sistem Melakukan analisis sistem terhadap masalah menentukan minimum spanning tree, Serta mempelajari matriks yang berhubungan dengan Algoritma Kruskal.
3. Desain Sistem Pada tahap ini dilakukan perancangan program, membuat desain progam tersebut.
4. Pengujian Program Proses pengujian program akan dilakukan setelah semua perancangan dilakukan, dan ketika terdapat beberapa kekurangan yang ada di program pada saat pengujian program dilaksanakan, maka penulis akan melakukan perbaikan pada rancangan guna memperoleh hasil akhir yang maksimal.
Universitas Sumatera Utara
5
5. Penulisan Tugas Akhir Pengerjaan tugas akhir penulis sekaligus membuat laporan tugas akhir yang mencakup bagaimana pembuatan dan penjelasan tentang tugas akhir penulis.
1.2 Sistematika Penulisan
Dalam penulisan tugas akhir ini, penulis membentuk suatu sistematika penulisan yang bertujuan untuk menggambarkan secara ringkas bab-bab yang mencakup hal– hal sebagai berikut:
BAB 1
: PENDAHULUAN Bab ini menguraikan latar belakang penulisan, rumusan masalah, masalah, tujuan, manfaat, metodologi penelitian, dan sistematika penulisan.
BAB 2
: LANDASAN TEORI Bab ini menjelaskan tentang landasan teori konsep dasar dan teoriteori yang mendukung pembahasan untuk tema penulisan ini yang didapat dari beberapa literatur.
BAB 3
: PERANCANGAN SISTEM Bab ini membahas tentang perancangan program Menentukan Minimum Spanning Tree menggunkan Algoritma Kruskal dengan bahasa pemrograman C dan gambaran umum rancangannya.
Universitas Sumatera Utara
6
BAB 4
: IMPLEMENTASI SISTEM Bab ini membahas analisa hasil dan pembahasan Program Menentukan Minimum Spanning Tree yang dirancang, pembuatan program, tampilan dari program, dan pengujian program.
BAB 5
: KESIMPULAN DAN SARAN Bab ini menguraikan tentang kesimpulan dari bab-bab yang ada, dan memberi saran-saran dari hasil akhir pembuatan progam yang berguna untuk melengkapi dan menyempurnakan pengembangan program ini untuk kedepannya.
Universitas Sumatera Utara
