Final del 06/08/18 (Algoritmos III)

Final escrito de Paula Zabala.

Enunciados

Ejercicio 1

Sea $G=(V,X)$ un grafo. Probar que si $d(v)\geq d,\forall v\in V$ para algún $d>0\implies$ existe un circuito simple de longitud al menos $d+1$ en $G$.

Ejercicio 2

Dados $G=(V,X)$ un digrafo con pesos en sus aristas, $s\in V$ y $k$ un entero positivo, se quiere hallar los $k$ vértices más cercanos a $s$ con un algoritmo cuya complejidad sea $O(nk)$.

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 $G=(V,X)$ un grafo con una función de peso definida sobre sus aristas, $l:X\rightarrow \Re$. Probar que $\exists e\in X$ tal que $l(e)<l(e'),\forall e'\in X\backslash \{e\}$ (es decir, hay una arista de peso menor estricto a todas las otras) $\implies e$ pertenece a todo árbol generador mínimo de $G$.

Ejercicio 4

Un grafo $G$ es coloreable en forma única si todo coloreo con $\chi (G)$ colores 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 inducida por los $\chi (G)$ 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 $\lambda >0$, el o los cortes mínimos no cambian.
• c) Si se multiplican las capacidades de todos los arcos por $\lambda >0$, el valor del o de los cortes mínimos no cambia
• d) Si se suma a las capacidades de todos los arcos $\lambda >0$, el o los cortes mínimos no cambia.
• e) Si se suma a las capacidades de todos los arcos $\lambda >0$, 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 $\Pi _{1}$a uno $\Pi _{2}$?
• 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 $d$, para evitar contraejemplos raros (por ejemplo, en un grafo compuesto por dos $K_{2}$ separados, todos los vértices tienen grado mayor o igual a 1, pero no hay circuitos de longitud 2) que arruinaran la demostración.