This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Dominating Set Problem”.
1. A dominating set of graph G, is the subset D of vertices, if each vertex not in D is adjacent to how many vertices?
a) At least 1
b) At most 1
c) 0
d) 1
View Answer
Explanation: In a graph G=(V, E), a dominating set is subset D, such that if we take any vertex from the set of vertices, either that vertex belongs to D or its adjacent belongs to D. Hence, if each vertex not in D, is adjacent to at least one vertex of D.
2. Which of the following refers to the domination number of a graph?
a) Smallest size of maximal dominating set
b) Largest size of minimal dominating set
c) Smallest size of minimal dominating set
d) Largest size of maximal dominating set
View Answer
Explanation: In a graph G=(V, E) a subset S is a dominating set if each vertex V of G is adjacent to some vertex u!= v, of S. The domination number of G, is the cardinality of the smallest size of a minimal dominating set.
3. Given below is the pseudocode of the dominating set problem. Which of the following best suits the blank?
Dominant(G = (V, E))
{
D = { }
while (E!=0)
{
pick any edge e connecting to vertices X and Y
add one vertex between X and Y to set D
________________
}
return D;
}a) delete all the edges connected to X
b) add all the edge connected to X
c) delete X
d) delete adjacent edge
View Answer
Explanation: The given pseudocode is an approximation algorithm for solving the dominating set problem. First, initialize an empty set D, which will store the results. Pick up any edge connecting to the vertices X and Y. Add one vertex between X and Y to the set D and delete all the edges connected to it. Repeat this for all the edges and return the resultant set D to get the dominating set of the graph.
4. What is the minimal dominating set for the graph given below?
a) {C, D}
b) {A, C}
c) {A, E}
d) {A, B}
View Answer
Explanation: The minimal dominating set D of a graph G contains the smallest number of vertices, such that the vertex belongs to D or its adjacent belongs to D. Following the greedy approach, select the vertex with the maximum number of the degree to cover maximum vertices i.e. E. E is adjacent to the vertex C, B, D, F, G. Hence, along with E, A can be added to the dominating set D to cover all the vertices of the graph. The minimal dominating sets of the graph are {A, E}, {B, E}, {B, F} and {B, G}.
5. In a graph, a maximal independent set is also a dominating set.
a) True
b) False
View Answer
Explanation: In a given graph G=(V, E), an independent set of G is a subset S of the vertices present in the graph G, such that no two vertices of S are adjacent in G. Hence, a maximal independent set of graph G is also a minimal dominating set.
6. What is the domination number of the graph given below?
a) 1
b) 2
c) 3
d) 4
View Answer
Explanation: The domination number of the graph is given by the smallest size of a minimal dominating set. Following the greedy approach for the given graph, vertices A and B have the maximum degree and cover all the adjacent vertices of the graph. The minimal dominating set of the graph will be {A, B}. Hence, the domination number of the graph is 2.
7. All the graphs have a dominating set of vertices.
a) True
b) False
View Answer
Explanation: A dominating set is subset D, such that if we take any vertex from the set of vertices, either that vertex belongs to D or its adjacent belongs to D. The graphs with a minimum degree of k – 1, have a k-tuple dominating set, only these graphs have a k-dominating set.
8. What is the minimum dominating set of the binary tree given below?
a) {B, E, F, G}
b) {B, C, D, F}
c) {A, E, F, G}
d) {C, D, F, I}
View Answer
Explanation: To find the minimum dominating set of a binary tree, a dynamic programming approach can be used. First of all, choose the node and mark its children which are covered. Then check and update if its children are covered or not. Do this for all the nodes. Hence, if we select node B and node C, they cover all the nodes except H and I. So, in order to cover these nodes, node D and node F are also selected in the resultant set.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Practice Computer Science MCQs
- Check Programming Books
- Practice Data Structure MCQ
- Check Design and Analysis of Algorithms Books
- Check Computer Science Books
