13

14

15

16

a)

b)

a)

b)

a)

b)

a)
b)

06000CS309122002

determines a fundamental cut-set S is contained in every fundamental circuit

associated with the chords in S”.

With proper arguments and facts prove the statement, “The edge connectivity
of a graph cannot exceed the degree of the vertex with the smallest degree in 0.
Find the centre, radius and diameter of the tree given below:

a J

Find the geometric dual for the given graph.

How many labelled trees are possible with 4 vertices? Draw eight different
labelled trees with 4 vertices A, 3, C and D.
PART E

Answer any four full questions, each carries 10 marks.
With an example compare the Edge listing and Two Linear Arrays form of

computer representation for graphs.

With a neat flow chart explain the algorithm for determining the connectedness
and components for a graph.

State the different properties of an incidence matrix representation of a graph.
Given below are the adjacency matrix representations of two graphs. Draw the
graph corresponding to each matrix. (Note: Assume suitable vertex name if not

given).

(3)

(6)

(4)

(5)

(4)

(6)

(4)
(6)