LAPORAN TUGAS AKHIR Topik Tugas Akhir: Kajian Matematika Murni ANALISA SISTEM TRANSPORTASI DARAT ANGKUTAN KOTA DI KOTA PASURUAN DENGAN PRESPEKTIF TEORI GRAF TUGAS AKHIR Diajukan Kepada Fakultas Keguruan dan Ilmu Pendidikan Universitas Muhammadiyah Malang Sebagai Salah Satu Prasyarat untuk Mendapatkan Gelar Sarjana Pendidikan Matematika
Oleh: AGUNG LUKMAN PRANAJAYA NIM: 201010060311040
PROGRAM STUDI PENDIDIKAN MATEMATIKA FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS MUHAMMADIYAH MALANG 2015
i
ii
iii
iv
MOTTO
“Barang siapa keluar dalam menuntut ilmu maka ia berada di jalan Allah hingga kembali” (HR.Turmudzi)
“Hai orang-orang yang beriman, bersabarlah kamu dan kuatkanlah kesabaranmu dan tetaplah bersiap siaga (di perbatasan negerimu) dan bertakwalah kepada Allah, supaya kamu beruntung.” (QS. Ali Imran: 200)
"Keberuntungan adalah sesuatu yang terjadi ketika kesempatan bertemu dengan kesiapan" “Manusia tidak merancang untuk gagal, mereka gagal untuk merancang.” ( William J. Siegel )
v
PERSEMBAHAN Puji syukur kehadirat Allah SWT yang telah menciptakan manusia dalam bentuk yang sempurna. Shalawat serta salam tetap tercurahkan kepada Rosulullah Muhammad SAW yang telah menuntun umat islam dari zaman jahiliyah menuju zaman terpelajar. Tugas Akhir ini saya persembahkan untuk: 1.
Ayah dan Ibu saya yang saya cintai, terimakasih atas do’a, dorongan materi dan moral yang selalu di berikan tiada henti kepada saya.
2.
Kakakku, Mbak Ririt, Terimakasih atas dukungannya selama ini. Do’aku selalu menyertaimu.
3.
Guru-guru dari jenjang TK hingga SMA yang telah membimbing dan memberikan ilmu yang bermanfaat untuk saya.
4.
Dosen-dosen matematika, yang telah membimbing saya mulai semester 1 hingga semester 9 ini.
5.
Teman-teman Ikatan Mahasiswa Muhammadiyah yang tidak mampu saya sebutkan satu persatu yang selalu bersama-sama untuk menimba ilmu diluar perkuliahan.
6.
Teman-teman HMJ MATRIKS periode 2011-2012 yang bahu membahu menuntaskan amanah yang diberikan mahasiswa matematika selama satu periode.
7.
Teman-teman satu angkatan dan teman-teman Matkom A 2010 khususnya Ratu, Riki, Fia, Fachrudin, Izza, Desy, Mas Hanggara. Masa-masa indahku di Malang adalah saat kita bersama menyelesaikan tugas kuliah hingga hanya sekedar kumpul-kumpul saja.
8.
Sahabat saya, Ruri, Indra, Fiqri, Mega, firdha, dan Mas Aldidik. Terimakasih sudah memberikan semangat kepada saya.
9.
Teman-teman Co Trainer dan Part Time BKMA yang selalu memberikan semangat kepada saya dalam menjalankan tugas di kantor.
vi
KATA PENGANTAR
Puji syukur penulis panjatka kehadirat Allah SWT, atas limpahan rahmat dan hidayah-Nya penulis dapat menyelesaikan Tugas Akhir dengan judul “Analisa Sistem transportasi Darat Angkutan Kota di Kota Pasuruan dengan Prespektif Teori Graf”. Shalawat serta salam selalu tercurahkan kepada Rosulullah Muhammad SAW suri tauladan yang baik bagi seluruh umat manusia. Tugas Akhir ini merupakan kajian mengenai aplikasi teori graf pada bidang transportasi. Kajian ini merepresentasikan peralihan rute angkot yang mengacu pada teori Hamilton. Tugas Akhir ini dapat terselesaikan berkat bimbingan, bantuan dan motivasi dari banyak pihak. Oleh sebab itu, dengan setulus hati penulis mengucapkan terimakasih kepada: 1.
Dr. Moh. Mahfud Effendi, MM., selaku dosen pembimbing I yang begitu sabar mengarahkan dan membimbing ketika penulis mengalami kesulitan dalam menyelesaikan Tugas Akhir ini.
2.
Dr. Sutrisno, selaku dosen pembimbing II yang telah meluangkan waktu untuk membimbing penulis dalam menyelesaikan Tugas Akhir ini.
Semoga Allah SWT membalas segala kebaikan yang telah diberikan kepada penulis. Penulis berharap Tugas Akhir ini dapat bermanfaat bagi semua pihak yang membutuhkan. Dalam penulisan Tugas Akhir ini penulis menyadari masih banyak kekurangan dan kelemahan karena terbatasnya kemampuan penulis, oleh karena itu saran dan kritik sangat dibutuhkan, guna mengembangkan Tugas Akhir ini ke depannya. Malang, 17 Januari 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 TABEL ......................................................................................
xii
DAFTAR GAMBAR .................................................................................
xiii
DAFTAR LAMPIRAN ..............................................................................
xv
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 ........................................................................
6
1.6 Definisi Operasional ................................................................
6
1.7 Kerangka Konseptual ..............................................................
7
BAB II KAJIAN PUSTAKA ..................................................................... 2.1 Graf .........................................................................................
9
2.1.1 Definisi Graf ..................................................................
9
2.1.2 Graf Sederhana ..............................................................
11
2.1.3 Graf Tak Sederhana........................................................
11
2.1.4 Keterhubungan Graf .......................................................
14
2.1.4.1 Jalan (walk) dan Jalan Tertutup (Closed Walk) .
14
2.1.4.2 Jejak (Trail) dan Sirkuit .....................................
15
x
2.1.4.3 Lintasan (Path) dan Cycle .................................
16
2.2 Graf Hamiltonian .....................................................................
17
2.3 Algoritma Bondy dan Chvatal .................................................
18
BAB III PEMBAHASAN .........................................................................
22
3.1 Pemodelan Graf Trayek H, E.1 dan K .....................................
23
3.2 Cycle Hamiltonian Pada Peralihan Rute Angkot Trayek H Terhadap Trayek E.1 dan K ......................................................
25
3.3 Perbaikan Rute Trayek E.1 dan Trayek K ................................
53
BAB IV PENUTUP ...................................................................................
56
4.1 Kesimpulan..............................................................................
56
4.2 Saran ........................................................................................
57
DAFTAR PUSTAKA ................................................................................
58
xi
DAFTAR TABEL
Tabel 1.1 Rute Trayek E.1, H, dan K ....................................................
4
Tabel 3.1 Daftar Terminal/halte Trayek H, E.1, dan K .........................
24
Tabel 3.2 Daftar Terminal/halte Trayek M, Trayek N ..........................
26
Tabel 3.3 Rute Trayek E.1, H, dan K .....................................................
53
Tabel 3.4 Perbaikan Rute Trayek E.1 dan K .........................................
54
xii
DAFTAR GAMBAR
Gambar 1.1
Contoh Graf ......................................................................
1
Gambar 1.2
Contoh Cycle Hamilton ....................................................
3
Gambar 2.1
Jenis-jenis Graf
................................................
10
Gambar 2.2
Graf G Tak Berhingga ......................................................
12
Gambar 2.3
Graf G Graf Berarah (directed graph/digraph) .................
13
Gambar 2.4
Graf G ...............................................................................
14
Gambar 2.5
Graf G ...............................................................................
15
Gambar 2.6
Graf G ...............................................................................
16
Gambar 2.7
Graf Dodecahedron ...........................................................
17
Gambar 2.8
Cycle Hamiltonian dari Graf Dodecahedron ....................
18
Gambar 2.9
Graf G ...............................................................................
19
Gambar 2.10 Cycle Hamiltonian Pada Graf G .......................................
21
Gambar 3.1
Rute Trayek H, E.1, dan K ...............................................
22
Gambar 3.2
Graf G Terminal/halte yang Dilalui Trayek H, E.1, dan K
25
Gambar 3.3
Graf
Terminal/halte yang Dilalui Trayek M ...............
27
Gambar 3.4
Graf
Terminal/halte yang Dilalui Trayek N ................
39
,
,
Gambar 3.5
Pada Graf
..................................................................
30
Gambar 3.6
Pada Graf
.................................................................
31
Gambar 3.7
Pada Graf
.................................................................
32
Gambar 3.8
Pada Graf
................................................................
33
Gambar 3.9
Pada Graf
..............................................................
34
Gambar 3.10
Pada Graf
..............................................................
35
Gambar 3.11
Pada Graf
..............................................................
37
Gambar 3.12
Pada Graf
..............................................................
38
Gambar 3.13
Pada Graf
.................................................................
40
Gambar 3.14
Pada Graf
................................................................
42
Gambar 3.15
Pada Graf
.................................................................
43
Gambar 3.16
Pada Graf
................................................................
44 xiii
Gambar 3.17
Pada Graf
................................................................
45
Gambar 3.18
Pada Graf
................................................................
46
Gambar 3.19
Pada Graf
..............................................................
48
Gambar 3.20
Pada Graf
..............................................................
49
Gambar 3.21
Pada Graf
..............................................................
50
Gambar 3.22 Graf
Rute Trayek M .....................................................
52
Gambar 3.23 Graf
Rute Trayek N ......................................................
52
Gambar 3.24 Rute Peralihan Trayek H Terhadap Trayek E.1 dan K .....
55
xiv
DAFTAR LAMPIRAN
Lampiran 1
Lampiran 2
Peta Rute Angkot Trayek E.1, H, dan K di Kota Pasuruan ............................................................................................
59
Surat Perizinan Observasi .................................................
60
xv
DAFTAR PUSTAKA Cahyono, Hendarto.2000. Pengantar Teori Graf. UMM: Malang. Maps, Google. 2014. Kota Pasuruan. (http://www.google.com/maps, diakses 20 Oktober 2014) Griffin, Christopher. 2011. Graph Theory: Penn State Math 485 Lecture Notes (Version 1.4.1). Jayanti, Dian Dwi, Skripsi: Aplikasi Digraf Berbobot untuk Menentukan Jalur Angkot Terpendek di Malang Jurusan Arjosari - Gadang, Malang: Program Studi Pendidikan Matematika Fakultas Keguruan dan Ilmu Pendidikan UMM, 2014. John M. Harris, Jeffry L. Hirst, dan Michael J. Mossinghoff, 2008. Combinatorics and Graph Theory (ed. 2). Springer Science+Business Media: New York. Munir, Rinaldi. 2003. Matematika Diskrit (ed. 2). Informatika Bandung: Bandung Muslich, Asikin. 2001. Sistem Manajemen Transportasi Kota. Philosophy press: Yogyakarta. Pasuruan, BPS. 2013. Badan Pusat Statistik Kota Pasuruan. (http://www.pasuruankota.bps.go.id, diakses 26 September 2014). Rifa’i, Hasbilah, Skripsi: Aplikasi Graf Terhadap Sistem Transportasi Darat Bus Patas Trans Jogja di Daerah Istimewa Yogyakarta, Yogyakarta: Program Studi Matematika Fakultas Sains dan Teknologi UIN DIY, 2009. Ross, Sheldon M. 2004.Topics in Finite and Discrete Mathematics. Cambridge: Cambridge University Press. Wibisono, Samuel. 2008. Matematika Diskrit (ed. 2). Graha Ilmu: Yogyakarta.
58
