Introduction to Graph Theory — DU B.Sc. (Prog) Physical Sciences courses pertaining to Mathematical Sciences Previous Year Question Papers

What is the minimum number of time periods required to schedule all six club meetings so that no student has a conflict? 3. Both parts of a question to be attempted together. 1. (a) Define Degree of a Vertex. Find the Indegree and Outdegree of each Vertex in the following directed graphs. (c) A university needs to schedule introductory meetings for six different student clubs. Some students belong to multiple clubs, so those clubs cannot meet at the same time. 6. (a) Verify the law of conservation of flow at a, c, and d. Find the value of indicated flow and also determine the capacity of the (s, t)-cut defined by Also 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? (b) What is Hamiltonian graph? Is the following graph Hamiltonian, explain. Find Hamiltonian path in the following graph. Also define Eulerian Graph with examples. Give an example of a graph which is Eulerian as well as Hamiltonian. (b) State the Max flow-Min Cut theorem and verify it for the given below graph. (c) Use Dijkstras Algorithm, find the shortest path between the vertices a and g in the following (b) For the given graph, find the number of regions. List all the edges which form the boundary of each region and verify the Euler’s formula. 2. (a) Find the Adjacency matrices A1 and A2 of the graphs G1 and G2 shown below. Find a Permutation matrix P such that A2 = PA1PT. Prove that G1 and G2 are Isomorphic. (c) Define a chromatic number of the graph. Find a coloring which requires the least number of colors for the given graph, hence fmd its chromatic number. (b) Apply Prim’s algorithm to the above given graph in (a) to find the minimum spanning tree and compare results. (b) Solve the following Traveling Salesman Problem. The distances from one city to another city are given in the following table: (c) Apply Bellman’s algorithm to the given digraph, to fmd the length of the shortest path from node 2 to every other vertex. (c) Define a Bipartite graph, hence or otherwise determine whether the following graph is bipartite. Give reasons in support of your answer. 5. (a) Define the Planar graph. Show that K3,3 is not planar. Define a Complete bipartite Graph. Draw K2.3. Is it a Bipartite or a Complete Bipartite Graph? 3. (a) Apply Beliman-Ford algorithm in the digraph given below to find the length of shortest path from vertex s to every other vertex. (b) Solve the Chinese Postman problem for the given weighted graph. (c) Determine whether the given pair of digraphs are isomorphic. 4. (a) Find minimum spanning tree of the following weighted graph using Kruskafs algorithm.