Anna University Questions  CS9032 Graph Theory April May 2014, Computer Science and Engineering (CSE), Sixth semester, regulation 2008
Exam

B.E/B.Tech. (Full
Time) DEGREE END SEMESTER EXAMINATIONS

Academic
Year

April May 2014

Subject
Code

CS9032 
Subject
Name

Graph Theory 
Branch

Computer Science and Engineering

Semester

Sixth Semester

Regulation

2008

B.E
/ B.Tech. (Full Time) DEGREE END SEMESTER EXAMINATIONS, APRIL / MAY 2014
Computer Science
and Engineering
Sixth Semester
CS9032
GRAPH THEORY
(Regulations 2008)
Time : 3 Hours Answer A L L Questions Max. Marks 100
PARTA
(10 x 2 = 20 Marks)
1. Define fundamental numbers for a
complete graph K_{5}.
3. Show that a Hamiltonian path is a
spanning tree.
4. State Max flow min cut theorem and
prove it through an example.
5. Given the adjacency matrix of a
connected graph, how do you determine the diameter of the graph.
6. Complete matching is present in a
tree  Argue on this statement.
7. Prove that nonempty intersection
of two fundamental circuits in a graph is always a path.
8. State how adjacency matrix
representation of a graph helps in quickly checking if the graph is connected
or not.
10. Define transitive closure of a
digraph with an example.
PartB
(5* 16 = 80 Marks)
11. (i) If the distance d(x,y) between
two vertices x and y in a graph is defined to be the length of the shortest
path connecting them, then prove that the distance function is a metric. (4)
(ii) In a complete graph having odd
number of vertices, how many edge disjoint Hamiltonian circuits exist? Prove.
(6)
(iii) State and prove two theorems to
check if a connected graph G is Eulerian. (6)
12. a) (i) Establish and prove the
relation between vertex connectivity, edge connectivity and number of vertices
and edges. (8)
(ii) Prove that the largest number of
edges in a planar graph is 3n6, where n is the number of vertices in the
graph. (8)
(OR)
b) (i) State and prove theorems
relating fundamental circuits and fundamental cutsets with respect to a
spanning tree. (8)
(ii) Prove that the number of labeled
trees with n vertices is n^{n2} (8)
13. a) (i) In a network as shown
below, during propagation of worms, protection strategy need to be adopted
against the attack. Derive the optimal number of nodes where the defense
strategy can be deployed using Boolean arithmetic. (8)
(ii) Show that digraph representing
the relation " congruent mod 3 " on a set of finite integers 111 is
an Equivalence graph. (8)
(OR)
b) (i) Given a connected graph G,
derive the rank of a matrix that defines the graph within 2isomorphism. (8)
(ii) Derive the chromatic polynomial
for the given graph and use that to find information on chromatic number of the
graph. (8)
14. a) (i) Write down the algorithm to
find all cycles in a digraph using exhaustive search method and state the
precautions to be taken. (10)
(ii) Prove that an Euler graph cannot
have a cutset with odd number of edges. (6)
(OR)
b) (i) Sketch the algorithm to find
cut vertices and bridges in a graph. (10)
(ii) Prove that a spanning tree T of a
given weighted connected graph G, is a shortest spanning tree of G if and only
there exists no other spanning tree at a distance of one from T whose weight is
smaller than that of T. (6)
15. a) (i) Explain the algorithm to
find the shortest path from a given source vertex to any vertex in a graph with
an example. (10)
(ii) Explain the steps involved in
testing for planarity of graphs. (6)
(OR)
b) (i) Illustrate the search algorithm
that can be employed to find the components or blocks in a graph, with an
example. (10)
(ii) Define graph isomorphism and
characterize graphs possessing 1isomorphism and 2isomorphism. (6)
************************
No comments:
Post a comment