Rangkaian dalam Teori Graf
Pokok
Rangkaian bersambung tanpa kitaran.
| English | Tree |
|---|---|
| Bahasa Melayu | Pokok |
| 中文 | 树 |
Cara ia digunakan
Empat bandar A, B, C dan D yang disambung sebagai A–B, B–C dan B–D membentuk pokok, kerana semuanya bersambung namun tiada kitaran. Pokok dengan n bucu sentiasa mempunyai tepat n − 1 tepi, jadi 4 bandar memerlukan 4 − 1 = 3 jalan.
Di mana ia muncul dalam SPM
Muncul dalam bab Rangkaian dalam Teori Graf (Tingkatan 5). Kertas 2 mungkin meminta anda mengenal pasti atau melukis pokok, atau mencari bilangan tepi paling sedikit yang diperlukan untuk menyambung semua bucu, menggunakan fakta bahawa pokok dengan n bucu mempunyai n − 1 tepi.
Jangan kelirukan dengan
Buka bab: Rangkaian dalam Teori Graf →
Soalan lazim
Bagaimana saya tahu jika sesuatu rangkaian ialah pokok?
Semak dua perkara: rangkaian mesti bersambung, bermaksud anda boleh sampai ke setiap bucu dari mana-mana bucu lain, dan ia mesti tiada kitaran, bermaksud tiada gelung tepi tertutup. Jika kedua-duanya benar, ia pokok, dan ia mempunyai tepat satu tepi kurang daripada bilangan bucunya.
Mengapa pokok dengan n bucu mempunyai n − 1 tepi?
Bermula daripada satu bucu, setiap tepi baharu yang anda tambah membawa masuk tepat satu bucu baharu tanpa membentuk kitaran. Untuk menyambung n bucu secara ini anda memerlukan n − 1 tepi; menambah sebarang tepi lanjut akan mencipta kitaran dan merosakkan pokok.