E E1199 Pages: 5

b) Prove that two graphs G1 and G2 are isomorphic if and only if their incidence
matrices A(G1) and A(G2) differ only by permutations of rows and columns.
c) Give Dijkstra’s algorithm to find shortest path between a vertex pair. Use it to

find shortest path between A and G.

16 a) Prove that if B is a circuit matrix of a connected graph G with n vertices and ९
edges, then rank of B is e-n+1.
b) How will you get fundamental circuit matrix from a circuit matrix. Derive the
rank of a fundamental circuit matrix.
c) Explain successor listing and incidence matrix methods used in computer
representation of a graph?
17 a) Prove that the rank of cut set matrix C(G) is equal to rank of the incidence matrix
A(G), which equals the rank of the graph G.
b) Define path matrix. What is the disadvantage of path matrix compared to other
matrices.
c) Find a minimum spanning tree of the following graph. Also give its rank and

nullity.

Page 4 5