Ini Blognya Satia Raras :): GRAF

GRAF

Teori graf adalah cabang kajian yang mempelajari sifat-sifat 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).

Sebuah 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. Ekstensi lain pada graf adalah dengan membuat sisinya berarah, yang secara teknis disebut graf berarah atau digraf (directed graph). Digraf dengan sisi berbobot disebut jaringan.

Jaringan banyak digunakan pada cabang praktis teori graf yaitu analisis jaringan. Perlu dicatat bahwa pada analisis jaringan, definisi kata "jaringan" bisa berbeda, dan sering berarti graf sederhana (tanpa bobot dan arah).

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:

Graf sederhana (simple graph)

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

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 :

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.

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.

Pada graf diatas :

d(P) = d(Q) = d (S)= 5, sedangkan d(R) = 3.

Derajat sebuah simpul pada suatu graf berarah dijelaskan sebagai berikut :

• din(v) merupakan jumlah busur yang masuk ke simpul v

• dout(v) merupakan jumlah busur yang keluar dari simpul v

Dengan demikian derajat pada simpul tersebut, diperoleh : d(v) = din(v) + dout(v).

Lintasan (Path)

Lintasan dari suatu simpul awal v0 ke simpul tujuan vT di dalam suatu graf G merupakan barisan sebuah sisi atau lebih (x0, x1), (x1, x2), (x2, x3), …, (xn-1, xn) pada G, dimana x0 = v0 dan xn = vT. Lintasan ini dinotasikan oleh : x0, x1, x2, x3, …, xn.

• Pada graf tersebut lintasan P, Q, R memiliki panjang 2. Sementara itu

lintasan P, Q, S, R memiliki panjang 3.

• Lintasan P, Q, R, S, P dinamakan siklus atau sirkuit dengan panjang 4.

• Antara simpul P dan U maupun T tidak dapat ditemukan lintasan.

Cut-Set

Cut-set dari suatu graf terhubung G adalah himpunan sisi yang jika dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah subgraf . Pada graf di bawah, {(1,4), (1,5), (2, 3), (2,4)} adalah cut-set. Terdapat banyak cut-set pada sebuah graf terhubung. Himpunan {(1,5), (4,5)} juga adalah cut-set, {(1,4), (1,5), (1,2)} adalah cut-set, {(5,6)} juga cut-set, tetapi {(1,4), (1,5), (4,5)} bukan cut-set sebab himpunan bagiannya, {(1,5), (4,5)} adalah cut-set.

Disini saya akan memberikan contoh graf teratur berderajat 3 , 4 dan 5 ( 3D, 4D, 5D ) maksud dari :

3D yaitu setiap titik dapat menghasilkan 3 garis

4D yaitu setiap titik dapat menghasilkan 4 garis

5D yaitu setiap titik dapat menghasilkan 5 garis

berikut contoh gambar dari graf teratur :