perancangan algoritma keterhubungan suatu graf dan...

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Perancangan Algoritma KeterhubunganSuatu Graf dan Penerapannya dalam

Pengaturan Arus Lalu Lintas Jalan Raya

Darill Muflih Arief1207100069

Dosen Pembimbing :Drs. Sumarno, DEA.1 Drs. Soetrisno, MI.Komp.2

Jurusan MatematikaFakultas Matematika dan Ilmu Pengetahuan Alam

Institut Teknologi Sepuluh Nopember

Sidang Tugas Akhir - Ruang Sidang II,20 Januari 2012

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Latar Belakang

Graf

1 Graf adalah salah satu bidang ilmu matematika.2 Graf sering digunakan untuk merepresentasikan

objek-objek diskrit dan hubungan antara objek-objektersebut.

3 Graf merupakan topik yang banyak mendapat perhatiankarena representasinya sangat berguna untuk aplikasiyang luas.

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Latar Belakang

Aplikatif

Salah satu aplikasi pada graf -> arus lalu lintas.arus lalu lintas -> terhubung kuat.Algoritma keterhubungan?

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Perumusan Masalah

1 Bagaimana merancang sebuah algoritma untukmengetahui status keterhubungan suatu graf berarah.

2 Bagaimana merepresentasikan suatu arus lalu lintas jalanraya ke dalam sebuah graf.

3 Bagaimana mengaplikasikan algoritma keterhubungan grafdalam pengaturan arus lalu lintas jalan raya.

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Batasan Masalah

Batasan1 Algoritma yang dirancang adalah algoritma untuk

mengecek status keterhubungan suatu graf berarah.2 Arus lalu lintas jalan raya yang akan diterapkan adalah

arus lalu lintas kampus ITS.

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Tujuan dan Manfaat

Tujuan1 Untuk mengetahui status keterhubungan suatu graf.2 Untuk menyelesaikan permasalahan perubahan arus lalu

lintas jalan raya.

ManfaatManfaat dari tugas akhir ini adalah memberikan informasitentang status keterhubungan suatu jalan raya, memberikanpertimbangan dalam pemilihan arus dan atau perubahan aruslalu lintas agar setiap ruas jalan raya tetap terhubung kuat.

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Dasar TeoriGrafJenis-Jenis GrafTerminologi DasarRepresentasi Graf dalam MatriksRepresentasi Graf Berarah dalam MatriksAlgoritmaJavaScript

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Algoritma

Perancangan

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Algoritma

Implementasi

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Algoritma

Implementasi Aplikasi

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Algoritma

Implementasi Aplikasi Evaluasi

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

PENARIKAN KESIMPULAN

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Perancangan Algoritma

Ide Dasar

Penelusuran lintasan yang mungkin dari setiap simpul.Peninjauan busur-busur pada setiap simpul.

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Algoritma I

InisialisasiInput merupakan graf terhubung berarah.n sebagai banyaknya simpul.m sebagai banyaknya busur.

RepresentasiDibuat matriks n x n.Matriks n x n diisi dengan aturan

Mij =

