Page 142 - Buku Teks Digital Mate KSSM T5

Bab 5 Rangkaian dalam Teori Graf

Contoh 12
Lukis dua pokok berdasarkan graf yang diberikan di bawah.
(a) (b) ZON INFORMASI
Pokok digunakan untuk
menentukan laluan
terpendek dengan syarat
semua bucu dilalui
hanya sekali.
Penyelesaian:

(a) Bucu = 5 (b) Bucu = 6
Tepi = 7 (terlebih 3) Tepi = 8 (terlebih 3)
(i) (ii) (i) (ii)

Contoh 13

Rajah di bawah menunjukkan suatu graf tak terarah dan berpemberat. Lukis satu pokok dengan 5
jumlah nilai pemberat yang minimum. BAB
Q 20 R

25 10 12 17

P 19 T 14 S
Penyelesaian:
Langkah 2
Langkah 1 Langkah 2
• Antara pemberat bernilai 19
Bucu = 5, tepi = 7 dengan 25, pemberat bernilai 19
• 3 tepi perlu dibuang. perlu dikekalkan kerana nilainya
• keluarkan tepi dengan pemberat nilai tertinggi lebih rendah.
( PQ, QR, PT) • Antara pemberat 12, 14 dengan
17, pemberat bernilai 17 perlu
dikeluarkan.
Q R Q R

10 12 17 10 12

P T 14 S P 19 T 14 S
Graf di atas bukan pokok kerana,
• bucu P tidak dikaitkan dengan bucu lain. Graf yang terhasil ialah pokok.
Jumlah pemberat minimum pokok
• tiga tepi, RS, ST dan RT mengaitkan tiga bucu sahaja. = 10 + 12 + 14 + 19 Saiz sebenar
= 55
141