TUGAS AKHIR
Topik Tugas Akhir : Kajian Matematika Komputasi
PENERAPAN ALGORITMA POHON MERENTANG MINIMUM PADA GRAF TERHUBUNG BERBOBOT TAK BERARAH DENGAN MATLAB R2012B
TUGAS AKHIR Diajukan Kepada Fakultas Keguruan dan Ilmu Pendidikan Universitas Muhammadiyah Malang sebagai Salah Satu Prasyarat untuk Mendapatkan Gelar Sarjana Pendidikan Matematika
oleh : HAMIM AFIF NURHAM NIM : 201010060311049
PROGRAM STUDI PENDIDIKAN MATEMATIKA FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS MUHAMMADIYAH MALANG 2014
LEMBAR PERSETUJUAN
Tugas Akhir dengan Judul: PENERAPAN ALGORITMA POHON MERENTANG MINIMUM PADA GRAF TERHUBUNG BERBOBOT TAK BERARAH DENGAN MATLAB R2012B
Oleh: HAMIM AFIF NURHAM NIM: 201010060311049
Telah memenuhi persyaratan untuk dipertahankan di depan Dewan Penguji dan disetujui pada tanggal 23 Oktober 2014
Menyetujui, Pembimbing I
Dr. Yus Mochamad Cholily, M.Si.
Pembimbing II
Drs. Hendarto Cahyono, M.Si.
ii
LEMBAR PENGESAHAN
Dipertahankan di depan Dewan Penguji Tugas Akhir Program Studi Pendidikan Matematika Fakultas Keguruan dan Ilmu Pendidikan Universitas Muhammadiyah Malang dan Diterima untuk Memenuhi Persyaratan Memperoleh Gelar Sarjana (S1) Pada Tanggal: 23 Oktober 2014
Mengesahkan: Fakultas Keguruan dan Ilmu Pendidikan Universitas Muhammadiyah Malang
Dekan,
Dr. Poncojari Wahyono, M.Kes.
Dewan Penguji, 1. Erwin Qodariyah, M.Pd. 2. Agung Deddiliawan I., M.Pd.
Tanda Tangan 1. ……………… 2. ………………..
3. Dr. Yus Mochamad Cholily, M.Si. 3. ……………… 4. Drs. Hendarto Cahyono, M.Si.
4. ………………..
iii
SURAT PERNYATAAN Saya yang bertanda tangan di bawah ini: Nama
: Hamim Afif nurham
Tampat tanggal lahir : Kupang, 13 Januari 1993 NIM
: 201010060311049
Fakultas
: Keguruan dan Ilmu Pendidikan
Program Studi
: Pendidikan Matematika
Dengan ini menyatakan dengan sebenar-benarnya bahwa: 1. Skripsi dengan judul “Penerapan Algoritma Pohon Merentang Minimum Pada Graf Terhubung Berbobot Tak Berarah dengan MATLAB R2012b” adalah hasil karya saya, dan dalam naskah skripsi ini tidak terdapat karya ilmiah yang pernah diajukan oleh orang lainuntuk memperoleh gelar akademik di suatu Perguruan Tinggi, dan tidak terdapat karya atau pendapat yang pernah ditulis atau diterbitkan oleh orang lain, baik sebagian atau keseluruhan, kecuali secara tertulis dikutip dalam naskah ini dan disebutkan dalam sumber kutipan atau daftar pustaka. 2. Apabila ternyata di dalam naskah skripsi ini dapat dibuktikan terdapat unsureunsur plagiasi, saya bersedia skripsi ini digugurkan dan gelar akademik yang telah saya peroleh dibatalkan, serta diproses dengan ketentuan hukum yang berlaku. 3. Skripsi ini dapat disajikan sumber pustakayang merupakan hak bebas royalty non eksklusif. Demikian pernyataan ini saya buat dengan sebenar-benarnya untuk dipergunakan sebagaimana mestinya. Malang, 24 Oktober 2014 yang menyatakan,
HAMIM AFIF NURHAM NIM: 201010060311049
iv
KATA PENGANTAR Puji syukur Alhamdulillah kepada Allah SWT. yang Maha Mengetahui lagi Maha Penyayang, karena dengan rahmat dan hidayat-Nya, penulis dapat menyelesaikan Tugas Akhir dengan judul “Penerpan Algoritma Pohon Merentang Minimum Pada Graf Terhubung Berbobot Tak Berarah dengan MATLAB R2012b”. Sholawat serta salam semoga tercurah kepada Rosulullah SAW., keluarga, para sahabatnya serta seluruh pengikutnya hingga akhir zaman. Tugas Akhir ini mengkaji tentang penerapan pohon merentang minimum pada graf tehubung berbobot tak berarah yang merupakan salah satu konsep dari teori graf. Penentuan pohon merentang minimum menerapkan dua algoritma yaitu algoritma Kruskal dan algoritma Prim. Algoritma-algoritma tersebut kemudian disusun dengan struktur bahasa pemrograman MATLAB R2012b sehingga menghasilkan sebuah program yang dapat digunakan untuk menentukan pohon merentang dengan jumlah sisi minimum dari sebuah graf terhubung berbobot tak berarah yang disajikan dalam bentuk gambar dan nilai. Penulis menyadari bahwa Tugas Akhir ini dapat diselesaikan berkat bimbingan, bantuan, dan motivasi dari banyak pihak. Oleh karena itu dengan ketulusan hati penulis menghaturkan rasa hormat dan terimakasih kepada: 1.
Dr. Yus M. Cholily, M.Si., selaku dosen pembimbing I yang telah meluangkan waktu dan kesabaran dalam memberi petunjuk, bimbingan dan pengarahan kepada penulis sehingga terselesaikan skripsi ini.
2.
Drs. Hendarto Cahyono, M.Si., selaku dosen pembimbing II yang telah memberikan
pengarahan
dan
bimbingan
kepada
penulis
sehingga
terselesaikan skripsi ini. Semoga Allah SWT. menunjukan jalan dan memberikan cahaya-Nya, serta serta melapangkan dada kita dengan limpahan iman dan keindahan tawakkal kepada-Nya. Penulis berharap semoga skripsi ini bermanfaat bagi semua pihak yang berkepentingan. Namum demikian tiada manusia yang sepurna, oleh karena itu v
kritik dan saran yang membangun sangat kami harapkan untuk menjadikan skripsi ini lebih sempurna. Malang,
Penulis
vi
MOTTO
“Karena sesungguhnya setelah kesulitan ada kemudahan, sesungguhnya setelah kesulitan ada kemudahan, maka apabila kamu telah selasai dari suatu urusan, kerjakanlah dengan sungguh-sungguh urusan lain.” (Al-Inshirah:7-9).
“Bukannya tidak bisa, tetapi belum bisa.”
Talk less do more “Sedikit bicara banyak bekerja.”
vii
PERSEMBAHAN
Rasa syukur kepada Allah SWT yang memberikan Rahmat-Nya, nikmat-Nya, dan hidayah-Nya dan Rosulullah SAW yang memberikan petunjuk ke jalan yang terang dan benar sehingga penulis dapat menyelesaikan Tugas Akhir ini. Alhamdulillah dengan segala kerendahan hati, kupersembahkan karya ini kepada: 1.
Ayahanda Nurdin Halamai yang telah memotivasiku dengan beribu pengalaman hidup beliau. Ibunda Endang Murni (Almh) yang telah berjuang mengandung dan melahirkanku serta mengajariku arti kasih sayang yang sebenarnya. Ibunda Binura yang telah membesarkanku dan mengingatkanku untuk makan dan minum obat selama masa kuliahku. Kepada kakak-kakakku, Ahid Anshori Nurham, Ifah Nuzula Nurham (almh), Insiana Nurham, dan Bonan Sani Nurham, yang telah memotivasiku dengan ketegaran dan nasihatnasihat mereka.
viii
DAFTAR ISI Halaman Judul.......................................................................................................... i Lembar Persetujuan ................................................................................................. ii Lembar Pengesahan ............................................................................................... iii Surat Pernyataan..................................................................................................... iv Kata Pengantar .........................................................................................................v Halaman Motto....................................................................................................... vi Halaman Persembahan .......................................................................................... vii Kata Pengantar ..................................................................................................... viii Abstrak ................................................................................................................... ix Abstract ....................................................................................................................x Daftar Isi................................................................................................................. xi Daftar Tabel ......................................................................................................... xiii Daftar Gambar...................................................................................................... xiv Daftar Lampiran ................................................................................................... xvi BAB I PENDAHULUAN ........................................................................................1 1.1
Latar Belakang ......................................................................................1
1.2
Rumusan Masalah .................................................................................3
1.3
Pembatasan Masalah .............................................................................3
1.4
Tujuan Kajian ........................................................................................4
1.5
Manfaat Kajian ......................................................................................5
BAB II KAJIAN PUSTAKA ...................................................................................6 2.1
Konsep Graf ..........................................................................................6
2.2
Terminologi Graf...................................................................................9
2.3
Jenis-jenis Graf ....................................................................................13
2.4
Graf Khusus.........................................................................................17
2.5
Matriks Ketetanggaan (Matrix Adjecency) .........................................18
2.6
Konsep Pohon (Tree) ..........................................................................20
ix
2.7
Sifat-sifat Pohon ..................................................................................22
2.8
Pohon Merentang ................................................................................27
2.9
Pohon Merentang Minimum ...............................................................28
2.10 Algoritma Kruskal ...............................................................................28 2.11 Algoritma Prim ....................................................................................32 2.12 MATLAB (Matrix Laboratory) R2012b...............................................35 2.13 Bagian-bagian Antarmuka (Interface) MATLAB ................................35 2.14 Operator Komputasi ............................................................................36 2.15 Prosedur Penulisan Variabel ...............................................................38 2.16 Bagian Antarmuka Grafik Pada MATLAB R2012b ............................39 BAB III PEMBAHASAN ......................................................................................41 3.1
Pohon Merentang ................................................................................41
3.2
Pohon Merentang Minimum ...............................................................44
3.3
Algoritma Kruskal ...............................................................................46
3.4
Algoritma Prim ....................................................................................47
3.5
Pohon Merentang Minimum dengan Algoritma Kruskal dan Algoritma Prim ...................................................................................49
3.6
Langkah Penyusunan Program ............................................................57
3.7
Bagian-bagian Program .......................................................................61
3.8
Diagram Alir (Flowchart Program) ....................................................65
3.9
Langkah-langkah Pengoperasian Program ..........................................67
BAB IV PENUTUP ...............................................................................................73 4.1
Kesimpulan..........................................................................................73
4.2
Saran ....................................................................................................74
DAFTAR PUSTAKA ............................................................................................76 LAMPIRAN ...........................................................................................................77
x
DAFTAR PUSTAKA Abdussakir. (2009). Teori Graf. Malang: UIN-Malang Press. Agnarsson, G., & Greenlaw, R. (2007). Graph Theory: Modeling, Applications, and Algorithms. New Jersey: Prentice Hall. Gilat, A. (2013). MATLAB: An Introduction with Applications (5th ed.). Ohio: Wiley. Harris, J. M., Hirst, J. L., & Mossinghoff, M. J. (2008). Combinatorics and Graph Theory (2nd Edition ed.). New York: Springer. Hunt, B. R., Lipsman, R. L., & Rosenberg, J. M. (2001). A Guide to MATLAB for Beginners and Experienced Users. Cambridge: Cambridge University Press. Johnsobaugh, R. (2008). Discrete Mathematics. New Jersey: Prentice Hall. Kolman, B., Busby, R. C., & Ross, S. C. (2000). Discrete Mathematical Structures (4th Edition ed.). New Jersey: Prentice Hall. Lipschutz, S., & Lipson, M. (2008). Matematika Diskret (3rd Edition ed.). Jakarta: Penerbit Erlangga. Munir, R. (2012). Matematika Diskrit. Bandung: Informatika. Rosen, K. H. (2011). Discrete Mathematics and Its Applications (7th Edition ed.). New York: Mc Graw Hill. Sharma, S. C. (2007). Graph Theory. New Delhi: Discovery Publishing House. Sianipar, R. H. (2013). Pemrograman MATLAB dalam contoh dan Penerapan. Bandung: Penerbit Informatika. Sutrisno, I. (2009). Pemrograman Komputer dengan Software MATLAB. Surabaya: ITS Press. Vasudev, C. (2006). Graph Theory with Applications. New Delhi: New Age international Publisher.
xi
