Contoh Soal Graph dan Jawabannya

HEDYANA PRATIWI                       53416254

DANDY M PUTRA                          51416691

SALMA KHAIRUNNISA                   56416772

BIRKY WIRKA                               51416453

TYAS KUSMULIATI                         57416466

FIRDA DAFFA UTAMI                     52416855

TIAR FAJRIAN                               57416378

M. HAIKAL                                   54416890

A. LUTFI                                       50416382

M. KEMAL R                                 54416176

ECHA TIRAYANA                          52416245

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: