Final del 11/06/19 (Algoritmos III)

De Cuba-Wiki
Revisión del 00:16 15 sep 2019 de IM359 (discusión | contribuciones)
(dif) ← Revisión anterior | Revisión actual (dif) | Revisión siguiente → (dif)
Saltar a: navegación, buscar

Final escrito:

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.