10

11

೩)

0)

a)

b)

06000CS309122002

State travelling salesman problem.
Consider a weighted graph as below. Find and draw the minimum cost

travelling salesman’s tour for it. Also mention the cost.

1
A ಈ B
Sos ‏کی‎
‎40 22 50
5 20 ற 10 ८

Define the terms: (i) Simple Graph (ii) Finite Graph (iii) Infinite Graph (iv)
Null Graph.

PART ^
Answer all questions, each carries 3 marks.
Define the terms: (i) Vertex Connectivity (ii) Cut Vertex (iii) Separable Graph

If G is a planar graph, then any plane drawing of G divides the plane into
regions, called faces. One of these faces is unbounded, and is called the infinite
face. If fis any face, then the degree of f is the number of edges encountered in
a walk around the boundary of the face f. If all faces have the same degree say
g, then G is face-regular of degree g. Consider a graph with face regular degree
of 5 and 8 vertices, then find the number of edges in the graph.

Prove that “Every cut set in a connected graph G must contain at least one
branch of every spanning tree of G “

State the different metric properties of distance.

PART D
Answer any two full questions, each carries 9 marks.
Define spanning tree. Find and draw two different spanning trees from the

graph given below:

For the given graph below, find any one spanning tree contained in it and
determine the fundamental cut-sets associated with that spanning tree. Then

verify the theorem “With respect to a given spanning tree T, a branch 2 that

(5)

(4)

(3)

(3)

(3)

(3)

(3)

(6)