B.TECH - Semester 8 graph theory Question Paper 2013 (apr)
Practice authentic previous year university questions for better exam preparation.
Sample Questions
- Give examples of (a) Graph that is Euler and Hamiltonian
- Give examples of (b) Graph that is Euler but not Hamiltonian.
- Define a planar graph. Show that $K_{5}$ is not a planar graph.
- Prove that a pendent edge in a connected graph $G$ is contained in every spanning tree of $G$.
- Define 1-isomorphic graph and 2-isomorphic graphs.
- Differentiate gate networks from contact networks. $$ (5 \times 4=20 \text { Marks) } $$ (Answer any one question from each Module. Each question carries 20 marks.)
- (a) For a connected graph G prove that the following statements are equivalent.
- (i) $G$ is Eulerian. (ii) The degree of each vertex of $G$ is even. (iii) $G$ is an edge disjoint union of cycles. Hence show that the Konigsberg bridge problem has no solution.
- (b) Prove the following theorems
- (i) Prove that in any tree, there are atleast two pendant vertices. (ii) Show that a Hamiltonian path is a spanning tree.
- (a) Using the algorithm of Kruskal, find the shortest spanning tree in the following graph.
- (b) Which of the following simple graphs have a Hamilton Circuit or if no, a Hamilton Path?
- (c) Explain traveling salesman problem. Express the problem in terms of graph terminology.
- (a) Prove the graphs $K_{5}$, and $K_{3,3}$ are non-planar.
- (b) Find the number of vertices, edges and regions for the following planar graph and verify that Euler's Theorem for connected planar graphs is 10 satisfied.
- (a) How binary relations are closely related to theory of graphs? Explain in detail.
- (b) Explain the steps involved in testing for planarity of graphs. Module - III
- (a) Discuss about the different computer representation of a graph.
- (b) With suitable examples, illustrate the method to find out the number of components or blocks in a given graph. OR
- (a) Explain about fundamental cut set and fundamental circuit in a graph with an example.
- (b) Write an algorithm for finding shortest path between two specified vertices.
- (a) Discuss in detail about different methods used to describe a sequential machine with a suitable example.
- (b) Illustrate the applications of graphs in coding theory. OR
- (a) How do you express a given switching function on the m-cube? Explain with an example.
- (b) For a given n-vertex graph, how do you find the cut set code? Explain with an example. ( $4 \times 20=80$ Marks)