Final del 06/08/18 (Algoritmos III)

De Cuba-Wiki
Revisión del 16:16 24 oct 2018 de Pmontepagano (discusión | contribs.)
(difs.) ← Revisión anterior | Revisión actual (difs.) | Revisión siguiente → (difs.)

Final escrito de Paula Zabala.

Enunciados

Ejercicio 1

Sea un grafo. Probar que si para algún existe un circuito simple de longitud al menos en .

Ejercicio 2

Dados un digrafo con pesos en sus aristas, y un entero positivo, se quiere hallar los vértices más cercanos a con un algoritmo cuya complejidad sea .

a) ¿Se puede modificar fácilmente el algoritmo de Dijkstra para resolver esto? En caso afirmativo, explicar cómo; en caso negativo, justificar por qué no.

b) ¿Se puede modificar fácilmente el algoritmo de Bellman-Ford para resolver esto? En caso afirmativo, explicar cómo; en caso negativo, justificar por qué no.

Ejercicio 3

Dado un grafo con una función de peso definida sobre sus aristas, . Probar que tal que (es decir, hay una arista de peso menor estricto a todas las otras) pertenece a todo árbol generador mínimo de .

Ejercicio 4

Un grafo es coloreable en forma única si todo coloreo con colores induce la misma partición de los vértices. Probar que si es coloreable de forma única, entonces el subgrafo inducido por dos conjuntos cualesquiera de la partición inducida por 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 red 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) ¿Cuándo un problema pertenece a la clase P?
  • b) ¿Cuándo un problema pertenece a la clase NP?
  • c) ¿Cuándo 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 (en su versión de decisió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.

Notas

En el ejercicio 1, aclaró en el momento del examen que supongamos una cota 'conveniente' para , para evitar contraejemplos raros (por ejemplo, en un grafo compuesto por dos separados, todos los vértices tienen grado mayor o igual a 1, pero no hay circuitos de longitud 2) que arruinaran la demostración.