Question 1:

(a).

 

(b). No , it is not a connected graph.

(c).

(d). yes , there is one cycle Jimmy , Daisy , Alfred , Ivy.

(e). Vertex daisy has largest in degree which is 2.

(f). Vertex jimmy has largest out degree which is 2.

(g). Vertex William has smallest in degree which is 0.

(h). Vertex Ivy has smallest out degree which is 0.

Question 2:

(a). There are 7 nodes in a graph so there is 6 directed edges. So , maximum number of edges is 7*(6) = 42.

If we consider the graph as undirected graph then maximum number of edges is (7 * (6))/2 = 21.

(b).

If we consider the graph

using Kruskal’s Minimum Spanning Tree Algorithm

The process finishes with the edge EG of length 9, and the minimum spanning tree is found.

(c). The ratio is 42 / 9 = 4.6666667.

(d). Ratio becomes smaller as the number of nodes increases.

 

Question 3:

(a).

(b).

Greatest number of nodes that we have to visit is 11.

Least number of nodes that we have to visit is 1.

Average number of nodes that we have to visit is 6 .

(c).

 

(d). Greatest number of nodes that we have to visit is 12.

Least number of nodes that we have to visit is 1.

Average number of nodes that we would to visit is 7.

(e).

The performance of binary search can be analyzed by reducing the procedure to a binary comparison tree, where the root node is the middle element of the array; the middle element of the lower half is left of the root and the middle element of the upper half is right of the root. The rest of the tree is built in a similar fashion. This model represents binary search; starting from the root node, the left or right subtrees are traversed depending on whether the target value is less or more than the node under consideration, representing the successive elimination of elements. The worst case is {\textstyle \lfloor \log n+1\rfloor }iterations (of the comparison loop), where the {\textstyle \lfloor \rfloor }notation denotes the floor function that rounds its argument down to an integer.

Question 4:

The minimum path cost is 25.