makalah teori graph

13
MAKALAH TEORI GRAPH Penerapan Algoritma Fleury Pada Jalur Penerbangan Pesawat Garuda Indonesia Disusun Oleh : Muhaimin Muis Mustika Nurul Fitriani Jumriana Lestari Nur Sukmawati JURUSAN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NEGERI ALAUDDIN MAKASSAR 2015

Upload: naomiyukimotho

Post on 26-Jan-2016

957 views

Category:

Documents


150 download

DESCRIPTION

Matematika

TRANSCRIPT

Page 1: Makalah Teori Graph

MAKALAH

TEORI GRAPHPenerapan Algoritma Fleury Pada Jalur Penerbangan

Pesawat Garuda Indonesia

Disusun Oleh :

Muhaimin Muis

Mustika

Nurul Fitriani

Jumriana Lestari Nur

Sukmawati

JURUSAN MATEMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS ISLAM NEGERI ALAUDDINMAKASSAR

2015

Page 2: Makalah Teori Graph

2

KATA PENGANTAR

Mengawali pengantar dari tugas ini adalah sabda Rasulullah SAW yaitu

“ilmu yang tidak di amalkan bagaikan pohon yang tak berbuah”, dan sabda lain

Rasulullah SAW adalah “Satu kebaikan yang kita lakukan maka akan berbuah

sepuluh kebaikan yang kita peroleh”. Dari dua sabda Rasulullah tersebut memberi

motivasi kepada kami bahwa ilmu itu sangat berguna dan bermanfaat apabila kita

pergunakan di jalan kebaikan dan mencari ilmu sangatlah di anjurkan kepada kita

kaum muslimin.

Dalam pembuatan makalah ini, kami berharap kita dapat memahami

segala isi dan makna yang tercantum di dalam makalah ini dam mudah-mudahan

dengan adanya makalah ini kita dapat lebih mudah memperoleh ilmu pengatahuan

khususnya tentang Aplikasi Algoritma Fleury dalam kehidupan sehari-hari.

Demikianlah makalah yang penuh kekurangan ini kami buat semata-mata

ingin mengembangkan potensi kami sebagai mahasiswa untuk tetap aktif dalam

mencapai segala cita-cita kami. Kami sebagai penyusun makalah ini memohon

maaf apabila di dalam makalah ini masih banyak kekurangan. Penyusun berharap

dalam penyusunan makalah barikutnya bisa lebih baik lagi.

Samata-Gowa, Juni 2015

Penyusun

Page 3: Makalah Teori Graph

3

Daftar Isi

Kata pengantar.........................................................................................................ii

Daftar isi.................................................................................................................iii

Bab I Pendahuluan

1.1. Latar Belakang..................................................................................................1

1.2. Rumusan Masalah.............................................................................................2

1.3. Tujuan Pembahasan..........................................................................................2

Bab II Tinjauan Pustaka

2.1. Pengertian graph...............................................................................................3

2.2. Jenis-jenis graph...............................................................................................3

2.3. Algoritma Fleury..............................................................................................4

Bab III Pembahasan

3.1 Pengertian graph Euler dan graph semi-Euler.................................................5

3.2 Jalur penerbangan pesawat Garuda Indonesia dengan menggunakan

algoritma Fleury................................................................................................5

Bab IV Penutup

4.1. Simpulan..........................................................................................................9

4.2. Saran.................................................................................................................9

Daftar pustaka

Page 4: Makalah Teori Graph

4

BAB I

PENDAHULUAN

A. Latar Belakang

Perjalanan melalui jalur udara merupakan salah satu alternatif bagi

seseorang untuk melakukan perjalanan jarak jauh. Salah satu hal dipilihnya

perjalanan jalur udara dikarenakan waktu tempuh yang relatif cepat jika

dibandingkan menggunakan transportasi laut ataupun darat.

Pesawat terbang sebagai armada komersil transportasi udara telah

menjadi pilihan bagi setiap orang yang menginginkan waktu perjalanan yang

singkat. Penggunaan pesawat terbang sebagai alat transportasi semakin

diminati. Menurut data dari Direktorat Hubungan Udara dari tahun 2005

