$.$ Use Kruskal$$s algorithm to find the minimum spanning tree of the

following weighted graph.

s

a

b

c

d

e

f

g

$8$

$4$

$7$

$3$

$5$

$2$

$4$

$3$

$5$

$5$

$8$

$4$

$7$

$2$

$3$

$2.$ Use Prim$$s algorithm to find the minimum spanning tree of the graph

in the previous question.

$3.$ Use Dijkstra$$s algorithm to find the shortest path from node s to node

g in the following weighted, undirected graph:

$1$

s

a

b

c

d

e

f

g

$7$

$9$

$5$

$2$

$4$

$4$

$5$

$8$

$6$

$6$

$2$

$4$

$7$

$3$

$1$

$4.$ Use Dijkstra$$s algorithm to find the shortest path from node s to node

g in the following weighted, directed graph:

s

a

b

c

d

e

f

g

$9$

$7$

$2$

$5$

$4$

$4$

$8$

$5$

$5$

$3$

$4$

$2$

$3$

$7$

$1$

$5.$ Use the Bellman$-$Ford algorithm to find the shortest path from node

s to node g in the following graph:

$2$

s

a

b

c

d

e

f

g

$9$

$7$

$-2$

$5$

$-1$

$-4$

$-2$

$5$

$5$

$3$

$4$

$2$

$-3$

$7$

$1$

$6.$ We usually define a graph as a collection of vertices plus at most one

edge between any two vertices. In other words, a graph is described by

a set V $($vertices$)$ and a subset of the set of all two$-$element subsets of

V $.$ If we allow more than one edge between any two vertices, we have

what is known as a multigraph. An Euler path in a graph or multigraph

G is a path which uses each edge in the graph exactly once. An Euler

circuit is an Euler path that starts and ends at the same vertex.

Consider the following graph, and try to find a path $($starting and

ending at any vertices$)$ which uses each edge exactly once $($you do not

need to submit this, just try it in order to follow the discussion$).$