Download JNTUK M-Tech 2020 R19 IT Advanced Graph Theory Model Question Paper

FirstRanker.com

I M. Tech I Semester (R19) Regular Examinations

ADVANCED GRAPH THEORY

--- Content provided by​ FirstRanker.com ---

Department of Information Technology

MODEL QUESTION PAPER

TIME: 3 Hrs. Max. Marks: 75

Answer ONE Question from EACH UNIT

All questions carry equal marks

--- Content provided by FirstRanker.com ---

UNIT -1

1. a). Analyze the maximum number of edges in a simple graph with n vertices is n(n-1)/2. (1 4)
   b). Prove that if a graph has exactly two vertices of odd degree, there must be a path joining these two vertices. (1 5)

OR

1. a). Identify Hamiltonian path as spanning tree (1 3)
   

   --- Content provided by​ FirstRanker.com ---

   b). List some of the properties of tree. (1 4)

UNIT - II

1. a). Distinguish max-flow min-cut theorem (2 4)
   b). Prove that in any tree, there are at least two pendant vertices (1 5)

OR

--- Content provided by​ FirstRanker.com ---

1. a). Compare Fundamental cut set and Fundamental circuit in a graph. (1 4)
   b). List some types of digraph with suitable example (1 4)

UNIT - III

1. a). Prove that every connected graph has at least one spanning tree (2 5)
   b). Distinguish Tutte's f- factor theorem with example (2 4)

--- Content provided by FirstRanker.com ---

OR

1. a). Identify problems in Euler digraph (2 3)
   b). Distinguish Turen’s with Example. (2 4)

UNIT - IV

1. a). Solve the recurrence relation. 6a_n-7a_n-1=0, n>1, a₃=343. (3 3)
   

   --- Content provided by‌ FirstRanker.com ---

   b). Analyze Traveling Salesman Problem (3 4)

OR

1. a). Analyze Greedy algorithm with example (3 4)
   b). Prove that a graph of n vertices is a complete graph if its chromatic polynomial is P_n(?)=?(?-1)(?-2)...(? -n+1) (3 5)

UNIT - V

--- Content provided by‍ FirstRanker.com ---

1. a). Compare direct paths and cycle (3 4)
   b). Distinguish max flow min cut theorem (3 4)

OR

1. a). Classify Brooks theorem with example (3 4)
   b). Identify greedy algorithm (3 3)

--- Content provided by‌ FirstRanker.com ---

FirstRanker.com