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


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.


Latar Belakang

Aplikatif

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


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.


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.


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.


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


Algoritma

Perancangan


Algoritma

Implementasi


Algoritma

Implementasi Aplikasi


Algoritma

Implementasi Aplikasi Evaluasi


PENARIKAN KESIMPULAN


Perancangan Algoritma

Ide Dasar

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


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


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.


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.


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


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


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



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



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



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


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


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


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


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


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).


ALGORITMA I


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.


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.

perancangan algoritma keterhubungan suatu graf dan...

Documents

Teori Graf

PENGANTAR DAN JENIS-JENIS GRAF

Keterhubungan Antara Citra Toko

KETERHUBUNGAN DALAM GRAF KOMUTATIF DARI …etheses.uin-malang.ac.id/6713/1/06510016.pdf · matriks bilangan real skripsi oleh: yustycia pratamasari nim. 06510016 jurusan matematika

PEMBERIAN NOMOR VERTEX PADA TOPOLOGI JARINGAN GRAF … filejaringan graf yang berbentuk graf wheel , graf helm dan graf lollipop . Didapatkan hasil penelitian berupa penomoran vertex

ALGORITMA UNTUK MEMECAHKAN MASALAH …rinaldi.munir/...K1 K2 K3 K4 K5 K6 Dalam pengaplikasian graf pada program komputer, masalah keterhubungan (connectedness) merupakan salah satu

PELABELAN JUMLAH EKSKLUSIF PADA GRAF MATAHARI, GRAF …lib.ui.ac.id/file?file=digital/20299156-S1957-Pelabelan jumlah.pdfpelabelan jumlah eksklusif pada graf matahari, graf korona,

Pembahasan UTS IF2211rinaldi.munir/Stmik/...Soal 2: DFS dan BFS (3) (b) Terdapat sebuah graf pada Gambar 2, yang menunjukkan keterhubungan antar simpul dan jarak antar simpul. (ii)

graf theory

Angio Graf i

Makalah Teori Graf(Graf Berarah)

AUTOMORFISME GRAF BINTANG DAN GRAF LINTASAN …etheses.uin-malang.ac.id/6709/1/07610029.pdf · 2.8.1 Graf Lintasan (Path Graph) ... 2.9. Isomorfisme Graf..... 25 2.10. Automorfisme

BILANGAN KETERHUBUNGAN PELANGI KUAT …pewarnaan pelangi-k pada G disebut bilangan keterhubungan pelangi. Bilangan keterhubungan pelangi dari G dinotasikan dengan (Chatrand dan Zhang,

TEORI GRAF - ilhamsaifudin12.files.wordpress.com · 4 Contoh Aplikasi Graf Terminologi Graf 5 6 Graf-graf Khusus Representasi Graf 7 8 Graf Isomorfik . OUTLINE 1. PENDAHULUAN 1. PENDAHULUAN

BILANGAN KETERHUBUNGAN PELANGI KUAT PADA GRAF … · bertetangga jika dan hanya jika terhubung oleh sebuah sisi. Sebuah jalan dari ... sehingga setiap jalur pengiriman informasi membutuhkan

ANALISIS KETERHUBUNGAN ANTARA INDEKS PEMBANGUNAN MANUSIA, BELANJA DAERAH, TINGKAT ...sandrasembel.weebly.com/uploads/1/8/7/6/18764622/... · 2019-11-21 · analisis keterhubungan

Dokumen Kurikulum 2013-2018 Program Studi : Magister ... · memahami prinsip inklusi-eksklusi dan aplikasinya. Subbab 8.4-8.6 12. Graf Graf dan model graf, isomorfisma, keterhubungan

KETERHUBUNGAN DENGAN KECENDERUNGAN ...eprints.radenfatah.ac.id/2953/1/DWI PUJI SEPTIANA...Siswa Kelas IX SMP 55 Palembang Penelitian ini bertujuan untuk menguji hubungan antara keterhubungan

PELABELAN SUPER SISI AJAIB PADA GRAF MULTI STAR · BAB II: KAJIAN PUSTAKA A. Graf ... Penelitian mengenai pelabelan super sisi ajaib pada beberapa jenis graf ... pada kasus-kasus

SKRIPSI KETERHUBUNGAN BESARAN VOLUME FLUIDA …

Pengantar Graf

Multi Graf Ida

Makalah Graf

pewarnaan graf

febianto.staff.gunadarma.ac.idfebianto.staff.gunadarma.ac.id/.../47041/Teori+Graf.doc · Web viewTeori Dasar Graf. Kelahiran Teori Graf . Teori Graf mulai dikenal pada saat seorang

PELABELAN GRAF SIKLUS SEDERHANA UNTUK … · sebuah graf siklus untuk memperoleh vertex-magic graph (graf simpul ajaib). Vertex-magic graph adalah graf siklus dengan v simpul dan

pemberian nomor vertex pada topologi jaringan graf wheel, graf

Teori Graf

Graf - dinus.ac.id · contoh graf sederhana 2. Graf tak-sederhana (unsimple-graph ). Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph ). G

Graf · contoh graf sederhana 2. Graf tak-sederhana (unsimple-graph ). Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph ). G 2 dan G 3 pada

Representasi Graf, Graf Isomorfik, Graf Plannar dan Graf Dual

SIFAT-SIFAT GRAF KOSET DAN GRAF …repository.uin-malang.ac.id/1774/7/1774.pdfLAPORAN PENELITIAN PENGUATAN PROGRAM STUDI SPEKTRUM GRAF KONJUGASI DAN GRAF KOMPLEMEN GRAF KONJUGASI DARI

PLAGIAT MERUPAKAN TINDAKAN TIDAK … Graf .....7 2.1.1 Definisi Graf .....7 2.1.2 Definisi Walk, Trail, Path dan 2.1.3 Graf Eulerian dan Graf Hamiltonian.....9 2.1.4 Macam-macam Graf

Graf Pohon

Keterhubungan&Planaritas Suatu Graf