LAPORAN TUGAS AKHIR
Topik Tugas Akhir : Kajian Matematika
ANALISIS ASUMSI ALGORITMA FLOYD WARSHALL PADA GRAF BERARAH
TUGAS AKHIR Diajukan Kepada Fakultas Keguruan dan Ilmu Pendidikan Universitas Muhammadiyah Malang Sebagai Salah Satu Prasyarat untuk Mendapatkkan Gelar Sarjana Pendidikan Matematika
Oleh: OKTA FEBRIANSYAH NIM: 201010060311109
PROGRAM STUDI PENDIDIKAN MATEMATIKA FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS MUHAMMADIYAH MALANG 2015
i
LEMBAR PERSETUJUAN
Tugas Akhir dengan Judul: ANALISIS ASUMSI ALGORITMA FLOYD WARSHALL PADA GRAF BERARAH
Oleh: OKTA FEBRIANSYAH NIM: 201010060311109
telah memenuhi persyaratan untuk dipertahankan di depan Dewan Penguji dan disetujui pada tanggal 26 Agustus 2015
Menyetujui, Pembimbing I
Pembimbing II
Dr. Moh. Mahfud Effendi, M.M.
Alfiani Athma Putri Rosyadi, M.Pd.
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) Pendidikan Matematika pada Tanggal: 26 Agustus 2015
Mengesahkan: Fakultas Keguruan dan Ilmu Pendidikan Universitas Muhammadiyah Malang
Dekan,
Dr. Poncojari Wahyono, M. Kes.
DewanPenguji:
TandaTangan 1. …………………….
1. Dr. Siti Inganah, M.M.,M.Pd.
2. …………………….
2. Rizal Dian Azmi, M.Sc.
3. …………………….
3. Dr. Moh. Mahfud Effendi, M.M.
4. …………………….
4. Alfiani Athma Putri Rosyadi, M.Pd.
iii
SURAT PERNYATAAN
Saya yang bertanda tangan di bawah ini: Nama
: Okta Febriansyah
Tempat tanggal lahir
: Malang, 19 Oktober 1991
NIM
: 201010060311109
Fakultas
: Keguruan dan Ilmu Pendidikan
Program Studi
: Pendidikan Matematika
Denganini menyatakan dengan sebenar-benarnya bahwa: 1.
2.
3.
Skripsi dengan berjudul “Analisis Asumsi Algoritma Floyd Warshall pada Graf Berarah” adalah hasil karya saya, dan dalam naskah skripsi ini tidak terdapat karya ilmiah yang pernah diajukan oleh orang lain untuk 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. Apabila ternyata di dalam naskah skripsi ini dapat dibuktikan terdapat unsurunsur plagiasi, saya bersedia skripsi ini digugurkan dan gelar akademik yang telah saya peroleh dibatalkan, serta diproses dengan ketentuan hukum yang berlaku. Skripsi ini dapat dijadikan sumber pustaka yang merupakan hak bebas royalty non eksklusif.
Demikian pernyataan ini saya buat dengan sebenar-benarnya untuk dipergunakan sebagaimana mestinya. Malang, 02 September 2015 yang menyatakan,
Okta Febriansyah NIM: 201010060311109
iv
MOTTO
Jangan pernh mengeluh ketika tangan belum dapat menggapai bintang di langit, tapi bersyukurlah ketika kamu masih dapat menginjakkan kaki di bumi. Kamu tak akan pernah menyesal ketika kamu mati untuk meraih mimpi mu, namun kamu akan menyesal seumur hidup mu ketika kamu menyerah untuk meraih mimpi mu itu. (OP) “Dan memohonlah pertolongan (kepada Allah) dengan sabar dan shalat. Dan (shalat) itu sungguh berat, kecuali bagi orang-orang yang khusyuk”. (Q.S Al-Baqoroh: 45) Setiap orang belum tentu baik, tetapi selalu ada kebaikan pada setiap orang. Jangan terlalu cepat menilai seseorang, karena setiap orang suci pasti punya masa lalu, dan setiap pendosa masih punya masa depan (Oscar Wilde)
v
PERSEMBAHAN
Puji syukur kehadirat Allah SWT yang telah memberikan Rahmat dan Hidayah-Nya serta shalawat serta salam tetap tercurahkan kepada Rosulullah Muhammad SAW yang telah menuntun umat islam dari zaman jahiliyah zaman yang penuh dengan kebodohan serta pembodohan menuju zaman terang dan zaman kebenaran serta zaman terpelajar. Tugas Akhir ini saya persembahkan untuk: 1.
Ibu saya yang saya cintai serta Alm. Ayah yang selalu saya banggakan, terimakasih atas doa, dorongan materi dan moral yang selalu di berikan tiada henti kepada saya.
2.
Kakak-kakakku, serta saudara-saudara yang lainnya, terimakasih atas dukungannya selama ini. Doa ku selalu menyertaimu.
3.
Bapak. Dr. Moh. Mahfud Effendi, M.M. dan Ibu Alfiani Athma Putri Rosyadi, M.Pd. selaku dosen pembimbing I dan II yang selalu sabar membimbing serta memberi arahan saya hingga tugas akhir ini terselesaikan.
4.
Teman-teman kelas Matkom C angkatan 2010, Ustad, Paeq, Ucup, Aris, Pras, Johan, Fadhil dan Aris yang selalu memberi motifasi, semangat dan saling memberi masukan pada setiap langkah hidup ini.
vi
KATA PENGANTAR Puji syukur Alhamdulillah kepada Allah SWT, yang Maha Mengetahui lagi Maha Penyayang, karena dengan rahmat dan hidayah-Nya, penulis dapat menyelesaikan tugas Tugas Akhir judul “Analisi Algoritma Floyd Warshall pada Graf Berarah”. Shalawat serta salam selalu tercurahkan kepada Rosulullah Muhammad SAW, Keluarga dan para Sahabatnya. Tugas Akhir ini merupakan kajian mengenai asumsi dari algoritma Floyd Warshall untuk menentukan jalur terpendek pada graf berarah. Dimana apabila asumsi tersebut tidak terpenuhi, maka akan menjadikan suatu algoritma yang tidak memberikan solusi yang benar serta akan menjadikan suatu algoritma yang tidak efektif dan tidak efisien dalam proses pengerjaannya. Penulis menyadari bahwa Tugas Akhir ini dapat terselesaikan berkat bimbingan, bantuan dan motivasi dari banyak pihak. Oleh karena itu, dengan setulus hati penulis mengucapkan terimakasih kepada: 1.
Dr. Moh. Mahfud Effendi, M.M., selaku dosen pembimbing I yang telah meluangkan waktu dan kesabaran dalam memberi petunjuk, bimbingan dan pengarahan kepada penulis sehingga terselesaikan Tugas Akhir ini.
2.
Alfiani Athma Putri Rosyadi, M.Pd., selaku dosen pembimbing II yang telah meluangkan waktu untuk membimbing penulis dalam menyelesaikan Tugas Akhir ini. Semoga Allah SWT menunjukkan jalan dan memberikan cahaya-Nya, serta
melapangkan dada kita dengan limpahan iman dan keindahan tawakal kepadaNya. Penulis berharap semoga Tugas Akhir ini dapat bermanfaat bagi semua pihak yang berkepentingan. Namun dalam penulisan Tugas Akhir ini penulis menyadari masih banyak kekurangan dan kelemahan karena terbatasnya kemampuan penulis, oleh karena itu kritik dan saran yang membangun sangat dibutuhkan, guna mengembangkan Tugas Akhir ini ke depannya. Malang, 02 September 2015
Penulis
vii
DAFTAR ISI
Halaman Judul ...........................................................................................
i
Lembar Persetujuan ...................................................................................
ii
Lembar Pengesahan ..................................................................................
iii
Halaman Pernyataan Keaslihan .................................................................
iv
Halaman Motto ..........................................................................................
v
Halaman Persembahan ..............................................................................
vi
Kata Pengantar ..........................................................................................
vii
Abstrak ......................................................................................................
viii
Abstract .....................................................................................................
ix
DAFTAR ISI ..............................................................................................
x
DAFTAR GAMBAR .................................................................................
xii
DAFTAR LAMPIRAN ..............................................................................
xiii
BAB I PENDAHULUAN ..........................................................................
1
1.1 Latar Belakang ........................................................................
1
1.2 Rumusan Masalah ...................................................................
5
1.3 Pembatasan Masalah ...............................................................
5
1.4 Tujuan Kajian ..........................................................................
5
1.5 Manfaat Kajian ........................................................................
5
1.6 Metode Penelitian ...................................................................
6
1.7 Kerangka Konseptual .............................................................
7
BAB II LANDASAN TEORI ....................................................................
9
2.1 Graf...........................................................................................
9
2.1.1 Graf Secara Umum ........................................................
9
2.1.2 Jenis Graf Berdasarkan Orientasi Arahnya ...................
10
1. Graf Tak-Berarah ......................................................
10
2. Graf Berarah ..............................................................
11
2.2 Representasi Graf Kedalam Bentuk Matriks ...........................
12
x
2.3 Lintasan ....................................................................................
14
2.4 Jarak Terpendek (Shortes Path) Pada Graf .............................
15
2.4.1 Algoritma Jarak Terpendek ...........................................
15
1. Algoritma Floyd Warshall .......................................
15
BAB III PEMBAHASAN .............................................................
18
3.1 Analisis Asumsi ke-1 ..............................................................
18
3.1.1 Dibuktikan dengan graf yang memiliki arah ganda pada garisnya .............................................................................
18
3.1.2 Dibuktikan dengan graf yang memiliki satu arah pada setiap garisnya ..................................................................
21
3.2 Analisis Asumsi ke-2 ...............................................................
27
3.3 Pengaruh dari asumsi tersebut .................................................
27
3.3.1 Pengaruh Asumsi ke-1 .....................................................
18
3.3.2 Pengaruh Asumsi ke-2 .....................................................
21
BAB IV PENUTUP ...................................................................................
28
4.1 Kesimpulan...............................................................................
28
4.2 Saran .........................................................................................
28
DAFTAR PUSTAKA .................................................................................
29
LAMPIRAN ...............................................................................................
31
xi
DAFTAR GAMBAR
Gambar 1.1
Peta Konsep .......................................................................
8
Gambar 2.1
Graf G .................................................................................
10
Gambar 2.2
Graf berarah (undirected graph) ........................................
11
Gambar 2.3
Graf Berarah (directed graph/digraph) .............................
11
Gambar 2.4
Graf Sederhana dan Graf Rangkap ....................................
12
Gambar 2.5
Representasi Graf G kedalam Bentuk Matriks Kedekatan
13
Gambar 2.6
Graf Berarah (directed graph/digraph) ..............................
13
Gambar 2.7
Graf G .................................................................................
14
Gambar 2.8
Graf G .................................................................................
14
Gambar 2.9
Digraph G...........................................................................
15
Gambar 2.10 Flowchart ..........................................................................
17
Gambar 3.1
Digraph G dengan arah ganda ............................................
18
Gambar 3.2
Digraph G dengan satu arah ..............................................
21
Gambar 3.3
Digraph G dengan arah ganda ............................................
24
Gambar 3.4
Digraph G dengan satu arah ...............................................
25
xii
DAFTAR LAMPIRAN
Lampiran 1:
Proses pembahasan algoritma jalur terpendek pada graf yang memiliki arah ganda pada garisnya ..........................
xiii
31
DAFTAR PUSTAKA
Abdussakir, Nilna Niswatin A. dan Fifi Framelia N. 2009.Teori Graf. UINMalang Press: Malang. Aji, Rizqon Halal Syah .15 juni 2014: jurnal: “Khazanah Sains dan Matematika Dalam Islam” http://www.academia.edu/9990160/KHAZANAH_SAINS_DAN_MATEMATIKA_DALAM_ISLAM_Rizqon_Halal_Syah_Aji,diakses pada tanggal 30 Maret 2015. Andhy. 2011. Jurnal Unikom: “Penerapan Algoritma Label-Setting Untuk Menentukan Jalur Terpendek Dari Dua Node Pada Peta Kota Bandung“, http://elib.unikom.ac.id/gdl.php?mod=browse&op=read&id=jbptunikompp -gdl-andhynim10-26393&q=andhy, diakses pada tanggal 15 Maret 2015. Ali, Thantowi. 2003 : Jurnal:”Analisis Teori Graf, Volume II Univ. Diponegoro”, http://eprints.undip.ac.id/32238/6/M03_Ali_Thantowi_chapter_II.pdf, diakses pada tanggal 21 April 2015 Cahyono, Hendarto.2000:PengantarTeori Graf. UMM: Malang. Hidayat, Andri, Mei 2013. Jurnal: ”Pencarian rute terpendek dengan menggunakan algoritma Fyold Warshall untuk taksi dengan rute Terminal Leuwi Panjang – Dipati Ukur”, http://elib.unikom.ac.id/files/disk1/625/jbptunikompp-gdl-andrihiday31214-10-unikom_a-i.pdf,
diakses
pada
tanggal 4 Maret 2015. Kurniawati, Anik. 2007: Jurnal UMM: “Implementasi Algoritma Floyd Warshall Untuk Mencari Jarak Terpendek Dengan Menggunakan Program Turbo Pascal”. Lipschutz, Seymour dan Lipson, March. 2008: Matematika Diskrit, Edisi Ketiga. Erlangga. Masido, Nurio Juliandatu. 2007: jurnal Program Studi Teknik Informatika, Institut Teknologi Bandung : “Pengaplikasian Graf Dalam Kehidupan Sehari-Hari”,
29
http://infor-matika.stei.itb.ac.id/~rinaldi.munir/Matdis/2006-2007/Makalah/Makalah060-784.pdf, diakses pada tanggal 30 Maret 2015. Siang, Jong Jek. 2002: Matematika Diskrit Dan Aplikasinya Pada Ilmu Komputer. Andi: Yokyakarta. Suryadi. MT. 1996: Pengantar Analisis Algoritma. Gunadarma: Jakarta. Saniman dan M. Fathoni. 2008: Jurnal Saintikom: “Pengantar Algoritma Dan Pemrograman”,
http://lppm.trigunadharma.ac.id/public/fileJurnal/6BEB3-
OK-Jurnal13-Sani-MF-Algo1-1.pdf, diakses pada tanggal 4 Maret 2015. Wibisono, Samuel. 2008: Matematika Diskrit Edise Ke-II. Graha Ilmu: Yogyakarta. Wilson, Robin J. dan Watkins, John J.1989: Graphs An Introductory Approach.
30
