Final del 01/08/18 (Algoritmos III)

Final escrito. Eramos tres. Así que tampoco se confíen con que n grande Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Leftrightarrow} escrito. A lo sumo será: n grande Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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 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, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle l: X \rightarrow R } . Probar que si Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \exists e \in X} tal que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle l(e) < l(e'), \forall e' \in X \backslash \{e\} } , entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle e} pertenece a todo árbol generador mínimo de GError al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle }

Ejercicio 4

Un grafo G es coloreable en forma única si todo coloreo con Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \lambda > 0} , el o los cortes mínimos no cambian.
• c) Si se multiplican las capacidades de todos los arcos por Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \lambda > 0} , el valor del o de los cortes mínimos no cambia
• d) Si se suma a las capacidades de todos los arcos Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \lambda > 0} , el o los cortes mínimos no cambia.
• e) Si se suma a las capacidades de todos los arcos Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Pi_1} a uno Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A} y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle B} de la partición inducida Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle P'} tal que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A\cup B \in P'} pero Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 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) V d) F e) F