Wednesday, March 9, 2016

CS9032 - Graph Theory - April May 2014

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

Academic Year
April May 2014
Subject Code


Subject Name

Graph Theory

Computer Science and Engineering
Sixth Semester

Computer Science and Engineering
Sixth Semester
(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)
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)
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)
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)
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)


Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents

data recovery