sampai tahun 2009 rata-rata terjadi peningkatan jumlah penumpang yang

melakukan perjalanan dengan transportasi udara.

Bertambahnya jumlah penumpang dan kebutuhan penumpang dari

tahun ke tahun telah mengakibatkan munculnya banyak operator maskapai

penerbangan. Operator maskapai penerbangan muncul dengan berbagai cara

untuk menarik jumlah penumpang baik meningkatkan pelayanan,

memurahkan harga tiket sampai mengoperasikan pesawat sesuai jadwal

penerbangan (on time).

Hal inilah yang melatarbelakangi pembuatan makalah ini yaitu

perlunya diketahui jalur-jalur yang mana saja yang akan dilalui oleh pesawat

sehingga pesawat dapat dioperasikan sesuai dengan jadwal penerbangan.

Berdasarkan latar belakang di atas, maka makalah ini mengambil

judul “Penerapan Algoritma Fleury pada Jalur Penerbangan Pesawat Garuda

Indonesia”.

Page 5: Makalah Teori Graph

5

B. Rumusan Masalah

Adapun rumusan masalah dalam makalah ini adalah sebagai berikut:

1. Apa pengertian graph Euler dan graph semi-Euler?

2. Bagaimana jalur penerbangan pesawat Garuda Indonesia dengan

menggunakan algoritma Fleury?

C. Tujuan Pembahasan

Adapun tujuan pembahasan dalam makalah ini adalah sebagai berikut:

1. Untuk mengetahui pengertian graph Euler dan graph semi-Euler!

2. Untuk mengetahui jalur penerbangan pesawat Garuda Indonesia dengan

menggunakan algoritma Fleury!

D. Manfaat

Manfaat dari penulisan makalah ini adalah mengetahui jalur

penerbangan pesawat Garuda Indonesia dengan menggunakan algoritma

Fleury.

Page 6: Makalah Teori Graph

6

BAB II

TINJAUAN PUSTAKA

A. Pengertian Graph

Suatu graph adalah himpunan benda – benda yang disebut verteks (atau

node) yang terhubung oleh sisi (atau edge). Biasanya graph digambarkan

sebagai kumpulan verteks (melambangkan titik) yang dihubungkan oleh

garis-garis (melambangkan sisi atau edge). Sebuah graph = ( , ) adalah

suatu sistem yang terdiri atas suatu himpunan objek = { , , . . . } yang

disebut himpunan titik, dan sebuah himpunan = { , , . . . } yang

merupakan himpunan sisi sedemikian hingga tiap sisi dikaitkan dengan

suatu pasangan tak-terurut ( , ). Titik pada graph dapat dilabeli dengan

huruf, misalkan , , …, atau dengan menggunakan bilangan asli 1, 2, 3, …,atau gabungan keduanya. Sedangkan sisi yang menghubungkan titik vi

dengan titik vj dinyatakan dengan pasangan , ., atau dengan lambang, , … Dengan kata lain, jika e adalah sisi yang menghubungkan titik

dengan titik , maka e dapat dituliskan sebagai = , dimana i,j

adalah indeks angka bilangan asli 1, 2, 3, …B. Jenis-jenis Graph

Adapun beberap jenis graph yaitu sebagai berikut:

1. Graph kosong

Graph kosong yaitu graph yang himpunan sisinya merupakan

himpunan kosong atau tidak mempunyai sisi.

2. Graph berbobot

Graph yang setiap sisinya diberikan suatu bobot dinamakan dengan

graph berbobot.

3. Graph sederhana (simple grafh).

Graph yang tidak mengandung loop maupun sisi ganda dinamakan

graph sederhana.

Page 7: Makalah Teori Graph

7

4. Graph sederhana.

Graph yang tidak mengandung atau tidak memiliki sisi ganda atau

loop (gelung).

5. Graph tak-berarah (undirected graph).

Graph yang sisinya tidak mempunyai orientasi arah disebut graph

tak berarah.

6. Graph berarah (directed graph).

Graph berarah (directed graph) adalah graph yang sisi-sisinya

diberikan orientasi arah.

C. Algoritma Fleury

