E
b)
15 a)
b)
16 a)
b)
17 a)
b)
18 a)
b)
19 a)
b)

௩5905 Pages: 4

connectivity
Define spanning tree. Show that the edges forming a spanning tree in a planar (5)
graph G correspond to the edges forming a set of chords in the dual G*

PARTE

Answer any four full questions, each carries 10 marks.

Draw the flow chart of spanning tree algorithm and also clearly mark the five (6)

conditions to be tested in connection with the spanning tree construction in the

flowchart

Obtain a cut-set matrix for the following graph: (4)
< |>

Draw the flowchart to determine the components of a graph. (6)

Define adjacency matrix and construct a graph from the following adjacency (4)
matrix:

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

Write edge listing and successor listing methods used in computer representation (4)
of graphs.

Two graphs ೮1 and G2 are isomorphic if and only if their incidence matrices (6)
(೮1) and A(G2) differ only by permutations of rows and columns

Write the Dijkstra's Shortest Path Algorithm and apply this algorithm to find the (6)
shortest path between a and z

Let A and B be, respectively, the circuit matrix and incidence matrix of a self- (4)
loop-free graph G. Prove that A x B'= 0 (mod 2)

Define cut-set matrix and list down any four properties of cut-set matrix (5)
Apply Kruskal’s procedure to find the minimum spanning tree from the (5)

Page 3 of 4