{1, jika ada busur dari vi ke vj0, jika tidak ada busur dari vi ke vj

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Algoritma I

Operasi Baris1 Baris pertama dioperasikan dengan baris yang menjadi

kolom bernilai 1 pada baris tersebut. Operasi baris yangdigunakan adalah operasi penjumlahan biner yaitu1 + 1 = 1,1 + 0 = 1,0 + 1 = 1, dan 0 + 0 = 0

2 Jika pada baris yang dioperasikan terdapat lagi kolomyang bernilai 1, maka baris tersebut dioperasikan lagidengan baris yang menjadi kolom bernilai 1 pada baristersebut (rekursif).

3 Operasi dilakukan terhadap setiap baris yang memilikielemen bernilai 1.

Operasi baris berhenti jika seluruh baris yang memiliki elemenbernilai 1 telah selesai dioperasikan.

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Penentuan Status

Didapat matriks akhir hasil operasi baris yangmerepresentasikan keterhubungan serta lintasan yangmungkin dari tiap-tiap simpul.Jika elemen-elemen pada matriks akhir bernilai 1 semua,maka matriks tersebut merepresentasikan sebuah grafterhubung kuat.

M =

1 1 1 1 11 1 1 1 11 1 1 1 1

1 1 1. . .

...1 1 1 · · · 1

Jika terdapat elemen bernilai 0 pada matriks akhir, makamatriks tersebut merepresentasikan sebuah graf yangtidak terhubung kuat.

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Ilustrasi Algoritma I

Representasi GrafD :

v1 v2 v3 v4 v5

v1 1 1 0 0 1v2 0 0 1 0 0v3 0 0 0 1 0v4 0 0 0 0 1v5 0 0 0 1 0

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Ilustrasi Algoritma I

Representasi GrafD :

v1 v2 v3 v4 v5

v1 1 1 0 0 1v2 0 0 1 0 0v3 0 0 0 1 0v4 0 0 0 0 1v5 0 0 0 1 0

Baris yang ditinjau

Elemen bernilai 1

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Operasi baris 1 dengan baris 2

v1 v2 v3 v4 v5

v1 1 1 0 0 1v2 0 0 1 0 0v3 0 0 0 1 0v4 0 0 0 0 1v5 0 0 0 1 0

=⇒

v1 v2 v3 v4 v5

v1 1 1 1 0 1v2 0 0 1 0 0v3 0 0 0 1 0v4 0 0 0 0 1v5 0 0 0 1 0

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Operasi baris 1 dengan baris 3

v1 v2 v3 v4 v5

v1 1 1 1 0 1v2 0 0 1 0 0v3 0 0 0 1 0v4 0 0 0 0 1v5 0 0 0 1 0

=⇒

v1 v2 v3 v4 v5

v1 1 1 1 1 1v2 0 0 1 0 0v3 0 0 0 1 0v4 0 0 0 0 1v5 0 0 0 1 0

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Operasi baris 1 dengan baris 4

v1 v2 v3 v4 v5

v1 1 1 1 1 1v2 0 0 1 0 0v3 0 0 0 1 0v4 0 0 0 0 1v5 0 0 0 1 0

=⇒

v1 v2 v3 v4 v5

v1 1 1 1 1 1v2 0 0 1 0 0v3 0 0 0 1 0v4 0 0 0 0 1v5 0 0 0 1 0

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Operasi baris 1 dengan baris 5

v1 v2 v3 v4 v5

v1 1 1 1 0 1v2 0 0 1 0 0v3 0 0 0 1 0v4 0 0 0 0 1v5 0 0 0 1 0

=⇒

v1 v2 v3 v4 v5

v1 1 1 1 1 1v2 0 0 1 0 0v3 0 0 0 1 0v4 0 0 0 0 1v5 0 0 0 1 0

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Operasi baris 2

v1 v2 v3 v4 v5

v1 1 1 1 1 1v2 0 0 1 0 0v3 0 0 0 1 0v4 0 0 0 0 1v5 0 0 0 1 0

=⇒

v1 v2 v3 v4 v5

v1 1 1 1 1 1v2 0 1 1 1 1v3 0 0 0 1 0v4 0 0 0 0 1v5 0 0 0 1 0

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Operasi baris 3

v1 v2 v3 v4 v5

v1 1 1 1 1 1v2 0 1 1 1 1v3 0 0 0 1 0v4 0 0 0 0 1v5 0 0 0 1 0

=⇒

v1 v2 v3 v4 v5

v1 1 1 1 1 1v2 0 1 1 1 1v3 0 0 0 1 1v4 0 0 0 0 1v5 0 0 0 1 0

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Operasi baris 4

v1 v2 v3 v4 v5

v1 1 1 1 1 1v2 0 0 1 1 1v3 0 0 0 1 1v4 0 0 0 0 1v5 0 0 0 1 0

=⇒

v1 v2 v3 v4 v5

v1 1 1 1 1 1v2 0 1 1 1 1v3 0 0 0 1 1v4 0 0 0 1 1v5 0 0 0 1 0

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Operasi baris 5

v1 v2 v3 v4 v5

v1 1 1 1 1 1v2 0 1 1 1 1v3 0 0 0 1 1v4 0 0 0 1 1v5 0 0 0 1 0

=⇒

v1 v2 v3 v4 v5

v1 1 1 1 1 1v2 0 1 1 1 1v3 0 0 0 1 1v4 0 0 0 1 1v5 0 0 0 1 1

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Algoritma II

Pelabelan Simpul1 Label ± diberikan pada sebarang simpul va pada graf.2 Label + diberikan pada simpul yang dituju oleh busur

keluar simpul va.3 Misalkan vb adalah simpul yang dituju oleh busur keluar

simpul va, label + diberikan juga pada simpul yang ditujuoleh busur keluar simpul vb.

4 Pelabelan (label +) dilanjutkan terhadap semua simpulyang mungkin diberi label + sesuai dengan aturan padapoin (3).

5 Label - diberikan pada simpul awal busur masuk simpul va.6 Misalkan vc adalah simpul awal busur masuk simpul vc ,

label - diberikan juga pada simpul awal busur masuksimpul vc .

7 Pelabelan (label -) dilanjutkan terhadap semua simpul yangmungkin diberi label - sesuai dengan aturan pada poin (5).

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

ALGORITMA I

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Kesimpulan dan Saran

Kesimpulan1 Baik pada algoritma I maupun algoritma II, jumlah eksekusi

algoritma berbanding lurus dengan banyaknya busur padagraf. Namun, untuk menentukan jumlah maksimumeksekusi mengacu pada banyaknya simpul pada graf.

2 Batas atas kompleksitas algoritma I adalah n2(n − 1)dengan waktu eksekusi terlama sebesar n2(n − 1)×maksimum waktu yang diperlukan dalam 1 kali iterasi.

3 Batas atas kompleksitas algoritma II adalah 2n(n − 1)dengan waktu eksekusi terlama sebesar 2n(n − 1)×maksimum waktu yang diperlukan dalam 1 kali iterasi.

Pendahuluan Dasar Teori Metodologi Penelitian Perancangan Algoritma dan Implementasi Algoritma I Algoritma II Implementasi Algoritma Kesimpulan dan Saran

Kesimpulan dan Saran

SaranUntuk pengembangan penelitian lebih lanjut, disarankan:

1 Implementasi algoritma dapat dicoba dalam bentukstruktur data yang lain selain matriks.

2 Untuk pembanding proses dari algoritma I, dapatdilakukan implementasi dan aplikasi terhadap algoritma II.