Terminologi Graf

1. Ketetanggaan (Adjacent)
Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.
Tinjau graf G1 : simpul 1 bertetangga dengan simpul 2 dan 3,
simpul 1 tidak bertetangga dengan simpul 4.

2. Bersisian (Incidency)
Untuk sembarang sisi e = (vj, vk) dikatakan
e bersisian dengan simpul vj , atau
e bersisian dengan simpul vk

Tinjau graf G1: sisi (2, 3) bersisian dengan simpul 2 dan simpul 3,
sisi (2, 4) bersisian dengan simpul 2 dan simpul 4,
tetapi sisi (1, 2) tidak bersisian dengan simpul 4.

3. Simpul Terpencil (Isolated Vertex)
Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian dengannya.
Tinjau graf G1: simpul 5 adalah simpul terpencil.
4. Graf Kosong (null graph atau empty graph)
Graf yang himpunan sisinya merupakan himpunan kosong (Nn).
Graf N5 :


5. Derajat (Degree)
Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.
Notasi: d(v)

Tinjau graf G1:
d(1) = d(4) = 2
d(2) = d(3) = 3

Tinjau graf G3: d(5) = 0  simpul terpencil
d(4) = 1  simpul anting-anting (pendant vertex)

Tinjau graf G2: d(1) = 3  bersisian dengan sisi ganda
d(2) = 4  bersisian dengan sisi gelang (loop)

Pada graf berarah,
din(v) = derajat-masuk (in-degree)
= jumlah busur yang masuk ke simpul v

dout(v) = derajat-keluar (out-degree)
= jumlah busur yang keluar dari simpul v

d(v) = din(v) + dout(v)
Lemma Jabat Tangan. Jumlah derajat semua simpul pada suatu graf adalah genap, yaitu dua kali jumlah sisi pada graf tersebut.

Dengan kata lain, jika G = (V, E), maka




Tinjau graf G1: d(1) + d(2) + d(3) + d(4) = 2 + 3 + 3 + 2 = 10
= 2  jumlah sisi = 2  5

Tinjau graf G2: d(1) + d(2) + d(3) = 3 + 3 + 4 = 10
= 2  jumlah sisi = 2  5


Tinjau graf G3: d(1) + d(2) + d(3) + d(4) + d(5)
= 2 + 2 + 3 + 1 + 0 = 8
= 2  jumlah sisi = 2  4