Graph Theory previous year question paper 2022 | HNBGU MCA second semester

Graph Theory

HNBGU MCA Previous Question Paper 2022

    1. Discuss permutation and determine the number of permutations that can be made out of the letters of the word "PROGRAMMING".

    2. Discuss combination and determine the number of triangles that are formed by selecting points from a set of 15 points out of which 8 are collinear.

    1. Differentiate between homogeneous linear recurrence relation and non-homogeneous linear recurrence relation. Discuss the method used to solve the linear homogeneous recurrence relation with constant coefficients.

    2. Solve the recurrence relation Ar+2 - 5Ar+1 + 6Ar = 2 by the method of generating functions satisfying the initial conditions a0 = 1 and a1 = 2.

    1. Define a connected graph. Prove that a connected graph with n vertices has at least (n-1) edges.

    2. Define the following:

      1. Planer graph
      2. Complete Bipartite graph
      3. Dual of a planer graph
      Give one example each.
    1. Check whether the two graphs are isomorphic or not. Justify your answer.

      check whether two graphs are isomorphic or not
    2. Define Hamilton and Eulerian graphs. Prove the complete graph K3,3 is Hamilton but not Eulerian.

      finad a minimal spanning tree for the weighted graph
    1. Write short notes on the following:

      1. Tree and fundamental circuit.
      2. Rooted and Binary tree
      3. Various operation on graph
      4. Vector space of a graph
    2. Discuss the Prim's algorithm. Using Prim's algorithm, find a minimal spanning ttree for the weighted graph shown in the following:

    1. Define cut set. Find a cutsets of the graph G given below and also find the edge connectivity of G:

      find a cutsets of the graph
    2. Prove that a connected Planar graph with n vertices and e edges has e-n+2 regions.

    1. Differentiate between combinatorial and geometrical dual of a graph. Draw the geoetric dual of the graph G given below.

      draw the geometric dual of the graph
    2. Define Incidence matrix and Adjacency matrix of a directed and undirected graph. Explain with suitable examples.

  1. Write short notes on the following:

    1. Rule of sum and products.
    2. Coloring and covering partitioning of a graph
    3. Graph enumeration
    4. Four color problem
    5. Thickness and crossing of a graph