Edición de «Final del 12/02/10 (Algoritmos III)»

De Cuba-Wiki
Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si inicias sesión o creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.

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:
{{Back|Algoritmos y Estructuras de Datos III}}
== Ejercicio 1 ==
== Ejercicio 1 ==
a) Si el camino entre ''i'' y ''j'' tiene más de un camino mínimo ¿Cual elige Floyd?.
a) Si el camino entre ''i'' y ''j'' tiene mas 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 10:
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)
 
 
[[Image:Grafo.png|thumb|Grafo ej. 2]]


== Ejercicio 3 ==
== Ejercicio 3 ==
Un grafo G es coloreable en forma única si todo coloreo induce la misma partición de los vértices. Probar que si G es coloreable de forma única entonces el subgrafo inducido por dos conjuntos cualesquiera de la partición es conexo.
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 34: Línea 29:


== Ejercicio 5 ==
== Ejercicio 5 ==
a) ¿Qué se puede decir de <math>\Pi_1</math> sabiendo que existe una reducción polinomial de <math>\Pi_1</math> a <math>\Pi_2</math> y que <math>\Pi_2 \in P </math>?
a) ¿Que se puede decir de \pi_1 sabiendo que existe una reduccion polinomial de \pi_1 a \pi_2 y que \pi_2 \in P ?
 
b) ¿Que se puede decir de \pi_1 sabiendo que existe una reduccion polinomial de \pi_1 a \pi_2 y que \pi_2 \in NP ?
b) ¿Qué se puede decir de <math>\Pi_1</math> sabiendo que existe una reducción polinomial de <math>\Pi_1</math> a <math>\Pi_2</math> y que <math>\Pi_2 \in NP</math> ?
c) ¿Que se puede decir de \pi_1 sabiendo que existe una reduccion polinomial de \pi_1 a \pi_2 y que \pi_2 \in NP-Completo ?
 
d) ¿Que se puede decir de \pi_2 sabiendo que existe una reduccion polinomial de \pi_1 a \pi_2 y que \pi_1 \in NP-Completo ?
c) ¿Qué se puede decir de <math>\Pi_1</math> sabiendo que existe una reducción polinomial de <math>\Pi_1</math> a <math>\Pi_2</math> y que <math>\Pi_2 \in NP-Completo </math> ?
e) ¿Que se puede decir de \pi_2 sabiendo que existe una reduccion polinomial de \pi_1 a \pi_2 y que \pi_1 \in NP-Completo y \pi_2 \in NP?
 
d) ¿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> ?
 
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>?
 
[[Category:Finales]]
Ten en cuenta que todas las contribuciones a Cuba-Wiki pueden ser editadas, modificadas o eliminadas por otros colaboradores. Si no deseas que las modifiquen sin limitaciones, no las publiques aquí.
Al mismo tiempo, asumimos que eres el autor de lo que escribiste, o lo copiaste de una fuente en el dominio público o con licencia libre (véase Cuba-Wiki:Derechos de autor para más detalles). ¡No uses textos con copyright sin permiso!

Para editar esta página, responde la pregunta que aparece abajo (más información):

Cancelar Ayuda de edición (se abre en una ventana nueva)

Plantilla usada en esta página:

Obtenido de «https://www.cubawiki.com.ar/index.php/Final_del_12/02/10_(Algoritmos_III)»