(1) A forest is a simple graph with no cycles. A rooted forest is a forest with a distinguished root for each connected component. (Notice that the connected components are trees and so a rooted forest is just a collection of rooted trees.) A forest∗ is a pair (F, <F ) where <F is a transitive, irreflexive relation on F with the property that for every t ∈ F, the set {x∈F |x<F t}is linearly ordered by<F.
(a) Show that every rooted forest gives rise to a forest∗ in a natural way.
(b) Show that every forest∗ gives rise to a rooted forest in a natural way.
(c) Show that the processes in (a) and (b) are the reverse of each other.
(2) Try to find a definition of tree∗ and prove that there is a similar correspondence between rooted trees and tree∗s.
thank you so much
(a) Show that every rooted forest gives rise to a forest∗ in a natural way.
(b) Show that every forest∗ gives rise to a rooted forest in a natural way.
(c) Show that the processes in (a) and (b) are the reverse of each other.
(2) Try to find a definition of tree∗ and prove that there is a similar correspondence between rooted trees and tree∗s.
thank you so much