UGC NET COMPUTER SCIENCE SOLVED PAPERS 2014-16 - UGC NET Computer Science Paper 2 December 2015

1. How many committees of five people can be chosen from 20 men and 12 women such that each committee contains at least three women?

  • Option : B
  • Explanation :

    We must choose at least 3 women, so we calculate the case of 3 women, 4 women and 5 women and by addition rule add the result.

    12C3 x 20C2 +12C4 x 20C1 + 12C5 x 20C0 = (12x11x10/3x2x1) x (20x19/2x1) + (12x11x10x9/4x3x2x1) x 20 + (12x11x10x9x8/5x4x3x2x1) x 1

    = 220 x 190 + 495 x 20 + 792

    = 52492

Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


2. Which of the following statement(s) is/are false?

(a) A connected multigraph has an Euler Circuit if and only if each of its vertices has even degree.

(b) A connected multigraph has an Euler Path but not an Euler Circuit if and only if it has exactly two vertices of odd degree.

(c) A complete graph (Kn) has a Hamilton Circuit whenever n ≥ 3

(d) A cycle over six vertices (C6) is not a bipartite graph but a complete graph over 3 vertices is bipartite.

  • Option : D
  • Explanation :
    EulerCircuits: An Euler circuit is a circuit that uses every edge of a graph exactly once.
    HamiltonCircuit: Hamilton circuit, is a graph cycle (i.e., closed-loop) through a graph that visits each node exactly once
    Bipartite Graph: A bipartite graph, also called a bigraph, is a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent. A bipartite graph is a special case of a k-partite graph with k=2.
    From the above definitions, we can see that (d) is false. So the answer is (D).
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


3. Which of the following is/are not true?
(a)The set of negative integers is countable.
(b)The set of integers that are multiples of 7 is countable.
(c)The set of even integers is countable.
(d)The set of real numbers between 0 and ½ is countable.

  • Option : D
  • Explanation :
    • The set of negative integers is countable.
    • The set of integers that are multiples of 7 is countable.
    • The set of even integers is countable.
    • The set of real numbers between 0 and ½ is countable.This is not true because we can not count set of real numbers.
    So, Option (D) is correct.
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


4. Consider the graph given below:

The two distinct sets of vertices, which make the graph bipartite are:

  • Option : C
  • Explanation :
    A simple graph G=(V,E) is called bipartite if its vertex set can be partitioned into two disjoint subsets V=V1⋃V2, such that every edge has the form e=(a,b) where aϵV1 and bϵV2.
    Bipartite graphs are equivalent to two-colorable graphs.
    1. Assign Red color to the source vertex (putting into set V1).
    2. Color all the neighbours with Black color (putting into set V2).
    3. Color all neighbour’s neighbour with Red color (putting into set V1).
    4. This way, assign color to all vertices such that it satisfies all the constraints of m way coloring problem where m = 2.
    5. While assigning colors, if we find a neighbour which is colored with same color as current vertex, then the graph cannot be colored with 2 colors (ie., graph is not Bipartite).
    So answer is option (C).
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


5. A tree with n vertices is called graceful, if its vertices can be labelled with integers 1, 2, ...,n such that the absolute value of the difference of the labels of adjacent vertices are all different. Which of the following trees are graceful?

  • Option : D
  • Explanation :
    Caterpillar tree: In graph theory, a caterpillar is a tree in which all the vertices are within distance 1 of a central path.
    Theorem: All caterpillars are graceful.
    So, (a), (b) and (c) are graceful.
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *