Teori Graf

Definisi Graf
Graf G (V, E), adalah koleksi atau pasangan dua himpunan
(1) Himpunan V yang elemennya disebut simpul atau titik, atau vertex, atau point,
atau node.
(2) Himpunan E yang merupakan pasangan tak terurut dari simpul, disebut ruas
atau rusuk, atau sisi, atau edge, atau line.

JENIS – JENIS GRAF

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

1. Graf sederhana (simple graf).
Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf
sederhana.

2. Graf tak-sederhana (unsimple-graf/multigraf).
Graf yang mengandung ruas ganda atau gelung dinamakan graf tak-sederhana
(unsimple graf atau multigrapf).

• Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat
digolongkan menjadi dua jenis:

1. Graf berhingga (limited graf)
Graf berhingga adalah graf yang jumlah simpulnya, n, berhingga.

2. Graf tak-berhingga (unlimited graf)
Graf yang jumlah simpulnya, n, 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 graf)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah.

2. Graf berarah (directed graf atau digraf)
Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah.
Dua buah graf pada Gbr 3 adalah graf berarah.

sumber:
http://staff.gunadarma.ac.id/