TUGAS 14 (GRAF)

1.   Jelaskan pegertian Graf !

Jawab :

Graph digunakan untuk merepresentasikan objek-objek diskrit  dan hubungan antara objek-objek tersebut.

2.   Sebutkan 5 contoh terminologi Graf dan jelaskan !

Jawab :

a)   Ketetanggaan (Adjacent)

Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.

b)   Simpul Terpencil (Isolated Vertex)

Simpul yang tidak mempunyai sisi yang bersisian dengannya.

c)    Graf  Kosong (null graph atau empty graph)

Graf yang himpunan sisinya merupakan himpunan kosong (N_n).

d)   Derajat (Degree)

Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.

e)   Lintasan (Path)

Lintasan yang panjangnya n dari simpul awal v₀ ke simpul tujuan.  

3.   Jelaskan pengertian dari beberapa Graf khusus

Jawab :

v Graf Lengkap (Complete Graph)

Graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya.

v Graf Lingkaran

Graf sederhana yang setiap simpulnya berderajat 2.

v Graf Teratur (Regular Graphs)

Graf yang simpulnya mempunyai derajat yang sama.

v Graf Bipartite (Bipartite Graph)

Graf G yang himpunan simpulnya dapat dipisah menjadi 2 himpunan bagian V₁  dan V₂,  sedemikian sehingga setiap sisi pada G menghubungkan sebuah simpul tersebut.

4.   Representasi Graf memiliki 3 unsur. Buatlah 1 contoh dari masing-masing unsur tersebut !

Jawab :

a)   Matriks Ketetanggaan (adjacency matrix)

Matriks Bersisian (incidency matrix

)

b)   Senarai Ketetanggaan (adjacency list)

5.   Gambarkan 2 buah graf yang isomorfik dengan graf teratur berderajat 3 yang mempunyai 8 buah  simpul !

Jawab :