Algoritma Fleury digunakan untuk mengkontruksi sebuah sirkit Euler

pada graph Euler. Berikut disajikan langkah-langkah sistematis dari algoritma

tersebut.

INPUT : Graph Euler G

STEP 1: Pilih sebuah titik di graph G. Tulis = .

STEP 2: Misalkan jejak = ( , , , … , , ) telah terpilih.

Selanjutnya, pilih semua sisi dari E(G)-{ , , … } sedemikian

hingga:

i. Sisi terkait dititik , dan

ii. Sisi bukan sisi-pemutus pada graph , dengan = −{ , , … }, kecuali tidak ada pilihan lain.

Tulis jejak = ∪ { }STEP 3: STOP bila STEP 2 tidak bisa dilanjutkan; dan beri pesan: “

adalah jejak Euler tertutup (sirkit Euler) di graph G”.

Page 8: Makalah Teori Graph

8

BAB III

PEMBAHASAN

A. Pengertian Graph Euler dan Graph Semi Euler

Sebuah sirkit di graph G yang memuat semua sisi G disebut sirkit

euler. Jika graph G memuat sirkit Euler, maka graph G disebut graph Euler.

Sebuah jejak-buka yang memuat semua sisi graph disebut jejak Euler. Graph

G disebut graph semi-Euler jika G memuat jejak Euler. Sebagai contoh,

perhatikan gembar 1, graph G1 adalah graph Euler karena memuat sirkit Euler

S = (v1, v2, v4, v3, v5, v4, v1, v5, v6, v1), graph G2 adalah graph semi-euler

karena memuat jejak Euler buka J = (v1, v2, v3, v4, v1, v3), sedangkan graph

G3 bukan graph Euler maupun semi-Euler.

Gambar 1 : G1 graph Euler ; G2 graph semi-Euler ; G3 bukan Euler

dan bukan semi-Euler

B. Jalur Penerbangan Pesawat Garuda Indonesia dengan Menggunakan

Algoritma Fleury

Dalam makalah ini akan dicari jalur penerbangan pesawat Garuda

Indonesia dari kota satu ke kota yang lain dengan menggunakan algoritma

Fleury. Adapun contohnya yaitu sebagai berikut:

8

BAB III

PEMBAHASAN

A. Pengertian Graph Euler dan Graph Semi Euler

Sebuah sirkit di graph G yang memuat semua sisi G disebut sirkit

euler. Jika graph G memuat sirkit Euler, maka graph G disebut graph Euler.

Sebuah jejak-buka yang memuat semua sisi graph disebut jejak Euler. Graph

G disebut graph semi-Euler jika G memuat jejak Euler. Sebagai contoh,

perhatikan gembar 1, graph G1 adalah graph Euler karena memuat sirkit Euler

S = (v1, v2, v4, v3, v5, v4, v1, v5, v6, v1), graph G2 adalah graph semi-euler

karena memuat jejak Euler buka J = (v1, v2, v3, v4, v1, v3), sedangkan graph

G3 bukan graph Euler maupun semi-Euler.

Gambar 1 : G1 graph Euler ; G2 graph semi-Euler ; G3 bukan Euler

dan bukan semi-Euler

B. Jalur Penerbangan Pesawat Garuda Indonesia dengan Menggunakan

Algoritma Fleury

Dalam makalah ini akan dicari jalur penerbangan pesawat Garuda

Indonesia dari kota satu ke kota yang lain dengan menggunakan algoritma

Fleury. Adapun contohnya yaitu sebagai berikut:

8

BAB III

PEMBAHASAN

A. Pengertian Graph Euler dan Graph Semi Euler

Sebuah sirkit di graph G yang memuat semua sisi G disebut sirkit

euler. Jika graph G memuat sirkit Euler, maka graph G disebut graph Euler.

Sebuah jejak-buka yang memuat semua sisi graph disebut jejak Euler. Graph

G disebut graph semi-Euler jika G memuat jejak Euler. Sebagai contoh,

perhatikan gembar 1, graph G1 adalah graph Euler karena memuat sirkit Euler

