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

Nainc o.f the Course : GRAPH TIREORY : B.Sc. a-Ions.) Computer Scicncc (NI]P- (For admissions of 2022 onwards) - (c) Attc]npt any four questions from Section-B. (d) Parts of a question should be attempted together. Q1 a) What is Handshaking theorem? Find the number of edges of graph has 8 vertices with 5 What is Path matrix? Find the path matrix for the vertex v3 and v6 of the graph G1 5 c) What is complement of graph? Find the complement of the graph, G = (V, E), where, 5 d) Find the number of faces and verify the graph satisfies planar condition or not for a 5 connected planar graph has 12 vertices and 18 edges. How many simple graphs is possible for 4 vertices in the graph? Find the isomorphic 5 class for graph having 4 vertices and draw all of it. Determine whether graph exists or not for the following degree sequence: (i) 4, 3, 3, 2, 5 Q2 a) Find the union, intersection and ring sum of the graphs Gz and G3 7 b) What is dual graph? Find the dual graph and chromatic number of the graph G+ 8 Q3 a) Find incidence matrix, in-degree, out-degree, in-neighbor and out-neighbor of the graph 7 b) Suppose that a new company has five employees: Zamora, Agraharam, Smith, Chou, 8 and Macintyre. Each employee will assume one of six responsibilities: planning, publicity, sales, marketing, development, and industry relations. Each employee is capable of doing one or more of these jobs: Zamora could do planning, sales, marketing, or industry relations; Agraharam could do planning or development; Smith could do publicity, sales, or industry relations; Chou could do planning, sales, or industry relations; and Macintyre could do planning, publicity, sales, or industry relations. Give the solution for the following query: i) Model the capabilities of these employees using a bipartite graph. ii) Find an assignment of responsibilities such that each employee is assigned one responsibility. iii) Is it a complete matching? iv). Is it a maximum matching? Q4 (a) What is distance, eccentricity, radius, diameter and center of connected graph? Find 7 distance, eccentricity, radius, diameter and center of the graph G6 Find the shortest path from vertex A to all vertex in a graph Gy using Dijkstra's 8 algorithm and calculate the length of shortest path from vertex A to vertex D. Q5 a) Justify the graph Gg and Go is planar or not? 7 b) Find the maximum.flow of the graph Gio from vertex s to vertex t. Q6 a) What is ilidependent set. and dominating set? Compute the maximum size o.f jndependcnl. set for jf4 and C4. b) What is spanning tree and minimum spanning tree of a graph? Find t.he minimum spanning t.rcss for the graph Gil were, st.arting vertex c using ldruskal's algorithm. Q7 a) What is isomorphic graph? Prove the graphs G12 and G13 are isomorphic or not? 7 Find out graph G14 have Euler Path; Euler Circuit, Hamiltonian Path, Hamiltonian Circuit or not with proper reasoning.