Graph Theory — DU B.Sc. (Hons.) Mathematics Previous Year Question Papers

Type of Paper, : DSE Parts of each question to be attempted together. (a) (i) Draw a graph with 5 vertices and as many edges as possible. How many edges does your graph contain? What is the name of this graph and how is it denoted? (ii) Does there exist a graph G with 28 edges and 12 vertices, each of degree 3 or 4. Justify your answer. 4.5,3 b) (i) Define sub-graph of a graph. Draw pictures of the subgraphs Gl{e), Glív} and Glu} of the following graph G: (it) What is bipartite graph ? Determine whether: graph given below is bipartite. Give the bipartition sets or explain why the graph is not bipartite : 4,3.5 (c) (i) Draw all non-isomorphic graphs for n = 3 vertices. Give the degree sequence of each graph. (i) Solve the Chinese Postman Problem for the graph below: 4,3.5 (a) Define Eulerian graph and Hamiltonian graph. Consider the graph given below. Is it Hamiltonian ? If no, explain your answers, if yes find a Hamiltonian cycle. Also check whether the graph is Eulerian or not : 7.5 (b) Define adjacency matrix of a graph. Find the adjacency matrices Ay and Az of the graphs G, and Gz shown below. Find a permutation matrix P such that Az = PA, PT: 7.5 (c) Apply the Dijkstra's Algorithm to. find a shortest path from A tọ Z in the graph shown. Label all vertices and write steps : 7.5 3. (a) Apply the Bellman-Ford algorithm to find the shortest distance from v, to all other vertices in the following Weighted Digraph : 7.5 (b) When are two Digraphs said to be isomorphic ? Are the following Digraphs Gy and Go isomorphic? Explain your answer : 7.5 The construction of a certain part in an automobile engine involves four activities: pouring the mold, calibration, polishing and inspection. The mold is poured first; calibration must occur before inspection. Pouring the mold takes 8 units of time, calibration takes 3 units, polishing takes 6. units for an uncalibrated product and 8 units for a calibrated one, and inspection takes 2 units of time for a polished product and 3 units for an unpolished one : (1) What type of scheduling problem is this (type I or II) ? Why ? (ii). What is the shortest time required for this job. ? Describe the critical path.. 4. (a) (1) Define tree and find the number of spanning trees in K2,2: (i) A connected graph with n vertices is a tree if and only if it has n- 1 edges. (b) Find a minimum spanning tree for the graph tising Kruskal algorithm. Give the weight of your minimum tree and show your steps : 7.5 (c) (1) Find a Hamiltonian cycle of lowest weight. What is the weight ? : (ii) By removing vertex E, find a lower bound for the weight of any Hamiltonian cycle. (iii) By removing vertex G, find a lower bound for the weight of any Hamiltonian cycle. 5. (a) (i) Define cut-vertex of a Graph G and find all the cut-vertices of the graph G given below: (ii) Draw the induced graph by deleting all the cut-vertices. 4.5,3