GRAF

Secara informal, suatu graf adalah himpunan benda-benda yang disebut simpul (vertex atau node) yang terhubung oleh sisi (edge) atau busur (arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan simpul) yang dihubungkan oleh garis-garis (melambangkan sisi) atau garis berpanah (melambangkan busur). Suatu sisi dapat menghubungkan suatu simpul dengan simpul yang sama. Sisi yang demikian dinamakan gelang (loop).

Jenis-jenis Graf

Graf memiliki banyak jenis, dalam tulisan ini akan dibahas beberapa jenis graf yang sering digunakan. Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf dan berdasarkan sisi pada graf yang mempunyai orientasi arah.

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

1. Graf sederhana (simple graph)

Graf yang tidak mengandung gelang maupun sisi ganda dinamakan graf sederhana.

2. Graf tak-sederhana (unsimple graph)

Graf yang mengandung sisi ganda atau gelang dinamakan graf tak sederhana (unsimple graph). 

Ada dua macam graf tak sederhana, yaitu :

1. Graf ganda (multigraph)

Graf ganda merupakan graf tak berarah  yang tidak mengandung gelang  (loop).

2. Graf semu (pseudograph).

Graf semu adalah graf yang mengandung gelang (loop).

Jumlah simpul pada graf disebut sebagai kardinalitas graf, dan dinyatakan dengan n = |V|, dan jumlah sisi kita nyatakan dengan m = |E|

Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis :

1. Graf tak-berarah (undirected graph)

Graf berarah merupakan  graf yang setiap sisinya mempunyai arah dan

diantara dua buah simpul tidak mempunyai dua sisi yang berlawanan.

2. Graf berarah (directed graph atau digraph)

Graf ganda berarah merupakan  graf berarah yang membolehkan adanya sisi ganda pada graf tersebut (boleh mempunyai dua sisi yang berlawanan antara dua buah simpul).

3. Graf  ganda  berarah  (directed multigraph).

Graf ganda berarah merupakan  graf berarah yang membolehkan adanya sisi ganda pada graf tersebut (boleh mempunyai dua sisi yang berlawanan antara dua buah simpul).

Terminologi Graf

1. Bertetangga  (Adjacent)

Jika kedua simpul tersebut terhubung langsungoleh suatu sisi. 

            

2. Bersisian (Incidency)

Suatu sisi e dikatakan bersisian dengan simpul v1 dan simpul v2 jika e menghubungkan kedua simpul tersebut.

3. Simpul Terpencil (Isolated Vertex)

Jika suatu simpul tidak mempunyai sisi yang bersisian dengan simpul itu sendiri.

4. Derajat (Degree)

Derajat suatu simpul merupakan  jumlah sisi yang bersisian dengan simpul tersebut. Misalkan, suatu simpul v  mempunyai 3 buah sisi yang bersisian dengannya maka dapat dikatakan simpul tersebut berderajat 3, atau dinotasikan oleh d(v) = 3.

Contoh graf 3D, 4D, dan 5D yang telah saya buat: 

Berikut adalah vidio tutorial membuat graf teratur yang telah saya buat:

Versi Youtube: disini

sumber: disini