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. Mostrar que si G es coloreable en forma única, 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 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. Entonces ...

espero que bien

Al no ser conexos, en el subgrafo inducido de $A$ y $B$ existen dos componentes conexas (como mínimo).

Llamemoslas $C_{1}$ $C_{2}$, además algunos vértices de $C_{1}$ caen en A y otros en B, y lo mismo con $C_{2}$.

Entonces podemos elegir todos los nodos de $V(C_{1})\cap A$ y swapear sus colores con $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 $\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 pensándolo 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 $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.

b,c

usando la definición, un corte mínimo S es aquel tal que $c(S)\leq c(S')$ con $S'$ cualquier otro corte mínimo.

Entonces se puede escribir esta condición:

$\sum \limits _{e\in SS_{c}}c(e)\leq \sum \limits _{e'\in S'S_{c}'}c(e')$

con $S_{c}=V\backslash S$ es decir, el complemento.

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

$\sum \limits _{e\in SS_{c}}\lambda c(e)\leq \sum \limits _{e'\in S'S_{c}'}\lambda c(e')$

por distributiva:

$\lambda \sum \limits _{e\in SS_{c}}c(e)\leq \lambda \sum \limits _{e'\in S'S_{c}'}c(e')$

por ser != 0

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

$\sum \limits _{e\in SS_{c}}c(e)+\lambda \leq \sum \limits _{e'\in S'S_{c}'}c(e')+\lambda$

$\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 $SS_{c}{\text{y}}S'S_{c}'$ respectivamente.

entonces podemos re escribir:

$\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:

${\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.

${\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 $S$ dejará de ser un corte mínimo.