GRAF

1.     Buat sebuah graf dan cari walk, trail, path, sirkuit

 

Keterangan :

-       Walk : barisan simpul dan ruas

-       Trail : Walk dengan ruas yang berbeda

-       Path / Jalur :   Walk dengan simpul yang berbeda

-       Cycle / Sirkuit : Trail tertutup dengan derajat setiap simpul = 2

                                                                                                                  

1)   A, B, C, D, E, F, C, A, B, D, C ® Walk

2)   A, B, C, D, E, F, C, A ® Trail

3)   A, B, C, A ® Cycle

4)   A, B, D, C, B, D, E ® Walk

5)   A, B, C, D, E, C, F ® Trail

6)   A, B, D, C, E, D ® Trail

7)   A, B, D, E, F, C, A ® Cycle

8)   C, E, F ® Path

9)   B, D, C, B ® Cycle

10) C, A, B, C, D, E, C, F, E ® Trail

11) A, B, C, E, F, C, A ® Trail

2.     Buat graf isomorfisma dan homomorfisma dan sebutkan jumlah derajat, simpul dan ruasnya

-       Graf isomorfisma

Adalah dua graf atau lebih yang memiliki jumlah ruas, simpul, derajat simpul sama.

Gambar 1             Gambar 2

Derajat Gambar 1                                              Derajat Gambar 2

d(A) = 2                                                             d(A) = 1

d(B) = 2                                                             d(B) = 2

d(C) = 2                                                             d(C) = 2

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

d(E) = 2                                                             d(E) = 2

d(t) = 10                                                             d(t) = 10

	Gambar 1	Gambar 2
Derajat	10	10
Simpul	5	5
Ruas	5	5

Derajat simpul : banyaknya ruas yang menghubungi simpul atau derajat sama dengan 2 kali jumlah ruas yang ada

Ruas : garis/edge

Simpul : titik/vertex

-       Graf homomorfisma

           Adalah dua graf atau lebih yang gambarnya sama, tapi order, size dan derajatnya simpul berbeda.

Gambar 1                                Gambar 2

Derajat Gambar 1                                              Derajat Gambar 2

d(A) = 1                                                             d(A) = 1

d(B) = 1                                                             d(B) = 2

d(C) = 1                                                             d(C) = 4

d(D) = 1                                                             d(D) = 1

d(E) = 4                                                             d(E) = 1

                                                                           d(F) = 1

d(t) = 8                                                               d(t) = 10

	Gambar 1	Gambar 2
Derajat	8	10
Simpul	5	6
Ruas	4	5

Derajat simpul : banyaknya ruas yang menghubungi simpul atau derajat sama dengan 2 kali jumlah ruas yang ada

Ruas : garis/edge

Simpul : titik/vertex

3.     Buat 2 buah graf dan lakukan operasi pada graf tersebut

Bila diketahui 2 buah graf : G₁(V₁,E₁)  dan G₂(V₂,E₂), maka operasi-operasi yang akan dilakukan adalah :

1. Gabungan G₁ È G₂ adalah graf dengan himpunan V nya = V₁ È V₂ dan himpunan E nya = E₁ È E₂

2.  Irisan G₁ Ç G₂ adalah graf dengan himpunan V nya = V₁ Ç V₂ dan himpunan E nya = E₁ Ç E₂

3.  Selisih G₁ - G₂ adalah graf dengan himpunan V nya = V₁ dan himpunan E nya = E₁ - E₂

Sedangkan Selisih G₂ – G₁ adalah graf dengan himpunan V nya = V₂ dan himpunan E nya = E₂ – E₁

4.  Penjumlahan Ring G₁ Å G₂ adalah graf yang dihasilkan dari

(G₁ È G₂) – (G₁ Ç G₂) atau (G₁ - G₂) È (G₂ - G₁)

1.Hasil dari G1 union G2                                2. Hasil dari G1 irisan G2

                          

3. Hasil dari Penjumlahan                                     4. Hasil dari selisih