Edición de «Final del 12/02/10 (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 1: | Línea 1: | ||
== Ejercicio 1 == | == Ejercicio 1 == | ||
a) Si el camino entre ''i'' y ''j'' tiene más de | a) Si el camino entre ''i'' y ''j'' tiene más de una camino mínimo ¿Cual elige Floyd?. | ||
b) Adaptarlo para que calcule los caminos mas cortos tal que no pasen por un conjunto de nodos dado. | b) Adaptarlo para que calcule los caminos mas cortos tal que no pasen por un conjunto de nodos dado. | ||
Línea 12: | Línea 11: | ||
a) Dar un ejemplo de que el teorema no es una condición suficiente para asegurar que el grafo es hamiltoniano. | a) Dar un ejemplo de que el teorema no es una condición suficiente para asegurar que el grafo es hamiltoniano. | ||
b) Mostrar, usando el teorema, que el grafo de la figura no es hamiltoniano. | b) Mostrar, usando el teorema, que el grafo de la figura no es hamiltoniano.(AGREGO EL DIBUJO DESPUES, NO LO TENGO A MANO) | ||
== Ejercicio 3 == | == Ejercicio 3 == | ||
Un grafo G es coloreable en forma única si todo coloreo induce la misma partición de los vértices. | Un grafo G es coloreable en forma única si todo coloreo X(G) induce la misma partición de los vértices. Si G es coloreable de forma única entonces el subgrafo inducido por dos conjuntos cualesquiera de la partición inducida por el X(G)-Coloreo es un subgrafo conexo. | ||
== Ejercicio 4 == | == Ejercicio 4 == | ||
Línea 43: | Línea 39: | ||
e) ¿Qué se puede decir de <math>\Pi_2</math> sabiendo que existe una reducción polinomial de <math>\Pi_1</math> a <math>\Pi_2</math> y que <math>\Pi_1 \in NP-Completo</math> y <math>\Pi_2 \in NP</math>? | e) ¿Qué se puede decir de <math>\Pi_2</math> sabiendo que existe una reducción polinomial de <math>\Pi_1</math> a <math>\Pi_2</math> y que <math>\Pi_1 \in NP-Completo</math> y <math>\Pi_2 \in NP</math>? | ||