15

16

17

18

19

20

a)

E7131

PART E
Answer any four full questions, each carries10 marks.
List down any four properties of adjacency matrix
Construct an adjancy matrix(X) for the following graph and also mention how
the concept of edge sequenes is described with X*(no need to find X? from X)

Prove the theorem:

If A(G) is an incidence matrix of a connected graph © with ர vertices, the rank of
A(G) is n-1

Describe with examples the usage of incidence matrix to find two graphs (81 and
g2) are isomorphic.

Define cut-set matrix with an example and list down any four properties of cut-
set matrix

If B is a circuit matrix of a connected graph G with e edges and n vertices, then
show that the number of linearly independent rows in B = e-n+/

Draw the flow chart of minimum spanning-tree algorithm.

Find MST from the graph given below by simply applying Kruskal’s procedure.

Write the Dijkstra’s shortest path algorithm (no need to draw flowchart). Apply
this algorithm to find the shortest path between v1 and v6
~ 4

Draw the flowchart of Connectedness and Components algorithm and also apply
this algorithm on any graph (G) with 2 components.

اد ‎೫‏ كد با

Page 3 of 3

(4)
(6)

(4)

(6)
(6)
(4)

(7)
(3)

(10)

(10)