Graf adalah :
¨ Himpunan V (Vertex) yang elemennya disebut simpul (atau point atau node atau titik)
¨ Himpunan E (Edge) yang merupakan pasangan tak urut dari simpul, anggotanya disebut ruas (rusuk atau sisi)
Notasi : G(V,E)
Simpul u dan v disebut berdampingan bila terdapat ruas (u,v).
Graf dapat pula disajikan secara geometrik, simpul disajikan sebagai sebuah titik, sedangkan ruas disajikan sebagai sebuah garis yang menghubungkan 2 simpul.
Contoh 1 :
Graf G(V,E) dengan :
1. V terdiri dari 4 simpul, yaitu simpul A, B, C dan D
2. E terdiri dari 5 ruas, yaitu e1 = (A, B) e2 = (B, C) e3 = (A, D)
e4 = (C, D) e5 = (B, D)
A e3 D
· ·
e1 e5 e4
· ·
B e2 C
Banyak simpul disebut ORDER, banyak ruas disebut SIZE dari graf.
Graf yang lebih umum disebut Multigraf
Contoh 2 :
Graf G(V,E) dengan :
1. V terdiri dari 4 simpul, yaitu simpul A, B, C dan D
2. E terdiri dari 6 ruas, yaitu e1 = (A, C) e2 = (A, A) e3 = (A, D)
e4 = (C, D) e5 = (B, C) e6 = (B, C)
A e2 e3 D
· ·
e1 e4
e5
· ·
B e6 C
Di sini ruas e2 kedua titik ujungnya adalah simpul yang sama, yaitu simpul A, disebut Gelung atau Self-Loop. Sedangkan ruas e5 dan e6 mempunyai titik ujung yang sama, yaitu simpul B dan C, disebut Ruas Berganda atau Ruas Sejajar.
Suatu graf yang tidak mengandung ruas sejajar ataupun self-loop disebut Graf Sederhana atau Simple Graf.
Suatu graf G’(V’,E’) disebut subgraf dari G(V,E), jika V’ himpunan bagian dari V dan E’ himpunan bagian dari E.
Jika E’ mengandung semua ruas dari E yang titik ujungnya di V’, maka G’ disebut subgraf yang direntang oleh V’ (Spanning subgraf).
Contoh :
A e5 D
G · ·
e1 e3 e4
· ·
B e2 C
A D
G’ · · G’ subgraf dari G (namun bukan dibentuk
oleh V’ = {A,B,D})
e1 e3
·
B
G’ subgraf yang dibentuk oleh V’ = (A,B,D)
A e5 D
G’ · ·
e1 e3
· B
mau lebih lengkapnya, download aja dibawah ini :
0 komentar:
Posting Komentar