TEORI GRAF V

Derajat (Degree)
Derajatsuatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.
Notasi: d(v)
Tinjau graph G1:
d(1) = d(4) = 2
d(2) = d(3) = 3

Derajat (Degree)
Tinjau graph G3:
d(5) = 0 = simpul terpencil
d(4) = 1 = simpul anting-anting (pendant vertex)
Tinjau graph G2:
d(1) = 3 = bersisian dengan sisi ganda
d(2) = 4 = bersisian dengan sisi gelang (loop)





Derajat (Degree)
Pada graph berarah,
d in(v) = derajat-masuk (in-degree) = jumlah busur yang masuk ke simpul v
d out(v) = derajat-keluar (out-degree) = jumlah busur yang keluar dari simpul v
d(v) = d in(v) + d out(v)

Derajat (Degree)
Tinjau graph :
d in(1) = 2; d out(1) = 1
d in(2) = 2; d out(2) = 3
d in(3) = 2; d out(3) = 1
d in(4) = 1; d out(4) = 2





Lemma Jabat Tangan
Jumlah derajat semua simpul pada suatu graph adalah genap, yaitu dua kali jumlah sisi pada graph tersebut.
Dengan kata lain, jika G= (V, E), maka

Lemma Jabat Tangan
Tinjau graph G1:
d(1) + d(2) + d(3) + d(4) =
2 + 3 + 3 + 2 = 10 =
2 jumlah sisi = 2 x 5
Tinjau graph G2:
d(1) +d(2) + d(3)
= 3 + 3 + 4 = 10
= 2 jumlah sisi = 2 x 5




Lemma Jabat Tangan
Tinjau graph G3:
d(1) + d(2) + d(3) + d(4) + d(5)
= 2 + 2 + 3 + 1 + 0
= 8
= 2 jumlah sisi
= 2 x 4

Lemma Jabat Tangan
Contoh.
Diketahui graph dengan lima buah simpul. Dapatkah kita menggambar graph tersebut jika derajat masing-masing simpul adalah:
(a) 2, 3, 1, 1, 2
(b) 2, 3, 3, 4, 4
Penyelesaian:
(a) tidak dapat, karena jumlah derajat semua simpulnya
ganjil
(2 + 3 + 1 + 1 + 2 = 9).
(b) dapat, karena jumlah derajat semua simpulnya
genap
(2 + 3 + 3 + 4 + 4 = 16).