Final del 11/06/19 (Algoritmos III)

De Cuba-Wiki
La versión para imprimir ya no se admite y puede contener errores de representación. Actualiza los marcadores del navegador y utiliza en su lugar la función de impresión predeterminada del navegador.

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.

Obtenido de «https://www.cubawiki.com.ar/index.php?title=Final_del_11/06/19_(Algoritmos_III)&oldid=12749»