Contoh Soal dan Pembahasan Graf Tak Berarah

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 saja yang terkandung didalam 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, C), (B, D)

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

Ruas disebut SIZE dari graf. 

6. Berapakah derajat graf pada gambar 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                      Jadi, derajat graf G = 14

d(B) = 5            d(E) = 1                      (2 * 7)

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

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 di sini yaitu simpul B yang di ujung 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

Kelompok 4

Anggota:

Nico Ivananda Nugroho           55415045

Indah Maulina                          53415337

Dayu Citra Mai Wahyudi         51415614

Dzaky Rafid Resihanto            52415098

Iqbal Zarkasy Adiatma             53415410

Fajar Ismail W                          52415430

Mohamad Akromudin              54415251

Ary Prabowo Hamonangan Po 51415064