Edición de «Final del 11/06/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 2: | Línea 2: | ||
1) Describir el problema de árbol generador mínimo y los algoritmos que lo resuelven. Demostrar correctitud de alguno de ellos. | 1) Describir el problema de árbol generador mínimo y los algoritmos que lo resuelven. Demostrar correctitud de alguno de ellos. | ||
2) Definir los problemas de recubrimiento por vértices y aristas y enunciar y demostrar las diferentes relaciones con matching máximo y conjunto independiente. Decir a qué clase de complejidad computacional (P o NP-completo) pertenece cada uno de ellos. | 2) Definir los problemas de recubrimiento por vértices y aristas y enunciar y demostrar las diferentes relaciones con matching máximo y conjunto independiente. Decir a qué clase de complejidad computacional (P o NP-completo) pertenece cada uno de ellos. |