Diferencia entre revisiones de «Final del 06/03/15 (Algoritmos III)»

De Cuba-Wiki
Línea 18: Línea 18:
== Ejercicio 2 ==
== Ejercicio 2 ==


Sean <math>M1</math> y <math>M2</math> dos matching maximales de G, demostrar que <math>|M1|<= 2|M2|</math>.
Sean <math>M1</math> y <math>M2</math> dos matching maximales de G, demostrar que <math>|M1|\leq 2|M2|</math>.


== Ejercicio 3 ==
== Ejercicio 3 ==

Revisión del 18:19 13 mar 2015

El final fue parte oral y parte ejercicios.

Parte Oral

Qué es NP. Qué significa que un problema sea NP. Qué es un problema P. Qué signifca que un problema sea NP-C, cómo se verifica esto. Ejemplos de problemas NP-C, también me empezó a nombrar problemas y preguntaba a qué clase pertenecían (por ejemplo coloreo de vertices, circuito euleriano, hamiltoniano, etc). Para que me sirve saber si un problema es NP. Que algoritmos de camino minimo existen y sus complejidades. Que es programación dinámica.

Ejercicio Escritos

Ejercicio 1

1) Sea (V, ) y (V, ) arboles, demostrar que para todo existe un tal que (V, - e + f) y (V, - f + e) son arboles

Ejercicio 2

Sean y dos matching maximales de G, demostrar que .

Ejercicio 3

no me acuerdo

Ejercicio 4

Dado que clique es np completo sobre un grafo G. si a G lo modificamos de las siguientes maneras, sigue siendo NP completo el problema de clique?

  • G es bipartito
  • G es planar
  • G es conexo