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
PART-A
(10 x 2 = 20 Marks)
1. Define fundamental numbers for a
complete graph K5.
2. Draw induced sub graph for
V={A,C,D} and complement of the following graph.
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 non-empty 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.
9. Represent the following graph using
successive listing and 2 linear arrays.
10. Define transitive closure of a
digraph with an example.
Part-B
(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 3n-6, where n is the number of vertices in the
graph. (8)
(OR)
b) (i) State and prove theorems
relating fundamental circuits and fundamental cut-sets with respect to a
spanning tree. (8)
(ii) Prove that the number of labeled
trees with n vertices is nn-2 (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 1-11 is
an Equivalence graph. (8)
(OR)
b) (i) Given a connected graph G,
derive the rank of a matrix that defines the graph within 2-isomorphism. (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 cut-set 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 1-isomorphism and 2-isomorphism. (6)
************************
No comments:
Post a Comment