Name of the University : Mahatma Gandhi University
Department : Information Technology
Degree : M.Tech
Subject Code/Name : MITNE 205.4/Advanced Topics In Graph Theory
Sem : II
Website : mgu.ac.in
Document Type : Model Question Paper
Download Model/Sample Question Paper :
I : https://www.pdfquestion.in/uploads/mgu.ac.in/5324-1-MITNE%20205_4%20Advanced%20Topics%20in%20Graph%20theory%20-set1.doc
II : https://www.pdfquestion.in/uploads/mgu.ac.in/5324-2-MITNE%20205_4%20Advanced%20Topics%20in%20Graph%20theory%20-set2.doc
Advanced Topics in Graph Theory :
M.TECH. Degree Examination :
Model Question Paper – II :
Second Semester :
Related / Similar Question Paper : MGU M.Tech Modern Digital Communication Question Paper
Branch: Information Technology
Specialization: Network Engineering
MITNE 205.4 Advanced Topics In Graph Theory :
(Elective III)
(Regular – 2011 Admission onwards)
Time: Three hours
Maximum: 100 Marks
1. a)Define planar graph and plane graph. Give examples. Prove that , where n is the number of vertices, is number of edges , is the number of faces and is the number of components of a plane graph . (10 marks)
b)The complete graph of 5 vertices is nonplanar. (15 marks)
OR
2. a)Define geometric dual and combinatorial of a given graph G. Prove that a graph hadual iff it is planar (15 marks)
b) Let G be a simple graph with less than 30 edges. Prove that G has a vertex v such that d(v)=4 (5 marks)
c) Show that the complete graph of 4 vertices is self dual (5 marks)
3. a)Define directed graph.Explain different types of diagraph with examples (5 marks)
b)Prove that ,a graph G is Orientale iff it is connected and has no bridges. (15 marks)
c)Give an example of 2-regular diagraph with 5 vertices (5 marks)
OR
4. a)Prove that every edge in a diagraph belongs either to a connected circuit or a directed cut set (10 marks)
b)Explain Hopcraft and Tarjan algorithm. Illustrate the algorithm, using suitable examples, for Produce a strongly connected orientation (15 marks)
5. a) State and prove Menger’s theorem (15 marks)
b) Prove that maximum flow possible between two vertices a and b in a network is equal to the minimum of the capacitor of all cut-sets w.r.to a and b (10 marks)
OR
6 a) Let f be a flow of network N=(V,A)and let f have value d. If is a cut in N then and . (15 marks)
b) Every circuit has an even number of edges is common with any cut set (10 marks)
7. Prove that for any graph G
a) (10 marks)
b) iff G is bipartite (8 marks)
c) iff G has an odd cycle (7 marks)
OR
8. a) Let G be a nonempty bipartite graph then (20 marks)
b) A map G is 2 face colorable iff it is an Euler graph (5 marks)
M.Tech. Degree Examination :
Model Question Paper – II : Second Semester
Branch : Information Technology
Specialization : Network Engineering
MITNE 205.4 : Advanced Topics In Graph Theory (Elective III) (Regular – 2011 Admission onwards)
Time : Three hours
Maximum : 100 Marks
1. a)Define planar graph and plane graph. Give examples. Prove that n-e+f=k+1 , where n is the number of vertices, e is number of edges , f is the number of faces and k is the number of components of a plane graph G . (10 marks)
b)The complete graph of 5 vertices is nonplanar. (15 marks)
OR
2. a)Define geometric dual and combinatorial of a given graph G. Prove that a graph hadual iff it is planar (15 marks)
b) Let G be a simple graph with less than 30 edges. Prove that G has a vertex v such that
d(v)≤4 (5 marks)
c) Show that the complete graph of 4 vertices is self dual (5 marks)
3. a)Define directed graph.Explain different types of diagraph with examples (5 marks)
b)Prove that ,a graph G is Orientale iff it is connected and has no bridges. (15 marks)
c)Give an example of 2-regular diagraph with 5 vertices (5 marks)
OR
4. a)Prove that every edge in a diagraph belongs either to a connected circuit or a directed cut set (10 marks)
b)Explain Hopcraft and Tarjan algorithm. Illustrate the algorithm, using suitable examples, for Produce a strongly connected orientation (15 marks)
5. a) State and prove Menger’s theorem (15 marks)
b) Prove that maximum flow possible between two vertices a and b in a network is
equal to the minimum of the capacitor of all cut-sets w.r.to a and b (10 marks)
OR
6 b) Every circuit has an even number of edges is common with any cut set (10 marks)
7. b) A map G is 2 face colorable iff it is an Euler graph (5 marks)