Page 96 - Trends in Science and Technology fo Sustainable Living

Trends in Science and Technology 57
for Sustainable Living

banyaknya titik G, yaitu VG
() , yang dinotasikan dengan n(G).
Ukuran G adalah banyaknya sisi G, yaitu E ()G , yang dinotasikan
dengan m(G). Sebagai ilustrasi, berikut ini diberikan contoh graf.

Gambar 3. Contoh Graf G
Graf G pada Gambar 3 mempunyai himpunan titik
v
V ( )G = { 1 ,v 2 ,v 3 ,v 4 ,v 5 ,v 6 } dan himpunan sisi
e
E ( )G = { 1 ,e 2 ,e 3 ,e 4 ,e 5 ,e 6 ,e 7 } . Adapun orde G adalah n(G) = 6 dan
ukuran G adalah m(G) = 7.
Graf G disebut graf trivial jika berorde satu, namun jika
berorde lebih dari satu disebut graf non-trivial. Misalkan u dan v
adalah sepasang titik di G dengan e = uv adalah suatu sisi di G.
Titik u dan v dikatakan bertetangga jika uv ∈ G , sedangkan sisi e
dikatakan terkait dengan titik u dan v. Dua titik yang terkait dengan
satu sisi yang sama disebut titik ujung sisi tersebut. Adapun dua
sisi yang terkait dengan satu titik yang sama disebut bertetangga.
Sebagai contoh, perhatikan graf G pada Gambar 3. Terlihat bahwa
titik v bertetangga dengan titik v . Adapun sisi e = v v terkait
4 5 5 4 5
dengan titik v dan v sehingga kedua titik tersebut dikatakan
4 5
sebagai titik ujung dari sisi e . Sisi e dan e adalah contoh sisi yang
5 1 2
bertetangga karena terkait dengan titik yang sama, yaitu titik v .
2
Sisi yang mempunyai titik ujung yang sama disebut loop.
Adapun sisi ganda adalah dua atau lebih sisi yang titik-titik
ujungnya sama. Suatu graf dikatakan sederhana jika tidak memuat
loop atau sisi ganda. Sebagai contoh, perhatikan Gambar 3. Graf