GRAF
Graf
digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara
objek-objek tersebut.
Definisi Graf
Graf G = (V, E), yang dalam hal ini:
V =
himpunan tidak-kosong dari simpul-simpul (vertices)
= { v1
, v2 , ... , vn }
E =
himpunan sisi (edges) yang menghubungkan sepasang simpul
= {e1 ,
e2 , ... , en }
Jenis-Jenis Graf
Berdasarkan ada tidaknya gelang atau sisi ganda pada
suatu graf, maka graf digolongkan menjadi dua jenis:
1. Graf sederhana (simple graph).
Graf yang tidak
mengandung gelang maupun sisi-ganda dinamakan graf sederhana.
2. Graf tak-sederhana (unsimple-graph).
Graf yang
mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple
graph).
·
Berdasarkan orientasi arah pada sisi, maka secara umum
graf
dibedakan atas 2
jenis:
1. Graf tak-berarah
(undirected graph)
Graf yang sisinya
tidak mempunyai orientasi arah disebut graf tak-berarah.
2. Graf berarah (directed graph atau digraph)
Graf yang setiap
sisinya diberikan orientasi arah disebut sebagai graf berarah.
·
Contoh Terapan Graf
1.
Rangkaian listrik.
2.
Isomer senyawa kimia karbon
3.
Jejaring makanan (Biologi)
4.
Pengujian program
5.
Pemodelan Mesin Jaja (vending Machine)
Terminologi Graf
1. Ketetanggaan (Adjacent)
Dua buah simpul dikatakan bertetangga bila keduanya
terhubung langsung.
2. Bersisian (Incidency)
Untuk sembarang sisi e = (vj, vk) dikatakan e
bersisian dengan simpul vj , atau e bersisian dengan simpul vk
3. Simpul Terpencil (Isolated Vertex)
Simpul terpencil ialah simpul yang tidak mempunyai
sisi yang bersisian dengannya.
4. Graf Kosong (null graph atau empty graph)
Graf yang himpunan sisinya merupakan himpunan kosong
(Nn).
5. Derajat
(Degree)
Derajat suatu simpul adalah jumlah sisi yang bersisian
dengan simpul tersebut.
Notasi: d(v)
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 disebut sirkuit atau siklus. Panjang sirkuit adalah jumlah sisi dalam
sirkuit tersebut.
8. Terhubung
(Connected)
Dua buah simpul v1 dan simpul v2 disebut terhubung
jika terdapat lintasan dari v1 ke v2. G disebut graf terhubung (connected
graph) jika untuk setiap pasang simpul vi dan vj dalam himpunan V terdapat
lintasan dari vike vj. Jika tidak, maka G disebut graf tak-terhubung (disconnected
graph).
· Graf berarah G
dikatakan terhubung jika graf tidak berarahnya terhubung (graf tidak berarah
dari G diperoleh dengan menghilangkan arahnya).
· Dua simpul, u dan v, pada graf berarah G
disebut terhubung kuat (strongly connected) jika terdapat lintasan berarah dari
u ke v dan juga lintasan berarah dari v ke u.
· Jika u dan v
tidak terhubung kuat tetapi terhubung pada graf tidak berarahnya, maka u dan v
dikatakan terhubung lemah (weakly coonected).
9. Upagraf (Subgraph)
dan Komplemen Upagraf
Misalkan G = (V, E) adalah sebuah graf. G1 = (V1, E1)
adalah upagraf (subgraph) dari G jika V1 Í V dan E1 Í E. Komplemen dari
upagraf G1 terhadap graf G adalah graf G2 = (V2, E2) sedemikian sehingga E2 = E
- E1 dan V2 adalah himpunan simpul yang anggota-anggota E2 bersisian dengannya.
10. Upagraf
Rentang (Spanning Subgraph)
Upagraf G1 = (V1, E1) dari G = (V, E) dikatakan
upagraf rentang jika V1 =V (yaitu G1 mengandung semua simpul dari G).
11. Cut-Set
Cut-set dari graf terhubung G adalah himpunan sisi
yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu
menghasilkan dua buah komponen. Terdapat banyak cut-set pada sebuah graf
terhubung.
12. Graf Berbobot (Weighted Graph)
Graf berbobot adalah graf yang setiap sisinya diberi
sebuah harga (bobot).
Beberapa Graf Khusus
a. Graf Lengkap
(Complete Graph)
Graf lengkap ialah graf sederhana yang setiap
simpulnya mempunyai sisi ke semua simpul lainnya. Graf lengkap dengan n buah
simpul dilambangkan dengan Kn. Jumlah sisi pada graf lengkap yang terdiri dari
n buah simpul.
b. Graf
Lingkaran
Graf lingkaran adalah graf sederhana yang setiap
simpulnya berderajat dua. Graf lingkaran dengan n simpul dilambangkan dengan
Cn.adalah n(n – 1)/2.
c. Graf Teratur
(Regular Graphs)
Graf yang setiap simpulnya mempunyai derajat yang sama
disebut graf teratur. Apabila derajat setiap simpul adalah r, maka graf
tersebut disebut sebagai graf teratur derajat r. Jumlah sisi pada graf teratur
adalah nr/2.
d. Graf
Bipartite (Bipartite Graph)
Graf G yang himpunan simpulnya dapat dipisah menjadi
dua himpunan bagian V1 dan V2, sedemikian sehingga setiap sisi pada G
menghubungkan sebuah simpul di V1 ke sebuah simpul di V2 disebut graf bipartit.
Representasi Graf
1. Matriks
Ketetanggaan (adjacency matrix)
A = [aij],
1, jika simpul i dan j
bertetangga
aij = {
0, jika simpul i dan j
tidak bertetanggainyatakan sebagai G(V1, V2).
2. Matriks
Bersisian (incidency matrix)
A = [aij],
1, jika simpul i bersisian
dengan sisi j
aij = {
0, jika simpul i tidak
bersisian dengan sisi j
3. Senarai
Ketetanggaan (adjacency list)
Graf Isomorfik
Diketahui
matriks ketetanggaan (adjacency matrices) dari sebuah graf tidak berarah.
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 korespondensi satu-satu antara simpul-simpul
keduanya dan antara sisi sisi keduaya sedemikian sehingga hubungan kebersisian
tetap terjaga.
· Dengan kata
lain, misalkan sisi e bersisian dengan simpul u dan v di G1, maka sisi e’ yang
berkoresponden di G2 harus bersisian dengan simpul u’ dan v’ yang di G2.
· Dua buah graf
yang isomorfik adalah graf yang sama, kecuali penamaan simpul dan sisinya saja
yang berbeda. Ini benar karena sebuah graf dapat digambarkan dalam banyak cara.
Dari definisi graf isomorfik dapat dikemukakan bahwa
dua buah graf isomorfik memenuhi ketiga syarat berikut [DEO74]:
1. Mempunyai jumlah simpul yang sama.
2. Mempunyai jumlah sisi yang sama
3. Mempunyai jumlah simpul yang sama berderajat
tertentu.
Komentar
Posting Komentar