Final del 01/08/18 (Algoritmos III)

De Cuba-Wiki
Revisión del 02:33 22 oct 2018 de C4t0 (discusión | contribs.) (Se avisa que el ejercicio 4 está mal resuelto y se propone otra solución)

Final escrito de Paula Zabala. 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 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, 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. Mostrar que si G es coloreable en forma única, el subgrafo inducido por dos conjuntos cualesquiera de la partición inducida por 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. Entonces ...

espero que bien

Al no ser conexos, en el subgrafo inducido de 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} existen dos componentes conexas (como mínimo).

Llamemoslas 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 C_1} 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 C_2} , además algunos vértices de 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 C_1} caen en A y otros en B, y lo mismo 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 C_2} .

Entonces podemos elegir todos los nodos de 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 V(C_1) \cap A} y swapear sus colores 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 V(C_2) \cap B} .

Con lo cual, tenemos una coloración de mismo número cromático, que induce otra partición de los vértices.

Un dibujo puede ayudar a visualizar: 

      -------                  
A:  -/       \-       B:       
   /           \        -------
  /     a(q)----\------/---d(p)\-
 /               \   /     |     \
 |               |  /      |      \
 |      b(q)-----+--+------+      |
 |               |  \             /
 \               /   \           /
  \     c(q)--------------e(p)/-
   \           /        -------
    -\       /-            
      -------


A: tiene 3 vértices, a, b, c con color q y B tiene 2 (d, e) con color p.

Si cambiamos c(q) y e(p) por c(p) y e(q), movimos el vértice c al conjunto B y el e al A.

Con esto demostramos la contra recíproca: si el subgrafo inducido por dos conjuntos cualesquiera de la partición inducida por 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 *no* es un subgrafo conexo; entonces el grafo original no es coloreable de forma única.

mal resuelto

Esto está *mal* resuelto. Que no sean conexos *no* significa que no tengan aristas entre si y que por lo tanto se pueda usar el mismo color.

Lo dejo por si alguien pensandoló comete la misma metida de pata.

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) F d) F e) F

a

A.png

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 S=\{s\}, S'=\{s, a, b\}}

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 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.

b,c

usando la definición, un corte mínimo S es aquel 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 c(S) \leq c(S')} 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 S'} cualquier otro corte mínimo.

Entonces se puede escribir esta condició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 \sum\limits_{e \in SS_c} c(e) \leq \sum\limits_{e' \in S'S_c'} c(e') }

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 S_c = V\backslash S} es decir, el complemento.

si multiplicamos por una constante mayor que cero, no cambia nada:

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 \sum\limits_{e \in SS_c} \lambda c(e) \leq \sum\limits_{e' \in S'S_c'} \lambda c(e') }

por distributiva:

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 \sum\limits_{e \in SS_c} c(e) \leq \lambda \sum\limits_{e' \in S'S_c'} c(e') }

por ser != 0

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 \sum\limits_{e \in SS_c} c(e) \leq \sum\limits_{e' \in S'S_c'} c(e') }

Si bien, la desigualdad no cambia, el valor de cada corte mínimo, si.

d, e

Planteamos lo mismo que en b pero esta vez ...

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 \sum\limits_{e \in SS_c} c(e) + \lambda \leq \sum\limits_{e' \in S'S_c'} c(e') + \lambda }

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 \sum\limits_{e \in SS_c} c(e) + \sum\limits_{e \in SS_c} \lambda \leq \sum\limits_{e' \in S'S_c'} c(e') + \sum\limits_{e' \in S'S_c'} \lambda }

es decir, se suman las constantes, tantas veces como aristas hay en los 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 SS_c \text{y} S'S_c'} respectivamente.

entonces podemos re escribir:

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 \sum\limits_{e \in SS_c} c(e) - \sum\limits_{e' \in S'S_c'} c(e') \leq |S'S_c'|\lambda - |SS_c|\lambda }

si llamamos dc a la diferencias de las capacidades, a la parte izquierda de la inecuació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 \frac{\text{dc}}{\lambda} \leq |S'S_c'| - |SS_c| }

Tenemos una condición para saber cuando un corte puede dejar de ser mínimo al sumar las capacidades por una constante mayor a 0.

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 \frac{\text{dc}}{\lambda} > |S'S_c'| - |SS_c| }

es decir, si encontramos una constante que no compence la diferencia en capacidades vs la diferencia de aristas para un corte mínimo y algún otro corte cualquiera, vamos a tener un cambio en el orden y por lo tanto al menos 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 S} dejará de ser un corte mínimo.

Obtenido de «https://www.cubawiki.com.ar/index.php?title=Final_del_01/08/18_(Algoritmos_III)&oldid=12183»