Definisi
Graph
Graf
digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara
objek-objek tersebut
Sejarah
Graf: masalah jembatan Königsberg (tahun 1736).Graf yang merepresentasikan
jembatan Königsberg:
Simpul
(vertex) menyatakan daratan
Sisi (edge)
menyatakan jembatan
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
Graph
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.
2. Graf
tak-sederhana (unsimple-graph).
Graf yang mengandung sisi ganda atau gelang
dinamakan graf tak-sederhana (unsimple
graph).
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 tak-berarah.
2. Graf
berarah (directed graph atau digraph)
Graf yang setiap sisinya diberikan orientasi
arah disebut sebagai graf berarah.
Tabel 1 Jenis-jenis graf [ROS99]
|
Jenis
|
Sisi
|
Sisi
ganda dibolehkan?
|
Sisi gelang
dibolehkan?
|
|
Graf sederhana
Graf ganda
Graf semu
Graf berarah
Graf-ganda berarah
|
Tak-berarah
Tak-berarah
Tak-berarah
Bearah
Bearah
|
Tidak
Ya
Ya
Tidak
Ya
|
Tidak
Tidak
Ya
Ya
Ya
|
EmoticonEmoticon