Final del 06/03/15 (Algoritmos III)

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 1

1) Sea (V, $T_{1}$) y (V, $T_{2}$) arboles, demostrar que para todo $v\in T_{1}$ existe un $f\in T_{2}$ tal que (V, $T_{1}$ - e + f) y (V, $T_{2}$ - f + e) son arboles

Ejercicio 2

Sean $M1$ y $M2$ dos matching maximales de G, demostrar que $|M1|\leq 2|M2|$.

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