Edición de «Final del 20/12/19 (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 32: | Línea 32: | ||
== Ejercicio 5 == | == Ejercicio 5 == | ||
El problema del conjunto dominante es: dado un grafo <math>G = (V_G, E_G)</math> y un entero <math>k</math>, ¿existen un subconjunto <math>W \subseteq V_G</math> con a lo sumo <math>k</math> vértices tal que cualquier vértice <math>u \in V_G \ W</math>, <math>u</math> es vecino de algún vértice <math>w \in W</math> | El problema del conjunto dominante es: dado un grafo <math>G = (V_G, E_G)</math> y un entero <math>k</math>, ¿existen un subconjunto <math>W \subseteq V_G</math> con a lo sumo <math>k</math> vértices tal que cualquier vértice <math>u \in V_G \ W</math>, <math>u</math> es vecino de algún vértice <math>w \in W</math>. Este problema es NP-Completo para la clase general de grafos. Probar que este problema sigue siendo NP-Completo para grafos bipartitos. (sugenerencia: utilizar subdivisiones de aristas que es agregar vértices de grado 2). |