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
Bisakah melalui setiap jembatan tepat sekali dan kembali lagi ke tempat semula ?
Definisi Graf
Graf 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 }
Jenis-Jenis Graf
Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis:
1. Graf sederhana (simple graph).
Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. G1 pada Gambar 2 adalah contoh graf sederhana
2. Graf tak-sederhana (unsimple-graph).
Graf yang mengandung sisi ganda atau gelang dinamakan graf taksederhana (unsimple graph).
G2 dan G3 pada Gambar 2 adalahcontoh graf tak-sederhana.
Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf
dapat digolongkan menjadi dua jenis:
1. Graf berhingga (limited graph) Graf berhingga adalah graf yang jumlah simpulnya berhingga.
2. Graf tak-berhingga (unlimited graph) Graf yang jumlah simpulnya tidak berhingga banyaknya disebut graf tak-berhingga.
Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis:
1. Graf tak-berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf takberarah.
Tiga buah graf pada Gambar 2 adalah graf tak-berarah.
Graf berarah (directed graph atau digraph)
Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah.
Dua buah graf pada Gambar 3 adalah graf berarah.
EmoticonEmoticon