graph acyclicity 1/8Q92 tree edge · back edge 01/1 forward edge:… · cross edge … 3/6 type edge(u,) tree vu u forward An edge (u,v)is a back edge itf oost(u post cross VⅣvlul 2/32021 Xiaojuan CaiGraph acyclicity u v x y w z 1/ 2/ 3/ 4/5 6 7 8 9/ 10/ 11 12 • tree edge: • back edge: • forward edge: • cross edge: type edge(u,v) tree [u [v ]v ]u back [v [u ]u ]v forward [u [v ]v ]u cross [v ]v [u ]u An edge (u,v) is a back edge iff post(u) < post(v) 2/3/2021 Xiaojuan Cai 36