Matdis 1C

GRAF

A.    Pengertian Graf

Graf adalah himpunan benda-benda yang disebut simpul (vertex atau node ) yang terhubung oleh sisi (edge).

Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf maka graf digolongkan menjadi:

1.      Graf Sederhana (Simple Graph)

Graf yang tidak mengandung gelang maupun sisi ganda.

2.      Graf tak sederhana (Unsimple Graph)

Graf yang mengandung sisi ganda atau gelang dinamakan graf tak sederhana. Ada dua macam graf tak sederhana, yaitu graf ganda dan graf semu.`

gambar garf ganda

gambar graf semu

 Berdasarkan orientasi arah pada sisi secara umum dibagi menjadi :

1.      Graf tak berarah (Undirected Graph)

Graf yang setiap sisinya tidak mempunyai orientasi arah. Pada graf tak berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan.

2.      Graf berarah (Directed Graph)

Graf yang setiap sisinya diberikan orientasi arah. Urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan.

B.      Termonologi Graf

1.      Termonologi bertetanggaan (Adjacent)

Adalah  dua buah simpul yang terhubung secara langsung.

2.      Termonologi bersisian (Incidency)

Sembarang sisi yang bersisian sampul dengan sisi.

3.      Termonologi terpencil (Isolated Vertex)

Adalah simpul yang tidak bertetanggaan dengan simpul-simpul lainnya.

4.      Graf  Kosong (null graph atau empty graph)

Graf yang himpunan sisinya merupakan himpunan kosong.

5.      Derajat (Degree)

Adalah suatu simpul pada graf tak berarah adalah jumah sisi yang bersisian dengan simpul tersebut.

6.      Lintasan (path)

Adalah panjang simpul awal hingga akhir.

7.      Siklus (cycle)atau sirkuit (circuit)

Adalah lintasan yang berawal dan berakhir pada sampul yang sama.

8.      Terhubung (connected)

Adalah dua simpul yang terhubung.

9.      Upagraf (subgraph) dan komplemen (subgraph)

Pada upagraf merupakan potongan graf dan sedangkan komplemen merupakan potongan garaf yang apabila di gabungkan akan menjadi graf yang utuh

10.  Upragraf rentang (spanning  Subgrab)

Upagraf G₁ = (V₁, E₁) dari G = (V, E) dikatakan upagraf rentang    jika V₁ =V (yaitu G₁ mengandung semua simpul dari G).

11.  Cut Set 

Cut-set dari graf terhubung G adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen.

12.  Graf Berbobot (Wieghted Graph)

Adalah graf yang setiap sisinya diberikan sebuah harga (bobot).

C.     Graf Khusus

1.      Graf Lengkap (Complete Graph)

Adalah graf yang sederhana yang setiap simpulnya mempunyai sisi ke semua simpulnya lainnya.

2.      Graph Lingkaran

Adalah graph sederhana yang setiap  simpulnya derajat yang sama.

3.      Graph Teratur (Regular Graph)

Adalah setiap simpulnya mempunyai derajat yang sama

4.      Graph Bipartit (Bipaetite Graph)

Adalah graph yang himpunan simpulnya dapat dikelompokkan menjadi 2 himpunan.