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

(Como dice el título... 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.