Pradina Utami Blog's: GRAF

GRAF

Graf adalah sekelompok simpul-simpul (nodes/vertices) V, dan sekelompok sisi (edges) E yang menghubungkan sepasang simpul. Bayangkan simpul-simpul tersebut sebagai lokasi-lokasi, maka himpunan dari simpul-simpul tersebut adalah himpunan lokasi-lokasi yang ada. Dengan analogi ini, maka sisi merepresentasikan jalan yang menghubungkan pasangan lokasi-lokasi tersebut.
Graf juga didefinisikan sebagai himpunan benda-benda yang disebut verteks (node) yang terhubung oleh sisi (atau edge ata u arc). biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan verteks) yang dihubungkan oleh garis-garis (melambangkan sisi).

Jenis-Jenis Graf

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

1. Graf sederhana ( simple graph ).

Graf yang tidak memiliki gelang maupun sisi-ganda.

2. Graf tak-sederhana ( unsimple-graph ).

Graf yang memiliki gelang maupun sisi-ganda. Ada dua macam graf tak-sederhana, yaitu graf ganda (multigraph) dan graf semu (pseudograph). Graf ganda adalah graf yang memiliki sisi ganda, sedangkan graf semu adalah graf yang memiliki gelang.

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

1. Graf berhingga ( limited graph ).

2. Graf tak-berhingga ( unlimited graph ).

Berdasarkan orientasi arah pada sisi maka secara umum graf dapat digolongkan menjadi dua jenis:

1. Graf berarah ( directed graph ).

Graf yang setiap sisinya diberikan orientasi arah. Pada graf berarah, ( vj, vk ) dan ( vk , vj ) menyatakan dua busur yang berbeda, dengan kata lain

( vj ,vk ) ≠ ( vk ,vj )

Untuk busur ( vj ,vk ), simpul vj disebut simpul asal ( initial vertex ) dan untuk simpul vkdisebut simpul terminal

( terminal vertex ).

2. Graf tak-berarah ( undirected graph ).

Graf yang sisinya tidak memiliki orientasi arah. Pada graf tek-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan, dengan kata lain:

( vj ,vk ) = ( vk ,vj ).

Terminologi Dasar

Terdapat beberapa istilah penting yang berkaitan dengan graf. Berikut ini didefinisikan beberapa terminologi yang sering digunakan:

1. Bertetangga ( Adjacent )

Dua buah simpul pada graf tak-berarah G dikatakan bertetangga bila keduanya terhubung langsung dengan sebuah sisi. Dengan kata lain, vj bertetangga dengan vk jika (vj , vk ) adalah sebuah sisi pada graf G.

2. Bersisian ( Incident )

Untuk sembarang sisi e = (vj , vk ), sisi e dikatakan bersisian dengan simpul vj dan simpul vk .

3. Simpul Terpencil ( Isolated Vertex )

Simpul yang tidak mempunyai sisi yang bersisian dengannya. Atau, dapat juga dinyatakan bahwa simpul terpencil adalah simpul yang tidak satupun bertetangga dengan simpul-simpul lainnya.

4. Graf Kosong ( Null atau Empty Graph )

Graf yang himpunan sisinya merupakan himpunan kosong, ditulis sebagai Nn, yang dalam hal inin adalah jumlah simpul.

5. Derajat ( Degree )

Derajat suatu simpul pada graf tak berarah adalah jumlah sisi yang bersisian dengan simpul tersebut.

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

din(v) = derajat masuk (in-degree)

= jumlah simpul yang masuk ke simpul v

dout(v) = derajat masuk (in-degree)

= jumlah simpul yang keluar dari simpul v

dan

d(v) = din(v) + dout(v).

Notasi: d(v) menyatakan derajat simpul.

6. Lintasan ( Path )

Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graf G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v0 , e1 , v1 , e2 , v2 ,…,vn-1,en ,vn sedemikian sehingga e1 = ( v0 , v1 ) ,

e2 = ( v1 , v2 ) , … , en = ( vn-1 , vn ) adalah sisi-sisi dari graf G.

7. Siklus ( Cycle ) atau Sirkuit ( Circuit )

Lintasan yang berawal dan berakhir pada simpul yang sama.

8. Terhubung (connected)

Graf tak-berarah G disebut graf terhubung ( connected graph ) jika untuk setiap pasang simpulvi dan vj di dalam himpunan V terdapat lintasan dari vi ke vj ( yang juga harus berarti ada lintasan dari vi ke vj ). Jika tidak, maka G disebut graf tak-terhubung (disconnected graph ). Sedangkan graf berarah G dikatakan terhubung jika graf tak-berarahnya terhubung (graf tak-berarah dari G diperoleh dengan menghilangkan arahnya).

9. Upagraf ( Subgraph )

Misalkan G = (V,E) adalah sebuah graf. G1 = (V1 , E1) adalah upagraf dari G jika V1 C V dan E1 C E

10. Komplemen Upagraf

Komplemen dari upagaraf G1 terhadap graf G adalah graf G2 = (V2 , E2) sedemikian sehinggaE2 = E – E1 dan V2 adalah himpunan simpul yang anggota – anggota E2 bersisian dengannya.

11. Upagraf Merentang (Spanning Subgraph )

Upagraf G1 = (V1 , E1) dari G = (V, E) dikatakan upagraf merentang jika V1 = V ( yaitu G1mengandung semua simpul dari G ).

12. Cut-set

Cut-set dari graf terhubung G adalah himpunan sisi yang bila dibuang dari G menyebabkan Gtidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen terhubung.

13. Graf Berbobot ( Weighted Graph )

Graf yang setiap sisinya diberi harga (bobot).

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 :

Graf Teratur dengan 3D, 4D dan 5D