Dalam teori graf, pokok ialah graf tidak berarah di mana mana-mana dua bucu disambungkan dengan tepat satu laluan, atau secara bersamaan dengan graf tidak berarah akiklik yang disambungkan. … Hutan poli (atau hutan terarah atau hutan berorientasikan) ialah graf asiklik terarah yang graf tidak terarahnya adalah hutan.
Apakah pokok terarah dan tidak terarah?
Graf tidak berarah tanpa kitaran ialah hutan dan jika ia disambungkan ia dipanggil pokok. Graf terarah ialah hutan (atau pokok) jika apabila semua tepi ditukar kepada tepi tidak terarah ia adalah hutan tidak terarah (atau pokok). Pokok berakar ialah pokok dengan satu bucu ditetapkan sebagai akar.
Mengapa pokok tidak terarah?
Teorem: Graf tidak berarah ialah pokok jika terdapat betul-betul satu laluan mudah antara setiap pasangan bucuBukti: Jika kita mempunyai graf T yang merupakan pokok, maka ia mesti disambungkan tanpa kitaran. Memandangkan T disambungkan, mesti ada sekurang-kurangnya satu laluan mudah antara setiap pasangan bucu.
Apakah yang dimaksudkan dengan pokok terarah?
Pokok terarah ialah graf terarah akiklik Ia mempunyai satu nod dengan tidak darjah 1, manakala semua nod lain mempunyai tidak darjah 1 seperti yang ditunjukkan dalam rajah: Nod yang mempunyai darjah luar 0 ialah dipanggil nod luaran atau nod terminal atau daun. Nod yang mempunyai darjah luar lebih besar daripada atau sama dengan satu dipanggil nod dalaman.
Bagaimanakah anda mengetahui sama ada graf tidak terarah ialah pokok?
Dalam kes graf tidak terarah, kami melakukan tiga langkah:
- Lakukan semakan DFS daripada mana-mana nod untuk memastikan setiap nod mempunyai tepat satu induk. Jika tidak, kembalikan.
- Semak semua nod dilawati. Jika semakan DFS tidak dapat melawati semua nod, kemudian kembali.
- Jika tidak, graf ialah pokok.
