Final del 01/08/18 (Algoritmos III)

De Cuba-Wiki

Final escrito. Eramos tres. Así que tampoco se confíen con que n grande escrito. A lo sumo será: n grande escrito.

Enunciados

Ejercicio 1

a) Nombrar las técnicas algorítmicas vistas en la materia.

b) Describir alguna de ellas

Ejercicio 2

Modificaciones del algoritmo de Dijkstra:

a) para contar el número de caminos mínimos de v a w

b) para que se elija el camino con el menor número de aristas.

Ejercicio 3

Dado un grafo G=(V,X) con una función de costo definida sobre sus airstas, . Probar que si tal que , entonces pertenece a todo árbol generador mínimo de G

Ejercicio 4

Un grafo G es coloreable en forma única si todo coloreo con colores induce la misma partición de los vértices. Mostarr si G es coloreable ne forma única el subgrafo inducido por dos conjuntos cualesquiera de la partición inducida dpor los -colores es un subgrafo conexo.

Ejercicio 5

Decidir si las siguientes afirmaciones son verdaderas o falsas. Justificar.

  • a) Si todos los arcos de una rede tienen diferentes capacidades, la red tiene un único corte mínimo.
  • b) Si se multiplican las capacidades de todos los arcos por , el o los cortes mínimos no cambian.
  • c) Si se multiplican las capacidades de todos los arcos por , el valor del o de los cortes mínimos no cambia
  • d) Si se suma a las capacidades de todos los arcos , el o los cortes mínimos no cambia.
  • e) Si se suma a las capacidades de todos los arcos , el valor del o de los cortes mínimo no cambia.

Ejercicio 6

  • a) ¿cuando un problema pertenece a la clase P?
  • b) ¿cuando un problema pertenece a la clase NP?
  • c) ¿cuando un problema pertenece a la clase NP-C?
  • d) ¿Qué es una reducción polinomial de un problema de decisión a uno ?
  • e) Demostrar que el problema de conjunto independiente máximo (versión desición) pertenece a la clase NP.
  • f) En la práctica, ¿cómo se demuestra que un problema pertenece a la clase NP-C? Justificar.
  • g) Enunciar 5 problemas estudiados en la materia que sean P y 5 que sean NP-C.

Soluciones

Ejercicio 3

idea

Hacer un absurdo, suponer que existe un T Arbol Generador Mínimo que no contiene esa arista y luego mostrar que existe un árbol menor que la arista.

Ejercicio 4

Absurdo de nuevo.

Tomar dos conjuntos y de la partición inducida .

Suponer que no son conexos.

Pero entonces se les puede asignar el mismo color pues entre ellos no hay adyacencias en el grafo original y con el resto de los vértices no hay problemas pues pertenecen a otro conjunto, es decir tenían otro color.

Entonces existe un coloreo que induce una partición tal que pero , absurdo, la partición era única.

El absurdo provino de suponer que *no* son conexos ergo deben serlo.

Ejercicio 5

a) F b) V c) V d) F e) F