Abrir menú principal

Cuba-Wiki β

Final del 12/02/10 (Algoritmos III)

Ejercicio 1Editar

a) Si el camino entre i y j tiene más de un 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.

Ejercicio 2Editar

G=(V,X) es Hamiltoniano entonces para todo  

  (W(G) es la cantidad de componentes conexas de G)

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.


 
Grafo ej. 2

Ejercicio 3Editar

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.

Ejercicio 4Editar

Dado un flujo máximo que puede circular por una red donde   es la capacidad máxima de la arista e y   es el valor del flujo del arco e, decimos que el arco es vital máximo si al eliminarlo de la red se produce el máximo decrecimiento del valor del flujo (obtenido eliminando un solo arco). Decir si es V o F y justificar.

a) Un arco vital máximo es un arco e que tiene valor maximo de  .

b) Un arco vital máximo es un arco e que tiene valor maximo de  .

c) Un arco vital máximo es un arco e que tiene valor maximo de   entre los que pertenecen a un corte mínimo.

d) Un arco que no pertenece a un corte de capacidad mínima no puede ser un arco vital máximo.

e) Una red puede contener varios arcos vitales maximos.

Ejercicio 5Editar

a) ¿Qué se puede decir de   sabiendo que existe una reducción polinomial de   a   y que  ?

b) ¿Qué se puede decir de   sabiendo que existe una reducción polinomial de   a   y que   ?

c) ¿Qué se puede decir de   sabiendo que existe una reducción polinomial de   a   y que   ?

d) ¿Qué se puede decir de   sabiendo que existe una reducción polinomial de   a   y que   ?

e) ¿Qué se puede decir de   sabiendo que existe una reducción polinomial de   a   y que   y  ?