Rangkaian dalam Teori Graf · 5.1.3
Subgraf dan pokok dalam rangkaian
Subgraf terbentuk dengan mengekalkan sebahagian atau semua bucu dan sisi daripada graf asal, tanpa mengubah hubungan antaranya. Pokok pula ialah subgraf terhubung istimewa yang tiada gelung tertutup, dengan bilangan sisi tepat satu kurang daripada bilangan bucu.
Murid perlu mengenal pasti ciri ini pada graf yang diberi dan melukis contoh subgraf serta pokok sendiri.
Standard pembelajaran rasmi (5.1.3)
“Mengenal pasti dan melukis subgraf dan pokok.”
Apa maksudnya
Subgraf terbentuk dengan mengekalkan sebahagian atau semua bucu dan sisi daripada graf asal, tanpa mengubah hubungan antaranya. Pokok pula ialah subgraf terhubung istimewa yang tiada gelung tertutup, dengan bilangan sisi tepat satu kurang daripada bilangan bucu.
Murid perlu mengenal pasti ciri ini pada graf yang diberi dan melukis contoh subgraf serta pokok sendiri.
Bagaimana ia diuji
Kertas 1 mungkin menunjukkan gambar rajah dan meminta murid mengenal pasti sama ada ia subgraf atau pokok bagi graf yang diberi. Soalan struktur Kertas 2 boleh meminta murid melukis subgraf tertentu, atau pokok menggunakan bucu yang diberi, berdasarkan gambar rajah rangkaian dalam soalan.
Contoh berjawab
Rajah menunjukkan graf G dengan bucu P, Q, R, S dan sisi PQ, QR, RS, SP dan PR. (a) Lukis satu subgraf bagi G dengan 4 bucu dan 4 sisi.
(b) Lukis satu pokok yang merupakan subgraf bagi G menggunakan keempat-empat bucu.
- Subgraf mengekalkan sebahagian atau semua bucu dan sisi G tanpa mengubah hubungan asal.
- Bagi (a), pilih sisi PQ, QR, RS, SP (buang pepenjuru PR): ini menggunakan keempat-empat bucu dan 4 sisi, membentuk gelung bersisi 4.
- Pokok dengan 4 bucu memerlukan tepat 4 − 1 = 3 sisi, dan mesti tiada gelung tertutup.
- Bagi (b), pilih sisi PQ, QR, RS (buang SP dan PR): ini menghubungkan keempat-empat bucu dalam satu laluan P–Q–R–S dengan 3 sisi dan tiada gelung.
Sumber:DSKP KSSM Mathematics Form 4 and 5 (Versi English)
Soalan lazim
Apakah beza antara subgraf dan pokok?
Subgraf ialah sebarang graf yang terbentuk daripada memilih sebahagian bucu dan sisi daripada graf asal, dengan hubungan yang sama dikekalkan. Pokok pula ialah subgraf istimewa yang terhubung, tiada gelung tertutup, dan mempunyai bilangan sisi tepat satu kurang daripada bilangan bucunya.
Berapakah bilangan sisi yang mesti ada pada pokok dengan n bucu?
Tepat n − 1 sisi. Ini ialah ciri utama pokok: ia mempunyai sisi yang cukup untuk menghubungkan semua n bucu tanpa membentuk sebarang gelung tertutup, jadi membuang mana-mana satu sisi lagi akan memutuskan sambungannya.
Bolehkah sebuah pokok mengandungi semua bucu graf asal?
Boleh. Pokok yang menggunakan setiap bucu graf asal dipanggil pokok merentang, dengan syarat ia kekal terhubung, tiada gelung, dan mempunyai bilangan sisi tepat satu kurang daripada jumlah bucu dalam graf itu.