06000CS309122001

16 a) Draw the flowchart of connectedness and components algorithm. (5)

b) Prove that” If B is a circuit matrix of a connected graph G withe edges andn_ (5)
vertices then rank of B=e-n+1
17 Explain Prim’s algorithm. Using Prim's algorithm construct a minimum (10)

spanning tree starting with node A.

18 a) Adjacency matrix of a graph G is given below. From the given adjacency (6)
matrix construct a pictorial representation of the graph. Also list the properties

of adjacency matrix representation of a graph.

0 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1

b) An undirected graph G has n nodes. its adjacency weight matrix is given by (4)
nxn square matrix whose (1) diagonal elements are 0’s and (ii) non-diagonal
elements are 175, State whether the following statements are TRUE/FALSE.

Justify your answers

Page 4 5