Graf

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

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

· Sejarah Graf: masalah jembatan Königsberg (tahun 1736)

· Graf yang merepresentasikan jembatan Königsberg:

Simpul (vertex) à menyatakan daratan

Sisi (edge) à menyatakan jembatan

Definisi Graf

Graf G = (V, E), yang dalam hal ini:

V = himpunan tidak-kosong dari simpul-simpul (vertices)

= { v₁ , v₂ , ... , v_n }

E = himpunan sisi (edges) yang menghubungkan sepasang

simpul

= {e₁ , e₂ , ... , e_n }