TEORI GRAF 4

Berdasarkan orientasi arah pada sisi, maka secara
umum graph dibedakan atas 2 jenis:

1. Graph tak-berarah (undirected graph)
Graph yang sisinya tidak mempunyai orientasi arah
disebut graph tak-berarah. Tiga buah graph pada
Gambar 2 adalah graph tak-berarah.
2. Graph berarah (directed graph atau digraph)
Graph yang setiap sisinya diberikan orientasi arah
disebut sebagai graph berarah. Dua buah graph pada
Gambar 3 adalah graph berarah.

Jenis-Jenis Graph

Berdasarkan orientasi arah pada sisi, maka
secara umum graph dibedakan atas 2 jenis:
1. Graph tak-berarah (undirected graph)
2. Graph berarah (directed graph atau digraph)


Graph tak-berarah (undirected graph)Graph yang sisinya tidak mempunyai orientasi
arah disebut graph tak-berarah. Graph G1, G2,
dan G3 adalah graph tak-berarah.

Graph berarah (directed graph atau digraph)
Graph yang setiap sisinya diberikan orientasi arah
disebut sebagai graph berarah.

TEORI GRAF 3

Jenis-Jenis Graph

Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graph, maka graph
digolongkan menjadi dua jenis:

1. Graph sederhana (simple graph).
2. Graph tak-sederhana (unsimple-graph).

Graph sederhana (simple graph)
Graph yang tidak mengandung gelang maupun sisi-ganda dinamakan graph

sederhana. G1 adalah contoh graph sederhana.

Graph tak-sederhana (unsimple-
graph)
Graph yang mengandung sisi ganda atau
gelang dinamakan graph tak-sederhana
(unsimple graph). G2 dan G3 adalah contoh
graph tak-sederhana.

Jenis-Jenis Graph

Berdasarkan jumlah simpul pada suatu
graph, maka secara umum graph dapat
digolongkan menjadi dua jenis:
1. Graph berhingga (limited graph)
2. Graph tak-berhingga (unlimited
graph)


Graph berhingga (limited graph)
Graph berhingga adalah graph yang jumlah
simpulnya, n, berhingga.
 Graph tak-berhingga (unlimited graph)
Graph yang jumlah simpulnya, n, tidak
berhingga banyaknya disebut graph tak-
berhingga.

TEORI GRAF 2

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}