SOAL GRAF DAN PEMBAHASAN

KELOMPOK 1

Birky Wirka                            51416453

Dandy M Putra                       51416691

Echa Tirayana                        52416245

Firda Daffa Utami                  52416855

Hedyana Pratiwi                     55416254

M. Haikal                                54416890

M. Kemal R.                           54416176

M . Lutfi                                 50416382

Tiar Fajrian                             57416378

Tyas Kusmuliati                      57416466

1.      Sebutkan simpul yang terkandung dalam graf berarah diatas!

2.      Sebutkan arkus yang terkandung dalam graf berarah diatas!

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,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: