Edición de «Final del 21/02/13 (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
| Revisión actual | Tu texto | ||
| Línea 8: | Línea 8: | ||
== Ejercicio 2 == | == Ejercicio 2 == | ||
Sea G un grafo y T un AGM de G. | Sea G un grafo y T un AGM de G. | ||
a) Probar que si e arista de G no pertenece a G, entonces e es una de las aristas más pesadas del circuito al que pertenece. | |||
a) Probar que si e arista de G no pertenece a | |||
b) Probar que si e es puente en G pertenece a T | b) Probar que si e es puente en G pertenece a T | ||
c) Si T es AGM de G y e no pertenece a T, es T un AGM de G\{e} ? Todo árbol mínimo de G\{e} es AGM de T? | c) Si T es AGM de G y e no pertenece a T, es T un AGM de G\{e} ? Todo árbol mínimo de G\{e} es AGM de T? | ||
== Ejercicio 3 == | == Ejercicio 3 == | ||
Sea G conexo y completo Kn con n>=3 con pesos en los ejes y no dirigido. Decir si es cierto lo siguiente y justificar la respuesta: | Sea G conexo y completo Kn con n>=3 con pesos en los ejes y no dirigido. Decir si es cierto lo siguiente y justificar la respuesta: | ||
a) Si un cto hamiltoniano mínimo de G contiene a un camino hamiltoniano mínimo. Es el camino igual al cto pero sin su arista más pesada? | a) Si un cto hamiltoniano mínimo de G contiene a un camino hamiltoniano mínimo. Es el camino igual al cto pero sin su arista más pesada? | ||
b) Algún cto hamiltoniano mínimo contiene a un camino mínimo hamiltoniano? | b) Algún cto hamiltoniano mínimo contiene a un camino mínimo hamiltoniano? | ||
c) Todo cto hamiltoniano mínimo contiene a un camino hamiltoniano mínimo? | c) Todo cto hamiltoniano mínimo contiene a un camino hamiltoniano mínimo? | ||
d) Repetir a, b, c pero sabiendo que los pesos de los ejes cumplen con la desigualdad triangular | d) Repetir a, b, c pero sabiendo que los pesos de los ejes cumplen con la desigualdad triangular | ||
== Ejercicio 4 == | == Ejercicio 4 == | ||
Que obtenemos si cortamos en la iteración k al algotirmo de dijkstra? | Que obtenemos si cortamos en la iteración k al algotirmo de dijkstra? | ||
== Ejercicio 5 == | == Ejercicio 5 == | ||
a) Enunciar el teorema de Cook y dar su importancia. | a) Enunciar el teorema de Cook y dar su importancia. | ||
b) Si P = NP, podemos decir que P = Np-Hard? | b) Si P = NP, podemos decir que P = Np-Hard? | ||
c) Cuál es la ventaja de saber si un problema es Np-completo o np-hard en la práctica? | c) Cuál es la ventaja de saber si un problema es Np-completo o np-hard en la práctica? | ||
[[Category:Finales]] | [[Category:Finales]] | ||
