LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034
M.Sc. DEGREE EXAMINATION – MATHEMATICS
SECOND SEMESTER – APRIL 2012
MT 2813 – ALGORITHMIC GRAPH THEORY
Date : 24-04-2012 Dept. No. Max. : 100 Marks
Time : 9:00 – 12:00
Answer all questions. Each question carries 20 marks.
- (a) Prove that every nontrivial loopless connected graph has at least two vertices that are
not cut vertices. (5)
(OR)
- Define walk, trail, path, cycle and tree with examples. (5)
- (i) Prove that a connected graph is a tree if and only if every edge is a cut edge.
(ii) State Dijkstra’s algorithm and use it to find the shortest distance between the vertices A and H in the weighted graph given below. (5+10)
(OR)
- (i) Find a Hamiltonian path or a Hamiltonian cycle if it exists in each of the graphs given below. If it does not exist, explain why?
- Prove that an edge e of G is a cut edge of G if and only if e is contained in no cycle of G. (6+9)
- (a) Define the connectivity and edge connectivity of a graph G and give an example of a graph G in which k(G) < k¢ (G) < d (G). (5)
(OR)
(b) Prove that K5 is non-planar. (5)
(c) Define Eulerian graph. State and prove a necessary and sufficient condition for a graph to be Eulerian. (15)
(OR)
- Explain Chinese Postman problem. Use Fleury’s algorithm to find the Euler tour for the following graph.
(15)
- (a) Define and obtain a minimal vertex separator for b and g.
(5)
(OR)
(b) State the Lexicographic breadth first search algorithm. (5)
(c) Let G be an undirected graph. Then prove that the following statements are equivalent.
(i) G is triangulated.
(ii) G is the intersection graph of a family of subtrees of a tree.
(iii) There is a tree T whose vertex set is the set of maximal cliques of a graph G such that each induced subgraph: v ε V is connected, where Kv consists of those maximal cliques which contain v. . (15)
(OR)
- (i) Prove that a family of subtrees of a tree satisfies the Helly property.
(ii) Let G be an undirected graph. Then prove that the following statements are equivalent.
(1) G is triangulated.
(2) Every minimal vertex separator induces a complete subgraph of G. (6+9)
- (a) Let G be a split graph with the vertex set partitioned into a stable set S and a clique K. If |S| = α(G) and |K| = ω(G) – 1, then prove that there exists an x ε S such that K +{x} is a clique. (5)
(OR)
(b) Define a permutation graph. Draw the permutation graph corresponding to the permutation [9, 7, 1, 5, 2, 6, 3, 4, 8]. (5)
(c) Let G be an undirected graph with degree sequence d1 ≥ d2 ≥ … ≥ dn and let m = max {i : di ≥ i – 1}. Then prove that G is a split graph if and only if . (15)
(OR)
(d) (i) Prove that an undirected graph G is a permutation graph if and only if G and are comparability graphs.
(ii) Obtain the permutation from the following transitive orientations of G and.
(8+7)
- (a) State the depth-first search algorithm. (5)
(OR)
(b) Obtain an interval representation for the following interval graph.
(5)
(c) State the breadth-first search algorithm and simulate it on the following graph by
selecting the vertex a.
(OR)
(d) Let G be an undirected graph. Then prove that the following statements are
equivalent.
(1) G is an interval graph
(2) G contains no chordless 4-cycle and its complement is comparability
graph.
(3) The maximal cliques can be linearly ordered such that for every vertex v of
G the maximal cliques containing v occurs consecutively. (15)
Latest Govt Job & Exam Updates: