(a) Writeup Prove Theorem 1 Using Theorem 1, describe an algorithm in words to check bipartiteness and analyze its run time. b da di Figure 1: Example 1 b2 da Figure 2: Example 2 Problem 1 Is Graph...

(a) Writeup

Prove Theorem 1

Using Theorem 1, describe an algorithm in words to check bipartiteness and analyze its run time.

Extracted text: b da di Figure 1: Example 1 b2 da Figure 2: Example 2


Extracted text: Problem 1 Is Graph Bipartite? There is an undirected graph with n nodes, where each node is numbered between 0 and n- 1. You are given a 2D array graph, where graphlu] is an array of nodes that node u is adjacent to. More formally, for each v in graphlu), there is an undirected edge between node u and node v. The graph has the following properties: • There are no self-edges (graphlu] does not contain u). There are no parallel edges (graphlu] does not contain duplicate values). • If v is in graph[u), then u is in graph[u} (the graph is undirected). • The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them. A graph is bipartite if the nodes can be partitioned into two disjoint sets A and B such that every edge in the graph connects a node in set A and a node in set B. There are other equivalent definitions of a bipartite graph. A graph is bipartite if and only if it has no odd length cycle, i.e., no cycle in the graph has an odd mumber of edges. Note that if a graph has no cycles it is bipartite (hence trees are bipartite graphs). It is an interesting exercise for you to show that the above two definitions are equivalent (highly recommended if you want to get a taste of graph theory). But that is not the goal of this exercise. Using the odd cycle definition one can use DFS or BFS to elegantly check whether a graph is bipartite in linear time, ie., O(m + n) time. Such solutions are discussed in leetcode (note that some of these may not be fully correct). This is also not the goal of this exercise. accepted and will receive O points. The goal of this exercise is to explore yet another approach to check bipartiteness and is based on the following ides. You have to argue that the idea is correct (as mentioned below) and implement the idea as an algorithm that checks for bipartiteness of a graph. Let G = (V,E) be the input graph that you want to check for bipartiteness. We first transform G into a new graph G' = (V', E') as follows. For each esch node v e V, construct two nodes v1, v2 € V' and for each edge (u, v) € E, create two edges (u1, 12) and (u2, v1) in E'. This completes the description of constructing G' from G. See Figure 1 for an illustration. The idea of this construction is that we reduce the problem of checking bipartiteness of G to checking the number of connected components of G as stated in the following theorem. you give such a solution, this will not be Theorem 1 Let C be the mumber of connected components in G. Then the mumber of connected components in G' is 20 if and only if the graph G is bipartite. Your first goal is to give a proof of the above theorem (soe the submissions instruetions below). To get an idea of why the above theorem might be true, see the two examples given in Figures 1 and 2. The graph in Example 1 is bipartite (no cycle) and the number of connected components is 1; it is 2 in G'. The graph in Example 2 is not bipartite (odd cycle of length 3) and the number of connected components is 1; it is 1 also in G'. Your second goal is to use the theorem above to give an efficient algorithm for checking bipartiteness.