Diferencia entre revisiones de «Final del 06/03/15 (Algoritmos III)»
mSin resumen de edición |
|||
| (No se muestran 2 ediciones intermedias de otro usuario) | |||
| Línea 1: | Línea 1: | ||
{{Back|Algoritmos y Estructuras de Datos III}} | |||
El final fue parte oral y parte ejercicios. | El final fue parte oral y parte ejercicios. | ||
| Línea 14: | Línea 15: | ||
== 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 == | ||
Sean <math>M1</math> y <math>M2</math> dos matching maximales de G, demostrar que <math>|M1| | 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 actual - 23:51 27 jul 2015
Plantilla:Back 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
