# TDA | Practica 5 ejercicio 8 ## Consigna 8. Un **sistema de restricciones de diferencias** (SRD) es un sistema $\mathcal{S}$ que tiene $m$ inecuaciones y $n$ incógnitas $x_1, \ldots, x_n$. Cada inecuación es de la forma $x_i - x_j \leq c_{ij}$ para una constante $c_{ij} \in \mathbb{R}$; por cada par $i, j$ existe a lo sumo una inecuación (¿por qué?). Para cada SRD $\mathcal{S}$ se puede definir un digrafo pesado $D(\mathcal{S})$ que tiene un vértice $v_i$ por cada incógnita $x_i$ de forma tal que $v_j \to v_i$ es una arista de peso $c_{ij}$ cuando $x_i - x_j \leq c_{ij}$ es una inecuación de $\mathcal{S}$. Asimismo, $\mathcal{S}$ tiene un vértice $v_0$ y una arista $v_0 \to v_i$ de peso 0 para todo $1 \leq i \leq n$. a. Demostrar que si $D(\mathcal{S})$ tiene un ciclo de peso negativo, entonces $\mathcal{S}$ no tiene solución. b. Demostrar que si $D(\mathcal{S})$ no tiene ciclos de peso negativo, entonces $\{x_i = d(v_0, v_i) \mid 1 \leq i \leq n\}$ es una solución de $D(\mathcal{S})$. Aquí $d(v_0, v_i)$ es la distancia desde $v_0$ a $v_i$ en $D(\mathcal{S})$. c. A partir de los incisos anteriores, proponer un algoritmo que permita resolver cualquier SRD. En caso de no existir solución, el algoritmo debe mostrar un conjunto de inecuaciones contradictorias entre sí. ## Resolución ### a) - Eric $(AY_1)$ menciono que la forma indicada de hacerlo, es por induccion. - En la induccion habria que sacarle un vertice al ciclo de $n+1$ vertices y unir los dos vertices que te quedaron colgando para formar un ciclo de $n$ vertices. - $\forall \mathcal{S}:srd$ digrafo pesado $D(\mathcal{S}) v_i$ por cada incognita $x_i$ - $v_j \to v_i$ arista con $w = c_{ij}$ - Cuando $x_i-x_j \leq c_{ij}$ - $\mathcal{S}$ tiene un vertice en $v_0$ y una arista $v_0 \to v_i$ de peso cero. - $\forall i$ tq $1 \leq i \leq n$ - [ $D(\mathcal{S})$ tiene un ciclo negativo ] $\equiv A$ - [ $\mathcal{S}$ no tiene solución ] $\equiv B$ - Yo quiero probar que $A \Rightarrow B$ - Sabiendo que SRD es un sistema con $m$ inecuaciones, n incognitas. - $n : x_1,\dots,x_n$ - $m : x_i-x_j \leq c_{ij}$ - Entonces nos dicen que $D(\mathcal{S})$ es un digrafo pesado que por cada incognita $v_i$ tiene un vertice $v_i$ con $(v_j \to v_i) \iff x_i-x_j \leq c_{ij} \in V(D(\mathcal{S}))$ - Para probar $A \Rightarrow B$ voy a hacerlo por el absurdo. - **Suposición inicial**: $D(\mathcal{S})$ tiene un ciclo negativo. - Esto quiere decir que hay un conjunto de aristas en $D(\mathcal{S})$ que su peso es negativo. - Entonces esto nos diría algo como: - $$ x_i-x_j \leq c_{ij} < 0$$ - Ahora quiero llegar a una conclusión para dar a un absurdo. - sea $k$ el número de vértices involucrados específicamente en el ciclo. - $$(x_{i_1}-x_{i_2})+\dots+(x_{i_k}-x_{i_1}) \leq c_{i_1i_2}+\dots + c_{i_ki_1}$$ - $$(x_{i_1}-x_{i_2})+\dots+(x_{i_k}-x_{i_1}) = 0$$ - **~~Preguntar como justificar que esto da cero~~** - $\Uparrow$ **CON INDUCCION** - Para todo termino que aparece en esta suma, también se resta. - Entonces nos queda que $0<0$ lo cual **es absurdo** - Por lo tanto, concluimos que si $D(\mathcal{S})$ tiene un ciclo de peso negativo, entonces el sistema de restricciones de diferencias $\mathcal{S}$ no puede tener una solución consistente, es decir, $A⇒B$ es verdadero. $\square$ # ### b) - Demostrar que si $A \equiv D(\mathcal{S})$ no tiene ciclos de peso negativo entonces - $B \equiv \{ x_i = d(v_0,v_i) | 1 \leq i \leq n\}$ Es una solución del sistema. - Siendo $d(v_0,v_i)$ la distancia desde $v_0$ a $v_i$ en $D(\mathcal{S})$ - Quiero probar que $A \Rightarrow B$ - Nos dicen que $x_i$ es esa distancia dada tal que $i$ está acotado por la totalidad de los vértices. - Que sea una solución significa **que asignar a cada incognita $x_i$ el valor desde $v_0$ a $v_i$ satisface todas las inecuaciones del sistema $\mathcal{S}$** - Voy a utilizar la demostración por construcción: - Como consideramos $A$ verdadera, podemos utilizar el algoritmo de Dijkstra para calcular el camino minimo. - Defino a cada $x_i$ como $d(v_0,v_i)$ - Sabemos también que para cada inecuación, verifica que si la asignación satisface la inecuación. ~~(?? redacción re pro)~~ - Por camino minimo sabemos que cualquier otro camino que no cumpla la inecuación, no puede existir. - Subestructura optima $\Rightarrow$ Relax $\Rightarrow$ consistenica. - $$d(v_0,v_i) \leq d(v_0.v_j) + c_{ij} \iff d(v_0,v_i)-d(v_0,v_j) \leq c_{ij}$$ - $$d(v_0,v_i)-d(v_0,v_j) \equiv x_i - x_j$$ - Preguntar como terminar ade cerrar esto.