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

Download JNTUK (Jawaharlal Nehru Technological University Kakinada (JNTU kakinada)) M.Tech (ME is Master of Engineering) 2020 R19 IT Advanced Graph Theory Model Previous Question Paper

15

[M19 IT 1112]

I M. Tech I Semester (R19) Regular Examinations
ADVANCED GRAPH THEORY
Department of Information Technology
MODEL QUESTION PAPER
TIME: 3 Hrs. Max. Marks: 75 M
Answer ONE Question from EACH UNIT
All questions carry equal marks
*****
CO KL M
UNIT - I
1. a). Analyze the maximum number of edges in a simple graph with n vertices
is n(n-1)/2.
1 4 8
b). Prove that if a graph has exactly two vertices of odd degree, there must be
path joining these two vertices.
1 5 7
OR
2. a). Identify Hamiltonian path as spanning tree 1 3 8
b).
List t some of the properties of tree.
1 4 7

UNIT - II
3. a). Distinguish max-flow min-cut theorem 2 4 7
b). Prove that in any tree, there are at least two pendant vertices 1 5 8
OR
4. a). Compare Fundamental cut set and Fundamental circuit in a graph. 1 4 7
b). List t some types of digraph with suitable example 1 4 8
UNIT - III
5. a). Prove that every connected graph has at least one spanning tree 2 5 8
b). Distinguish Tutte's f- factor theorem with example 2 4 7
OR
6. a). Identify problems in Euler digraph 2 3 8
b).
Distinguish Turen?s with Example.
2 4 7
UNIT - IV
7. a).
Solve the recurrence relation. 6a
n
-7a
n-1
=0, n?1, a
3
=343.
3 3 8
b).
Analyze Traveling Salesman Problem
3 4 7
OR
8. a).
Analyze Greedy algorithm with example
3 4 7
b). Prove that a graph of n vertices is a complete graph if its chromatic
polynomialis P
n
(?) = ? (? ? 1) (? ? 2) ? (? - n + 1)
3 5 8
UNIT - V
9. a). Compare direct paths and cycle 3 4 7
b). Distinguish max flow min cut theorem 3 4 8
OR
10. a). Classify Brooks theorem with example 3 4 8
b). Identify greedy algorithm 3 3 7

FirstRanker.com - FirstRanker's Choice