a. A graph G(V,E) is called bipartite if we can partition V into two non-overlapping sets...

Transcribed Image Text:

a. A graph G(V,E) is called bipartite if we can partition V into two non-overlapping sets V₁ and V₂ where V = V₁ U V₂ such that every edge in G is between a node in V₁ and a node in V₂. (Note that not every graph is bipartite.) Based on a graph traversal technique, write an algorithm that takes as input an undirected graph G, and returns whether or not G is bipartite. Derive the time complexity of your algorithm. b. Recall the graph coloring problem for Homework Assignment # 2. We say that a graph is k- colorable if the graph nodes can be colored with k colors such that no two adjacent nodes have the same color. Prove that a graph G is 2-colorable if and only if it is bipartite. Then, use your algorithm of part (a) to derive an algorithm for checking if an input graph is 2- colorable and if so, to color the nodes with just two colors. c. Modify the DFS so it can check if an input graph G(V,E) is a tree in O(VI) time. Recall that DFS in general takes O(V+E) time. You need to show your algorithm takes O(VI) time. a. A graph G(V,E) is called bipartite if we can partition V into two non-overlapping sets V₁ and V₂ where V = V₁ U V₂ such that every edge in G is between a node in V₁ and a node in V₂. (Note that not every graph is bipartite.) Based on a graph traversal technique, write an algorithm that takes as input an undirected graph G, and returns whether or not G is bipartite. Derive the time complexity of your algorithm. b. Recall the graph coloring problem for Homework Assignment # 2. We say that a graph is k- colorable if the graph nodes can be colored with k colors such that no two adjacent nodes have the same color. Prove that a graph G is 2-colorable if and only if it is bipartite. Then, use your algorithm of part (a) to derive an algorithm for checking if an input graph is 2- colorable and if so, to color the nodes with just two colors. c. Modify the DFS so it can check if an input graph G(V,E) is a tree in O(VI) time. Recall that DFS in general takes O(V+E) time. You need to show your algorithm takes O(VI) time.