Trees and Spanning Trees Questions and Answers

11.

Consider the tree given below :

A tree with vertices a to n: a, b, d, e, f and g branch from c, a long edge joins c to h, and i, j, k, l, m and n branch from h

Using the property of eccentricity of a vertex, find every vertex that is the centre of the given tree.

A.d & h
B.c & k
C.g, b, c, h, i, m
D.c & h

Exam Year(s)

UGC NET - 2012,

Answer: D

The centre of a tree is the set of vertices of minimum eccentricity. The eccentricity of a vertex is its greatest distance from any other vertex. For c the farthest vertices are j, l and n, at distance 3 (c to h to i to j), and a, e and f are at distance 2, so the eccentricity of c is 3. For h the farthest vertices are a, e and f at distance 3, so its eccentricity is also 3.

Every other vertex is further from some end: d reaches j, l and n at 4, and b, g, i, k and m also reach 4, and the leaves reach 5. So the least eccentricity, 3, belongs to c and h, and the centre is c and h. The other options contain vertices with eccentricity 4 or more.

Discuss in Forum

12.

58 lamps are to be connected to a single electric outlet by using an extension board each of which has four outlets. The number of extension boards needed to connect all the light is

A.29
B.28
C.20
D.19

Exam Year(s)

UGC NET - 2012,

Answer: D

Each extension board has four outlets, and one outlet of every board except the first is used up to plug in the board that comes after it, or the first board plugs into the electric outlet. So k boards give 4k outlets, of which k - 1 are used by the boards themselves, leaving

\[ 4k - (k - 1) = 3k + 1 \]

free outlets for the lamps. For 58 lamps the condition is \(3k + 1 \ge 58\), so \(k \ge 19\). With 19 boards there are exactly 58 outlets, so 19 boards are needed. The options 29 and 28 are too many, and 20 is one more than needed. The keyed answer is 19.

Discuss in Forum

13.

How many edges are there in a forest of t-trees containing a total of n vertices ?

A.n + t
B.n - t
C.n * t
D.nt

Exam Year(s)

UGC NET - 2013,

Answer: B

A forest of t trees with n vertices in total has n - t edges. Each tree with n_i vertices has n_i - 1 edges, and adding these over the t trees gives the sum of (n_i - 1), which is n - t.

n + t is larger than the number of vertices for t above zero, which no forest could have. The products n x t and nt have no relation to the edge count of a forest, which has fewer edges than vertices.

Discuss in Forum

14.

Which of the following connected simple graph has exactly one spanning tree ?

A.Complete graph
B.Hamiltonian graph
C.Euler graph
D.None of the above

Exam Year(s)

UGC NET - 2013,

Answer: D

The answer is none of the above, option (D). A connected graph has exactly one spanning tree only if it is itself a tree, that is, it has no cycle, because every edge on a cycle can be dropped in turn to give a different spanning tree. A complete graph on three or more vertices has many spanning trees (n^(n-2) by Cayley's formula), a Hamiltonian graph has a cycle through all vertices and so at least two spanning trees, and an Euler graph has every vertex of even degree and so contains cycles. None of these three families satisfies the condition for the usual graphs of the question, so (D) is the key.

Discuss in Forum

15.

How many edges must be removed to produce the spanning forest of a graph with N vertices, M edges and C connected components ?

A.M+N-C
B.M-N-C
C.M-N+C
D.M+N+C

Exam Year(s)

UGC NET - 2013,

Answer: C

A spanning forest of a graph with N vertices and C connected components has N - C edges, because each component with n_i vertices needs n_i - 1 edges for its spanning tree and the sum is N - C. The graph has M edges, so the number to be removed is M - (N - C) = M - N + C, option (C). Option (A) M+N-C and option (D) M+N+C would be more than M, which cannot be removed, and option (B) M-N-C subtracts C instead of adding it. A check with a connected graph (C = 1) gives M - N + 1, the number of edges outside a spanning tree, which is right.

Discuss in Forum

16.

Consider the following statements :

(i) A graph in which there is a unique path between every pair of vertices is a tree.
(ii) A connected graph with e = v - 1 is a tree.
(iii) A graph with e = v - 1 that has no circuit is a tree.
Which of the above statements is/are true ?

A.(i) & (iii)
B.(ii) & (iii)
C.(i) & (ii)
D.All of the above

Exam Year(s)

UGC NET - 2013,

Answer: D

All three statements are true. A graph with a unique path between every pair of vertices is connected and has no cycle, which is the definition of a tree. A connected graph with e = v - 1 is a tree, because a connected graph needs at least v - 1 edges and has a cycle if it has more. A graph with e = v - 1 and no circuit is a forest with exactly one component, so it too is a tree.

Since all three hold, no option which leaves one out is acceptable. Option D is correct. This is the standard set of equivalent definitions of a tree, any of which can be used to prove that a graph is a tree.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Trees and Spanning Trees Questions and Answers || Trees and Spanning Trees MCQ Questions and Answers || Trees and Spanning Trees GK Questions and Answers || Trees and Spanning Trees GK MCQ Questions || Trees and Spanning Trees Multiple Choice Questions and Answers || Trees and Spanning Trees GK || GK on Trees and Spanning Trees || Discrete Mathematics Questions and Answers || Discrete Mathematics MCQ Questions and Answers || Discrete Mathematics GK Questions and Answers || GK on Discrete Mathematics

Trees and Spanning Trees Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications