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

(b) State and prove Max Flow-Min cut theorem. (c) Five ladies have men fri?nds as shown in the followingt&ble. Lady Me'n Friends Karen Stuart, Paul Mary Philip, Stuart Aurie David, Paul, Roger„ Stuart Pamela , Philip, Paul Lynne Stuart, .Philip, Paul aw a bit;artite graph depicting this situation a way in which each lady can marry a man she knows, or use Hall's Mandage Theorem to explain why no such matching exists. S1:{fuo. of Q, P;per.. : Introduct`ion to Graph : Bachelor ofAIts (Programme) with Mathematics as Major Tlme .' 8 Hours (a) ¥`€i:1:pg:#hiEs9gu¥:;i:: p¥;e:?P inmequately on 1. (a) draw the fonowing graphs and determine how many edges each has: (b) Given the following degree sequences, either conștruct a graph, with such a degree sequence, or explain why this would be impossible. (c) Ixplain the ditference between an Eulerian circui and a Hamiltonian cycle. Is the following grapl Eulerian? Does, there exist an Fulerian, trail? 2" (a) Draw thé pseudograph corresponding to each adjacency matrix: (b) Show that every graph is isomorphic to a subgraph of some camplete graph. Prove that if two graphs are isomorphic, they must contain the same number of triangles. 6. '(a) Define capacity of the (s,t)-cut. Find the capacity of the (s,t)-cut defined'by S = (s, a, b, d) and T= {c, e, I, t) for the given network. It's the weekend and Harry has several ways to spend hiș Friday and Saturday evenings. He can study, read, watch television or go out with the ›oys. Draw a tree that shows 'all possible ways Harry can spend his Friday and Saturday evenings. 5. (a) Define a planar graph and a plane graph. Show that the complete bipartite graph K2,s is planar by diawing an isomorphic plahe graph with straight edges. Also, label the region defined by your plane graph and list the edges that form the boundary of each region. (b) There are ten students who, in the coming semester, will be taking the courses shown in the following table. How many time periods must be allowed in order for these students to take the courses they want without conflicts? Arnold Physics, Mathematics, English Bill Physics, Earth Science, Economics Carol Earth Science, Business Calvin Statistics, Economics Eleanor Mathematics, Business Frederick Physics, Earth Sciencé George Business, Statistics Huber Mathematics, Earth 'Science Ingrid Physics, Water Skiing, Statistics Jacquie Physics, Economics, Water Skiing (c) Draw the line of sight graph G associated with the given net pattern, Is this graph planar. Explain your answer. (c) Apply the first form of Dijkstra's algorithm to find a shortest path from A to E in the graph shown. Label all the vertices. 3. (a) Solve the Chinese postman problem e grape following graph, where the edges of the graph represent the streets and all streets have the same unit length (starting with vertex A). (b) Find the adjacency matrix A of the following graph and also determine the (3,3) arid (1,4) entries of