¿Cuál es el tamaño del MIS (Conjunto Independiente Máximo) más pequeño de una string de nueve Nodes?
(A) 5
(B) 4
(C) 3
(D) 2
Respuesta: (C)
Explicación: Un conjunto de vértices se llama conjunto independiente cuando no hay dos vértices en el conjunto que sean adyacentes. Un conjunto independiente máximo (MIS) es un conjunto independiente que no es un subconjunto de ningún otro conjunto independiente.
La pregunta es sobre el MIS más pequeño. Podemos ver en el siguiente diagrama, los tres vértices resaltados (2.º, 5.º y 8.º) forman un conjunto independiente máximo (no un subconjunto de ningún otro MIS) y el MIS más pequeño.
0----0----0----0----0----0----0----0----0
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA