Graf Dan Analisis Algoritma

Graf Berarah

Di dalam situasi yang dinamis, seperti pada komputer digital ataupun pada sistem aliran (flow system), konsep graf berarah lebih sering digunakan dibandingkan dengan konsep graf tak berarah.

Suatu graf berarah (Directed Graph, yang dikenal sebagai Digraf) D terdiri dari 2 himpunan :

(1). Himp. V, yang elemennya disebut simpul

            ® Vertex / point / titik / node

(2). Himp. A, yang merupakan pasangan terurut dari simpul-simpul, disebut ruas berarah

            ® Arc / arkus

Sehingga sebuah digraf dinotasikan sebagai D ( V, A )         

Contoh :

Sebuah graf berarah D(V,A), dengan :

1. V = { 1, 2, 3, 4 }
2. A = { (1,4), (2,1), (2,1), (4,2), (4,3), (2,3), (2,2) }

Arc (2,2) disebut gelung (self-loop), sedangkan arc (2,2) muncul 2 kali, disebut arc sejajar atau arc berganda.

Apabila arc suatu graf berarah mempunyai suatu bobot, graf berarah tersebut dinamakan suatu jaringan atau network.

Beberapa  Pengertian dalam graf berarah :

·         Derajat ke luar (out degree) suatu simpul adalah banyaknya arc yang mulai / keluar dari simpul tersebut.

·         Derajat ke dalam (in degree) suatu simpul adalah banyaknya arc yang berakhir / masuk ke simpul tersebut.

·         Simpul berderajat ke dalam = 0 disebut sumber (source), sedangkan simpul berderajat ke luar = 0 disebut muara (sink).

·         Pengertian Walk, Trail, Path (Jalur) dan Sirkuit (Cycle) berlaku pula pada graf berarah, dimana harus sesuai dengan arah arc. Kalau tidak sesuai dengan arah arc-nya, maka disebut sebagai semi walk, semi path atau semi trail.

Pada graf berarah terdapat 3 pengertian keterhubungan, yakni :

·               Terhubung lemah, jika terdapat suatu semi path antara setiap 2 simpul dari D.

·               Terhubung unilateral, jika antara setiap 2 simpul u dan v dari D, terdapat jalur dari u ke v atau dari v ke u. 

·               Terhubung kuat, jika antara setiap 2 simpul u dan v dari D, terdapat jalur dari u ke v dan dari v ke u.

contoh graf berarah:

sumber: pict.google.com