Intan's Blog: Tugas Ilmu Alamiah Dasar : Graf

Definisi

Dalam bahasa sehari – hari, sebuah graf adalah himpunan dari objek – objek yang dinamakan titik, simpul, atau sudut dihubungkan oleh penghubung yang dinamakan garis atau sisi.

Graf adalah :

¨ Himpunan V (Vertex) yang elemennya disebut simpul (atau point atau node atau titik)

¨ Himpunan E (Edge) yang merupakan pasangan tak urut dari simpul, anggotanya disebut ruas (rusuk atau sisi)

Notasi : G(V,E)

Simpul u dan v disebut berdampingan bila terdapat ruas (u,v).

Graf dapat pula disajikan secara geometrik, simpul disajikan sebagai sebuah titik, sedangkan ruas disajikan sebagai sebuah garis yang menghubungkan 2 simpul.

Banyak simpul disebut ORDER, banyak ruas disebut SIZE dari graf.

Graf yang lebih umum disebut Multigraf

Derajat simpul V, ditulis d(v) adalah banyaknya ruas yang menghubungi v. Karena setiap ruas dihitung dua kali ketika menentukan derajat suatu graf, maka :

Jumlah derajat semua simpul suatu graf (derajat) = dua kali banyaknya ruas graf (size graf).

Jenis-jenis Graf

Graf dapat dikelompokkan berdasarkan ada tidaknya edge nya yang paralel atau loop, jumlah verteksnya, berdasarkan ada tidaknya arah pada edge nya, adatidaknya bobot pada edge nya, atau ada tidaknya hubungan dengan graf yang lain. Berikut ini adalah jenis graf berdasarkan ada tidaknya edge yang paralel atau loop.

1. Graf Sederhana

Graf sederhana adalah graf yang tidak mempunyai edge ganda dan atau loop, loop adalah edge yang menghubungkan sebuah verteks dengan dirinya sendiri).

2. Graf Tak-Sederhana

Graf tak-sederhana adalah graf yang memiliki edges ganda dan atau loop. Graf tak sederhana dapat dibagi dua yaitu:

• Graf Ganda (multigraph), adalah graf yang mengandung edge ganda. Sisi ganda yang menghubungkan sepasang verteks bisa lebih dari dua buah.

• Graf semu (pseudograph), adalah graf yang mempunyi loop, termasuk juga graf yang mempunyai loop dan edge ganda karena itu graf semu lebih umum daripada graf ganda, karena graf semu edge-nya dapat terhubung dengan dirinya sendiri

Selain berdasarkan ada tidaknya edge yang paralel atau loop, graf dapat juga dikelompokkan berdasarkan orientasi arah atau panah.

1. Graf tak-berarah (undirected graph)

Graf tak berarah adalah graf yang edge nya tidak mempunyai orientasi arah atau panah. Pada graf ini, urutan pasangan verteks yang dihubungkan oleh edge tidak diperhatikan. Jadi (vj, vk) = (vk, vj) adalah edge yang sama.

2. Graf Berarah (directed graph atau digraph)

Graf berarah adalah graf yang setiap edge nya memiliki orientasi arah atau panah. Pada graf berarah (vj, vk) ≠ (vk, vj).

Berdasarkan jumlah verteks pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:

1. Graf berhingga ( limited graph ).

Graf berhingga adalah graf yang jumlah verteksnya, n, berhingga.

2. Graf tak-berhingga ( unlimited graph ).

Graf tak-berhingga adalah graf yang jumlah verteksnya, n tidak berhingga.

Terminologi Dasar

Dibawah ini adalah beberapa terminologi (istilah) dasar yang berkaitan dengan graf.

1. Bertetangga (Adjacent)

Dua buah verteks pada graf tak berarah G dikatakan bertetangga bila keduanya terhubung langsung dengan sebuah edge . Dengan kata lain, vi bertetangga dengan vj jika (vi, vj) adalah sebuah edge pada graf G.

2. Bersisian (incident)

Untuk sembarang edge e = ( vj, vk), edge e dikatakan bersisian dengan verteks vj dan verteks vk.

3. Derajat (Degree)

Derajat suatu verteks pada graf tak berarah adalah jumlah edge yang bersisian dengan verteks tersebut.

Pada graf berarah, derajat verteks v dinyatakan dengan din(v) dan dout(v), yang dalam hal ini:

din(v) = derajat masuk (in-degree) = jumlah verteks yang masuk ke verteks v

dout(v) = derajat keluar (out-degree) = jumlah verteks yang keluar dari verteks v
dan d(v) = din(v) + dout(v).

Dalam hal ini d(v) menyatakan derajat verteks.

4. Lintasan (path)

Lintasan yang panjangnya n dari edge awal v0 ke verteks tujuan vn di dalam graf G ialah barisan berselang-seling verteks-verteks dan edge -edge yang berbentuk v0 , e1 , v1 , e2 , v2 ,…, vn-1 , en , vn sedemikian sehingga e1 = ( v0 , v1 ) , e2 = ( v1 , v2 ) , … , en = ( vn-1 , vn ) adalah edge -edge dari graf G. Sebuah lintasan dikatakan lintasan sederhana (simple path) jika semua verteksnya berbeda atau setiap edge yang dilalui hanya satu kali. Lintasan yang berawal dan berakhir pada verteks yang sama disebut lintasan tertutup (closed path) sedangkan lintasan yang memiliki verteks awal dan verteks akhir yang berbeda disebut lintasan terbuka (open path).

5. Graf Berbobot (Weighted Graph)

Graf berbobot adalah graf yang setiap sisinya diberikan sebuah harga (bobot). Bobot pada setiap sisi dapat menyatakan jarak antara dua buah kota, biaya perjalanan, waktu tempuh, ongkos produksi, dan sebagainya.

6. Sirkuit (Circuit) atau Cycle

Dalam satu graf terdapat suatu sirkuit apabila terdapat lintasan (path) yang mempunyai verteks awal dan verteks akhir sama .

Sebuah sirkuit dikatakan sirkuit sederhana (simple circuit) jika sirkuit tersebut tidak memuat/melewati edge yang sama dua kali (setiap edge yang dilalui hanya satu kali). Sebuah sirkuit dikatakan sirkuit dasar (elementary circuit) jika sirkuit tersebut tidak memuat/melewati verteks yang sama dua kali (setiap verteks yang dilalui hanya satu kali, verteks awal dan akhir boleh sama).

Berikut adalah contoh gambar graf :

Graf (d) 3