Derajat

Definisi

Misalkan v adalah titik dalam suatu Graf G. Derajat titik v (symbol (d(v) adalah jumlah garis yang berhubungan dengan titik v dan garis suatu loop dihitung dua kali.

Derajat total G adalah jumlah derajat semua titik dalam G.

Contoh :

Tentukan derajat tiap-tiap titik dalam graf pada gambar berikut ini. Berapa derajat totalnya?.

Teorema

Derajat total suatu graf selalu genap

Teorema

Dalam sembarang graf, jumlah titik yang berderajat ganjil adalah genap.

Penyelesaian :d(v1) = d(v2) =d(v3) =d(v4) =d(v5) =d(v6) =

Latihan

1. Gambarlah graf dengan spesifikasi dibawah ini (jika ada)a. Graf dengan 4 titik yang masing-masing berderajat 2,2,3,3b. Graf dengan 5 titik yang masing-masing berderajat 1,1,2,2,0c. Graf sederhana dengan 4 titik yang masing-masing berderajat 1,1,3,3d. Graf dengan 10 titik yang masing-masing berderajat 1,1,2,2,2,3,4,4,4 dan

6

2. Hitunglah masing-masing derajat titik dan derajat total dari graf berikut :

3. a. Hitunglah jumlah garis dari complete graph dengan jumlah titik 5.b. Gambarkan graf tersebutc. Hitung derajat masing-masing titik dan derajat totalnya.