TEORI GRAPH

TEORI GRAPH

Berdasarkan  jumlah simpul , graf dibedakan:

1. Graf berhingga (limited graph)

​​

2. Graf tak-berhingga (unlimited graph)

TERMINOLOGI​ GRAF

1. Bertetangga

​Dua buah simpul dikatakan bertetangga apabila keduasimpul tersebut terhubung langsung oleh suatu simpul ( Simpul dengan simpul ).

Contoh :

​​​

Penjelasan :

1. ​Simpul 1 bertetangga dengan simpul 2

2. ​Simpul 1 bertetangga dengan simpul 3

3. ​Simpul 1 tidak bertetangga dengan simpul 4

4. ​Simpul 2 bertetangga dengan simpul 1

5. ​Simpul 2 bertetangga dengan simpul 3

6. ​Simpul 2 tidak bertetangga dengan simpul 4

7. ​Simpul 3 bertetangga dengan simpul 1

8. ​Simpul 3 bertetangga dengan simpul 2

9. ​Simpul 3 bertetangga dengan simpul 4

10. Simpul 4 tidak bertetangga dengan simpul 1

11. Simpul 4 tidak bertetangga dengan simpul 2

12. Simpul 4 bertetangga dengan simpul 3

2. Bersisian

​Saat busur e dikatakan bersisian apabila busur emenghubungkan 2 simpul ( simpul dengan busur ).

Contoh :

​​​

​

Penjelasan :

1. Busur e1 bersisian dengan simpul A dan simpul B

2. Busur e2 bersisian dengan simpul A dan simpul B

3. Busur e3 bersisian dengan simpul B dan simpul C

4. Busur e4 bersisian dengan simpul B dan simpul C

5. Busur e5 bersisian dengan simpul C dan simpul D

6. Busur e6 bersisian dengan simpul B dan simpul D

7. Busur e7 bersisian dengan simpul A dan simpul D

3. Simpul Terpencil

​Simpul yang tidak memiliki busur.

Contoh :

                                 

Penjelasan :

Simpul 5 dan simpul 6 merupakan simpul terpencil

4. Derajat

​Jumlah sisi yang bersisian dengan simpul tersebut.Derajat disimbolkan dengan d(v).

Contoh :

​​​​

Penjelasan : 

1. Jumlah derajat simpul A ada 3 (busur e1 , busur e2 , busur e7 )

2. Jumlah derajat simpul B ada 5 (busur e1 , busur e2 , busur e3 , busur e4 , busur e6 )

3. Jumlah derajat simpul C ada 3 (busur e3 , busur e4 , busur e5 )

4. Jumlah derajat simpul D ada 3 (busur e5 , busur e6 , busur e7 )

Pada graf berarah :

din(v) ​= jumlah busur yang masuk ke simpul v

dout(v)​= jumlah busur yang keluar dari simpul v

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

contoh :

​​​​

Penjelasan :

1. din(1) = 3 dan dout(1) = 1

2. din(2) = 1 dan dout(3) = 2

3. din(3) = 3 dan dout(3) = 4

4. din(4) = 2 dan dout(3) = 2

jika Jumlah derajat semua simpul pada suatu graf adalah genap, yaitu dua kali  jumlah sisi pada graf tersebut. Dengan kata lain, jika G = (V, E), maka 

contoh :

​​​​

d(v)​ = d(v1) + d(v2) + d(v3) + d(v4)

​ = 2 + 3 + 3 + 2 

​ = 10 

Sehingga  

​​        = 2 ´ jumlah sisi

​​        = 2 ´ 5

JENIS – JENIS GRAF KHUSUS 

1. Graf Sederhana ( Simple Graph )

​Graf sederhana adalah graf yang tidak memiliki arah,tidak mengandung gelang ( loop ) , dan tidak memiliki sisi-ganda.

​​​

2. Graf Ganda

​Tak berarah dan tak mengandung gelang ( loop ).

​​​​

3. Graf Semu

​Graf yang boleh mengadung gelang ( loop ).

​​​​

4. Graf Berarah

​Graf yang memiliki arah , tidak memiliki sisi-gandadan mengandung gelang ( loop )

​​​​

5. Graf Ganda Berarah

​Graf yang memiliki arah , memiliki sisi-ganda danmengandung gelang ( loop ).

​​​​

Tabel 1 Jenis-jenis Graf Khusus

Jenis	Sisi	Sisi gandadibolehkan?	Sisi gelangdibolehkan?
Graf sederhana Graf ganda Graf semu Graf berarah Graf-ganda berarah	Tak-berarah Tak-berarah Tak-berarah Bearah Bearah	Tidak Ya Ya Tidak Ya	Tidak Tidak Ya Ya Ya

6. Graf Lengkap

​Graf sederhana yang setiap simpulnya terhubung oleh1 busur ke semua simpul lainnya , setiap simpulnyabertetangga . Graf lengkap dengan n buah simpuldilambangkan dengan Kn.  

 K1​    K2​             K3​           K4​​    K5    ​          K6

Jumlah derajat = n ( n – 1 ) 

Kn = n ( n – 1 )

​2

7. Graf Lingkaran

​​Graf sederhana yang setiap simpulnya berderajat 2.Graf lingkaran ​dengan n simpul dilambangkan dengan Cn.

​

​Jumlah Busur = Jumlah Simpul

8. Graf Roda (Wn)

​Graf yang diperoleh dengan cara menambahkan 1 simpul.

(Wn) = 2 ( n – 1 )

9. Graf Bipartit

​Graf G yang himpunan simpulnya dapat dipisahmenjadi dua himpunan bagian V1 dan V2,  sedemikiansehingga setiap sisi pada G menghubungkan sebuah simpuldi V1 ke sebuah simpul di V2 disebut graf bipartit dandinyatakan sebagai G(V1, V2). 

​​​ V1​​            V2