Rangkaian dalam Teori Graf · Tingkatan 4
Apakah pokok dalam rangkaian?
Pokok ialah rangkaian bersambung tanpa kitar, cukup-cukup tepi untuk menyambung setiap bucu, tanpa lebihan.
Pokok, secara ringkas
Pokok ialah rangkaian bersambung tanpa kitar, tiada cara untuk meninggalkan satu bucu, bergerak di sepanjang tepi, dan tiba semula di tempat asal tanpa mengulang tepi. Oleh sebab itu, terdapat tepat satu laluan antara mana-mana dua bucu.
Satu akibat yang kemas: pokok dengan n bucu sentiasa mempunyai tepat n − 1 tepi, bilangan terkecil yang masih mengekalkan semuanya bersambung.
Mengapa pokok penting
Pokok ialah cara paling jimat untuk menyambung segala-galanya tanpa lebihan, fikirkan jalan paling sedikit yang masih menghubungkan setiap bandar, atau pokok keluarga yang bercabang tanpa gelung. Buang mana-mana satu tepi dan pokok itu berpecah kepada dua bahagian yang terputus; tambah mana-mana satu tepi dan anda mencipta kitar, jadi ia berhenti menjadi pokok.
Sifat 'cukup-cukup, tidak lebih' itulah sebabnya ia berguna.
Mengecamnya (dan kekeliruan biasa)
Untuk mengenali pokok, semak dua perkara serentak: setiap bucu boleh dicapai (bersambung) dan tiada gelung tertutup di mana-mana. Ramai pelajar menganggap mana-mana graf bersambung ialah pokok, tetapi satu kitar sahaja sudah cukup untuk menidakkannya.
Jika anda boleh mengira lebih daripada n − 1 tepi untuk n bucu, tentu ada kitar tersembunyi, jadi ia bukan pokok.
Sumber:DSKP KSSM Mathematics Form 4 and 5 (Versi English)
Soalan lazim
Bagaimana saya menyemak sama ada rangkaian yang diberikan sebenarnya pokok?
Sahkan dua perkara: setiap bucu boleh dicapai daripada bucu lain (ia terhubung), dan tiada laluan yang berpatah balik ke bucu permulaannya tanpa mengulangi tepi (tiada kitaran). Semakan pantas: pokok dengan n bucu sentiasa mempunyai tepat n − 1 tepi.
Bukankah mana-mana rangkaian terhubung sudah pun menjadi pokok?
Tidak, kesilapan biasa ialah menamakan mana-mana rangkaian terhubung sebagai 'pokok' tanpa menyemak kitaran. Rangkaian terhubung masih boleh mengandungi laluan yang berpatah balik ke bucu terdahulu, yang menyebabkan ia tidak layak.
Sentiasa semak kedua-dua kehubungan dan ketiadaan kitaran sebelum menamakan gambar rajah sebagai pokok.
Apakah situasi sebenar yang dimodelkan oleh rangkaian pokok?
Pokok memodelkan bilangan minimum sambungan yang diperlukan untuk menghubungkan setiap titik dalam rangkaian tanpa membazirkan tepi, misalnya, memasang kabel sesingkat mungkin untuk menghubungkan beberapa bangunan, dengan mana-mana tepi tambahan melebihi n − 1 hanya akan mencipta kitaran tanpa menambah sambungan baharu.