TEORI GRAF

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.

 

 GraphSejarah 

• 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}