Pengenalan Teori Graf

Pendahuluan

Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.

Gambar di atas ini sebuah graf yang menyatakan peta jaringan jalan raya yang menghubungkan sejumlah kota di Provinsi Jawa Tengah.

Masalah jembatan Königsberg (tahun 1736) ditemukan oleh Euler

Gambar 1. Masalah Jembatan Königsberg

Graf yang merepresentasikan jembatan Königsberg: Simpul (vertex) → menyatakan daratan
Sisi (edge) → menyatakan jembatan
Bisakah melalui setiap jembatan tepat sekali?

Seorang pengantar pizza memiliki 5 alamat pemesan yang harus diantarkan dengan sekali berangkat. Pengantar pizza tersebut tidak boleh kembali sebelum semua pesanan diantarkan. Permasalahannya adalah bagaimana pengantar itu memilih rute yang paling cepat untuk mengunjungi ke 5 alamat itu supaya waktu yang ada lebih singkat dan setelah semuanya dikunjungi maka ia akan kembali ke toko pizza tempatnya ia bekerja lagi.

Rute perjalanan dari kota A ke P dapat dilakukan dengan berbagai macam alternatif. Dari sekian banyak alternatif yang ada maka tentukanlah rute yang paling minimal untuk ditempuh (misalkan minimal dalam hal jarak tempuh/waktu tempuh) ?

Jika kita lakukan analisis terhadap problem tadi, maka kita akan buatkan model persoalannya ke dalam model Graph.

Graf

G = (V, E)

, yang dalam hal ini:

~~~~~V = \text{himpunan simpul (*vertices*)}

~~~~~~~~~= \{v_1, v_2, \dots, v_n\}

~~~~~E = \text{himpunan sisi (*edges*) yang menghubungkan sepasang simpul}

~~~~~~~~~= \{e_1, e_2, \dots, e_n\}