MATERI TEORI GRAF

Graph Graph

• Graph digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.

• Gambar berikut ini sebuah graph yang menyatakan peta jaringan jalan raya yang menghubungkan sejumlah kota di Provinsi Jawa Tengah. 

Graph

• Sejarah Graph: masalah jembatan KÖnigsberg (tahun 1736)

Graph yang merepresentasikan jembatan KÖnigsberg:
Simpul (vertex) : menyatakan daratan
Sisi (edge) : menyatakan jembatan
Bisakah melalui setiap jembatan tepat sekali dan kembali lagi ke tempat semula?

Definisi Graph
Graph G= (V, E), yang dalam hal ini:
V= himpunan tidak-kosong dari simpul-simpul (vertices) = { v1 , v2 , ... , vn}
E= himpunan sisi (edges) yang menghubungkan sepasang simpul = {e1 , e2 , ... , en}