Apakah itu Graf Boleh Dilalui dalam Teori Graf?

Dalam konteks teori graf, graf boleh dilalui ialah graf yang boleh merentasi semua bucu dan tepi. Dalam erti kata lain, ia adalah graf yang membolehkan kita melawati setiap bucu tepat sekali dan kembali ke bucu permulaan.

Graf boleh dilalui juga dikenali sebagai graf bersambung, kerana ia adalah graf di mana semua bucu bersambung antara satu sama lain .

Sebagai contoh, pertimbangkan graf ringkas dengan tiga bucu A, B dan C, di mana terdapat tepi antara A dan B, tepi antara B dan C, dan tepi antara A dan C. Graf ini boleh dilalui kerana kita boleh mulakan di bucu A, ikut tepi ke B dan kemudian ke C, dan kembali ke A.

Sebaliknya, graf dengan dua komponen terputus, seperti dua graf berasingan, tidak boleh dilalui kerana tidak mungkin untuk melawati setiap bucu tepat sekali dan kembali ke puncak permulaan.