Contoh Soal Graf Berarah Oleh Kelompok 2

Soal

1. Sebutkan simpul yang terkandung dalam graf berarah diatas!
2. Sebutkan arkus yang terkandung dalam graf berarah di atas!

3. Barisan simpul E, A, B, F, G, B disebut...
4. Panjang walk dari graf G adalah...
5. Rank dari graf diatas adalah...
6. Nullity dari graf diatas adalah...
7. Diameter dari graf diatas adalah...

8. Buatlah Matrix Ruas dari graf diatas!
9. Buatlah Matrix Adjacency dari graf diatas!
10. Nyatakan Graf Berarah di bawah ini dengan matriks Sirkuit!

Pembahasan

1. Graf tersebut mengandung 4 simpul, yaitu: 1, 2, 3 dan 4.
2. Graf tersebut mengandung 7 arkus, yaitu: (1,4), (2,1), (2,1), (2,2), (2,3), (2,4), (4,3).
3. Trail, karena walk dengan semua ruas dalam barisan berbeda.
4. Panjang walk adalah 10, karena panjang walk = banyaknya ruas.
5. Diketahui: n=8; k=1

• Rank (G) = n – k

• Rank (G) = 8 – 1

• Rank (G) = 7

6. Diketahui: n= 8; k=1; e=1

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

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

• Nullity (G) = 3

7. Jarak maksimum dalam graf diatas adalah 4 (yaitu antara A-D, A-H, E-D, E-H), jadi diameter = 4.
8. 

9. 

10. 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:

Dari Kelompok 2 :

Bobby Chandra (51415385)

M. Gifari (54415617)

Yulio Siahaan (57415343)

Teguh Trisutami (56415845)

Rofiil Honi Ihzam (56415236)

Qadrisa Mutiara (55415471)

Prayoga Andika (55415384)

Didah (51415882)