GATE 2014 [Set-2]
December 10, 2024UGC NET CS 2008-june-Paper-2
December 11, 2024GATE 2008-IT
|
Question 4
|
What is the size of the smallest MIS(Maximal Independent Set) of a chain of nine nodes?
|
5
|
|
|
4
|
|
|
3
|
|
|
2
|
Question 4 Explanation:
1 – 2 – 3 – 4 – 5 – 6 – 7 – 8 – 9
(2, 5, 8) is the maximal independent set for a chain of 9 nodes. If we add any start node to the set then it will not be MIS.
Independent set:
A set of vertices is called independent set such that no two vertices in the set are adjacent.
(2, 5, 8) is the maximal independent set for a chain of 9 nodes. If we add any start node to the set then it will not be MIS.
Independent set:
A set of vertices is called independent set such that no two vertices in the set are adjacent.
Correct Answer: C
Question 4 Explanation:
1 – 2 – 3 – 4 – 5 – 6 – 7 – 8 – 9
(2, 5, 8) is the maximal independent set for a chain of 9 nodes. If we add any start node to the set then it will not be MIS.
Independent set:
A set of vertices is called independent set such that no two vertices in the set are adjacent.
(2, 5, 8) is the maximal independent set for a chain of 9 nodes. If we add any start node to the set then it will not be MIS.
Independent set:
A set of vertices is called independent set such that no two vertices in the set are adjacent.