Walk, Trail, Path, Cycle [PDF]

Citation preview

Soalan 2 : Graf a) Carikan maklumat dan menyediakan nota ringkas mengenai 4 jenis graf , iaitu “walk” , “trail”, “path”, dan “cycle”. Bincangkan perbezaan antara graf-graf tersebut.



Definisi WALK  Suatu `walk` dalam graf adalah suatu barisan berhingga dan simpul ( vertex ) dan sisi (edge) secara bergantian yang dimulai dan diakhiri dengan simpul sehingga setiap sisi yang bersisian dengan simpul sebelum dan sesudahnya , dimana sebuah sisi hanya melalui satu kali. TRAIL  Walk yang semua sisi di dalam setiap barisan berbeza disebut `trail`. Trail tertutup adalah suatu trail dengan simpul awal dan simpul akhir yang sama.



Perbezaan  Simpul ( vertex ) dan sisi ( edge ) boleh diulang.



Gambarajah Graf B A



C



F



E



D



CTH: A C D



 Simpul boleh diulangi.  Sisi tidak boleh diulang.



B



F



E



BA



A



CA GA DA FA CTH:F E C



Definisi



G



Perbezaan



EA D



C B



B G



Gambarajah Graf



A