Page 133 - Buku Teks Digital Mate KSSM T5

Bab 5 Rangkaian dalam Teori Graf

Penyelesaian:
(a) Bucu = 7 (b) Bucu = 7
Tepi = 7 Tepi = 9
Darjah = 2 × Tepi Darjah = 2 × Tepi
= 2 × 7 = 2 × 9
= 14 = 18

Apakah maksud berbilang tepi dan gelung pada graf?

Berbilang tepi

Tepi
• Melibatkan dua bucu. P Q R
• Kaitan antara dua bucu tersebut dinyatakan Bucu
melalui lebih daripada satu tepi.
• Bilangan darjah ialah dua kali bilangan tepi.
S
Berbilang tepi antara T Gelung
Gelung bucu P dengan bucu T

• Melibatkan satu bucu.
5
BAB • Tepi berbentuk lengkung atau bulatan yang berbalik kepada bucu asal.
• Bilangan darjah setiap gelung ialah dua.

Katakan, graf di sebelah ditulis dalam bentuk set pasangan tertib,
e 8
G(V, E), maka, D
V = {A, B, C, D} Berbilang tepi Gelung
} }
E = {(A, B), (A, B), (B, C), (B, C), (C, D), (B, D), (A, D), (D, D)} e 7 e 6 e 5
E = {e , e , e , e , e , e , e , e } e 1 e 4
3
2
4
7
8
5
6
1
Tepi AB yang kedua A C
Tepi AB yang pertama e 2 B e 3
Contoh 3
Rajah di sebelah menunjukkan suatu graf yang mempunyai P Q R
gelung dan berbilang tepi. Nyatakan
(a) V dan n(V)
(b) E dan n(E) S
(c) bilangan darjah. U T

Penyelesaian:
(a) V = {P, Q, R, S, T, U} MEMORI SAYA
n(V) = 6
V = Set bucu (Vertex)
(b) E = {(P, Q), (P, U), (P, U), (Q, R), (Q, U), (R, S), (R, T), (S, S), (S, T), (T, U)}
Saiz sebenar E = Set tepi (Edge)
n(E) = 10
132