$(20$ points$)$ Consider the following graph.

a$.(5$ points$)$ Write down the adjacency matrix and adjacency lists specifying this graph. $($Assume that the

matrix rows and columns and vertices in the adjacency lists follow in the alphabetical order of the vertex

labels.$)$

b$.(15$ points$)$ Starting at vertex a and resolving ties by the vertex alphabetical order, traverse the graph by

depth$-$first search and construct the corresponding depth$-$first search tree. Give the order in which the

vertices were reached for the first time $($pushed onto the traversal stack$)$ and the order in which the vertices

became dead ends $($popped off the stack$).$

$(15$ points$)$ Traverse the graph of Problem $4$ by breadth$-$first search and construct the corresponding

breadth$-$first search tree. Start the traversal at vertex a and resolve ties by the vertex alphabetical order.

$(15$ points$)$ 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 $($j$)$ is bipartite while graph $($ii$)$ is not.

$(1)$

$($ii$)$

Design a DFS$-$based algorithm for checking whether a graph is bipartite.

Function: ismbipartite$($graph$)$

$(10$ points, bonus$)$ Design a BFS$-$based algorithm for checking whether a graph is bipartite.