Objective: To get familiar with and practice Graphs related algorithms.

You must solve all the questions. Submit with your solutions a cover page where you are

expected to specify for each question the names of students with whom you discussed. In

addition to the complexity analysis parts, submit your programs, your test data and your

results.

Let $G(V,E)$ be a graph whose vertices are the integers $1$ through $8,$ and let the adjacency

list of each vertex be given by the table below:

Assume that, in a traversal of $G,$ the adjacent vertices of a given vertex are returned in the

same order as they are listed in the above table. Show all the steps of your work

$(15$ points$)$ Is G connected? If yes, determine and write down the minimum list of edges

to remove from E such that the graph becomes no longer connected. If no$,$ determine

and write down the minimum list of edges to add to E such that the graph becomes

connected.

$(15$ points$)$ Does G contain a cycle? Explain your answer. $($Hint: try to find topological

order$)(15$ points$)$ Is G a tree? If yes explain your answer. If no$,$ then find a spanning tree of

G$.$

$(25$ points$)$ Determine the shortest paths between every pair of vertices in G

Produce an undirected version of $G,$ that is there is an edge between two vertices in

the undirected version of $G$ if there is at least on edge between the same two vertices in

the directed version of $G.$ Randomly assign to each edge in the undirected $G$ a weight

from the sequence $1$ to $10$ such that every value is assigned to at least two edges.

$($a$)(30)$ Find minimum spanning tree of $G$ using three different algorithms

$($b$)(30)$ Find shortest paths between all pairs of edges in G$,$ use any algorithm you

prefer.