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
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
Tidak ada komentar:
Posting Komentar