LOGO

Derajat Simpul &

Barisan Derajat

Derajat Simpul &

Barisan Derajat

Oleh:

Davi Apriandi

PROGRAM STUDI PENDIDIKAN MATEMATIKAFAKULTAS PENDIDIKAN MATEMATIKA DAN ILMU PENGETAHUAN ALAM

IKIP PGRI MADIUN2013

Misal G sebuah graf dan v sebuah simpul di G.

Derajat simpul v di G adalah banyaknya rusuk yang hadir

(incident) di simpul v (catatan : loop dihitung dua kali).

Notasi: dG(v) atau d(v)

Derajat (Degree)

G1 G2 G3

1

32

4

1

23

4

5

1

2

e1

e2

e3

e4

e53

Tentukan derajat setiap simpul dari graf di atas.

Derajat minimum (terkecil) ) dari graf G, dilambangkan

dengan (G),

(G) = minimum {d(v) | v V(G)}

Derajat maksimum (terbesar) dari graf G, dilambangkan

dengan (G),

(G) = maksimum { d(v) | v V(G)}

Jika setiap simpul dari graf G berderajat k (k0), maka kita

sebut G graf teratur berderajat-k

Pada graph 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)

Tinjau graph :

din(1) = 2; dout(1) = 1

din (2) = 2; dout(2) = 3

din (3) = 2; dout(3) = 1

din (4) = 1; dout(4) = 2

1

2 3

4

Teorema Jabat Tangan

Jumlah derajat semua simpul pada suatu graph adalah

genap, yaitu dua kali jumlah rusuk pada graph tersebut.

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

Buktikan!

)(

)(GVv

vd = 2 |E(G)|

Tinjau graph G1:

d(1) + d(2) + d(3) + d(4) =2 +3+3+2= 10

= 2 jumlah sisi = 2 5

Tinjau graph G2:

d(1) +d(2) + d(3) =3+3+4= 10

= 2 jumlah sisi = 2 5

G1 G2

1

2

e1

e2 e

3

e4

e53

Akibat dari teorema (corollary):

Untuk sembarang graf G, banyaknya simpul berderajat

ganjil selalu genap.

Buktikan!

Barisan derajat graf G adalah barisan bilangan bulat non

negatif yang unsur-unsurnya adalah derajat simpul-simpul

graf G tersebut.

Misal G suatu graf dengan V(G) =

dan berturut-turut menunjukkan

derajat simpul di graf G.

Barisan d = disebut barisan

derajat dari graf G.

nvvvv ...,,, 321

)(...,),(),(),( 321 nvdvdvdvd

)(...,),(),(),( 321 nvdvdvdvd

G

f e d

b

c

a

Tentukan barisan derajat dari graf berikut!

Diketahui graph dengan lima buah simpul. Dapatkah menggambar graph tersebut jika derajat masing-masing simpul adalah:

a (3, 1, 1, 1, 2)

b (2, 5, 3, 2, 4)

c (5, 1, 2, 2, 3)

Mungkinkah dibuat graf-sederhana 5 simpul dengan derajat masing-masing simpul adalah:

a (5, 2, 3, 2, 4)

b (4, 2, 3, 2, 3)

c (3, 0, 1, 1, 1)

d (4, 2, 1, 3, 4)

e (3, 3, 0, 1, 2)

Jika mungkin, berikan satu contohnya, jika tidak mungkin, berikan alasan singkat.

Suatu barisan d =

dari bil. bulat non negatif adalah “graphic” jika

terdapat suatu graf sederhana dengan barisan

derajat d.

)(...,),(),(),( 321 nvdvdvdvd

ALGORITHM

Given a sequence of p ( ≥ 1) nonnegative integers:

1. If some integers in the sequence exceeds p-1, then the

sequence is not graphical. Otherwise, continue to Step 2.

2. If all integers in the sequence are 0, then the sequence is

graphical. If the sequence contains a negative integer, then the

sequence is not graphical. Otherwise, continue to Step 3.

3. Reorder the numbers in the current sequence, if necessary,

so that it is a nonincreasing sequence.

4. Delete the first number, say n, from the sequence, and

subtract 1 from the next number in the sequence. Return to

Step 2.

Tentukan apakah barisan-barisan berikut graphic atau

tidak. Jika graphic, konstruksikan suatu graf dgn degree

sequence yg sesuai.

d = (4, 2, 2, 2, 1, 3)

j = (4, 3, 1, 1, 1, 4)

k = (5, 4, 3, 3, 3, 3, 3)

p = (4, 3, 3, 2, 2, 2, 0, 0, 0)

q = (7, 3, 3, 4, 2, 2, 3, 2, 1, 1, 0)

Jarak : Lintasan terpendek dari suatu vertex ke vertex

lainnya

Diameter dari graf G

Dim (G) = max {d (u,v)}, u, v anggota V(G)