Page 7 - E-Modul

BAB II

TEORI PENDUKUNG
2.1. Definisi Graf

Sebuah graf G berisikan dua himpunan yaitu himpunan hingga tak kosong

V(G) yang elemen-elemennya disebut titik dan himpunan (mungkin kosong) E(G)
yang elemen-elemennya disebut sisi, sedemikian sehingga setiap elemen e dalam

E(G) adalah sebuah pasangan tak berurutan dari titik di V(G). V(G) disebut

himpunan titik-titik dan E(G) disebut himpunan sisi dari G.

Graf dapat dinyatakan atau direpresentasikan dengan Himpunan Pasangan

Berurutan, Diagram, Matriks Adjasensi, Matriks Insidensi, dan Daftar

Ketetanggaan. Cara merepresentasikan sebuah graf yang paling umum adalah
berupa diagram. Dalam diagram-diagram tersebut, titik-titik dinyatakan sebagai

noktah dan tiap sisi dinyatakan sebagai segmen garis yang menghubungkan tiap
dua titik.

2.2. Jenis – Jenis Graf

Jenis-jenis graf dapat diklasifikasikan berdasarkan beberapa faktor-faktor

sebagai berikut :

1. Berdasarkan ada tidaknya gelang atau edge ganda pada suatu graf, maka graf

digolongkan menjadi dua jenis, yaitu :

a. Graf sederhana

Graf sederhana yaitu graf yang tidak mengandung edge maupun edge
ganda. Gambar di bawah ini adalah contoh graf sederhana.
1

2 3

4
Gambar 1 : Graf sederhana

3