Question $2(4$ marks$)$

A $2-$colouring of an undirected graph with $\backslash ($ n $\backslash )$ vertices and $\backslash ($ m $\backslash )$ edges is the assignment of one of two colours $($e$.$g$.,$ black or white$)$ to each vertex of the graph so that no two adjacent nodes have the same colour. So$,$ if there is an edge $\backslash (($u ; v$)\backslash )$ in the graph, either node $\backslash ($ u $\backslash )$ is black and $\backslash ($ v $\backslash )$ is white, or vice versa. Give an $\backslash (\backslash$mathrm$\{$O$\}(\backslash$mathrm$\{$n$\}+\backslash$mathrm$\{$m$\})\backslash )$ time algorithm to a $2-$colour graph, or determine that no such colouring exists and justify the running time. For this problem, you are not allowed to assume the existence of any "black$-$box" algorithms. You may write a pseudocode instead of a full detailed algorithm.

Question $3(2$ marks$)$

Consider the following strategy for finding a shortest path from vertex start to vertex goal in a given connected graph:

$1.$ Initialize path to start

$2.$ Initialize VisitedVertices to $\backslash \{$start$\backslash \}$

$3.$ If start $=$ goal, return path and exit. Otherwise, continue

$4.$ Find the edge $($start$,$ v$)$ of minimum weight such that $\backslash ($ v $\backslash )$ is adjacent to start and $\backslash ($ v $\backslash )$ is not in VisitedVertices.

$5.$ Add $\backslash ($ v $\backslash )$ to path.

$6.$ Add v to VisitedVertices.

$7.$ Set start equal to $\backslash ($ v $\backslash )$ and go to step $3$

Does this strategy always find a shortest path from the start to goal? Either explain intuitively why it works or give a counter example

Question $4(2$ marks$)$

Show the execution of Dijkstra's shortest path algorithm on the following graph starting from vertex $0.$ Copy and paste the information below into your assignment document and complete the following table, Dhow the length of the best paths found so far for each vertex after each relaxation step. The first line in the table is filled out for you.

Next Vertex Tentative Distance from Start Vertex Edge Connecting Next Vertex to Cloud $12345680812$ oo oo oo oo oo oo

I will be awarded full marks if you adequately answer the questions addressed. You will be awarded partial marks if your response demonstrates:

Application of the major and alternative approaches, methods, or algorithms to solve the problem.

Evidence of appropriate logic.

Evidence of correct computational skills and data structures.

Inclusion of appropriate comments or explanations.