17

18

19

20

Discuss an algorithm for finding the shortest path from a specified vertex to
another specified vertex. Illustrate with example.

©

Pages: 3

Discuss an algorithm for finding the connected components of a graph G with
suitable example.
Discuss an algorithm to find the minimum spanning tree of a graph G with

example.

a) Define the incidence matrix of a graph G.Prove that the rank of an incidence

matrix of a connected graph with n vertices is n-1.
b) Draw the graph represented by the following incidence matrix.

x(G) =

ம்ம்‌
011010
100100
010100
001001

اد ‎ಶೇ‏ 2 با

Page 3 of 3

(10)

(10)

(10)

(6)

(4)