Dalam teori graf, pohon adalah sebuah graf tak-berarah di mana setiap dua titik dihubungkan oleh tepat satu jalur, atau ekuivalen graf tak-berarah asiklik terhubung. … Polihutan (atau hutan berarah atau hutan berorientasi) adalah graf asiklik berarah yang graf tak-berarah dasarnya adalah hutan.
Apa pohon berarah dan tidak berarah?
Grafik tak berarah tanpa siklus adalah hutan dan jika terhubung disebut pohon. Graf berarah adalah hutan (atau pohon) jika ketika semua sisi diubah menjadi tepi tak berarah, itu adalah hutan (atau pohon) tak berarah. Pohon berakar adalah pohon dengan satu simpul yang ditunjuk sebagai akar.
Mengapa pohon tidak terarah?
Teorema: Graf tak berarah adalah pohon jika terdapat tepat satu jalur sederhana antara setiap pasangan simpulBukti: Jika kita memiliki graf T yang merupakan pohon, maka harus terhubung tanpa siklus. Karena T terhubung, setidaknya harus ada satu jalur sederhana antara setiap pasangan simpul.
Apa yang dimaksud dengan pohon terarah?
Sebuah pohon berarah adalah sebuah graf berarah asiklik Memiliki satu simpul dengan derajat masuk 1, sedangkan semua simpul lainnya memiliki derajat masuk 1 seperti yang ditunjukkan pada gambar: simpul yang memiliki derajat keluar 0 adalah disebut simpul eksternal atau simpul terminal atau daun. Node yang memiliki derajat keluar lebih besar atau sama dengan satu disebut simpul internal.
Bagaimana cara mengetahui graf tak berarah adalah pohon?
Dalam kasus graf tak berarah, kita melakukan tiga langkah:
- Lakukan pemeriksaan DFS dari simpul mana pun untuk memastikan bahwa setiap simpul memiliki tepat satu induk. Jika tidak, kembalikan.
- Periksa apakah semua node dikunjungi. Jika pemeriksaan DFS tidak dapat mengunjungi semua node, maka kembalikan.
- Jika tidak, grafnya adalah pohon.
