8. A graph is said to be bipartite if all its vertices can be partitioned into...

 

Transcribed Image Text:

8. A 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. (One can also say that a graph is bipartite if its vertices can be colored in two colors so that every edge has its vertices colored in different colors; such graphs are also called 2-colorable.) For example, graph (i) is bipartite while graph (ii) is not. (x1) (X3) 888 ( (i) (Y2) (ii) a. Design a DFS-based algorithm for checking whether a graph is bipartite. b. Design a BFS-based algorithm for checking whether a graph is bipartite. 8. A 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. (One can also say that a graph is bipartite if its vertices can be colored in two colors so that every edge has its vertices colored in different colors; such graphs are also called 2-colorable.) For example, graph (i) is bipartite while graph (ii) is not. (x1) (X3) 888 ( (i) (Y2) (ii) a. Design a DFS-based algorithm for checking whether a graph is bipartite. b. Design a BFS-based algorithm for checking whether a graph is bipartite.