Graf Berarah

Sebuah graf terarah atau digraf G terdiri dari suatu himpunan V dari verteks-verteks (atau simpul-simpul) dan suatu himpunan E dari rusuk-rusuk (atau busur-busur) sedemikian rupa sehingga setiap rusuk e ∈ E menghubungkan pasangan verteks terurut.

[gambar ghraf berarah] 

Graf berarah dianggap yang paling tepat untuk merepresentasikan masalah ini karena jalan-jalan di bumi memiliki arah dan tidak semua jalan “dua arah” ada juga jalan “satu arah”. Oleh karena itu dengan graf berarah masalah tersebut dapat terselesaikan. Sehingga jalan tercepat menuju ke tempat tujuan dapat ditemukan tanpa perlu khawatir akan jalan “satu arah”.

Tetapi masih ada masalah selanjutnya yaitu kepadatan jalan-jalan di perkotaan yang sering menimbulkan kemacetan terutama di saat liburan seperti libur Natal dan tahun baru 2008 di Kota Bandung sangat padat akan kendaraan dari luar kota dan juga dari dalam kota. Selain itu banyaknya jalan-jalan yang rusak akibat cuaca yang tidak menentu sehingga banyak perbaikan jalan yang menyebabkan jalan ditutup atau macet total. 

Sebagai contoh adalah jalan yang hancur akibat ledakan pipa PDAM di Jalan L.L.R.E. Martadinata, Bandung menyebabkan jalan tidak bias dilalui kendaraan sehingga menimbulakan kemacetan dan perlu dicari jalan alternatif. Masalah ini dapat diselesaikan dengan merepresentasikan gambar jalan yang diterima oleh perangkat navigasi GPS dari satelit dengan graf berbobot.

referensi : Inggriani Liem, “Draft Diktat Struktur Data”, Institut Teknologi Bandung, Bandung, 2008