Graf Tak Berarah (Matematika Informatika)

   1. Himpunan garis yang menghubungkan tiap node / vertex disebut..

    A. Weight
    B. Vertex
    C. Path
    D. Edge
 

Jawaban : D. Edge

Himpunan E (Edge) yang merupakan pasangan tak urut dari simpul, anggotanya disebut ruas (rusuk atau sisi).

2.  Suatu Walk dengan semua ruas dalam barisan berbeda, disebut ?

A.      Path

B.      Trail

C.      Walk

D.     Digraph

Jawaban : B. Trail 

Gambar Graf di bawah ini untuk menjawab soal nomor 3 – 5!

 
3. Berapakah order pada Graf diatas ?  

    A.      1 
    B.      5 
    C.      4 
    D.     6

 

Jawaban : C. 4

Order adalah banyaknya simpul yang terdapat pada graf, jadi banyaknya simpul pada graf tersebut adalah 4

4. Tentukan size pada Graf diatas ! 

    A.      4 
    B.      5 
    C.      6 
    D.     1

Jawaban : C. 6  

Size adalah banyaknya ruas pada graf, jadi banyaknya size ada graf tersebut adalah 6

5. Ruas apa sajakan yang terkandung dalam graf diatas?

    

   A. (A, D), (A, B), (D, C), (B, C), (B, D)

   B. (A, C), (A, B), (D, C), (B, C), (B, D)

   C. (A, D), (C, A), (D, C), (B, C), (B, D)

   D. (A, D), (A, C), (D, C), (B, D), (B, C)

   Jawaban : A. (A, D), (A, B), (D, C), (B, C), (B, D) 

   Ruas disebut Size dari graf

 

 Gambar Graf di bawah ini untuk menjawab soal nomor 6 – 7 !

6. Berapakah derajat graf pada graf diatas ?
  
    A.      14 
    B.      12 
    C.      10 
    D.     5

Jawaban : A. 14

Jumlah derajat semua simpul suatu graf (derajat) = dua kali banyaknya ruas graf (size graf). gambar graf diatas memiliki ruas = 7, sedangkan derajat masing-masing simpul adalah :

d(A) = 2                 d(D) = 3                      

d(B) = 5                 d(E) = 1                       

d(C) = 3                 d(F) = 0 

Jadi, derajat graf G = 14
(2 * 7) 

 7. Dari gambar di atas, ruas yang di sebut sebagai Gelung adalah….

     

    A. A

    B. B

    C. C

    D. D

Jawaban: B. B

Ruas yang disebut Gelung disini yaitu simpul B yang diujung garisnya ada lingkaran kecil

Gambar Graf di bawah ini untuk menjawab soal nomor 8 – 10!

  

 

8. Ada berapakah komponen pada graf diatas ? 

   A.      3 
   B.      5 
   C.      6 
   D.     4

   Jawaban : D. 4

   komponen, karena pada A, E, H, dan J tidak ada jalur

9. Berapakah Rank pada graf diatas ? 

    
    A.      6
    B.      7
    C.      1 
    D.     4

   Jawaban : A. 6

            Dik : n = 10

                        k = 4

R = n - k

   = 10 – 4 = 6

10. Berapakah Nullity pada graf diatas ? 

     A.      6 
     B.      7
     C.      1
     D.     2

Jawaban : C. 1

            Dik : n = 10

                        K = 4

                        e = 7

            Nullity = e – (n – k)

                        = 7 –(10 – 4) = 7 – 6 = 1