i

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

ii

iii

iv

v

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 )

vi

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.

vii

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

x

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

xi

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

xii

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

xiii

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

xiv

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

xv

DAFTAR LAMPIRAN

Lampiran 1 Peta Rute Angkot Trayek E.1, H, dan K di Kota Pasuruan

............................................................................................ 59

Lampiran 2 Surat Perizinan Observasi ................................................. 60

58

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.