Loyola College M.Sc. Mathematics April 2012 Algorithmic Graph Theory Question Paper PDF Download

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.

 

  1. (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)
  1. (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)

 

  1. (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)

 

  1. (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)

 

  1. (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)

 

Go To Main page

 

 

© Copyright Entrance India - Engineering and Medical Entrance Exams in India | Website Maintained by Firewall Firm - IT Monteur