Labs Homeworks |
## HW5## HW5: Due: March 9 (Fri), 11:59:59pmQ1. (10 points) An undirected graph is said to be bipartite if all its vertices can be partitioned into two disjoint subsets X and Y so that every edge connects a vertex in X with a vertex in Y. Design a linear time, i.e., O(|V| + |E|), time algorithm to check if a graph is bipartite or not. Q2. (15 points) Answer the following questions: Q3. (10 points) Describe a linear time algorithm to compute the neighbor degree for each vertex in an undirected graph. The neighbor degree of a node x is defined as the sum of the degree of all of its neighbors. Q4. (20 points) Consider a directed graph that has a weight w(v) on each vertex v. Define the reachability weight of vertex v as follows:
$$r(v) = \max \{ w(u) | u \text{ is reachable from } v \}$$
That is, the reachability weight of v is the largest weight that can be reached from v. Answer the following questions: |

Page last modified on February 28, 2018, at 10:16 PM