Sea G un grafo simple con 20 vértices y 100 aristas. El tamaño de la cobertura mínima de vértices de G es 8. Entonces, el tamaño del conjunto independiente máximo de G es
(A) 12
(B) 8
(C) Menos de 8
(D) Más de 12
Respuesta: (A)
Explicación : Antecedentes Explicación: La
cobertura de vértices es un conjunto S de vértices de un gráfico tal que cada borde del gráfico incide en al menos un vértice de S.
Conjunto independientede un gráfico es un conjunto de vértices tales que ninguno de los vértices de este conjunto tiene una arista que los conecte, es decir, no hay dos adyacentes. Un solo vértice es un conjunto independiente, pero estamos interesados en el conjunto independiente máximo, que es el conjunto más grande que es un conjunto independiente.
Relación entre conjunto independiente y cobertura de vértices: un hecho interesante es que el número de vértices de un gráfico es igual a su número de cobertura de vértice mínimo más el tamaño de un conjunto independiente máximo. ¿Cómo? eliminar todos los vértices de la cobertura mínima de vértices conduce al conjunto independiente máximo.
Entonces, si S es el tamaño de la cobertura mínima de vértices de G(V,E), entonces el tamaño
del conjunto independiente máximo de G es |V| – S.
Solución:
tamaño de la cobertura mínima de vértices = 8
tamaño del conjunto independiente máximo = 20 – 8 =12
Por lo tanto, la respuesta correcta es (A).
Referencias:
vértice de cobertura
máximo conjunto independiente .
Esta solución es aportada por Nitika Bansal.
Cuestionario de esta pregunta
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