S = (v1, v2, v4, v3, v5, v4, v1, v5, v6, v1), graph G2 adalah graph semi-euler

karena memuat jejak Euler buka J = (v1, v2, v3, v4, v1, v3), sedangkan graph

G3 bukan graph Euler maupun semi-Euler.

Gambar 1 : G1 graph Euler ; G2 graph semi-Euler ; G3 bukan Euler

dan bukan semi-Euler

B. Jalur Penerbangan Pesawat Garuda Indonesia dengan Menggunakan

Algoritma Fleury

Dalam makalah ini akan dicari jalur penerbangan pesawat Garuda

Indonesia dari kota satu ke kota yang lain dengan menggunakan algoritma

Fleury. Adapun contohnya yaitu sebagai berikut:

Page 9: Makalah Teori Graph

9

STEP 1: Pilih Bandara( ). Tulis Jalur =STEP 2: Jalur telah terpilih.

Pilih Bandara = . Tulis jalur= ( , , ) Pilih Bandara = . Tulis jalur= ( , , , , ) Pilih Bandara = . Tulis jalur =( , , , , , , ) Pilih Bandara = . Tulis jalur=( , , , , , , , , ) Pilih Bandara = . Tulis jalur=( , , , , , , , , , ,) Pilih Bandara = . Tulis jalur=( , , , , , , , , , ,, , )

Page 10: Makalah Teori Graph

10

Pilih Bandara = . Tulis jalur=( , , , , , , , , , ,, , , , ) Pilih Bandara = . Tulis jalur=( , , , , , , , , , ,, , , , , , ) Pilih Bandara = . Tulis jalur=( , , , , , , , , , ,, , , , , , , , ) Pilih Bandara = . Tulis jalur =( , , , , , , , , , ,, , , , , , , , , ,) Pilih Bandara = . Tulis jalur =( , , , , , , , , , ,, , , , , , , , , ,, , ) Pilih Bandara = . Tulis jalur=( , , , , , , , , , ,, , , , , , , , , ,, , , , ) Pilih Bandara = . Tulis jalur=( , , , , , , , , , ,, , , , , , , , , ,, , , , , , ) Pilih Bandara = . Tulis jalur=( , , , , , , , , , ,, , , , , , , , , ,, , , , , , , , ) Pilih Bandara = . Tulis jalur=( , , , , , , , , , ,, , , , , , , , , ,

Page 11: Makalah Teori Graph

11

, , , , , , , ,, , )STEP 3: Karena STEP 3 tidak dapat dilanjutkan lagi, maka STOP, dan

Bandara = . Tulis jalur=( , , , , , , , , , ,, , , , , , , , , ,, , , , , , , ,, , ) adalah jalur (jejak) Euler dengan gambarsebagai berikut

Page 12: Makalah Teori Graph

12

BAB IV

PENUTUP

A. Kesimpulan

Adapun kesimpulan dari makalah ini adalah sebagai berikut:

1. Graph Euler adalah sebuah grap terhubung yang memuat sisrkit Euler.

Sedangkan graph semi Euler adalah sebuah graph yang memuat jejak

Euler dimana jejak Euler adalah sebuah jejak buka yang memuat semua

sisi graph.

2. Setelah dilakukan penerapan Algoritma Fleury pada jalur penerbangan

pesawat Garuda Indonesia maka diperoleh jalur (jejak) Euler

seperti berikut :

= ( , , , , , , , , , ,, , , , , , , , ,, , , , , , , , ,, , )B. Saran

Kritik dan saran yang membangun, kami harapkan untuk perbaikan

dan kemajuan makalah berikutnya.

Page 13: Makalah Teori Graph

13

DAFTAR PUSTAKA

Anonim.http://repository.usu.ac.id/bitstream/123456789/20418/5/Chapter20I.pdf(Diakses pada hari Minggu tanggal 7 Juni 2015)

Anonim. http://digilib.its.ac.id/public/ITS-Undergraduate-8026-1203109025-Bab1.pdf (Diakses pada hari Minggu tanggal 7 Juni 2015)

Anonim. https://meyouusblogshare.files.wordpress.com (Diakses pada hariMinggu tanggal 7 Juni 2015)