Anna University Regulation 2013 Computer Science and Engineering (CSE) CS6702 GTA old Question Papers for previous years are provided below. Download link for CSE 7th SEM CS6702 Graph Theory & Applications Previous Year Question Papers are listed down for students to make perfect utilization and score maximum marks with our study materials.
B.E / B.Tech ( Full Time ) DEGREE END SEMESTER EXAMINATIONS, APRIL / MAY 2014
Computer Science and Engineering/ Information Technology
Semester VI
CS 9032 Graph Theory (Regulation 2008)
Time: 3 Hours Answer ALL 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. B
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. / f t
10. Define transitive closure of a digraph with an example.
Part – B (5 x 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 w.r.t a spanning tree. (8)
(ii) Prove that the number of labelled 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.
CS6702 GTA Question Paper5– Download Here
If you require any other notes/study materials, you can comment in the below section.
Related Links
For CS6702 GTA Question Bank/2marks 16marks with answers – Click here
For CS6702 GTA Important Questions/Answer Key – Click here
For CS6702 GTA Lecture Handwritten Notes – Click here
Search Terms
Anna University 7th SEM CSE GTA Question Papers with answers
CS6702 Graph Theory & Applications previous year question papers free download
Anna University CSE GTA old question papers Regulation 2013
CS6702 Question Papers with answers, GTA previous year question bank – CSE 7th Semester