Contoh Soal Graf Berarah

1. Apa yang dimaksud dengan Graph Berarah?
Jawab :

Graph berarah (directed graph atau digraph) adalah Graph yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah

2. Sebutkansimpul yang terkandungdalam graph berarahdiatas!

Jawab :

Graph tersebut mengandung 4 simpul, yaitu : 1, 2, 3 dan 4

3.  Sebutkan arkus yang terkandung dalam graph berarah di atas!

Jawab:

Graph tersebut mengandung 7 arkus, yaitu: (1,4), (2,1), (2,1), (2,2), (2,3), (2,4), (4,3).

4. Barisan simpul E, A, B, F, G, B disebut ….

Jawab :

Trail, karena walk dengan semua ruas dalam barisan berbeda

5. Panjang walk darigraf G adalah …..

Jawab :

Panjang walk adalah 10, karena panjang walk = banyaknya ruas

6. Rank dari graph diatas adalah?

Jawab :

• Diketahui: n=8; k=1

• Rank (G) = n – k

• Rank (G) = 8 – 1

• Rank (G) = 7

7.Nullity dari graph diatas adalah?

Jawab :

• Diketahui: n= 8; k=1; e=1

• Nullity (G) = e – (n – k)

• Nullity (G) = 1 – (8 – 1)

• Nullity (G) = 3

8. Diameter dari graph diatasadalah ….

Jawab :

Jarak maksimum dalam graph diatas adalah 4 (yaituantara A-D, A-H, E-D, E-H), jadi diameter = 4

9. Nyatakan graph dibawah ini kedalam matriks hubung

Jawab:

Graf tersebut terdiri dari 5 titik (v1 ... v5) sehingga matriks hubungnya adalah matriks bujur sangkar 5 x 5.  jadi bentuk matriksnya adalah : 

10. Nyatakan Graf Berarah di bawah ini dengan matriks Sirkuit !

Jawab:

Ada 4 sirkuit pada graf tersebut, masing – masing sirkuit itu adalah 

S1 = v4 v6 v4

S2 = v2 v4 v5 v2

S3 = v1 v2 v5 v1

S4 = v1 v2 v4 v5 v1

Misalkan orientasi yang dipilih pada s2 dan s3 sesuai dengan arah jarum jam, sedangkan pada s1 dan s4 berlawanan dengan arah jarum jam. Dengan demikian, matriks sirkuitnya adalah : 

Kelompok 3
1. Bambang
2. EkoSaputra
3. FirdaAzmalia
4. Nada Verrell M.
5. Randy Indra R.
6. Septian
7. VeriTanjung
8. IbnuRamadhan
9. Riyan Septa