TI POLITALA MATDIS 1C

A.    Definisi Graf

Secara sederhana graf didefinisikan sebagai kumpulan titik yanag dihubungkan oleh garis. Secara matematis, graf adalah pasangan himpunan (V,E) dimana V adalah himpunan tak kosong yang memiliki elemen disebut simpul (vertices) dan E  adalah kumpulan dari dua elemen subsets V yang disebut busur (edges).

Graf G = (V, E) yang dalam hal ini adalah:

V = Himpunan tidak kosong dari simpul – simpul (vertices)

= {v1, v2, ... , vn}

E = Himpunan sisi (edges) yang menghubungkan sepasang simpul

= {e1, e2, ... , en}

B.     Jenis - jenis Graf

Graf dapat dibedakan dalam beberapa jenis, sebagai berikut:

1.      Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis:

a.       Graf sederhana (simple graph).

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

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

Graf yang mengandung sisi ganda atau gelang dinamakan  graf tak-sederhana (unsimple graph).

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

a.       Graf berhingga (limited graph)

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

b.      Graf tak-berhingga (unlimited graph)

Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf tak-berhingga.

3.      Berdasarkan orientasi arah pada sisi, maka secara umum graf  dibedakan atas 2 jenis:

a.       Graf tak-berarah (undirected graph)

Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Tiga buah graf pada Gambar 2 adalah graf tak-berarah.

b.       Graf berarah (directed graph atau digraph)

Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. 

Keterangan : (a) graf berarah, (b) graf-ganda berarah

Berikut adalah perbedaannya.

Jenis	Sisi	Sisi Ganda	Sisi Gelang
Graf sederhana Graf ganda Graf semu Graf berarah	Tak-berarah Tak-berarah Tak-berarah Bearah Bearah	Tidak Ya Ya Tidak Ya	Tidak Tidak Ya Ya Ya

 

C.   Contoh Penerapan Graf

   Graf digunakan untuk mempresentasikan obje - objek diskrit dan hubungan antara objek - objektersebut.Gambar diatas adalah sebuah graf yang menyatakan peta jaringan jalan raya yang menghubungkan sejumlah kota di Provinsi Jawa Tengah.

Selain gambar diaatas, juga terdapat  beberapa kejadian yang merupakan penerapan dari graf, sebagi berikut.
1.      Rangkaian listrik.

2.  Isomer senyawa kimia karbon

 

D.    Graf Isomorfik

Dua buah graf yang sama tetapi secara geometri berbeda disebut graf yang saling isomorfik. Dua buah graf G1 dan G2 dikatakan isomorfik jika terdapat korespondesi satu - satu antara simpul - simpul keduanya dan antara sisi - sisi keduanya sedemikian sehingga jika sisi e bersisian dengan simpul u dan v di G1, maka sisi e yang berkorespon di G2 juga harus bersisian dengan simpul u dan v di G2.

Dengan kata lain misalkan sisi e bersisian dengan simpul u dan v di G1, maka sisi e yang berkorespondensi di G2 harus bersisian dengan simpul u dan v di G2.

Dua buah graf yang isomorfik adalah graf yang sama kecuali penamaan simpul dan sisinya saja yang berbeda. 

Keterangan :

a.       G1 isomorfik dengan G2

b.      G1 tidak isomorfik dengan G3

Keterangan :

G1 isomorfik dengan G2

Dari definisi graf isomorfik dapat dikemukakan bahwa dua buah graf isomorfik memenuhi ketiga syarat berikut :

1.      Mempunyai jumlah simpul yang sama.

2.      Mempunyai jumlah sisi yang sama.

3.      Mempunyai jumlah simpul yang sama berderajat tertentu.

E.    Graf Planar (Planar Graph) dan Graf Bidang (Plane Graph)

Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi tidak saling memotong disebut sebagai graf planar, jika tidak ia disebut graf tak-planar. 

Contoh:          

    

  Ket: Karena sisi tidak saling berpotongan

   Ket: Karena sisi tidak saling berpotongan

Graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan disebut graf bidang (plane graph). 

Ket: Graf (b) dan (c) adalah graf bidang.

Sisi-sisi pada graf planar membagi bidang menjadi beberapa wilayah (region) atau muka (face). Jumlah wilayah pada graf planar dapat dihitung dengan mudah. Jumlah wilayah memiliki hubungan dengan graf bidang. Hal ini membentu sebuah rumus yaitu:

Rumus Euler:

n – e + f = 2

Keterangan:

f = jumlah wilayah

e = jumlah sisi

n = jumlah simpul

Contoh:

Pada gambar diatas memiliki 6 wilayah yaitu R1,R2,R3,R4,R5, dan R6.

Jadi, e = 11; f = 6; n = 7 maka 7 - 11 + 6 = 2.

F.    TEOREMA KURATOWSKI

Teorema kuratowski adalah teorema untuk menentukan keplanaran suatu graf. Sesuai dengan konsep graf planar yaitu: “Graf G bersifat planar jika dan hanya jika ia tidak mengandung subgraf yang sama dengan salah satu graf kuratowski atau homomorfis dengan salah satunya”

Teorema graf kuratowski memiliki sifat, yaitu:

1.      Kedua graf kuratowski adalah graf teratur.

2.      Kedua graf kuratowski adalah graf non-planar.

3.      Penghapusan sisi atau simpul dari graf kuratowski menyebabkan menjadi graf planar.

G.     Dual Graf

Dual graf dapat dikatakan apabila sebuah graf planar G yang direpresentasikan dalam graf bidang mempunyai graf G yang secara geometris merupakan dual dari graf planar G.