Final del 01/08/18 (Algoritmos III)

Final escrito de Paula Zabala. Eramos tres. Así que tampoco se confíen con que n grande $\Leftrightarrow$ escrito. A lo sumo será: n grande $\Rightarrow$ 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 de todos los caminos mínimos, se elija el de menor número de aristas.

Ejercicio 3

Dado un grafo G=(V,X) con una función de costo definida sobre sus airstas, $l:X\rightarrow R$. Probar que si $\exists e\in X$ tal que $l(e)<l(e'),\forall e'\in X\backslash \{e\}$, entonces $e$ pertenece a todo árbol generador mínimo de G${\displaystyle }$

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. Mostarr si G es coloreable ne forma única el subgrafo inducido por dos conjuntos cualesquiera de la partición inducida dpor 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 rede 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) ¿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 $\Pi _{1}$a uno $\Pi _{2}$?
• 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 $A$ y $B$ de la partición inducida $P$.

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 $P'$ tal que $A\cup B\in P'$ pero $A\cup B\not \in P$, 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) F d) F e) F

a

$S={s},S'={s,a,b}$

$c(S)=3,c(S')=1+2=3$

todas las aristas tienen distintas capacidades y sin embargo hay más de un corte mínimo.