1. Consider an (arbitrary) spanning tree T of a graph G. Show how to label each node in Tas 0 or 1 so that whenever arc (i,j) is contained in the tree, nodes i and} have different labels. Using this result, prove that G is bipartite if and only if for every nontree arc (k, I), nodes k and I have different labels. Using this characterization, describe an O(m) algorithm for determining whether a graph is bipartite or not.
2. In an acyclic network G = (N, A) with a specified source node s, let o:(i) denote the number of distinct paths from node s to node i. Give an O( m) algorithm that determines aU) for all i ∈ N. (Hint: Examine nodes in a topological order.)