Diferencia entre revisiones de «Final del 06/03/15 (Algoritmos III)»
| Línea 14: | Línea 14: | ||
== Ejercicio 1 == | == Ejercicio 1 == | ||
1) Sea (V, <math>T_1</math>) y (V, <math>T_2</math>) arboles, demostrar que para todo <math> | 1) Sea (V, <math>T_1</math>) y (V, <math>T_2</math>) arboles, demostrar que para todo <math> e \in T_1</math> existe un <math> f \in T_2</math> tal que (V, <math>T_1</math> - e + f) y (V, <math>T_2</math> - f + e) son arboles | ||
== Ejercicio 2 == | == Ejercicio 2 == | ||
Revisión del 18:21 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
