Tuesday 11 September 2012

JUNE 2012 - PAPER II

4. The number of colours required to properly colour the vertices of every planer graph is

(A) 2
(B) 3
(C) 4
(D) 5

Ans:-D

Explanation:- According to the Five-colour theorem, Every planar graph is 5-colourable. Any planar graph G with n vertices requires five colors for proper coloring. So the answer must be option D which is 5. But in the UGC answer key it is given as 2, option A. But the correct answer is D.


5. Networks that use different technologies can be connected by using

(A) Packets
(B) Switches
(C) Bridges
(D) Routers

Ans:-D

Explanation:- Packets are the units of exchanging information in network. A bridge connects two or more networks, or segments of the same network. Switches are basically Bridges but usually have multiple ports. Routers forward data packets from one place to another. They forward data depending on the network, not the hardware(MAC)address. So the answer is option D.

6.Both hosts and routers are TCP/IP protocol software. However, routers do not use protocol from all layers. The layer for which protocol software is not needed by a router is

(A) Layer – 5 (Application)
(B) Layer – 1 (Physical)
(C) Layer – 3 (Internet)
(D) Layer – 2 (Network Interface)

Ans:-A

Explanation:- Routing is a way to get one packet from one destination to the next. But the Layer - 5 (Application) includes all the higher-level protocols. So the layer for which protocol software is not needed by a router is Layer - 5, the Application Layer which is option A.


7. In multiuser database if two users wish to update the same record at the same time, they are prevented from doing so by

(A) Jamming
(B) Password
(C) Documentation
(D) Record lock

Ans:-D

Explanation:- The explanation is quite simple. It is a straightforward question with less confusing options. So if we are talking about a multiuser database and if two users wish to update the same record at the same time, they are prevented from doing so by using Record lock.


8. A binary search tree is a binary tree :

(A) All items in the left subtree are less than root
(B) All items in the right subtree are greater than or equal to the root
(C) Each subtree is itself a binary search tree
(D) All of the above

Ans:-D

Explanation:- The statements given in the option A and C are true, is very clear. There could be only a slight confusion whether statement in option B is true or not. The above mentioned properties are mentioned in the book on Data structures:A pseudocode approach with C written by Richard F.Gilberg et al. According to the summary on binary search trees the following properties are mentioned.

  • All items in the left subtree are less than the root.
  • All items in the right subtree are greater than or equal to the root.
  • Each subtree is itself a binary search tree.
So the correct answer for this question would be option D.


9. What deletes the entire file except the file structure ?

(A) ERASE
(B) DELETE
(C) ZAP
(D) PACK

Ans:-C


3 comments:

  1. Q4 answer
    Theorem

    A planar graph G can be assigned a proper vertex k-coloring such that k≤5.

    Proof

    It is obvious the theorem is true for a graph with only one vertex.
    We will induct on the number of vertices.
    Each face of a planar graph is obviously bounded by at least 3 edges, and each edge bounds at most 2 faces, so 23e≥f.

    Handwavery.gifThis article contains statements that are justified by handwavery, in particular:
    "Obviously" needs to be demonstrated
    You can help ProofWiki by adding precise reasons why such statements hold.
    To discuss it in more detail, feel free to use the talk page.
    If you are able to do this, then when you have done so you can remove this instance of {{Handwaving}} from the code.
    If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
    We first suppose that every vertex of G is incident on 6 edges or more.
    2 = v−e+f By the Euler Polyhedron Formula
    2 ≤ v−e+23e
    e ≤ 3v−6
    2e ≤ 6v−12
    ∑degrees ≤ 6v−12
    However, if every vertex has degree greater than 5 as we supposed, ∑degrees≥6v, which is a contradiction.
    Therefore, G has at least one vertex with at most 5 edges, which we will call x.
    Remove that vertex x from G to create another graph, G′.
    By the induction hypothesis, G′ is five-colorable.
    If all five colors were not connected to x, then we can give x the missing color and thus five-color G.

    If all five colors were connected to x, we examine the five vertices x was adjacent to, and call them y1,y2,y3,y4 and y5 (in order around x).
    We color 1,2,3,4 and 5 respectively (note that "color" is just a way of labeling the vertices of a graph - it does not actually mean you take crayons and color the graph).

    We now consider the subgraph G1,3 of G′ consisting only of vertices colored 1 and 3 and the edges that connect vertices of color 1 to vertices of color 3.
    If there is no walk between y1 and y3 in G1,3, then we simply switch colors 1 and 3 in the portion of G1,3 connected to y1.
    Thus, x is no longer adjacent to a vertex of color 1, so we can color it 1.

    If there is a walk between y1 and y3 in G1,3, then we proceed to form G2,4 in the same manner.
    However, since G is planar and there is a circuit in G that consists of the walk from y1 to y3, x, and the edges xy1 and xy3, clearly y2 cannot be connected to y4 within G2,4.
    Thus, we can switch colors 2 and 4 in the portion of G2,4 connected to y2.
    Thus, x is no longer adjacent to a vertex of color 2, so we can color it 2.
    Five Color Theorem.png
    This graph illustrates the case in which the walk from y1 to y3 can be completed.
    Blue=1,Yellow=2,Red=3,Green=4,Turquoise=5
    The dotted lines represent edges and vertices that might exist, as this is simply a fairly minimal example graph that matches the conditions.

    ReplyDelete
  2. why ugc give 2 ans.?sir ...i m totally confuse

    ReplyDelete