MEMBUAT GRAF

Posted by : Unknown Selasa, 10 Juni 2014

Graf adalah himpunan benda-benda yang disebut (vertex atau node) yang terhubung oleh (edge) atau (arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan simpul) yang dihubungkan oleh garis-garis (melambangkan sisi) atau garis berpanah (melambangkan busur).

Struktur graf bisa dikembangkan dengan memberi bobot pada tiap sisi. Graf berbobot dapat digunakan untuk melambangkan banyak konsep berbeda. Sebagai contoh jika suatu graf melambangkan jaringan jalan maka bobotnya bisa berarti panjang jalan maupun batas kecepatan tertinggi pada jalan tertentu.

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).

Berikut contoh gambar sederhananya: